I ran into the following very difficult interview question:
Consider Queue Data Structure with three operations:
- Add into the front of list (be careful front of list) - Delete from Tail of the list (end of the list) - Extract Min (remove)
The best implementation of this data structure has amortized time:
A) three operation at O(1)
B) three operation at O(log n)
C) add and delete in O(1) and Extract-min in O(log n)
D) add and delete in O(log n) and Extract-min in O(n)
After the interview I saw that (C) is the correct answer. Why is this the case?
The first challenge is comparing the options: which option is better than the others and how we can understand the final correct option?
from What's the best time complexity of a queue that supports extracting the minimum?
No comments:
Post a Comment