Google VO: From a Priority Queue to a High-Concurrency Order Book

Google interviews are rarely just about writing code that runs. What interviewers really look for is whether you can model evolving requirements through follow-ups, make the right data-structure trade-offs, and justify complexity with precision.

This article breaks down a classic Google VO question: maintain a sell-side order book for product ABC, strictly ordered by price priority and timestamp priority, and then handle deeper follow-ups (cancellation, partial fill, concurrency).

---

📋 Problem Statement (Original)

Imagine a marketplace for product "ABC."
Sellers enter the market and input their desired price.

The system maintains an order book sorted by:

• Price (ascending)
• Timestamp (earlier entries first if prices are tied)

Constraints:

• All prices are between $0.01 and $100.00
• Each seller can submit only one active order
• Each order offers one unit of ABC

Core Functions

insert_order(seller_id, price, timestamp)
get_lowest_seller_id(): returns and removes the seller with the lowest price

---

🎯 What This Question Really Tests

This problem is usually driven through three phases:

1. Baseline data-structure choice
   • Priority Queue / Heap
2. State management & cancellation
   • Optimizing “delete from anywhere” via Lazy Deletion
3. Business extensions
   • Unbounded price precision
   • Partial fill
   • High concurrency / system-design discussion

---

💡 Solution Strategy (oavoservice Interview Guidance)

1) Clarify Assumptions First (Do This in the Interview)

oavoservice note: before coding, clarify these:

• Is timestamp guaranteed to be monotonic increasing?
• Is seller_id globally unique?
• If a seller calls insert_order twice:
  • overwrite the previous order?
  • or reject as invalid?

Proactive clarification is a strong senior signal.

---

🧠 Approach 1: Min-Heap + Lazy Deletion (Standard & Robust)

Core idea:

• Use a min-heap to enforce price priority
• Use a hash map to track the latest valid order per seller
• Use Lazy Deletion to avoid O(n) arbitrary deletion in a heap

Python Reference

import heapq

class OrderBook:
    def __init__(self):
        self.heap = []  # (price, timestamp, seller_id)
        self.active_sellers = {}  # seller_id -> timestamp

    def insert_order(self, seller_id, price, timestamp):
        self.active_sellers[seller_id] = timestamp
        heapq.heappush(self.heap, (price, timestamp, seller_id))

    def get_lowest_seller_id(self):
        while self.heap:
            price, ts, sid = heapq.heappop(self.heap)
            if self.active_sellers.get(sid) == ts:
                del self.active_sellers[sid]
                return sid
        return None

⏱️ Complexity

• Insert: O(log n)
• Get Lowest: amortized O(log n)
• Space: O(n)

---

🚀 Common Follow-ups

Q1: If the price range is fixed, can you do better than a heap?

Bucket + Queue (great for fixed range & fixed precision)

• Price range: 0.01 ~ 100.00
• Precision: 0.01
• Total buckets: 10,000
• Each bucket: a FIFO queue

Performance:

• Insert: O(1)
• Get Lowest: O(1) (keep a pointer to the current lowest non-empty bucket)

---

Q2: Follow-up — partial fills (Partial Fill)

Design upgrade:

• introduce an Order with a quantity / remaining_quantity

Matching logic:

• quantity > 0 → update remaining and re-insert
• quantity == 0 → remove the order

Key point:

• don’t mutate heap nodes in-place
• use an Order abstraction and versioning + lazy deletion

---

Q3: How do you avoid race conditions under high concurrency?

Good discussion directions:

• Price-level locking (lock by price level instead of a global lock)
• Read/write separation (e.g., read replicas)
• Message queue (Pub/Sub) to decouple matching
• Optimistic concurrency / CAS mindset

---

📊 Solution Comparison

Feature	Heap + Lazy Deletion	Bucket + Queue	Balanced BST
Price range	unbounded	fixed range	unbounded
Insert	O(log n)	O(1)	O(log n)
Get Min	O(log n)	O(1)	O(log n)
Best for	general-purpose	HFT-like fixed ticks	range queries

---

💼 How oavoservice Helps You in Google VO

In Google VO / technical rounds, oavoservice provides:

• ✅ Clarification guidance (hidden constraints)
• ✅ Optimal algorithm choices (match interviewer expectations)
• ✅ Implementation support (clean, production-like code)
• ✅ Follow-up playbook (from DS/Algo to system design)
• ✅ Architecture extension (senior-level thinking)

---

📣 Need real interview questions and live support? Contact WeChat Coding0201 to get real questions.