Katkat
Back

Implement concurrent structures and debug queue code

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates data-structure implementation and concurrent programming competencies by testing construction of an LRU cache, a custom hash map, a quadtree spatial index, and debugging of a producer-consumer queue.

The coding rounds covered several implementation and debugging tasks:

  1. Implement an LRU cache that supports get(key) and put(key, value) in constant time. Then explain how you would make the cache safe under concurrent access from multiple threads.
  2. Implement a hash map from scratch with put, get, and remove. Then discuss or extend the design so that it works correctly when multiple threads read and write concurrently.
  3. Implement a quadtree for two-dimensional points or rectangles, and support spatial query operations such as returning all items inside a query rectangle.
  4. Review and debug a C++20 producer-consumer program built around a message queue. Identify correctness issues, race conditions, synchronization mistakes, and any performance or API-design problems.