Complexity Analysis interview questions

Deriving and defending time and space bounds, including amortised reasoning.

3 questions in Data Structures & Algorithms.

Data Structures & AlgorithmsA 26-minute read on how the topic fits together, before the questions.Data structures and algorithms fundamentals54 short answers on one page, for revising rather than studying.

medium3

mediumCodingConcept

The assistant wrote a working solution and the interviewer asks for its complexity and one input that breaks it. How do you verify code you did not write?

Read every loop and recursive call, then price each line inside them, because the expensive part is often a library call such as pop(0), a list membership test or string concatenation. Aim inputs at that worst case and at the edges the samples skip, and compare against a slow, simple version on random inputs.

5 minmid, senior

mediumConcept

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.

5 minmid, senior, staff

mediumConceptScenario

A nightly job took 40 minutes last month and takes two hours forty on twice the data. What do you conclude about its complexity, and what would you measure next?

A fourfold cost for a doubled input is consistent with quadratic growth, but two points fit infinitely many curves and a one-off cliff such as spilling out of memory produces the same ratio. Get a series of ratios across several doublings, then confirm the exponent against the code.

4 minmid, senior, staff