PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • hard
  • Microsoft
  • Coding & Algorithms
  • Software Engineer

Implement concurrent structures and debug queue code

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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.

Quick Answer: 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.

Part 1: Simulate an LRU Cache

Design an LRU (Least Recently Used) cache and process a sequence of cache operations. The cache supports `get(key)` and `put(key, value)`. A `get` returns the stored value if the key exists, otherwise `-1`. Any successful `get` or `put` on an existing key makes that key the most recently used. When inserting a new key into a full cache, evict the least recently used key first. Return the results of all `get` operations in order. Follow-up discussion for the interview: explain how you would make the cache safe under concurrent access from multiple threads. That follow-up is not part of the returned value here.

Constraints

  • 0 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Each operation is either `('put', key, value)` or `('get', key)`
  • -10^9 <= key, value <= 10^9

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [1, -1, -1, 3, 4]

Explanation: Standard LRU example. Keys 2 and then 1 are evicted.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('get', 1), ('put', 3, 3), ('get', 2), ('get', 3)])

Expected Output: [10, -1, 3]

Explanation: Updating key 1 also makes it most recently used, so key 2 is evicted.

Input: (0, [('put', 1, 1), ('get', 1), ('put', 2, 2), ('get', 2)])

Expected Output: [-1, -1]

Explanation: A cache with capacity 0 never stores anything.

Input: (3, [])

Expected Output: []

Explanation: No operations means no outputs.

Hints

  1. Use a hash map to find a key's node in O(1) time.
  2. Keep keys in recency order with a doubly linked list; in the thread-safe follow-up, remember that the map and list must stay consistent together.

Part 2: Build a Hash Map from Scratch

Implement an integer hash map from scratch without using Python's built-in `dict` for storage. Support three operations: `put(key, value)`, `get(key)`, and `remove(key)`. Use correct collision handling so that all operations behave properly even when multiple keys land in the same bucket. Return the results of every `get` and `remove` operation in order. Follow-up discussion for the interview: explain how you would extend the design for concurrent readers and writers. That follow-up is not part of the returned value here.

Constraints

  • 0 <= len(operations) <= 2 * 10^5
  • Keys and values are integers
  • -10^9 <= key, value <= 10^9
  • Average-case target for each operation is O(1)

Examples

Input: ([('put', 1, 10), ('put', 2, 20), ('get', 1), ('remove', 2), ('get', 2)],)

Expected Output: [10, 20, -1]

Explanation: Basic insert, read, remove, and missing-key lookup.

Input: ([('put', -1, 5), ('put', 7, 8), ('put', -1, 9), ('get', -1), ('remove', 7), ('get', 7)],)

Expected Output: [9, 8, -1]

Explanation: Updating an existing key replaces its value.

Input: ([('put', 0, 0), ('put', 4, 16), ('put', 8, 64), ('get', 8), ('remove', 0), ('get', 0)],)

Expected Output: [64, 0, -1]

Explanation: This checks collision handling and removal.

Input: ([],)

Expected Output: []

Explanation: No operations produce no outputs.

Hints

  1. A common collision strategy is separate chaining: each bucket stores a small list of key-value pairs.
  2. If too many items are inserted, resize and rehash; for the concurrency follow-up, bucket-level locks scale better than one global lock, but resizing still needs coordination.

Part 3: Quadtree Rectangle Queries for 2-D Points

Implement a quadtree for 2-D integer points. You are given an overall boundary rectangle, a node capacity, a list of points to insert, and a list of query rectangles. Each quadtree node may store up to `node_capacity` points directly; when it exceeds that limit, it splits into up to four children and redistributes its points. For every query rectangle, return all inserted points that lie inside or on the boundary of that rectangle. The returned points for each query must be in original insertion order.

Constraints

  • 1 <= node_capacity <= 32
  • 0 <= len(points), len(queries) <= 10^4
  • All coordinates are integers
  • All points lie within the given boundary rectangle
  • Rectangle boundaries are inclusive

Examples

Input: ((0, 0, 7, 7), 1, [(1, 1), (2, 5), (5, 2), (6, 6)], [(0, 0, 3, 5), (4, 0, 7, 7), (3, 3, 4, 4)])

Expected Output: [[(1, 1), (2, 5)], [(5, 2), (6, 6)], []]

Explanation: Queries select the left side, the right side, and then an empty middle region.

