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 Technical Screen rounds at XPeng.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at XPeng during technical interviews.

Build a Least-Recently-Used Store | XPeng Coding Question

Build a Least-Recently-Used Store

Company: XPeng

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory key-value store with least-recently-used eviction. The store is initialized with a positive integer `capacity` and supports two operations: - `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key makes it the most recently used key. - `put(key, value)`: Insert or update `key` with `value`. Updating an existing key also makes it the most recently used key. If inserting a new key causes the number of keys to exceed `capacity`, evict the least recently used key. For this interview variant, you do not need to use a linked list. An implementation based on a hash map plus a dynamic array/list is acceptable, even if moving keys in the list costs linear time. Example: ```text store = Store(capacity = 2) put(1, 10) put(2, 20) get(1) -> 10 # key 1 becomes most recently used put(3, 30) # evicts key 2 get(2) -> -1 get(3) -> 30 put(1, 15) # updates key 1 and makes it most recently used get(1) -> 15 ```

Quick Answer: This question evaluates understanding of caching and eviction policies and practical proficiency with data structures such as hash tables and ordered collections for tracking and updating recency.

Implement a simulator for an in-memory key-value store with least-recently-used (LRU) eviction. The store starts empty and has a fixed positive integer capacity. You are given the commands as three parallel arrays: `operations`, `keys`, and `values`. For each index `i`: - If `operations[i] == "put"`, insert or update `keys[i]` with `values[i]`. - If `operations[i] == "get"`, return the current value for `keys[i]`, or `-1` if the key does not exist. In this case `values[i]` should be ignored. LRU rules: - A successful `get` makes that key the most recently used. - A `put` on either a new key or an existing key makes that key the most recently used. - If inserting a new key would make the number of stored keys exceed `capacity`, evict the least recently used key first. Return a list containing the outputs of all `get` operations in the order they occur. For this interview variant, a hash map plus a list of key usage order is acceptable, even if moving keys in the list takes linear time.

Constraints

1 <= capacity <= 1000
0 <= len(operations) <= 2000
len(operations) == len(keys) == len(values)
`operations[i]` is either "get" or "put"
-10^9 <= keys[i], values[i] <= 10^9

Examples

Input: (2, ["put", "put", "get", "put", "get", "get", "put", "get"], [1, 2, 1, 3, 2, 3, 1, 1], [10, 20, 0, 30, 0, 0, 15, 0])

Expected Output: [10, -1, 30, 15]

Explanation: After `get(1)`, key 1 becomes most recent, so inserting key 3 evicts key 2. Later, updating key 1 changes its value to 15 and keeps it most recent.

Input: (1, ["put", "put", "get", "put", "get", "get"], [1, 2, 1, 2, 1, 2], [5, 6, 0, 7, 0, 0])

Expected Output: [-1, -1, 7]

Explanation: With capacity 1, inserting key 2 evicts key 1. Updating key 2 does not evict anything. The two `get` calls for key 1 return -1, and `get(2)` returns 7.

Input: (2, ["put", "put", "get", "put", "get", "get"], [-1, 5, -1, 6, 5, 6], [-10, 50, 0, 60, 0, 0])

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

Explanation: Negative keys and values are allowed. Accessing key -1 makes it most recent, so inserting key 6 evicts key 5.

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

Expected Output: [3, -1, 4]

Explanation: Updating key 1 makes it most recent, so when key 3 is inserted, key 2 is evicted. The later gets confirm that key 1 remains with value 3, key 2 is gone, and key 3 exists.

Input: (3, [], [], [])

Expected Output: []

Explanation: No operations means there are no `get` results to return.

Hints

Use a hash map to store the current value for each key.
Keep a list of keys ordered from least recently used to most recently used. Whenever a key is accessed or updated, move it to the end.

Quick Overview

This question evaluates understanding of caching and eviction policies and practical proficiency with data structures such as hash tables and ordered collections for tracking and updating recency.