Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Look for Compile-time recursion (C) / Template meta-programming (C++), that's what they are looking for! :-)
Hi,
I have read that template meta programming will work only if you know what inputs to the factorial are at compile time. However, what happens if you wanna find factorials dynamically at run - time?
precompute the result in a single term and save them then take constant time to fetch...
That's what I said... since the operation will be recursive, you'll be able to precompute a lot of the results.
You can store them... but what else can you do?
The interviewer made me think that my solution was incomplete
You are almost correct. Simple code here for Fibonacci .
fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}
You will need to save only last two values to calculate the current value and can discard
all other values.
Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein
Since it's only 1000 at the most, we can cache all the values for maximum efficiency.
class Fib {
private int[] _solved;
Fib(int max) {
_solved = new int[max + 1];
_solved[0] = 1;
_solved[1] = 1;
for(int i = 2; i <= max; ++i) {
_solved[i] = _solved[i - 1] + _solved[i - 2];
}
}
public int fib(int term) {
return _solved[term];
}
}
Yep, you can use an array instead of a map. That solution will be blazing fast. Doesn't get much faster than that.
You are almost correct. Simple code here for Fibonacci here.
fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}
You will need to save only last to values to calculate the current value and can discard
all other values.
Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein
Section: Dynamic programming
You are almost correct. Simple code here for Fibonacci .
fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}
You will need to save only last to values to calculate the current value and can discard
all other values.
Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein
There is a much better approach using fibonnacci matrices, you can compute the nth fibonnacci in O(log(n)) time, use cache also, for future requests.
Here is the complete C# code:
- chuzpa October 14, 2012