← Lyft Interview Insights

Lyft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

One coding round for a software engineer role at Lyft, about an hour long but reportedly wrappable in half that time. Just the one problem, no follow-ups, pretty low-pressure as these things go.

Questions Asked (1)

Q1

Design and implement an LRU cache with O(1) get and put operations, including eviction of the least recently used entry when capacity is exceeded.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Classic hashmap plus doubly linked list combo.

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. Walk through the design, implement the core methods, and discuss trade-offs and edge cases.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases, and that you would consider thread-safety if the cache is shared across threads.

1. Clarify requirements

Ask about capacity constraints, thread-safety, and expected operations. Confirm that get and put must be O(1) and that eviction is based on least recent use.

2. Choose data structures

Propose a hash map for O(1) key lookup and a doubly linked list to track usage order. Explain that the map stores key to node pointers, and the list maintains most-recently used at one end and least-recently used at the other.

3. Design operations

Detail how get moves the accessed node to the front (most recently used) and returns its value. For put, insert or update the node, move it to the front, and if capacity is exceeded, remove the tail node and delete its key from the map.

4. Implement with sentinels

Use dummy head and tail nodes to avoid null checks and simplify insertion/removal. Write clean code for addToFront, removeNode, and moveToFront helper methods.

5. Analyze and test

State that both operations are O(1) time and O(capacity) space. Discuss edge cases like capacity 0 or 1, updating existing keys, and concurrency if needed.

Key Points to Mention

  • Hash map provides O(1) access to nodes; doubly linked list maintains usage order.
  • Sentinel nodes (dummy head and tail) simplify edge cases and avoid null checks.
  • Get operation must move the accessed node to the most-recently-used position.
  • Put operation must handle both insertion and update, and evict the least-recently-used node when at capacity.
  • Time complexity: O(1) for both get and put; space complexity: O(capacity).
  • Consider thread-safety (e.g., using locks) if the cache will be accessed concurrently.

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