Sollicitatievraag bij Amazon
Implement stack with maximum function. All functions (pop, push, max) should be O(1)
Antwoorden op sollicitatievragen
Anoniem
17 feb 2020
Such a stack does not exist... Here's an example why: push N items onto stack in O(N) time. Then retrieve N items with max function in O(N) time. You just sorted N items in O(N+N) = O(N) time which is impossible.