Top 3 Amortised analysis Interview Questions

Browse 3 real-world technical and behavioral interview questions about Amortised analysis. Review scenarios, edge cases, and architectural best practices.

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.

mediumcoding

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.

mediumconcept

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.

mediumcoding