Amazon Interview Question for Software Engineer / Developers


Country: -




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

O(n) using memorization and O(2^n) using recursion

- hashd September 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

fine it is possible in order n i know
but when we make tree it grows exponentially in (recursion tree)

- getjar.com/todotasklist my android app September 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that is when it becomes O(2^n)

- hashd September 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

While O(2^n) is technically correct, the more accurate answer is Theta(r^n) where r is the golden ratio. In fact, this is same as Theta(F_n), where F_n is the nth fibonacci number.

Notice how the time complexity recurrence and the recurrence for fibonacci are similar?

- Anonymous September 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It depends on the way you implement it. If u implement Fibonacci fn recursively the order is 2^n where as an iterative approach is n^2 (which is definitely better).

- hs September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hs: If you implement recursively, it is THeta(r^n). Please try to understand what others are saying...

- Anonymous September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

the tree grows exponentially O(2^n) ..correct..
but the height is log(O(2^n)) = n ..
so complexity = n * n = n^2

- annon October 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n2) is correct result.Check it out on stack-overflow.

- Anonymous October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this really an amazon question or are you trying to get your homework done? How many amazon interviews have you given so far, techcoderonwork?

- Anonymous September 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Either it's homework or he should have failed his CS degree.

- Anonymous September 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or both.

- Anonymous September 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi frnds
this is not my homework i m in last year of my PG(MCA).
i m already placed . now i m preparing for better comanies like amazon.
the questions i m posing are not asked to me because i have attended any interview of amazon. these are questions faced by our seniors. since we have all the questions and i m solving , in the case i am not able to solve i m posting here.

- techcoderonwork September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question he asked is very valid i was asked the same question when i was interviewed onsite at amazon seattle campus.

- SomeOne September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good :-).

I hope you understand why people might be skeptical. A lot of people here post questions which they came across on some website/homework and not really an interview, by attributing it to some random company (probably amazon is higher because that is could be first in the list, idk).

There is no harm in clarifying.

Of course you might say, how does it matter? It probably does not, but one good thing in not having such questions (i.e. unknown whether interview or not) is that by having them you distort reality :-)

Anyway...

- Anonymous September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i dont know why these r more interested in asking in knowing that ques is homework or something else rather than posting the solving them.

- getjar.com/todotasklist my android app September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i dont know why these r more interested in knowing that ques is homework or something else rather than posting the solving them.

- getjar.com/todotasklist my android app September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Because this is a very unusual question for an interview. It is more likely to be homework.

- Anonymous September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

'coz no one pays shit to a HW question! u better leave out of CC.

- anonymous2 September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

at anonymous2
people like u are mother fucker spoiling the coding dignity.
if u dont know the answer , then just shut ur mouth .
this is very valid question.u need to leave CC

- kamal September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kamal, you are worse.

- Anonymous September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the complexity should not be O(2^n) because the tree is not a balanced binary tree.

- joe September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi joe
the tree is not a balanced binary tree this ie true.
but the comlexity will be 2^n I have confirmed it from algo teacher.

- kamal September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi joe
the tree is not a balanced binary tree this is true.
but the comlexity will be 2^n I have confirmed it from algo teacher.

- kamal September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algo teacher sucks.

- Anonymous September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I shouldn't use the word "balanced binary tree". It's actually an incomplete tree, a lot of levels are not fully filled.

- joe September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have to make further modification. if calculate t(n) recursively, there are many terms such as t(n-4), t(n-5)...t(n-k). Generally the number of t(n-k) is t(k). And you have to sum them up one by one. assume t(n) takes the form as O(x^n) as one guy suggested above, then x = 1/2*(1+sqrt(5)) <2. From an intuitive point of view, many levels of the tree are not fully filled.

- joe September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simpler:

T(n) = T(n-1) + T(n-2) + K

Let G(n) - K/3 = T(n)

Then,
G(n) = G(n-1) + G(n-2)

And this gives G(n) = Theta(x^n) and thus T(n) = Theta(x^n).

(General form of G(n) is Ax^n + By^n where x,y are roots of z^2 = z+ 1, which comes out to Theta(x^n) for non-zero A).

- Anonymous September 20, 2011 | 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