Amazon Interview Report
- 0of 0 votes
AnswersImplement LRU cache.
- BlackMath June 26, 2012 in India for KDK - Kindle Development Kit
I think this question is already there on careercup.
I answered with hashmap + minheap.
Access takes O(1) and inserting new element takes O(lg n).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a stack.
- BlackMath June 26, 2012 in India for KDK - Kindle Development Kit
Can we find range of numbers in the stack ?
Range is Max value in stack - Min value in stack.
Q > How will we design the stack to get Range in O(1) ?
Ans > I answered this one saying we have max variable and min variable defined in the stack. Whenever we push any number into stack, we compare with the current max and update, if necessary. Same with min.
Q > Then, he asked me what happens when we pop ?
If the element to be popped is the max element, how do we find the second max to be the new max element.
Ans > This, i answered we maintain two different stacks inside a stack called maxStack and minStack for max and min elements. He asked me to code everything. I did.
Then, he asked me if there are duplicates in the stack, can we optimise our solution so that the max element doesn't get inserted into the maxStack more than once and still we get all the above functionalities in optimised way ?
Ans > I answered we maintain a map of integer and it count. When we push into the stack, if the element is already there in the stack, we increase its count and update the maxStack or minStack, if necessary. When we pop, we decrease the count. If count becomes 0, then we update the maxStack and minStack, if necessary.
I coded everything then.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm