The toughest interview questions asked recently

During a recent round of interviews, I was asked these 5 questions that I found particularly interesting / challenging. They each covered a different interesting pieces of computer science that I thought worth sharing. Check them out and see what you think about them:

1. A set of overlapping ranges are provided in [start, end) format. Find the max number of ranges that overlap each given range. Improve your solution to O(N log N) complexity (basic solution is: O(N^2) complexity for a set of ascending ranges [1,4), [2, 4), [3, 4) etc.).

2. Implement a multithreaded producer / consumer queue using condition variables.

3. Implement a multithreaded rate limiter (token bucket with defined capacity) using no hard-coded poll durations and without a background thread for "filling". Discuss fairness vs head of line blocking tradeoffs of the implementation.

4. Implement a multithreaded scheduler that executes tasks repeatedly at specified time intervals which manages task overruns (task time > interval time) and does not skip scheduled run points. Estimate the maximum number of outstanding threads that a task may produce.

5. Given a matrix of size NxM with 0 and 1 entries, find the number of connected regions in the matrix. Extend your solution to handle updates of 0 entries to 1s that may connect existing regions. Expected solution is O(NxM) complexity in the worst case even for the second case with updates being approximately O(1) and space being O(NxM). Hint: Disjoint sets. 

For System Design, the following were interesting questions:

1. Design typeahead search (given a query prefix, provide completions). 

The interesting part was managing hotspots for small query lengths, the use of a KV store for serving given the low latency requirements and managing personalization.

2. Design an ad click prediction system (ML infra pipeline).

3. Design a lineage system for tracking input data to ML model training to avoid sample bias.

Overall, interviewing was a pleasant process that refreshed a lot of skills. Let me know about other interview questions that might have been interesting for you.

Cheers!

Divye