Amazon Interview Question
Software Engineer / DevelopersCountry: -
fine it is possible in order n i know
but when we make tree it grows exponentially in (recursion tree)
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?
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).
the tree grows exponentially O(2^n) ..correct..
but the height is log(O(2^n)) = n ..
so complexity = n * n = n^2
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?
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.
The question he asked is very valid i was asked the same question when i was interviewed onsite at amazon seattle campus.
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...
i dont know why these r more interested in knowing that ques is homework or something else rather than posting the solving them.
Because this is a very unusual question for an interview. It is more likely to be homework.
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
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.
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.
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.
O(n) using memorization and O(2^n) using recursion
- hashd September 14, 2011