Find minimum steps required

Given a 2-d space with origin (0,0); find in how many minimum steps can a knight reach to a point (x,y) from (0,0)? Is it possible to traverse to any such point in the space from (0,0) or we have some specific conditions on x, y for such a path to exist? Prove your arguments.

Would your algorithm be still valid if traversing in x-axis direction is cheaper than traversing in y-axis direction or vice versa?

PS: a knight walks 2 units in X-axis and 1 unit in Y-axis or 2 units in Y-axis and 1 unit in X-axis in one move.

find nth max element in BST(Binary search tree)

Without using any extra space. Tree can be traversed only once.

Find nth fibonacci number

Write an algo for finding nth fibonacci number.

Hint: Recursive solution is not acceptable :D O(n) is obvious :D, We are talking about O(logn) solution :)

Sorting for large data sizes

I have a computer file containing 1,000,000 non-negative integers, in no particular order. Imagine that they are the membership numbers of people who are enrolled in my internet club. A new person wants to join the club, and we need to find an unused number to allocate to them. How would you find, in a reasonable time, a number that was not already in the file?

Hint: Use Selection trees for finding the first missing integer among those 1,000,000 integers. The in memory amount of data that we have to keep is very small.

Reference: http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch6.html