How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement Cache Eviction And Seat Assignment

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following two independent coding tasks. ### Task 1: Implement a least-recently-used cache Design a class `LRUCache` with the following methods: - `LRUCache(int capacity)`: Initialize the cache with a positive capacity. - `int get(int key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key makes it the most recently used key. - `void put(int key, int value)`: Insert or update `key` with `value`. If the cache exceeds capacity, evict the least recently used key. Both `get` and `put` should run in `O(1)` average time. ### Task 2: Assign seats to maximize distance Design a class `AssignSeat` for assigning employees to seats in a row. There are `n` seats numbered from `0` to `n - 1`. Each call to `assign()` seats one new employee. Once an employee is assigned a seat, they cannot be moved and the seat is never freed. On each call, choose an empty seat that maximizes the distance to the closest occupied seat. If there are multiple optimal seats, returning any of them is acceptable. If no seats are occupied yet, return seat `0`. Implement: ```python class AssignSeat: def __init__(self, n: int): pass def assign(self) -> int: pass ``` Example: ```python seats = AssignSeat(10) seats.assign() # returns 0 seats.assign() # returns 9 seats.assign() # returns 4 or 5 ```

Quick Answer: This question evaluates understanding of data structure design and algorithmic reasoning, covering cache eviction policies (least-recently-used) and seat-assignment strategies that maximize minimum distance.

Part 1: Simulate an LRU Cache

You are given a cache capacity and a sequence of operations to run on an LRU (least recently used) cache. Each operation is either ('put', key, value) or ('get', key). Rules: - 'get' returns the value for the key if it exists, otherwise -1. - Any successful 'get' makes that key the most recently used. - 'put' inserts or updates a key and makes it the most recently used. - If inserting a new key would make the cache exceed capacity, evict the least recently used key. Write a function that processes all operations and returns the results of every 'get' operation in order.

Constraints

1 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation is either ('put', key, value) or ('get', key)
-10^9 <= key, value <= 10^9

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [1, -1, -1, 3, 4]

Explanation: After accessing key 1, key 2 becomes least recently used and is evicted when key 3 is inserted. Later key 1 is evicted when key 4 is inserted.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])

Expected Output: [10, -1, 3]

Explanation: Updating key 1 also refreshes its recency, so key 2 is evicted when key 3 is inserted.

Input: (1, [('get', 5), ('put', 5, 50), ('get', 5), ('put', 6, 60), ('get', 5), ('get', 6)])

Expected Output: [-1, 50, -1, 60]

Explanation: With capacity 1, every new key replaces the previous one.

Input: (3, [])

Expected Output: []

Explanation: No operations means no 'get' results.

Hints

Use a hash map so you can find a key's node in O(1) time.
You also need a structure that can remove and reinsert nodes in O(1) when their recency changes.

Part 2: Assign Seats to Maximize Distance

There are n seats numbered from 0 to n - 1 in a row. Employees arrive one by one, and each employee must be assigned an empty seat. For each new employee: - Choose an empty seat that maximizes the distance to the closest occupied seat. - If multiple seats are equally good, choose the smallest seat index. - If no seats are occupied yet, the first employee must take seat 0. Write a function that simulates the first k assignments and returns the chosen seat indices in order.

Constraints

1 <= n <= 2 * 10^5
0 <= k <= n
Seats are never freed
If multiple optimal seats exist, choose the smallest index

Examples

Input: (10, 4)

Expected Output: [0, 9, 4, 2]

Explanation: The first seats chosen are 0, then 9, then 4. After that, seats 2 and 6 are tied, so choose the smaller index 2.

Input: (1, 1)

Expected Output: [0]

Explanation: Only one seat exists.

Input: (5, 5)

Expected Output: [0, 4, 2, 1, 3]

Explanation: The row eventually fills while always taking the seat with maximum nearest-neighbor distance.

Input: (7, 0)

Expected Output: []

Explanation: No assignments requested.

Hints

Think of the empty seats as intervals between already occupied seats.
A priority queue can help you always pick the interval whose best seat gives the largest distance; break ties using the seat index.

Quick Overview

This question evaluates understanding of data structure design and algorithmic reasoning, covering cache eviction policies (least-recently-used) and seat-assignment strategies that maximize minimum distance.