Amazon Interview Question for Interns


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
3
of 3 vote

Reference - webdocs.cs.ualberta.ca/~mreza/courses/204-F07/tut-notes/tut2.txt
We 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.

- Raji January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

- Arxo Clay January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am confused about this too. I think it should work, if we are not missing anything.
Can someone explain?

- ami February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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. ;-)

- Dpynes January 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Follow this sequence, test 1,2, 4, 8,16,......
if 2pwd k is empty 2pwd k-1 to x Using second wand Ologn

- Anonymous January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- IvgenyNovo January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

grt question

- Pras January 19, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More