CareerCup

1) Divide 9 marbles into group of 3, and then select any two group and check their weight. If either of is heavier, then select that group or select third group. Now select any two marbles out of this group of three and check their weight. By this procedure you need to compare just twice.

To find two nos in array whose sum is equal to given no:
1) If array is sorted the your method can give result in O(n) else it will require O(nlgn) + O(n)
2) If memory is not the constraint then add each element of array in hasttable in O(n). In other O(n) find the two nos. Total : O(n) + O(n)

1 evaluate(ExpressionTree t){
if(t is a leaf)
return value of t's operand ;
4 else{
5 operator = t.element ;
6 operand1 = evaluate(t.left) ;
7 operand2 = evaluate(t.right) ;
8 return(applyOperator(operand1, operator, operand2) ;
9 }
}

For the marbles problem, how are you able to say it is log n. Since you are diving it into group of three each time

Two years ago, I passed two phone interviews and went to Seattle WA for the interview. I was asked about the same elevator question in my second phone interview. It is amazing that they keep asking the same questions again and again over several years.

BTW the 9 marbles question is a variation of the original question which had only 8 marbles. 9 marbles can be solved by using the scale only 2 times.

The marbles problem has the answer log n(to base 3) only if, its given that the odd marble is either lighter or heavier.

Mindy, so finally you answered the "elevator question" and got hired by Amazon? You rock Mindy!
So give tips to your other friends out here who are waiting to be hired by Amazon. :-)