CareerCup

a. you must use m + n - 2 steps to get to the destination, of which m - 1 is go right. So the total number of path is C(m-1, m + n - 2). C is the combinatiuon number.

b. Use dynamical programming, T.C. = O(mn), S.C. = O(mn)

bool findLargest(Node* t, int n, int& size, int& value)
{
int rightCount = 0;
if (t->right == NULL && n == 1)
{
value = t->value;
return true;
}
if (t->right != NULL)
if (findLargest(t->right, n, rightCount, value))
return true;
if (n == rightCount + 1)
return true;
if (t->left == NULL)
{
size = rightCount + 1;
return false;
}
int leftCount = 0;
if (findLargest(t->left, n - rightCount - 1, leftCount, value))
return true;
size = leftCount + rightCount + 1;
return false;
}

int findLargest(Tree* t, int n)
{
int size = 0, value = 0;
findLargest(t->root, n, size, value);
return value;
}

It's still O(NKlog K), at level i, there are k/2^i pairs, but the length of each list is N*2^(i-1), so each level cost O(NK), the total cost is O(NKlogK)

Use a heap to store the head element of each list.
Each time remove the minimum element from the heap, and add the next element of corresponding list to the heap. The cost is O(NlogK)

use dynamical programming
O(n^2)