Median of Two Sorted Arrays

Source

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)).

This problem turns out to be somewhat difficult and is non-trivial to implement correctly (at least for the general case). However, it had been asked in interviews by various big-named companies (Google, Microsoft, and Amazon), so at least get the idea well-understood.
Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++ code. If you are using other languages, you can still verify your solution by looking at the judge’s test cases and its expected output.
Solution:
If you search this problem on Google, you will find tons of hits. However, most of them deal with the special case where m == n, and even so their code are filled with bugs. The CLRS book has this problem as exercise in section 9.3-8, however it also assumes the case where m == n. The only reliable solution I found on the web which deals with the generic case also seemed incorrect, as their definition of the median is the single middle element (although their approach of using binary search is pretty neat). According to the definition of the median, if (m + n) is even, then the median should be the mean of the two middle numbers.
If you read my previous post: Find the k-th Smallest Element in the Union of Two Sorted Arrays, you know that this problem is somewhat similar. In fact, the problem of finding the median of two sorted arrays when (m + n) is odd can be thought of solving the special case where k=(m+n)/2. Although we can still apply the finding k-th smallest algorithm twice to find the two middle numbers when (m + n) is even, it is no more a desirable solution due to inefficiency.
You might ask: Why not adapt the previous solution to this problem? After all, the previous algorithm solves a more general case. Well, I’ve tried that and I didn’t consider the previous solution is easily adaptable to this problem. The main reason is because when (m + n) is even, the two middle elements might be located in the same array. This complicates the algorithm and many special cases have to be dealt in a case by case basis.
Similar to finding the k-th smallest, the divide and conquer method is a natural approach to this problem. First, we choose A_i and B_j (the middle elements of A and B) where i and j are defined as m/2 and n/2. We made an observation that if A_i <= B_j, then the median must be somewhere between A_i and B_j (inclusive). Therefore, we could dispose a total of i elements from left of Ai and a total of n-j-1 elements to the right of B_j. Please take extra caution not to dispose A_i or B_j, as we might need two middle values to calculate the median (it might also be possible that the two middle values are both in the same array). The case where A_i > B_j is similar.

Two sorted arrays A and B. i is chosen as m/2 and j is chosen as n/2. A_i and B_j are middle elements of A and B. If A_i < B_j, then the median must be between A_i and B_j (inclusive). Similarly with the opposite.

The main idea illustrated above is mostly right, however there is one more important invariant we have to maintain. It is entirely possible that the number of elements being disposed from each array is different. Look at the example above: If A_i <= B_j, two elements to the left of A_i and three elements to the right of B_j are being disposed. Notice that this is no longer a valid sub-problem, as both sub-array’s median is no longer the original median.
Therefore, an important invariant we have to maintain is:

The number of elements being disposed from each array must be the same.

This could be easily achieved by choosing the number of elements to dispose from each array to be (Warning: The below condition fails to handle an edge case, for more details see the EDIT section below):

k = min(i, n-j-1) when Ai <= Bj.                   <--- 1(a)
k = min(m-i-1, j) when Ai > Bj.                    <--- 1(b)

Figuring out how to subdivide the problem is actually the easy part. The hard part is figuring out the base case. (ie, when should we stop subdividing?)
It is obvious that when m=1 or n=1, you must treat it as a special base case, or else it would end up in an infinite loop. The hard part is reasoning why m=2 or n=2 requires special case handling as well. (Hint: The two middle elements might be in the same array.)
Finally, implementing the above idea turns out to be an extremely tricky coding exercise. Before looking at the solution below, try to challenge yourself by coding the algorithm.
If you have a more elegant code to this problem, I would love to hear from you!
EDIT:
Thanks to Algorist for being the first person who points out a bug. (For more details, read his comment). The bug is caused by some edge cases that are not handled in the base case.
Shortly after I fixed that bug, I discovered another edge case myself which my previous code failed to handle.
An example of one of the edge cases is:

A = { 1, 2, 4, 8, 9, 10 }
B = { 3, 5, 6, 7 }

The above conditions ( 1(a), 1(b) ) fails to handle the above edge case, which returns 5 as the median while the correct answer should be 5.5.
The reason is because the number 5 is discarded in the first iteration, while it should be considered in the final evaluation step of the median. To resolve this edge case, we have to be careful not to discard the neighbor element when its size is even. Here are the corrected conditions ( 2(a), 2(b), 2(c), 2(d) ) for k which resolves this edge case.

k = min(i-1, n-j-1) when Ai <= Bj and m is even.   <--- 2(a)
k = min(i, n-j-1)   when Ai <= Bj and m is odd.    <--- 2(b)
k = min(m-i-1, j-1) when Ai > Bj  and n is even.   <--- 2(c)
k = min(m-i-1, j)   when Ai > Bj  and n is odd.    <--- 2(d)

Below is the bug-free code after going through a lengthy rigorous testing of all possible edge cases. (Not for the faint of heart!)

