Top 5 Amortised analysis Interview Questions
Browse 5 real-world technical and behavioral interview questions about Amortised analysis. Review scenarios, edge cases, and architectural best practices.
Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.
Keep a stack of bar indices with strictly increasing heights. When a bar no taller than the top arrives, pop: the popped bar's rectangle runs from just after the new top to just before the current bar. A height-zero sentinel flushes the stack. Each index is pushed once and popped at most once, so it is O(n).
Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?
Keep a deque of indices whose values strictly decrease from front to back. Each step drops the front if it has left the window, pops smaller or equal values from the back, then appends. The front is the window maximum. Each index enters and leaves once, so it is amortised O(n), against O(n log k) for a balanced tree.
Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.
Push arrivals onto an inbound stack and serve departures from an outbound one, transferring everything across only when the outbound stack is empty. Transferring on every dequeue instead reverses the order and breaks FIFO, and the empty-only rule is also what makes the amortised cost constant.
Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.
Dynamic array append is amortized O(1) because capacity doubling makes the resize copy costs form a geometric series below 2n over n appends, even though one individual append can still be O(n). Use this complexity analysis answer to show the decision, trade-off, and evidence rather than a memorised definition. It also connects amortised analysis to the point an interviewer is testing.
For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.
Scan left to right holding a stack of indices whose answers are still unknown, kept strictly decreasing by value. Each new element resolves and pops everything smaller than it, then pushes itself. Every index is pushed once and popped at most once, so the scan is O(n) despite the inner loop.