Input: ((0, 0, 4, 4), 2, [(0, 0), (4, 4), (2, 2), (2, 2)], [(0, 0, 4, 4), (2, 2, 2, 2)])

Expected Output: [[(0, 0), (4, 4), (2, 2), (2, 2)], [(2, 2), (2, 2)]]

Explanation: Boundary points count as inside, and duplicate points should both be returned.

Input: ((0, 0, 10, 10), 1, [], [(0, 0, 10, 10)])

Expected Output: [[]]

Explanation: Querying an empty tree returns an empty result list for that query.

Input: ((5, 5, 5, 5), 1, [(5, 5)], [(5, 5, 5, 5), (0, 0, 4, 4)])

Expected Output: [[(5, 5)], []]

Explanation: A degenerate one-point boundary still works.

Hints

  1. A node only needs two states: a small point list if it is a leaf, or children if it has been subdivided.
  2. During querying, immediately stop exploring a node if its rectangle does not intersect the query rectangle.

Part 4: Detect Producer-Consumer Queue Bugs from an Event Trace

A C++20 producer-consumer program uses a bounded FIFO message queue, but the implementation may contain correctness and synchronization bugs. Instead of reviewing source code directly, you are given an execution trace and must report which issue categories appear. This coding task focuses on issues that can be detected from the trace. Queue rules: - Capacity is fixed. - `('push', item)` tries to enqueue `item`. - `('pop', item)` claims that the consumer dequeued `item`. - `('wait_push',)` means a producer went to sleep because it believed the queue was full. - `('wait_pop',)` means a consumer went to sleep because it believed the queue was empty. - `('close',)` means producers are done; after this, no further pushes are allowed. Report each issue code at most once, in this exact order: 1. `OVERFLOW` - a push happened when the queue was already full. 2. `UNDERFLOW` - a pop happened when the queue was empty. 3. `FIFO_VIOLATION` - a pop from a non-empty queue reported the wrong item. 4. `MISSED_WAKE_PUSH` - `wait_push` happened even though the queue was not full. 5. `MISSED_WAKE_POP` - `wait_pop` happened even though the queue was not empty. 6. `PUSH_AFTER_CLOSE` - a push happened after `close`. 7. `UNCONSUMED_ITEMS` - the trace ends after `close` but the queue still contains items. Important simulation rules: - If a `push` is invalid because the queue is full or already closed, do not enqueue the item. - If a `pop` happens from a non-empty queue but reports the wrong item, still remove the actual front item before continuing.

Constraints

  • 0 <= capacity <= 10^5
  • 0 <= len(events) <= 2 * 10^5
  • Items are integers
  • Events are one of `('push', item)`, `('pop', item)`, `('wait_push',)`, `('wait_pop',)`, `('close',)`

Examples

Input: (2, [('push', 1), ('push', 2), ('pop', 1), ('pop', 2), ('close',)])

Expected Output: []

Explanation: A correct FIFO trace with clean shutdown.

Input: (2, [('push', 1), ('push', 2), ('pop', 2), ('pop', 1), ('pop', 3), ('close',)])

Expected Output: ['UNDERFLOW', 'FIFO_VIOLATION']

Explanation: The first two pops report the wrong items, and the last pop happens on an empty queue.

Input: (1, [('push', 5), ('wait_pop',), ('push', 6), ('wait_push',), ('pop', 5), ('wait_push',), ('close',)])

Expected Output: ['OVERFLOW', 'MISSED_WAKE_PUSH', 'MISSED_WAKE_POP']

Explanation: The consumer waited while data existed, a producer pushed into a full queue, and another producer waited even though space was available.

Input: (3, [('push', 1), ('close',), ('push', 2)])

Expected Output: ['PUSH_AFTER_CLOSE', 'UNCONSUMED_ITEMS']

Explanation: A push after close is invalid, and item 1 remains unconsumed at the end.

Input: (2, [])

Expected Output: []

Explanation: Empty trace means no detected issues.

Hints

  1. Simulate the queue state exactly; many issues are easiest to detect from the current size and front item.
  2. For a wrong `pop`, decide how the queue should evolve afterward before checking later events.
Last updated: May 2, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Return Top K Open Businesses - Microsoft (hard)
  • Implement Memory Allocation and In-Memory Records - Microsoft (medium)
  • Implement K-Means and Detect Divisible Subarrays - Microsoft (medium)
  • Sort Three Categories In Place - Microsoft (medium)
  • Retain Top K Elements - Microsoft (medium)