Explain Big-O notation. What do O(1), O(n), O(log n), O(n log n), O(n²) mean?

0-2 years experience

1. 1Suppose 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. 2If you have a hash map that gives O(1) average lookup, what does that mean for retrieving a value by key?
3. 3When you append an element to a dynamic array that occasionally resizes, what's the amortized time complexity?

2-5 years experience

1. 1Your 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. 2We 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. 3During 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. 1Design 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. 2Your 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. 3When 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. 1Our 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. 2We 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. 3When 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?