← NVIDIA Interview Insights

NVIDIA·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

NVIDIA SWE interview with a classic LRU cache problem in C, though they said C++ was fine. Pretty straightforward if you've done it before, but building everything from scratch with no stdlib shortcuts kept things honest.

Questions Asked (1)

Q1

Design and implement an LRU cache from scratch supporting get and put operations in O(1) average time. You must build the doubly linked list and hashmap yourself without relying on any built-in LRU containers.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

The C constraint was the part that tripped me up mentally at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then explain the design using a hashmap for O(1) access and a doubly linked list for O(1) recency updates. Implement the core operations step-by-step, handling edge cases like capacity 0 and updating existing keys, and analyze time/space complexity.

Pro tip: Use dummy head and tail nodes to simplify edge cases and avoid null checks, and mention thread-safety considerations for production systems, showing awareness beyond the basic algorithm.

1. Clarify Requirements

Confirm expected operations (get, put), capacity constraints, and behavior for edge cases like capacity 0 or updating existing keys.

2. Design Data Structures

Explain using a hashmap mapping keys to nodes and a doubly linked list to track usage order, with dummy head/tail for simplicity.

3. Implement Core Operations

Detail get: check map, move node to front if exists, return value or -1. Detail put: insert or update, move to front, evict least recently used if over capacity.

4. Handle Edge Cases

Address capacity 0, updating existing keys, and ensuring eviction removes both from list and map.

5. Analyze Complexity

State O(1) average time for both operations and O(capacity) space, and discuss potential optimizations or thread-safety if needed.

Key Points to Mention

  • Hashmap provides O(1) average lookup, doubly linked list provides O(1) insertion/deletion for recency updates.
  • Use dummy head and tail nodes to avoid null checks and simplify edge cases.
  • Eviction policy: remove the node just before the tail (least recently used) and delete its entry from the hashmap.
  • Updating an existing key should update the value and move the node to the front (most recently used).
  • Time complexity: O(1) average for get and put; space complexity: O(capacity).
  • Consider thread-safety for concurrent access, e.g., using locks or concurrent data structures, if relevant to production.

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