Some Interview questions

1. Given a sorted array which has distinct integers in ascending order,
find an index where a[k] = k;
Solution : modified binary search

2. Give me the data structure and algorithm for a locker system
where there are 3 types of lockers big,medium and small. Number of
lockers is n for every type.
Customers come with 3 types of bags, big,medium and small.
Small bag goes in small locker, and so on...

You have to support two operations :
a. insert bag,
b. retrieve bag.

For both of the operations, the expected time complexity is O(1).

3. Given a binary search tree, find two elements which sum up to k.
Solution : convert it into a doubly linked list and then solve the problem
as if you are solving it for an array.