Katkat
Back

Track the First Unique Restaurant in a Stream

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to maintain stream uniqueness using a combination of a hash map and a doubly linked list to ensure constant-time operations.

Track the First Unique Restaurant

In the DoorDash delivery system, restaurants arrive in a stream represented by a sequence of integer IDs. As these IDs arrive, the system needs to maintain the identity of the "first unique restaurant"—the ID that appeared exactly once and was the earliest to do so. If no restaurant has appeared exactly once, the system should report -1.

Design a class RestaurantTracker with the following methods:

  1. add_restaurant(int id): Records a new restaurant arrival.
  2. get_first_unique(): Returns the integer ID of the first unique restaurant, or -1 if none exists.

Constraints

  • 1 <= id <= 10^6
  • Total number of calls to add_restaurant will not exceed 10^5.
  • Your operations should aim for O(1) average time complexity.

Examples

# Example 1
tracker = RestaurantTracker()
tracker.add_restaurant(101)
tracker.add_restaurant(202)
tracker.add_restaurant(101)
tracker.get_first_unique() # returns 202, since 101 has appeared twice

tracker.add_restaurant(303)
tracker.get_first_unique() # returns 202, since 202 was the first to appear once

Edge Cases

  • The stream contains only duplicates.
  • The stream is empty.
  • The first unique restaurant is eventually removed from uniqueness status by a later arrival.

Hints

Hint 1

Use a hash map to keep track of the frequency of each restaurant ID.

Hint 2

To retrieve the 'first' unique item efficiently, maintain an ordered collection (like a doubly linked list) of IDs that currently have a frequency of 1.

Hint 3

When an ID's frequency changes from 1 to 2, remove it from your ordered structure; if it's the first element, move to the next unique one.

Follow-up questions

  • How would you modify your solution if the system needed to support a 'remove_restaurant' operation for when a restaurant goes offline?
  • What are the space complexity trade-offs if you pre-allocate memory for the maximum possible ID range versus using a dynamic hash map?
  • If the stream is distributed across multiple servers, how would you architect a system to maintain a global first unique ID?