Amazon Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
8
of 10 vote

First check your starting point for the object, obviously. Label this point 0. If the object is not there, start with i = 0. On iteration i: step forward 2^i times, checking each square. Return to 0 by stepping back 2^i times. Step backwards 2^i times, checking each square. Return to 0 by stepping forward 2^i times. Increment i and repeat, so long as the object has not been found.

Analysis: Assume the object is located at point n. Without affecting big-O, we may assume n = 2^k for some natural number k. Then using this method it will take 4*(2^0 + 2^1 + ... + 2^k) = 4*(2^(k+1) - 1) = 4*(2n -1) = O(n) steps. Linear time is the best we could hope to do, so asymptotically at least, this algorithm is optimal.

- zodiak770 September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

It might be better to increment i every time you change direction, this would lead to 2^(k+1)-1 steps. Not that it would change the big-O, but looks like it would find n faster.

- uruk_hai September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

@Amit

What answer did you give? I suppose you can move forward and backward in steps of powers of 2.

0. Let i = 0
1. Move 2^i steps in one direction(either forward or backward)
2. i++
3. Reverse direction and move 2^i steps
4 Reverse direction and move 2^i + 2^(i-1) steps
5. Repeat steps 2 to 4 until the element is found

- Murali Mohan September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe this solution is going down the right path. The only question I see would be, why use 2? Why not 3, 4, 5 or any other number? To this point, I believe you need to be able to speak to why the constant you pick helps to ensure the minimization of regret (going the wrong direction) as arbitrarily going one direction only could lead to no result, and not using a distributed pattern like the exponential approach mentioned here can lead to inefficient turning points.

Just to clarify, I personally think 2 is the best constant, as growth by an exponential value will have 2 going to super large numbers as early as the 20th iteration.

- masterjaso September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

For that matter, since it is an infinite line, i can be initialized to any value and the movement can be to the powers of any base. The bottom line is to have strategy to move back and forth incrementally.

There can be no optimal solution that can have time complexity defined in terms of a finite quantity 'n'

- Murali Mohan September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@masterjao

Plz see my comment above. You are right, the base of the power does not actually matter here, nor does the initial value set to i.

- Murali Mohan September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
4
of 6 votes

We might ask what base results in the best constant for that O(n) runtime. Using a base of sqrt(2) + 1 results in the best constant for the worst-case runtime out of all the exponential-based solutions.

Consider that the worst case is when our target value is some number N, but in the previous pass, we only reach N-1 before turning back. So, in that previous pass, we moved 4*(N-1) units (forward and back in the positive and negative direction). Furthermore, if our base is b, the passes before that one, we must have taken 4*(N-1) / b + 4*(N-1) / b^2 + ... 4* 1 steps. The total of this and 4*(N-1) is approximately 4 *(N-1) / (1 - 1/b) by the formula for the sum of a geometric series.
Now consider the pass on which we find the target. First we might go in the other direction and back to 0, taking 2*(N-1)*b steps. Then we finally reach the target in another N steps. So we have that in the worst case, reaching the target takes 4*(N-1) / (1 - 1/b)+ 2*(N-1)*b + N steps. We can ask for what value of b this expression is smallest. Fix N while treating r = 1/b as a variable. Taking the derivative with respect to b and setting to 0 gives -1/r^2 + 2 / (r-1)^2 = 0. Solving this, we get r^2 + 2r - 1 = 0. This has a positive solution for r = sqrt(2) - 1, that is, b = 1 / (sqrt(2) - 1) = sqrt(2) + 1 =~ 2.414.

- eugene.yarovoi September 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Abhi

>> If you are in the middle of the line this is probably going to be the worst solution.

What do you mean by or how can you define 'middle' for an infinite line in the first place?

- Murali Mohan September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene.yarovoi +1 great analysis. What about using Fibonacci sequence?
1 forward
2 backward
3 forward
5 backward
8 forward
...

- oOZz September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

i = {3...n}
step[1] = +1
step[2]= -2
step[i] = (step[i-1] * (-2)) + 1

- paul.nikonowicz September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can move only one step at a time.

- Anonymous September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Question not clear.(for me).Any conditions or extra info?

- kgpgeek September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we follow forward step as a prime number and backward next higher prime number ?

- Anonymous September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could not retrieve much information from the question:
1) Is the object at an integral number position on the line or can it be at any position?
2) We can go forward and backward one step. But how big can the step be?
3) The other answers here suggest the use of exponentiation and prime numbers. How are we sure that the object is to be found at an exponential position, etc ?
Kindly explain as it would help me understand what you all are thinking.

- june.pravin September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

some valid questions from June Pravin.

In computing , you could have two pointers traversing the positive and negative integers with one step each and trying to look for the object. To me , its about how you break down the problem and in a virtualized representation, each step is just an index with pos and -ve value and when you are physically traversing the line positive and -ve direction looking for the object, you are really looking for something like A(i) == true.or A(-i) == true where A defines the condition/criterion for object. I guess it all depends how one represents the data structures. Please comment as I may have misunderstood the problem.

- Rahul September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please explain ... by giving a simple example

- avikodak September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, let me ask a silly question. Why should we do steps of powers of 2?

- Jin September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree with an approach of sweeping in both directions with the movement constraints
the way we can distribute the sweeps uniquely is through a unique prime number way
1.) prime number point give us unique locations set of coordinates

- Rohit September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can take two pointers and move forward and backward simultaneously until the object found.

- kalyan September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I want to add another dimension to the problem.

Let's call 0 our starting position and N the position of the object.

Now if N is unbounded then the best answer is to pick an arbitrary direction and follow that without looking back.
Because, if N is unbounded, the chance of N being in range [0, x] is exactly the same as that of [-x/2, x/2] or [-x, 0] or any range of that width, and that renders the idea of moving back and forth rather pointless, it's only a waste of time.

If, on the other hand, N is bounded, that is there are L, R such that L < N < R, then the solution is obvious: go to one bound and then back to the other.

- uruk_hai September 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why going backward at all?
The question that should have been asked was how is the probability of finding that object distributed across that infinite line.
All the algorithms described in this thread assume that the object is more likely to be found closer from our initial position, and so everybody feels the need to come back and check the other side.
If the probability is equality distributed across the line, then you just keep going forward forever.
If the object is more likely to be closer from our initial position, then we need to know the probability distribution in order to know how many steps to take before it's worth coming back and checking the other side.
Any algorithm without that information is just pure guess.

- ben September 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The goal is to give an algorithm that is guaranteed to eventually find the object. If you just keep going forward, you may never find the object.

Suppose that the object we're trying to find is a distance of N from the starting point, though we have no knowledge of the value of N or its distribution among the possible test cases. We know that, for obvious reasons, no strategy can take fewer than N steps (whatever N is) to reach the object. If we don't know where the object is, no strategy can even always do it in exactly N steps, because there's the possibility of starting out moving in the wrong direction. It makes sense to ask whether there's a strategy that always achieves no worse than O(N) steps. Such a strategy would imply that with absolutely no initial knowledge about the whereabouts of the object, you can always reach it in a number of steps that is only a constant factor worse than the number of steps needed to reach it if you know exactly where it is ahead of time (it takes exactly N steps to reach it if you know where it is). The answer by zodiak770 describes one such algorithm.

- eugene.yarovoi September 23, 2013 | Flag


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