Google Interview Question

The first question is a dynamic programming problem, which I solved using top down dynamic programming + memoization. The second question is a standard binary search problem. The third question is a graph problem, but the interviewer came up this question himself, so he didn't know the right answer and we are basically discussing how to solve the problem. I tried topology sorting and he seems to like the idea. Overall I will say it's a fair interview.