Some interview questions

gistfile1.txt

1. Do binary search on a rotated array.
Eg., given [100, 110, 121, 5, 11, 44, 78, 91, 99], be able to binary search on it.

2. Implement the * and / operations without actual multiplication and division.

3. Implement the ^ operator without using any in-build exponentiation methods.

4. Implement the median of an unsorted array in O(n).

5. Implement sqrt()

6. Print the power-set of an array.
Eg. If the array is [1, 2, 3], print:
[1]
[1,2]
[1,2,3]
[1,3]
[2]
[2,3]
[3]

7. Given two binary strings, like "101", "11101", etc., write a function to return their sum in the same fashion.

8. Given two binary strings, like "101", "11101", etc., write a function to return their product in the same fashion.

9. Compute log2 using sqrt(). (Hint: Try to think what log2 really does, and try to work this on paper)

10. Given a BST, find the n-th node.

11. Find the majority element of an array. A majority element is an element which occurs at least ceil(n/2)+1 times in an array of size n. Expected complexity O(n).