CareerCup

Write a program to convert a BST to sorted list. You must use the same tree and make the right child pointer as the next pointer in the list.

I think I flunked this one.

How to find the strength of a pair of similar eggs given a N story building.

I explained the divide and conquer approach. He expected better.

Develop a hashing algorithm for strings.

I replied saying MD5 hashing and converting the hash to a BigInt implementation.

How to merge K sorted arrays into one array.

I explained the second part of external sort and said its in O(N logK). I don't think he understood the time complexity I explained.

How to find a number in a rotated sorted array.
He was looking for the binary search kinda solution

Simple questions were asked.
1. Get the number of employees from every department given employee and dept tables.
2. How would you optimize a query considering that it is performing very bad.
3. What happens behind the scene when you hit any website URL in the web browser.

Visualize holding an N-ary tree by its root in your left hand. Now hold any node in the tree with your right hand and release the left hand. How the tree would transform and give an algorithm to do it programatically.

Given an array such that ever number differ from its adjacent number by at max 1. Find a number in this array efficiently.

I told him i knew this question already and explained the answer real quick.

Vertical summation of a binary tree.
I told him I knew this question already and explained the answer real quick.

given a number say 312. find the next number using the same digits. 321.

How would you do check valid parenthesis in less than O(n) time. He was looking for divide and conquer.
We had a debate about it being in O(n) and he asked me to think about it in threaded environment.

Write a function to check valid parenthesis.
(()) - valid
)( - invalid.

Give a design for chessboard which allows two people to play. (Class/Object level)

Explain about a project I had in my resume from previous company in detail. (really detailed) :)

Give a low level (class/object) design for the document write component in the amazon's websync.

Give a high level design for amazon's websync architecture.

Given a huge file with number and limited memory, how would you sort it efficiently.
He was looking for external sort as the answer.

Given an array like below, construct a N-ary tree from it.
322100100
each number represents the number of children starting with root.

3
     / | \
    2  1  0
   / \  \
  2   0  0
 / \
1   0

Write a function to check if a binary tree is a binary search tree.