Apple·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Apple SWE interview with a classic LRU cache design problem. Not the hardest thing I've ever been asked, but the O(1) constraint is where people trip up if they haven't seen it before.

Questions Asked (1)

Design an LRU cache class supporting get and put operations, both running in O(1) average time, with a fixed capacity that evicts the least recently used entry when full.

Algorithms & Data StructuresSystem Design

Author's notes

I knew the answer because I'd drilled this one before, but I still fumbled explaining WHY a doubly linked list over a singly linked list.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a hash map combined with a doubly linked list to achieve O(1) operations. Explain how the hash map provides direct access to nodes while the linked list maintains usage order, and walk through the get and put logic including eviction.

Pro tip: Mention thread-safety considerations and how you would handle concurrency, as Apple often values production-ready solutions. Also, discuss potential optimizations like using a sentinel head/tail to simplify edge cases.

1. Clarify Requirements

Ask about expected capacity, thread-safety, and whether null values are allowed. Confirm that both get and put must be O(1) average time.

2. Choose Data Structures

Propose a hash map for O(1) access and a doubly linked list to track usage order. Explain why a singly linked list or array would not meet the O(1) requirement for both operations.

3. Design the Node and Cache

Define a node with key, value, prev, and next pointers. The cache holds a map from key to node, a head and tail sentinel, and capacity. Describe how sentinels simplify insertion and removal.

4. Implement get and put

For get: if key exists, move node to front and return value; else return -1. For put: if key exists, update value and move to front; else create node, add to front, and if over capacity, remove tail node and delete from map.

5. Analyze Complexity and Edge Cases

State that both operations are O(1) average time due to hash map and linked list operations. Discuss edge cases like capacity 1, updating existing key, and eviction order.

Key Points to Mention

Hash map provides O(1) average lookup, while doubly linked list allows O(1) removal and insertion.
Use sentinel head and tail nodes to avoid null checks and simplify edge cases.
On get, move the accessed node to the front (most recently used).
On put, if capacity is exceeded, remove the node just before the tail (least recently used) and delete its key from the map.
Time complexity: O(1) average for both get and put; space complexity: O(capacity).
Consider thread-safety: mention that a simple implementation is not thread-safe and discuss using locks or concurrent data structures if needed.

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