Find minimum range that includes an element from every array

Problem:
There are many sorted arrays. Find a minimum range, so that in each array there's at least one integer within this range.

Solution:
Do a "merge" operation (kind of) by maintaining a priority queue of minimum elements from each array. The range of the whole queue is the range of the current interval. Iterate over all elements until one of the arrays is exhausted and choose the minimum range. The priority queue guarantees that there's at least one element from each array present. The fact that the queue is sorted allows as to quickly retrieve the current min and max elements and therefore determine the current range. It's best to maintain the heap using a BST - all operations (including getMax/Min) will take O(log M), where M is the number of input arrays.
Example:

input {0,10,255} {2 , 11 , 257} {4,12,258} 

Let's take the first element from each array and push them into priority queue. 

step 0:  queue: [0,2,4]  range:0-4 
step 1:  pop 0 from queue , push next element to 0 from first array 
queue: [2,4,10] range: 2-10 
step2:  pop 2 , push 11 
queue: [4,10,11] range: 4-11 
step3:  pop 4 , push 12 
queue: [10,11,12] range: 10-12 <----- minimal range 

etc...

Complexity:

time - O(n log n) (we iterate once and maintain a heap)
space - O(M), where M - the number of arrays

Links and credits:
http://www.careercup.com/question?id=5103437989543936

Generate 1 and 0 with equal probability

Problem:
Given a function “f” in which 0 occurs with probability 0.4 and 1 occurs with probability 0.6. Using function “f” deduce a new function “f1” such that both 0 and 1 occurs with probability 0.5.

Solution:
Run the function f() two times. The possible outcomes are

00 with probability 0.4*0.4

11 with probability 0.6*0.6

01 with probability 0.4*0.6

10 with probability 0.6*0.4

Notice that the probabilities for 01 and 10 are the same. So create a new function f1() such that

f1():
   first = f()
   second = f()
   if (first == 0 and second == 0) or (first == 1 or second == 1):

      discard and run again
   else: 
      if first == 0 and second == 1: return 0
      else: return 1

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/amazon-interview-set-64-campus-sde/

Find heavy ball

Problem:
9 identical balls. one ball is heavy. find the heavy ball with only 2 measurements ........ dead easy.

Solution:
this is super easy. split the ball into three groups with 3 balls each. pick two groups out to measure if they are equal weight. this way, you could find out which group contains the heavy ball. Then from this particular group, you could pick two to do one more measurement, this way, you find out the heavy ball

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=5204967652589568

Circular right shift by n

Problem:
Given an integer array. Perform circular right shift by n.
Give the best solution.

Solution:

O(n)/O(1):

void reverse(int A[], int start, int end)
{
 while(start < end)
  swap(A[start++], A[end--]);
}

//shift A[0…sz-1] by n (n>0)
void shiftArray(int A[], int sz, int n)
{
 n = n%sz;
 reverse(A, 0, sz-1);
 reverse(A, 0, n-1);
 reverse(A, n, sz-1);
 return;
}

But the above solution performs too many swaps. There's an alternative O(n)/O(1) solution that swaps each element only once. We start with the first element at index 0 and put it to its final position (at index [n % length]). The former element at index [0 + n % length] will now be saved in a temporary variable. Now, on the next loop iteration we put the temporary element to its final position (at index [(n + n) % length]) and similarly store the element from that new position to a temporary variable. We continue the process until we put an element at index 0, after which the array is rotated. As an example, consider the following example with an array of 5 elements that needs to be shifted by 3:

1 2 3 4 5

Shift it by 3:

x 2 3 1 5 - 4
x 4 3 1 5 - 2
x 4 3 1 2 - 5
x 4 5 1 2 - 3
3 4 5 1 2

Each line above represents the state of the array on each iteration of the loop. A number after the '-' sign is the temporary storage used for an element currently being shifted. The 'x' represents a position that doesn't contain a valid data and needs to be filled last. So, the loop would look like this:

