LinkedIn·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

LinkedIn SWE interview with a system design coding problem around a weighted LRU cache. Pretty meaty for a single session but the problem was well-scoped once I understood what 'weight' actually meant in this context.

Questions Asked (1)

Design and implement a cache where each entry has a weight, the cache has a fixed total weight capacity (not a fixed item count), and eviction follows LRU order. get and put should both run in O(1) average time.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I spent the first few minutes confused about why weight mattered at all.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements: fixed total weight capacity, per-entry weight, LRU eviction, and O(1) average get/put. Then propose a hash map for O(1) access combined with a doubly linked list to maintain LRU order, and explain how to track total weight and evict from the tail when capacity is exceeded. Finally, discuss edge cases and trade-offs.

Pro tip: Mention that you would handle entries heavier than the total capacity by rejecting them, and that you'd consider thread-safety if the cache is shared, showing production awareness.

1. Clarify requirements and constraints

Confirm that capacity is total weight, each entry has a weight, eviction is LRU, and get/put must be O(1) average. Ask about concurrency, weight updates, and behavior for oversized entries.

2. Choose data structures

Use a hash map for O(1) key lookup and a doubly linked list to maintain access order. Store weight and value in each node, and keep a running total weight.

3. Define get and put operations

For get: if key exists, move node to front (most recently used) and return value. For put: if key exists, update value and weight, adjust total weight, and move to front; if new, create node, add to front, update total weight, and evict from tail while total weight exceeds capacity.

4. Handle edge cases and eviction

If a new entry's weight exceeds total capacity, reject it. During eviction, remove nodes from the tail until total weight <= capacity. Ensure the hash map and list stay in sync.

5. Analyze complexity and trade-offs

Explain that both get and put are O(1) average due to hash map and linked list operations. Discuss trade-offs: memory overhead of pointers, potential need for locking in concurrent scenarios, and alternative eviction policies.

Key Points to Mention

Hash map provides O(1) average key lookup.
Doubly linked list maintains LRU order with O(1) node moves and removals.
Track total weight to know when to evict; evict from the tail (least recently used).
Handle weight updates on existing keys by adjusting total weight and moving node to front.
Reject entries with weight greater than total capacity to avoid infinite eviction loop.
Consider thread-safety (e.g., using locks or concurrent data structures) if the cache is shared.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.