double findMedianBaseCase(int med, int C[], int n) {   if (n == 1)     return (med+C[0])/2.0;     if (n % 2 == 0) {     int a = C[n/2 - 1], b = C[n/2];     if (med <= a)       return a;     else if (med <= b)       return med;     else /* med > b */       return b;   } else {     int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];     if (med <= a)       return (a+b) / 2.0;     else if (med <= c)       return (med+b) / 2.0;     else /* med > c */       return (b+c) / 2.0;   } }   double findMedianBaseCase2(int med1, int med2, int C[], int n) {   if (n % 2 == 0) {     int a = (((n/2-2) >= 0) ? C[n/2 - 2] : INT_MIN);     int b = C[n/2 - 1], c = C[n/2];     int d = (((n/2 + 1) <= n-1) ? C[n/2 + 1] : INT_MAX);     if (med2 <= b)       return (b+max(med2,a)) / 2.0;     else if (med1 <= b)       return (b+min(med2,c)) / 2.0;     else if (med1 >= c)       return (c+min(med1,d)) / 2.0;     else if (med2 >= c)       return (c+max(med1,b)) / 2.0;     else  /* a < med1 <= med2 < b */       return (med1+med2) / 2.0;   } else {     int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];     if (med1 >= b)       return min(med1, c);     else if (med2 <= b)       return max(med2, a);     else  /* med1 < b < med2 */       return b;   } }   double findMedianSingleArray(int A[], int n) {   assert(n > 0);   return ((n%2 == 1) ? A[n/2] : (A[n/2-1]+A[n/2])/2.0); }   double findMedianSortedArrays(int A[], int m, int B[], int n) {   assert(m+n >= 1);   if (m == 0)     return findMedianSingleArray(B, n);   else if (n == 0)     return findMedianSingleArray(A, m);   else if (m == 1)     return findMedianBaseCase(A[0], B, n);   else if (n == 1)     return findMedianBaseCase(B[0], A, m);   else if (m == 2)     return findMedianBaseCase2(A[0], A[1], B, n);   else if (n == 2)     return findMedianBaseCase2(B[0], B[1], A, m);     int i = m/2, j = n/2, k;   if (A[i] <= B[j]) {     k = ((m%2 == 0) ? min(i-1, n-j-1) : min(i, n-j-1));     assert(k > 0);     return findMedianSortedArrays(A+k, m-k, B, n-k);   } else {     k = ((n%2 == 0) ? min(m-i-1, j-1) : min(m-i-1, j));     assert(k > 0);     return findMedianSortedArrays(A, m-k, B+k, n-k);   } }

EDIT2:
A reader buried.shopno had managed to code the solution more elegantly! I especially like how medianOfThree and medianOfFour were implemented. For more details, read his comment below. Great job!
Further thoughts:
A reader nimin98 suggested that the base case can be handled by simply doing a direct merge. In other words, we have to merge the short array (containing either one or two elements) with the longer array (pick the four elements near the middle. Deciding which four is another tricky business because of multiple special cases). nimin98′s code has few bugs in the handling of base case.
In general, The above approaches (including mine) to handle the base case are not recommended due to tricky implementation. How about Binary Search? We can use binary search to find the correct position to insert elements from the shorter array into the longer array, thus completing the merge (You don’t have to *actually* insert it, recording its index should be suffice).
\

Studious Student Problem Analysis

Source

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Here is my problem analysis for Facebook Hacker Cup Qualification Round: Studious Student.
Studious Student Problem Analysis:
As I mentioned, this problem is not as straight forward as you think it might be. The first most natural way to approach this problem is sorting. Most people will reason that you can sort and concatenate each individual word together to form the lexicographically smallest string. This is incorrect, as illustrated in one of the sample inputs:

jibw ji jp bw jibw

By sorting and concatenate, the answer is:

bwjijibwjibwjp,

while the correct answer should be:

bwjibwjibwjijp.

Lexicographical order is also known as dictionary order, since it is how the words are ordered in the dictionary.

Notice in the above words, “ji” is the prefix of “jibw“. The “sort and concatenate” method definitely does not work when there is a case where a word is a prefix of one or more other words.
Well, one might try a naive way of doing a brute force. Although it is highly inefficient, it works for this problem. This is because each input would be at most 9 words, and it turns out there are only a total of 9! = 362880 possible permutations of words being concatenated together. Therefore, one can generate all possible permutations and find the answer.
We make an easy observation that if all words in the list are of equal length, then sort + concatenate must yield the smallest dictionary order. In fact, a better argument would be:

If no word appears to be a prefix of any other words, then the simple sort + concatenate must yield the smallest dictionary order string.

To solve this problem correctly, we must also handle the special case where a word appears as a prefix of other words. One efficient and easy (non-trivial to prove but easy to reason) solution for this problem is to re-define the order relation of two words, s1 and s2, as:

    s1 is less than s2   iff (if and only if)

    s1 + s2 < s2 + s1.