int i = 0;
int temp = array[0];
do {
   int k = i + n % length;
   int t = array[k];
   array[k] = temp;
   temp = t;
   i = (i + n) % length;
} while (i != 0);
// Finally, fill the index 0:
array[0] = temp;

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=6282862240202752

Find elements with sum equal to the sum of their indexes

Problem:
Write a method which takes an array input and returns true if the sum of any two elements is equal to the sum of the corresponding indices. Like if for an array the sum of values at any two indices i and j is equal to the sum of i and j.

Solution:
Since we know we are looking for pairs where x+y = A[x] + A[y], by simple algebra, you can also look for x-A[x] = A[y]-y

public static ArrayList<ArrayList<Integer>> findSums(int[] A) {
  // Look for pairs where  x - A[x] == A[y] - y
  ArrayList<ArrayList<Integer>> soln = new ArrayList<ArrayList<Integer>>();
  HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
  
  for (int x = 0; x < A.length; x++) {
   h.put(x-A[x],x);
  }
  
  for (int y = 0; y < A.length; y++) {
   if (h.containsKey(A[y]-y)) {
    int x = h.get(A[y]-y);
    if (y != x) {
     ArrayList<Integer> pair= new ArrayList<Integer>();
     pair.add(x);
     pair.add(y);
     soln.add(pair);
    }
   }
  }
  
  return soln;
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5705699820568576

LCA or Lowest Common Ancestor of a Binary Tree

Problem:
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

E.g.:

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

In this tree, an LCA for 6 and 4 is 5. For 5 and 4 it is 5,too. For 7 and 1 it is 3. And so on.

Solution:
A Bottom-up Approach:
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Complexity:

time - O(n)
space - O(log n)

Links and credits:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Min number of slaves to find poison

Problem:
There is a king, who has got 1000 bottles of Rum with him, of which One bottle contains poison. And he has any number of slaves. He has got 1 hour to decide which bottle contains Poison, and any slave who even takes a sip of the poison, dies within an hour. How many least number of slaves does the king need to use, to make out which bottle contains poison.

Solution:
The answer is still 10. (2 power 10 = 1024) List numbers until 1000 in binary format vertically. Each 1 represents a slave and with the combination of slaves you can find the poisoned rum.
8 = 2 power 3. So three slaves

Eg:          1 2 3 4 5 6 7 8
Slave 1:     0 0 0 1 1 1 1 0
Slave 2:     0 1 1 0 0 1 1 0
Slave 3:     1 0 1 0 1 0 1 0

from the above combination you can find the rum bottle based on which slaves died

Complexity:

time - O(1)
space - O(log n)

Links and credits:
http://www.careercup.com/question?id=6345092675665920

Search in a matrix sorted by rows and columns

Problem:
Search in a row wise and column wise sorted matrix

Solution:
Assuming both sorted in strictly increasing order:

M[row][column] < M[row+1][column] and M[row][column] < M[row][column+1]

Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.

Complexity if O(#rows + #columns)

public Position searchSortedMatrix(int x, int[][] M) {
 if (M.length==0 || M[0].length==0) return Position(-1,-1);
 int row = 0, column = M[0].length-1, curVal;
 while (row<M.length && column>=0) {
  curVal = M[row][column];
  if (curVal == x) return Position(row,column);
  if (curVal > x) column--;
  else row++;
 }
 return Position(-1,-1);
}

Note that binary search won't work because the element being searched can be located virtually anywhere, so we can't choose the "right" row or column beforehand.


There's also a divide and conqure solution exist:
1) Find the middle element.
2) If middle element is same as key return.
3) If middle element is lesser than key then
….3a) search submatrix on lower side of middle element
….3b) Search submatrix on right hand side.of middle element
4) If middle element is greater than key then
….4a) search vertical submatrix on left side of middle element
….4b) search submatrix on right hand side.

