Amazon Interview Question
Software Engineer / DevelopersI think the solution is to have a list sorted by recently used order. So, there will be MRU on one end and LRU on other.
Push: add to MRU position, head of queue: const time
Pop: delete from LRU position, tail of queue: const time
find min: return LRU: const time.
Only thing which takes O(n) time is access. You have to find the entry and bring it to MRU position.
You can maintain 2 Linked Lists.
1. Stack List: This is simple & implements Push & Pop. Whish is or order(1).
2. Another List called "Min List" need to be maintained. Every Min number will be added to list.
For example, if you have below list.
2,5,4,6,1,8,0
Parse1:
Stack List: 2
Min List: 2
Here Order is O(1) for both.
Parse2:
Stack List: 5,2
Min List: 2 (Don’t insert because 5 is not min compare to 2)
Here Order is O(1) for both.
Parse3:
Stack List: 4,5,2
Min List: 2 (Don’t insert because 4 is not min compare to 2)
Here Order is O(1) for both.
Parse4:
Stack List: 6,4,5,2
Min List: 2 (Don’t insert because 6 is not min compare to 2)
Here Order is O(1) for both.
Parse5:
Stack List: 1,6,4,5,2
Min List: 1,2 (Insert it because 1 less min compare to previous min 2)
Here Order is O(1) for both.
Parse6:
Stack List: 8,1,6,4,5,2
Min List: 1,2 (Don’t insert because 8 is not min compare to 1)
Here Order is O(1) for both.
Parse7:
Stack List: 0,8,1,6,4,5,2
Min List: 0,1,2 (Insert it because 0 less min compare to previous min 1)
Here Order is O(1) for both.
At any point you will get the Min & Push with O(1).
Min: 0 (The first element. This is always like this.)
Regarding Pop.
Pop:
Value Output: 0
Change Min List to remove 0: 1,2 (1 is the Min of the list).
It’s Order(1).
Pop:
Value Output: 8
Min List is: 1,2
At any given point Push, Pop & Min are O(1)
the question appears to be simple. we can use a stack for this. push and pop are o(1) as done at the same end of list and min (i assume it to be the least recently used) is also o(1). Am i missing something here?
- peeyush.fun July 29, 2010