Tuesday, 19 January 2021

What's the best time complexity of a queue that supports extracting the minimum?

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