If given a n x n matrix, the time complexity of the divide and conqure solution is O(n^1.58) (follows from a recurrence: T(n) = 3T(n/2) + O(1), see geeksforgeeks link for details).

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=6448780970819584
http://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/

Find longest subarray with equal sum

Problem:
Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.

Solution:
This is same as finding the longest subarray with sum zero in the array C[i] = A[i] - B[i].

Prefix sums + hashtable should give it.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=25036663

Find a subarray divisible by 7

Problem:
WAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
calculate the complexity of your algorithm

Solution:
So, we want to find sub-set [i, j], such that

a[i]+a[i+1]+ ... a[j] ) % k = 0

with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:

s[i] = (a[1] + a[2] + ... + a[i]) % k

And we can note that, if there is such [i, j] that we are looking for, then:

s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0

So, for each s[i] == s[j], sum of sub-set [i, j] is divisible by k.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5812734516002816

Longest chain of non-overlapping intervals (activity selection)

Problem:
You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b<c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed

Solution:
This is known as Activity selection problem. Using a greedy algorithm to find a solution will always result in an optimal solution:

Sort the set of activities by finishing time (f[i])
S = {1}
f = f[1]
for i=2 to n
   if s[i] ≥ f
      S = S U i
      f = f[i]
endfor

Basically, we always choose an interval with the minimum possible finish-time, thus allowing us to build the longest chain using the rest of the intervals.

Complexity:

time - O(n log n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=5068766153015296
http://en.wikipedia.org/wiki/Activity_selection_problem

Integer to Roman

Problem:
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution:

public String intToRoman(int num) {
    int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder res = new StringBuilder();
    int i=0;
    while (num>0) {
        int times = num / nums[i];
        num -= nums[i]*times;
        for (; times>0; times--) {
            res.append(symbols[i]);
        }
        ++i;
    }
    return res.toString();
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/194/integer-to-roman

Reverse Nodes in k-Group

Problem:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:
It's easy to reverse the whole linked list (i.e. consider k === list length). Now, the definition of the "whole list" is only a matter of how we define its head and tail. We should just traverse the original list and treat each k-group as a separate list and reverse it one by one until we reach a group of size less than k.

ListNode *reverseKGroup(ListNode *head, int k) {
    if (!head || k <= 1) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy;

    int i = 0;
    while (head) {
        i++;
        if (i % k == 0) {
            pre = reverse(pre, head->next);                
            head = pre->next;
        } else {
            head = head->next;   
        }
    }

    return dummy.next;
}

ListNode *reverse(ListNode *pre, ListNode *next) {
    ListNode *last = pre->next;
    ListNode *cur = last->next;
    while (cur != next) {
        last->next = cur->next;
        cur->next = pre->next;
        pre->next = cur;

        cur = last->next;
    }
    return last;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/206/reverse-nodes-in-k-group

Median of Two Sorted Arrays

Problem:
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution:

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if (0 == total % 2) {
        return (FindKth(A, m, B, n, total/2) + FindKth(A, m, B, n, total/2 + 1)) / 2;
    } else {
        return FindKth(A, m, B, n, total/2 + 1);
    }
}

double FindKth(int A[], int m, int B[], int n, int k) {
    if (m > n) return FindKth(B, n, A, m, k);
    if (0 == m) return B[k-1];
    if (0 == n) return A[k-1];
    if (1 == k) return min(A[0], B[0]);

    int aMid = min(k/2, m);
    int bMid = k - aMid;
    if (A[aMid-1] < B[bMid-1]) {
        return FindKth(A + aMid, m - aMid, B, n, k - aMid);
    } else {
        return FindKth(A, m, B + bMid, n - bMid, k - bMid);
    }
}

Complexity:

time - O(log n)
space - O(log n) (for recursion stack; could be optimized to O(1) using iterative approach)

Links and credits:
http://discuss.leetcode.com/questions/142/median-of-two-sorted-arrays