1
If you have a loop that runs n times and inside it you perform a constant‑time operation, what is the Big‑O of that code? How does it compare to a nested loop over n?
2
Suppose you need to search for a value in a sorted array using binary search versus linear search. Which one has a better Big‑O, and why would you choose one over the other in a small utility script?
3
You wrote a function that builds a hash map from n items and then looks up each item once. What overall time complexity does that give you compared to using a list for lookups?

2-5 years experience

1
Our team noticed a performance regression after switching from a hash table to a linked list for caching recent queries. Walk me through how the change in Big‑O could cause that slowdown.
2
You need to implement pagination for a feed that can have millions of posts. Would you prefer O(n) or O(log n) retrieval for each page, and what trade‑offs does that involve?
3
During a code review you see a function that sorts a list with bubble sort and then does a binary search. How would you rank the overall complexity, and what would you suggest to improve it?

5-8 years experience

1
Design a service that aggregates real‑time metrics from thousands of sources. How would you choose data structures and algorithms to keep per‑metric update time as close to O(1) as possible, and what would be the impact if you accidentally used O(n) operations?
2
Our recommendation engine currently builds a user‑item matrix using a dense array, leading to O(n²) memory usage. Explain how moving to a sparse representation changes the time and space complexities, and what trade‑offs you’d need to consider at scale.
3
When scaling a search index, we observed that query latency grew from O(log n) to O(n) after a recent refactor. Walk me through how you would diagnose the regression and what design changes could restore the logarithmic behavior.

8+ years experience

1
The company plans to migrate legacy batch jobs that currently run in O(n²) time to a streaming architecture. How would you evaluate the long‑term cost and performance implications of moving to algorithms with O(n log n) or O(n) complexity across multiple teams?
2
We have a cross‑service data pipeline where each stage currently uses a quadratic algorithm for deduplication. Propose an architecture that enforces better asymptotic performance globally, and discuss how you’d convince stakeholders to adopt it.
3
In a multi‑tenant SaaS platform, you need to guarantee that any single tenant’s workload cannot degrade overall system performance. How would you use Big‑O analysis to set isolation limits and design resource throttling mechanisms?