Katkat
Back

Implement Cache Eviction And Seat Assignment

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to combine a Least Recently Used (LRU) cache mechanism with a greedy strategy for geometric optimization in seat assignments.

Part 1: LRU Cache

Design a data structure SessionCache that stores user sessions with a fixed capacity n. If the cache reaches capacity, it must evict the least recently used entry.

put(key, value): Insert or update a value. Mark the key as most recently used. get(key): Return the value associated with the key and mark it as most recently used. If the key does not exist, return -1.

Part 2: Seat Assignment

In an Uber shuttle, seats are represented as points on a 1D line from 0 to L. You are given a list of already occupied seat positions. When a new passenger arrives, they want to choose a seat that maximizes the minimum distance to the nearest occupied seat to ensure social distancing. If there is a tie, choose the smallest coordinate.

Implement a function assign_seat(occupied_seats, L):

  • occupied_seats: A sorted list of integers.
  • L: The total length of the shuttle range (seats are integers 0 to L).
  • Return: The optimal integer seat position.

Examples

Example 1 (Cache): cache = SessionCache(2) cache.put(1, 100) cache.put(2, 200) cache.get(1) // returns 100 cache.put(3, 300) // evicts 2

Example 2 (Seats): assign_seat([0, 10], 10) // The gaps are (0, 10). The midpoint is 5. Return 5.

assign_seat([0, 5, 10], 10) // Gaps are 0-5 and 5-10. Midpoints are 2 and 7. Both distances are 2. Choose 2.

Constraints

  • n and L are up to 10^5.
  • All seat positions are within [0, L].

Hints

Hint 1

Use a hash map combined with a doubly linked list to achieve O(1) operations for the LRU cache.

Hint 2

For the seat assignment, calculate the distance between all adjacent occupied seats and check the distance between the ends (0 and L) and the first/last occupied seats.

Hint 3

The optimal seat will be either the midpoint of the largest gap between existing seats or at the boundaries if the boundary gaps are larger.

Follow-up questions

  • How would you modify the seat assignment if multiple passengers arrive at once and must maintain social distancing from each other as well as existing passengers?
  • If the cache needs to be thread-safe, what synchronization primitives would you use and how do they impact throughput?
  • How would the seat assignment change if the shuttle were a 2D grid instead of a 1D line?