1
O(1): constant growth; input size does not affect the number of operations significantly.
2
O(log n): logarithmic growth; the problem size is repeatedly reduced, as in binary search.
3
O(n): linear growth; work increases proportionally with input size.
4
O(n log n): common in efficient comparison-based sorting algorithms.
5
O(n²): quadratic growth; often caused by nested loops over the input.

Difficulty: 3/10

Topics: time complexity, algorithm analysis, performance tradeoffs

0-2 years experience

1
Suppose you need to check if a user ID exists in an unsorted array of size n. What is the time complexity of a linear scan, and how would it change if the array were sorted?
2
If you have a hash map that gives O(1) average lookup, what does that mean for retrieving a value by key?
3
When you append an element to a dynamic array that occasionally resizes, what's the amortized time complexity?

2-5 years experience

1
Your recent feature added a nested loop to process a list of orders, and the latency doubled. Walk me through how you'd analyze the time complexity and identify the O(n²) part.
2
We switched from a binary search tree to a linked list for storing session tokens, and lookups got slower. Explain why the complexity changed from O(log n) to O(n).
3
During a code review you notice a function that sorts data using quicksort. Under what conditions could its performance degrade to O(n²), and how would you mitigate it?

5-8 years experience

1
Design a service that aggregates real‑time metrics from millions of devices. Which data structures and algorithmic complexities would you choose for ingest vs query paths, and why?
2
Your caching layer currently uses a simple array for LRU eviction, leading to O(n) updates. Propose a redesign that achieves O(1) operations and discuss trade‑offs.
3
When scaling a recommendation engine, you need to compute top‑k items per user. Compare using a heap (O(n log k)) vs sorting the entire list (O(n log n)) and justify your choice.

8+ years experience

1
Our company is refactoring a legacy analytics pipeline that processes petabytes of logs daily. How would you evaluate and improve the overall algorithmic complexity across the pipeline to ensure it stays sub‑linear where possible?
2
We plan to migrate a monolithic search service to microservices. Discuss how Big‑O considerations influence the partitioning of indexing and query handling across services.
3
When introducing a new feature that requires joining two massive datasets, what architectural patterns can you use to avoid O(n²) blow‑up, and how would you measure success?

❓Can you give an example where O(1) hides a large constant factor?
❓How do you decide between an O(n log n) and an O(n) solution in a production system?
❓What pitfalls arise when relying only on average‑case complexity?