Python · Module 7Module material
Time and Space Complexity interview questions
25 questions interviewers ask on this module’s topics, from first principles to the follow-ups. Each comes with a model answer.
Complexity
- What is time complexity, and why count operations rather than seconds?●
- What does Big-O notation keep, and what does it drop?●
- Order these from slowest-growing to fastest: O(n²), O(1), O(n log n), O(log n), O(n).●
- What are the best, worst and average cases of a linear search?●●
- A function takes 13 ms on 1,000 values and 55 ms on 2,000. What is its complexity likely to be?●●
- Why is this function O(n²), though it has one loop?●●
- What is space complexity?●
- What is a time–space trade-off? Give an example.●●
- What are the time complexities of
append,insert(0, x),x in a_listandsorted?●● - Does a lower Big-O always mean faster code?●●
Binary search
- How does binary search work, and what does it need?●
- Why is binary search O(log n)?●●
- What happens if you binary-search an unsorted list?●●
- When is sorting first, then binary search, worth it?●●
- What are the classic bugs in a hand-written binary search?●●
- What does
bisect_leftreturn for a value that is not in the list?●● - How would you count the occurrences of a value in a sorted list in O(log n)?●●
- Write binary search recursively. What is its space complexity?●●
Hash tables
- What is a hash table?●
- What is a collision, and how is it handled?●●
- What is the load factor, and why does it matter?●●
- Is a dictionary lookup always O(1)?●●
- Why must dictionary keys be hashable, and why is a list not?●●
- How do you find the elements two lists share, and at what cost?●●
- Why does a set of strings print in a different order each session?●●