Amazon Interview Question
InternsCountry: United States
Interview Type: Written Test
This might sound foolish, but shouldn't you just:
(1) Go over each box in sequence
(2) If your wand disappears for box k, the rest of the boxes (n - k) are empty
You don't even need to use the second wand.
A perfectly valid O(n) algorithm unless I am missing something.
I am confused about this too. I think it should work, if we are not missing anything.
Can someone explain?
Yeah this question is stupid and then I thought well maybe the interview is seeing if you would test that the first box doesn't contain a pearl so test the last box. ....but it explicitly states in the problem that the first pearl is at 1.....Lame question.
Funny to see people overthinking the algorithm though. ;-)
Follow this sequence, test 1,2, 4, 8,16,......
if 2pwd k is empty 2pwd k-1 to x Using second wand Ologn
This is actually an O(n) algorithm.
Consider the following case: n = 2^k and i=n-1. The first wand vanishes after k+1 tests while testing box 2^k. Then we use the second wand to test boxes 2^{k-1}+1 to 2^k - 1. The second wand would vanish after 2^{k-1} - 2 = n/2 -2 tests. Overall, you would require k + n/2 - 2 = logn + n/2 - 2 = O(n) tests - not O(logn).
Raji has offered a good idea to achieve O(sqrt(n)) asymptotic number of tests. Another similar approach to achieve the same asymptotic number of tests but with less tests in practice can be described as follows:
Like in Raji's solution, we will fix some number k later. We will use the first magic want to check the boxes in the following order: k, k+(k-1), k+(k-1)+(k-2),...
In other words we skip k-i boxes between test i-1 and i. This also implies that if the first wand vanishes after i tests, we will have at most k-i tests left to do with the second wand in order to determine where the first empty box is. The total number of tests using this algorithm will be i + (k - i) = k.
Now, how should we select k? We would want to select the minimum possible k such that k + (k-1) + (k-2) + ... >= n. The desired k will be the solution for the following equation (The other cases would contradict k's minimality):
n = k + (k-1) + (k-2) + ... + 1 = k*(k+1)/2
Thus, because k is positive its value is:
k = ceiling((sqrt(1+8n) - 1)/2)
Reference - webdocs.cs.ualberta.ca/~mreza/courses/204-F07/tut-notes/tut2.txt
- Raji January 13, 2014We will fix number k later.
The idea is first use one wand on boxes 1, k, 2k, 3k, ...
The smallest i for which the wand burns on box i*k indicates
that the first empty box is among (i-1)*k+1....i*k
Now we use the second wand sequentially from (i-1)*k+1 to i*k-1
to find it.
The total number of toches will be at most: n/k + k
n/k is the number of boxes for the first wand and k for the second one
If we now choose k to be (about) \sqrt{n} then we have n/\sqrt{n}+\sqrt{n}
which is in O(\sqrt{n}) touches.