Then, by sorting and concatenating the words using the above ordering, it must yield the lexicographically smallest string. Why?
Here is a concrete example why this works. We use an example where the list of words are:

ji jibw jijibw

By the definition of s1 is less than s2 iff s1+s2 < s2+s1, we found that the lowest ordered word in the list is “jibw“. This is because “jibwji” < “jijibw” and “jibwjijibw” < “jijibwjibw“.
Now, the key to understand why the order relation s1+s2 < s2+s1 yields the smallest dictionary order is:

• We have found the smallest-ordered word such that s1+x < x+s1. Therefore, it is impossible to swap the words to yield a smaller dictionary order. 
• For a case with more words, then this order relation holds: s1+x < x+s1, and x+y < y+x. As swapping at any point could not possibly yield a smaller dictionary order, therefore s1+x+y must yield the smallest dictionary order. 
• This result can be generalized to all M words by induction, due to the transitive property mentioned above.

I do not claim that this is a rigid or even a correctly constructed proof. However, it does help me in convincing myself this is a valid solution.

bool compareSort(const string &s1, const string &s2) {

  return s1 + s2 < s2 + s1;

}

 

int main() {

  string words[10];

  int N, M;

  cin >> N;

 

  for (int i = 0; i < N; i++) {

    cin >> M;

 

    for (int j = 0; j < M; j++)

      cin >> words[j];

 

    sort(words, words+M, compareSort);

 

    for (int j = 0; j < M; j++)

      cout << words[j];

    cout << endl;

  }

}

 

Hacking a Google interview (From MIT)

Source

» Hacking a Google Interview Course Website

Directly from MIT’s course website,

Learn the tricks. Beat the system.

Ever wanted to work at a company like Google, Apple, or Facebook? There’s just one thing standing in your way: the interview. But there’s no need to fear. We’ve mastered the interview questions and topics, and we want to show you how you can nail every programming question. Whether you’re a beginning programmer or a seasoned expert, this class is for you.

There are a total 5 handouts available for download, with the first few handouts discussing basic data structures and common interview questions with complete solutions. 5 stars and highly recommended!

Queue that Support Push_rear, Pop_front, and GetMin in Constant Time

Source

Problem

Design a queue that supports push_rear, pop_front, and get_min in O(1). Would that be elegantly possible too?

Solution

Maintain an extra queue lets call it secondary queue.

push_rear

-> push the element in the primary queue

-> start from the front of the queue. Remove all elements which are smaller then the element. If element is greater then all it will take the last position.

pop_front

--> remove the element from primary queue

--> if the element is present at head of secondary queue remove it.

get_minimum

-->return head of the secondary queue

Largest Binary Search Tree (BST) in a Binary Tree

Source

Problem

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

My Attempt

Every node in the BST will be an BST (Recursive definition of BST)

Go top down. In-order traversal. traversal. If you find a node which does not hav both children which does not follow BST property save them (Add them to linked list) we wil treat them as root of new possible BST,

lbst(node *root, int &count, node* queue) {

ChkPtrAssert(queue);

if (!root) { return; }

// visit the element if atleast one chil has BST property. Include the node in current BST tree

if (root->left && root->left->data <>data) || (root->right && root->right->data >= no)

count++;

//visit left child

if (root->left)

if(root->left->data <>data)

lbst(root->left, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

//visit tight child

if (root->right)

if(root->right->data <>data)

lbst(root->right, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

}

main() {

Queue *queue = new Queue();

Node* lbstRoot = root;

int maxCount = 0;

ChkMem(queue);

queue->addQueue(root);

node* currentNode = root;

while (CurrentNode)

{

lbst(currentNode, count, queue);

if (count > maxCount) {

maxCount = count;

lbstRoot = currentNode;

}

queue->popQueue(&currentNode);

}

Coins in a Line

Source

Here is an interview question you would expect from a typical Google interview, which is an interesting problem itself. Different solutions from multiple perspectives are provided in this post.

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

U.S. coins in various denominations in a line. Two players take turn to pick a coin from one of the ends until no more coins are left. Whoever with the larger amount of money wins.

My Attempt

1. sum all even positions and odd positions. Whichever is greater players takes those positions.

2.

int optimalSequenceValue (int arr[ ] , int left, int right, bool player, int P[ ] [ ])

{

if (left == right) // last element

return 0;

if (player == PLAYER1) // pick one left or right and select max of the output

p[left] [right] = max (arr[left] + optimalSequenceValue (arr, left + 1, right, P) ,

arr[righjt] + optimalSequenceValue (arr, left, right -1 , P)

return p[left][right];

if(player == PLAYER2) // value doesnt count just skip

return max (optimalSequenceValue (arr, left + 1, right, P) ,

optimalSequenceValue (arr, left, right -1 , P)

}

with values in P[][] we could back track the pattern.