Q: How do you spot hidden O(n²) complexity in code? Give an example.

The main signal is a hidden linear operation inside a loop. The code looks like a single loop, but a call inside it is itself O(n). Usual suspects: includes, indexOf, find, filter, some; building new arrays with slice/concat/spread inside a loop; unshift/splice inside a loop; string concatenation inside a loop (in some languages); sort inside a loop. Give a concrete example: joining two lists. orders.map(o => users.find(u => u.id === o.userId)) is O(n × m). Fix: build a Map from users once (O(m)), then look up each order in O(1) — O(n + m) overall. Also state the method: for every loop ask "what does each call inside cost?"; know your language's method complexities; and when unsure, multiply the input size by 10 and measure — if the time grows 100x, it's quadratic.

Question 1

Which array operations are O(1) and which are O(n)? Explain why.

Accepted Answer

Derive the answer from one principle — that reads much better than reciting a list: an array is contiguous, so addresses are computed (cheap), but any operation that breaks contiguity requires shifting (expensive). Then enumerate: O(1): read/write by index, append (amortized), remove from the end, read the length O(n): insert at the front/middle, remove from the front/middle, unsorted search, includes, indexOf, slice (proportional to the copied part) O(log n): binary search, but only on a sorted array O(n log n): sort Contrast front-removal with end-removal side by side: one shifts 999,999 elements, the other just decrements a counter. That concreteness lands well.

Question 2

How does a dynamic array work, and why is push amortized O(1)?

Accepted Answer

Start with the internal layout: a dynamic array holds a fixed-size buffer plus a separate length counter. capacity is the buffer size, length is the real element count. Then describe growth: when length == capacity, a buffer typically twice as large is allocated, all elements are copied (O(n)), and the old buffer becomes garbage. Now give the amortized argument — this is the heart of the answer: growth happens at 1, 2, 4, 8, ..., so across n appends the total elements copied is n + n/2 + n/4 + ... < 2n. That's O(n) overall, O(1) per operation. Finish with the contrast: if capacity grew by a constant step (+10 each time) instead of geometrically, total copying would be O(n²) — which is exactly why every real implementation (JS Array, ArrayList, std::vector, Dart List) uses a multiplicative factor. End with the practical note: pre-allocate capacity when you know the element count.

Question 3

How do you spot hidden O(n²) complexity in code? Give an example.

Accepted Answer

The main signal is a hidden linear operation inside a loop. The code looks like a single loop, but a call inside it is itself O(n). Usual suspects: includes, indexOf, find, filter, some; building new arrays with slice/concat/spread inside a loop; unshift/splice inside a loop; string concatenation inside a loop (in some languages); sort inside a loop. Give a concrete example: joining two lists. orders.map(o => users.find(u => u.id === o.userId)) is O(n × m). Fix: build a Map from users once (O(m)), then look up each order in O(1) — O(n + m) overall. Also state the method: for every loop ask "what does each call inside cost?"; know your language's method complexities; and when unsure, multiply the input size by 10 and measure — if the time grows 100x, it's quadratic.

Question 4

How do you choose between an array and a hash map?

Accepted Answer

Derive the choice from the access pattern, not from which structure is nicer. Pick an array when order matters, when you iterate sequentially, when you need index access, when the data is small (linear search over 10-20 items is fast anyway and hashing isn't worth it), or when memory density and cache locality matter. Pick a hash map when lookup, insert and delete by key are the main operations (O(1) average each), when keys are sparse or non-numeric, or when you need uniqueness/grouping (Set, groupBy). A strong addition: using both together is often the right answer. An LRU cache is a HashMap plus a doubly linked list; an ordered list that also needs fast lookup is an array plus an id → index map. Saying "if I need both ordering and O(1) lookup, I keep two structures in sync" reads as maturity. Mention the trade-offs too: a hash map uses more memory, iteration order may not be guaranteed (JS Map and Dart Map preserve insertion order, HashMap does not), and in the worst case collisions can degrade it to O(n).

Question 5

Why can one of two O(n) algorithms be much faster in practice?

Accepted Answer

Big O hides constants and the physical reality of memory — build the answer from there. Cache locality is the main factor: the CPU reads a whole cache line (typically 64 bytes) from RAM at once. Walking an array sequentially, the next elements are already in cache; walking a linked list, each node may sit anywhere in memory and every step risks a cache miss. A RAM access costs tens of times more than an L1 hit — so the same O(n) yields two very different practical outcomes. Other factors: the constant factor itself (3n vs 20n), how much work is done per element (a plain comparison vs allocating an object), the number of allocations and GC pressure, branch prediction, and language specifics (boxing, virtual dispatch, bounds checking). Closing position: "Asymptotics decide which algorithm I pick; constants decide how I implement it. The second part can't be memorised — it has to be measured."

Operation	Complexity	Why
Read/write by index `arr[i]`	O(1)	The address is computed by a formula
Append (`push`)	amortized O(1)	Usually writes into free capacity; growing costs O(n) when full
Remove from the end (`pop`)	O(1)	Only the length shrinks, nothing shifts
Insert at the front (`unshift`)	O(n)	Every element shifts one slot right
Remove from the middle (`splice`)	O(n)	Everything to the right shifts left so no hole remains
Search in an unsorted array	O(n)	Worst case you must look at every element
Binary search in a sorted array	O(log n)	The range halves at each step
Sorting (`sort`)	O(n log n)	The theoretical bound for comparison-based sorting

Arrays and dynamic arrays

📚 Sources and documentation