Yahoo Interview Questions-2

1. Design a data structure such that given a stream of numbers, you can find the maximum of the numbers at any point and also all the numbers.



2. Given an array of 1s and 0s arrange the 1s together and 0s together in a single scan of the array. Optimize the boundary conditions.


3. Find the common ancestor of two given nodes in a binary tree, how do you exploit the properties of a given BST for the same problem.


4. Given a function getsort(data),that sorts the data given. The function sorts in place and does not use any extra memory. How do you validate the function with respect to 1)it sorts 2) it does not use extra memory


5. Explain the Traveling Salesman problem? What is an NP-complete problem? What is the Hamiltonian cycle problem?


6. Find out the least common ancestor in a binary tree.