5)Create a data structure where inserting, deleting and finding the minimum element all have O(1) time. i said we can use augmented stack where with each element we can augment the minimum element along with its actual value.Then he said?what if you cannot create any new data structure but have to use only the previously available data structures?? I replied that then we can use two stacks one to store the actual data and other to store the minimum values

Question

Accepted Answer

Data structure with O(1) insert, delete, and find min without creating new structures

Use two stacks, one for actual data and one for minimum values
When inserting, push the value onto the data stack and push the minimum of the new value and the top of the minimum stack onto the minimum stack
When deleting, pop from both stacks
When finding the minimum, return the top of the minimum stack

Top Directi Software Engineer interview questions & answers

Popular interview questions of Software Engineer