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/