← Microsoft Interview InsightsSoftware Engineer

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Microsoft interview that came down to a single data structure design problem. Nothing crazy, but the details on handling corrections and lazy deletion tripped me up more than I expected.

Questions Asked (1)

Q1

Design a data structure that supports stock price updates (including corrections to past timestamps), and can return the current price, the maximum price, and the minimum price at any time.

Algorithms & Data StructuresSystem Design
Author's notes

The hash map part came to me pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify requirements first: whether updates are corrections to past timestamps, and whether queries are for the current time or any historical time. Then propose a data structure like a balanced BST or segment tree that supports point updates and range min/max queries, and discuss trade-offs between time and space complexity.

Pro tip: Demonstrate awareness of real-world constraints: stock prices are often append-only with occasional corrections, so consider a versioned or persistent data structure to handle historical queries efficiently. Also, mention that using a heap for min/max is insufficient because corrections require updating arbitrary elements.

1. Clarify Requirements

Ask whether updates are only for the current time or can correct past timestamps, and whether queries are for the current price or any historical time. Confirm if we need to support multiple stocks or just one.

2. Choose Data Structure

Propose a balanced binary search tree (e.g., AVL, Red-Black) or a segment tree over timestamps, where each node stores the price and subtree min/max. For corrections, update the node and propagate changes.

3. Handle Updates and Queries

For an update at timestamp t, insert or modify the node in O(log n) time. For current price, query the node at the latest timestamp; for max/min, use the root's stored min/max if the tree covers all timestamps.

4. Analyze Complexity

State that updates and queries run in O(log n) time, with O(n) space. Compare with alternatives like heaps (O(1) min/max but O(n) updates) or arrays (O(1) updates but O(n) queries).

5. Discuss Extensions

Mention handling multiple stocks by using a map from stock ID to the data structure, and supporting historical queries by making the structure persistent or using a segment tree with time as the key.

Key Points to Mention

  • Time complexity: O(log n) for updates and queries with balanced BST or segment tree.
  • Space complexity: O(n) for storing all timestamps and prices.
  • Handling corrections: need to update the data structure at the given timestamp, not just append.
  • Why heaps are insufficient: they don't support efficient updates to arbitrary elements.
  • Segment tree vs. balanced BST: segment tree is simpler for range min/max queries, BST is more flexible for order statistics.
  • Real-world considerations: concurrency, persistence, and handling multiple stocks.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.