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.

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 ```

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.

Read the full XPeng Data Engineer interview experience this question came from

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.

Hints

  1. Use a hash map to store the current value for each key.
  2. 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.

Loading coding console...