Implement LRU cache and copy random list
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Coding questions (two parts)
### Part A — Deep copy a linked list with random pointers
You are given the head of a singly linked list where each node has:
- `next`: pointer to the next node
- `random`: pointer to any node in the list or `null`
Return a **deep copy** of the list (all new nodes), preserving both `next` and `random` relationships.
**Goal:** The copied list must not share any nodes with the original.
---
### Part B — Design an LRU cache
Design a data structure `LRUCache` that supports:
- `get(key)`: return the value for `key` if present, else `-1`
- `put(key, value)`: insert or update the value
The cache has a fixed capacity `C`. When inserting causes the cache to exceed `C`, it must evict the **least recently used** item.
### Requirements
- Average time complexity: **O(1)** for both `get` and `put`
- Keys are hashable (e.g., integers/strings)
Quick Answer: This question evaluates competency in data-structure design, pointer and memory management, and hashing-based eviction policies by combining a deep-copy of a linked list with random pointers and an LRU cache requiring O(1) operations, and it belongs to the Coding & Algorithms domain.