Snapchat·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Snapchat SWE interview that was basically one big design question dressed up as a coding problem. They wanted a full LRU cache with per-entry TTL support and expected you to reason through the data structures and tradeoffs live, not just recite LeetCode 146.

Questions Asked (1)

Design a cache that supports LRU eviction and per-entry TTL. get(key) should return -1 if the key is expired or missing, and accessing a key should refresh its recency. put(key, value, ttl) should insert or update with a TTL and evict expired entries before falling back to LRU eviction when the cache is full. Walk through the data structures you'd use and the complexity of each operation.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with the standard hashmap plus doubly linked list setup for LRU and felt pretty solid until they pushed on the TTL piece.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a combined data structure: a hash map for O(1) key lookup and a doubly linked list for O(1) recency updates. Explain how to handle TTL by storing expiration timestamps and lazily or actively evicting expired entries, and analyze the time complexity of each operation.

Pro tip: Mention that you can use a min-heap or a timing wheel for efficient TTL expiration, but be prepared to discuss the trade-offs with the simpler lazy approach. Also, emphasize that you would handle concurrency with fine-grained locking or sharding in a real system.

1. Clarify requirements and constraints

Ask about expected cache size, read/write ratio, concurrency needs, and whether TTL is per-entry or global. Confirm that get should refresh recency and that expired entries should be evicted before LRU.

2. Choose core data structures

Use a hash map (dictionary) for O(1) key lookup and a doubly linked list to maintain recency order (most recently used at head). Each node stores key, value, expiration timestamp, and pointers.

3. Define operations and TTL handling

For get: check if key exists and not expired; if expired, remove and return -1; else move node to head and return value. For put: if key exists, update value and TTL and move to head; else insert new node at head, then evict expired entries (e.g., by scanning or using a min-heap) and if still over capacity, evict LRU tail.

4. Analyze complexity and trade-offs

Get and put are O(1) amortized with lazy expiration; active expiration may add O(log n) with a heap. Discuss trade-offs: lazy expiration is simpler but may leave expired entries until accessed; active expiration ensures timely removal but adds overhead.

5. Address concurrency and scalability

Mention that for thread safety, you can use a lock per shard or a read-write lock. For large scale, consider sharding the cache and using consistent hashing.

Key Points to Mention

Hash map + doubly linked list for O(1) get and put
Store expiration timestamp per entry and check on access
Eviction order: expired entries first, then LRU
Lazy vs. active expiration strategies and their trade-offs
Concurrency control (e.g., locks, sharding) for thread safety
Complexity: O(1) for get/put with lazy expiration, O(log n) with heap for active expiration

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