Google WSE Interview: Follow-up Solutions

#GoogleWSE#Series#Intermediate

Google WSE Interview: Follow-up Solutions This document addresses the advanced follow-up questions for the Product Inventory System. --- Q1: What if multiple o

Google WSE Interview: Follow-up Solutions This document addresses the advanced follow-up questions for the Product Inventory System. --- Q1: What if multiple orders have the same price? The Solution In our implementation, we store pairs in the Min-Heap: { price, timestamp }. Even if two orders have the same price, they have different timestamps, so they occupy different entries in the heap. Coding Example Why it works: The Map this.orders still contains 2 - 100. When the "Reality Check" runs for t=1, it fails (because t=1 is gone from the Map). It then looks at the next entry t=2 and succeeds. --- Q2: What if the same timestamp is updated? The Solution When a timestamp is updated with a new price, the Map is updated instantly. A new entry is added to the Heap. The old price entry for that timestamp remains in the Heap as "garbage." Coding Example The "Reality Check" logic: 1. System looks at the heap top: {price: 50, timestamp: 10}. 2. It checks the Map: orders.get(10) is indeed 50. Success! 3. If later the price changes to $200, the $50 entry in the heap will be popped because it no longer matches the Map's truth of $200. --- Q3: How do you handle this in a Distributed System? The Challenge If you have millions of products and thousands of servers, a single memory-based object won't work. The Solution: Redis + Sharding 1. Storage: Use Redis Sorted Sets (ZSET). ZADD inventory <price <timestamp ZRANGE inventory 0 0 WITHSCORES (Gets the minimum). ZREM inventory <timestamp (Removes an order). 2. Sharding: Shard the data by ProductID. Requests for "iPhone 15" always go to Server Group A. Requests for "Pixel 8" always go to Server Group B. 3. Concurrency: Use Redis transactions or Lua scripts to ensure price updates and map updates are atomic. Distributed Code (Conceptual Lua Script) Why Redis ZSET is Perfect Redis ZSETs are internally implemented using Skip Lists. They provide $O(\log N)$ for both insertion and retrieval