Full-stack engineer data structures interview questions

As asked

Implement a least-recently-used cache that supports get(key) and put(key, value) both in O(1) time. When the cache is full and a new key is inserted, evict the least recently used entry. Do not use any built-in ordered dictionary types.

Sample answer outline

The classic solution combines a hashmap for O(1) lookup with a doubly linked list to track recency order. On get, move the node to the front. On put, add to front; if over capacity, remove from the tail and delete from the map. A strong answer walks through the dummy head and tail sentinel trick to avoid null checks, then discusses thread-safety if the cache is shared across goroutines or threads.

Reference implementation (python)

class Node:
    def __init__(self, k=0, v=0):
        self.key, self.val = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            self._remove(self.cache[key])
            self._insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self._insert(self.cache[key])
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Expect these follow-ups

• How would you make this thread-safe for concurrent reads and writes?
• Can you extend this to support a TTL on each entry without changing the time complexity of get and put?

As asked

Implement an LRU (Least Recently Used) cache that supports get and put operations, both in O(1) time. Describe your data structure choice before writing any code.

Sample answer outline

The standard answer uses a doubly linked list combined with a hash map. The hash map provides O(1) lookup by key, and the doubly linked list maintains recency order so eviction from the tail is O(1). The candidate should explain why a singly linked list does not work (tail removal requires O(n) traversal), implement the Node class, and handle the edge cases of get on a missing key and put when at capacity. Amazon interviewers often push on the sentinel/dummy head-tail pattern for cleaner code.

Reference implementation (python)

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> Node
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

Expect these follow-ups

• How would you make this thread-safe?
• How would you extend this to support expiry times per key?

As asked

Given the root of a binary tree, return its level-order traversal as a list of lists, where each inner list contains the node values at that depth from left to right.

Sample answer outline

Standard BFS using a queue. At each iteration, pop the entire current level, record values, and enqueue all children. The key insight is measuring the queue length at the start of each level iteration to separate levels correctly. Time and space are both O(n). A strong candidate also mentions the recursive DFS alternative (tracking depth as a parameter) and explains why BFS is more natural here. Edge cases: null root returns an empty list.

Reference implementation (python)

from collections import deque

def level_order(root) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Expect these follow-ups

• How would you do a zigzag level-order traversal (left-to-right for odd levels, right-to-left for even)?
• How would you find the maximum width of the tree (widest level by node count)?

As asked

Implement an LRU cache that supports get and put in O(1) time. Explain why you chose the data structures you did.

Sample answer outline

A strong answer uses a doubly linked list for O(1) insertion and removal at both ends plus a hash map from key to node for O(1) lookup. The candidate should clearly explain the sentinel head and tail pattern to avoid null checks, and handle the eviction path: when capacity is hit, remove the tail node and delete its key from the map. They should mention thread safety as a follow-up concern since AMD's software often runs in multi-threaded contexts.

Reference implementation (python)

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

Expect these follow-ups

• How would you make this thread-safe for concurrent reads and occasional writes?
• How would you extend this to support expiration time on cached entries?

As asked

Implement an LRU cache with get and put operations, both in O(1) time. Walk me through your data structure choice before writing any code.

Sample answer outline

The classic solution combines a hash map for O(1) lookup with a doubly linked list to maintain access order. The hash map stores key to node mappings; the linked list has a sentinel head (most recently used) and tail (least recently used). On get, move the node to the head. On put, insert at head; if capacity is exceeded, remove the tail node and its hash map entry. The candidate should explain why a singly linked list does not work (deletion requires the previous node) and why an array or heap does not achieve O(1) for both operations.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> node
        # sentinel head (MRU side) and tail (LRU side)
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self._move_to_front(self.cache[key])
        return self.cache[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_front(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._insert_front(node)
            if len(self.cache) > self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

Expect these follow-ups

• How would you make this thread-safe for concurrent access?
• How does Python's OrderedDict give you an LRU cache almost for free?

As asked

Jira's issue-view caches recently loaded issues to avoid repeated API calls. Implement an LRU (Least Recently Used) cache that supports get(key) and put(key, value) in O(1) time. If the cache is at capacity when put is called, evict the least recently used entry before inserting the new one.

Sample answer outline

Use a doubly linked list plus a hash map. The map gives O(1) key lookup; the list maintains access order with head as most recent and tail as least recent. On get, move the node to head. On put, add to head; if at capacity, remove the tail and delete its key from the map. The candidate should handle the edge case where put updates an existing key.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> node
        self.head = Node(0, 0)  # most recent
        self.tail = Node(0, 0)  # least recent
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key not in self.cache:
            return -1
        self._move_to_head(self.cache[key])
        return self.cache[key].val

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.cap:
                tail = self._remove_tail()
                del self.cache[tail.key]

Expect these follow-ups

• How would you make this implementation thread-safe for concurrent access?
• How would you extend this to support a TTL per key?

As asked

Implement an LRU cache that supports get and put in O(1) time. The cache has a fixed capacity. When it is full and you insert a new key, you evict the least recently used entry. Any get or put on an existing key counts as a use.

Sample answer outline

The correct implementation combines a doubly linked list to maintain access order with a hash map from key to list node for O(1) lookup. The candidate should demonstrate adding new nodes at the head and removing the tail on eviction. In Python, OrderedDict is acceptable but the candidate should explain the underlying structure. Common mistakes are forgetting to update the map on eviction, or using a singly linked list.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> node
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self._move_to_front(self.cache[key])
        return self.cache[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key].val = value
            self._move_to_front(self.cache[key])
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._insert(node)
            if len(self.cache) > self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

Expect these follow-ups

• How would you make this LRU cache thread-safe?
• How would you extend it to an LFU (least frequently used) cache?

As asked

Design a data structure that supports two operations: addNum(int num) adds a number to the data stream, and findMedian() returns the median of all numbers added so far. What is the time complexity of each operation?

Sample answer outline

The classic solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping them balanced in size. addNum is O(log n) and findMedian is O(1). The candidate should explain the balancing logic: after each insert, if the heaps differ in size by more than 1, move the top element from the larger heap to the smaller. Edge cases: empty stream, single element, even versus odd total count.

Expect these follow-ups

• How would you find the median of a sliding window of the last k elements?
• How does your solution handle integer overflow if values can be very large?

As asked

You are given the root of a Figma document node tree where each node has a type (FRAME, GROUP, TEXT, RECTANGLE, etc.) and optionally a list of children. Write a function that returns all TEXT nodes whose characters field matches a given regular expression.

Sample answer outline

A strong answer uses BFS or DFS to traverse the tree, checks the type field before accessing characters, and handles missing or empty children gracefully without throwing. The candidate should note that DFS via recursion risks stack overflow on pathologically deep trees and offer an iterative BFS alternative. A great answer also considers the case where children arrays are lazily loaded and how you would handle async fetching in a real Figma plugin context.

Reference implementation (typescript)

interface FigmaNode {
  id: string;
  type: string;
  characters?: string;
  children?: FigmaNode[];
}

function findTextNodes(
  root: FigmaNode,
  pattern: RegExp
): FigmaNode[] {
  // your implementation
}

Expect these follow-ups

• How would you modify this to also return the full ancestor path from the root to each matching node?
• If you needed to replace the matched text in-place, how would you do that safely without corrupting the tree?

As asked

Figma's canvas can be much larger than the screen. The renderer divides the canvas into tiles and caches rendered tile bitmaps. Implement an LRU cache with a fixed capacity that evicts the least-recently-used tile when full. The cache must support O(1) get and O(1) put.

Sample answer outline

A strong answer uses a doubly linked list for O(1) removal from anywhere combined with a hash map from key to list node for O(1) lookup. On get, the node is moved to the head of the list. On put, a new node is added to the head; if capacity is exceeded, the tail node is evicted and removed from the map. The candidate should handle the case where a put replaces an existing key (update the value and move to head, do not evict). A great answer notes that in a real Figma tile cache, the key would be a tile coordinate and the value a GPU texture handle, and eviction should also free the GPU memory.

Reference implementation (typescript)

class LRUCache<K, V> {
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    // O(1)
  }

  put(key: K, value: V): void {
    // O(1), evict LRU on overflow
  }
}

Expect these follow-ups

• How would you make this cache thread-safe for use across web workers?
• How would you add a TTL (time-to-live) so that tiles from a stale file version are automatically expired?

As asked

Design and implement a least-recently-used cache class that supports get(key) and put(key, value) operations, both in O(1) time. The cache has a fixed capacity; when it's full, it should evict the least recently used entry. Code it up from scratch.

Sample answer outline

A doubly linked list combined with a hash map achieves O(1) for both operations. The map stores key-to-node pointers; the list tracks access order with head as most recent. Strong candidates handle the dummy head/tail trick to simplify edge cases, and correctly update on both get and put.

Reference implementation (typescript)

class LRUCache {
  private capacity: number;
  private map: Map<number, { key: number; val: number; prev: any; next: any }>;
  private head: any;
  private tail: any;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = {};
    this.tail = {};
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  // insert/remove helpers + get/put omitted for brevity
}

Expect these follow-ups

• How would you make this thread-safe for concurrent reads and writes?
• Could you implement an LFU cache with the same O(1) constraint? What additional data structure would you need?

As asked

Design a data structure that behaves like an LRU cache: it supports get(key) and put(key, value) operations, both in O(1) time, with a fixed capacity. When the cache is full and a new key is inserted, evict the least recently used entry. Implement it, then walk me through the time and space complexity.

Sample answer outline

A strong answer uses a doubly linked list combined with a hash map: the list maintains recency order, and the map provides O(1) key lookup to a node in the list. The candidate should implement get (move to front) and put (add to front, evict tail if over capacity) cleanly, handle edge cases like capacity 1 and repeated puts of the same key, and explain why a singly linked list would not work for O(1) deletion.

Reference implementation (python)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

Expect these follow-ups

• How would you make this thread-safe?
• What if you needed an LFU cache instead of LRU?

As asked

IBM coding rounds frequently include linked list problems to test fundamental data structure knowledge. Write a Java function that reverses a singly linked list in place and returns the new head. Then explain what you would do differently if the list had 10 million nodes and you needed to avoid stack overflow.

Sample answer outline

The iterative solution uses three pointers (prev, current, next) and runs in O(n) time with O(1) space. For 10 million nodes the iterative version is already safe since it avoids recursion; a recursive solution would blow the stack. Candidates should explain why the recursive solution fails and confirm the iterative one handles arbitrary length.

Reference implementation (java)

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Expect these follow-ups

• How would you reverse only a sublist from position m to n?
• What is the space complexity of the recursive version and why?

As asked

IBM technical interviews often combine data structure design with implementation. Design and implement an LRU (Least Recently Used) cache class in Java that supports get(key) and put(key, value) in O(1) time. Explain your data structure choices before you write any code, as IBM interviewers weight the upfront reasoning as heavily as the implementation.

Sample answer outline

The canonical solution combines a doubly linked list (to maintain access order with O(1) insert and delete at any position) and a HashMap (for O(1) lookup by key). On get, the node moves to the front. On put, if capacity is exceeded the tail node is removed. Candidates should walk through both operations before coding and handle edge cases like single-element capacity.

Reference implementation (java)

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail;

    LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    // get, put, addToFront, remove helpers omitted for brevity
}

Expect these follow-ups

• How would you make this thread-safe without using synchronized on every method?
• Java's LinkedHashMap already gives you LRU behavior. When would you roll your own?

As asked

Cache management is central to Intel's CPU microarchitecture and to many software systems built on Intel hardware. Implement a Least Recently Used cache that supports get and put operations both in O(1) time. The cache has a fixed capacity and should evict the least recently used entry when full. After your implementation, explain how you would adapt the eviction policy for a hardware prefetcher hint scenario where recently used is not always the best predictor of future use.

Sample answer outline

A correct answer uses a hashmap for O(1) lookup combined with a doubly linked list to maintain recency order. The head of the list holds the most recently used entry and the tail holds the least recently used. On each get or put, the accessed node is moved to the head. On eviction, the tail node is removed and its key is deleted from the hashmap. The candidate should discuss Python's OrderedDict as a shortcut but be ready to implement from scratch.

Reference implementation (python)

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}
        self.head, self.tail = Node(0,0), Node(0,0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

Expect these follow-ups

• How would you make this thread-safe for concurrent access without a global lock?
• How would you extend this to support a TTL per key?

As asked

Implement an LRU (Least Recently Used) cache that supports get(key) and put(key, value) both in O(1) time. The cache has a fixed capacity; when it is full, it should evict the least recently used item before inserting a new one.

Sample answer outline

The candidate should combine a hash map (for O(1) lookup) with a doubly linked list (for O(1) move-to-front and eviction from tail). They should handle the edge cases: capacity of one, get on a missing key, put that updates an existing key. A strong answer also discusses thread-safety considerations and when you would use an off-the-shelf LRU like Guava or Caffeine instead.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> node
        # sentinel head and tail
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            self._move_to_front(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key].val = value
            self._move_to_front(self.cache[key])
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._insert_front(node)
            if len(self.cache) > self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

Expect these follow-ups

• How would you make this thread-safe in a multi-threaded environment?
• What is the difference between LRU and LFU eviction, and when would you choose each?

As asked

Lyft's driver profile service caches frequently accessed driver metadata to reduce database load. Implement an LRU (Least Recently Used) cache with O(1) get and put operations. The cache should have a fixed capacity, and when it is full, it should evict the least recently used item before inserting a new one.

Sample answer outline

Strong answers use a doubly linked list plus a hash map: the list maintains insertion/access order and the map gives O(1) lookup. On get, move the node to the front. On put, if the key exists update it; if at capacity, remove the tail. They handle the key detail that 'put' on an existing key should update and move to front, not evict.

Reference implementation (python)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

Expect these follow-ups

• How would you make this thread-safe for concurrent access?
• How would you extend this to an LFU cache (least frequently used)?

As asked

You have k sorted linked lists. Merge them into one sorted linked list and return it. What is the most efficient approach you can think of, and what are the time and space complexities?

Sample answer outline

The optimal solution uses a min-heap of size k, pushing the head of each list, then repeatedly extracting the minimum and pushing the next node from that list. Time complexity is O(N log k) where N is total nodes, space is O(k) for the heap. The candidate should explain why naive pairwise merging is O(kN) and worse.

Reference implementation (python)

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def __lt__(self, other):
        return self.val < other.val

def mergeKLists(lists):
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, node)
    dummy = cur = ListNode(0)
    while heap:
        node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, node.next)
    return dummy.next

Expect these follow-ups

• How does your solution behave when one of the k lists is extremely long and the others are short?
• Implement this without a heap using divide and conquer.

As asked

Design and implement a Least Recently Used cache that supports get(key) and put(key, value) operations, both in O(1) time. The cache has a fixed capacity, and when it is full, the least recently used entry should be evicted. Walk me through your data structure choices before you write any code.

Sample answer outline

The candidate should choose a doubly-linked list combined with a hash map. The list tracks recency (head = most recent, tail = least recent) and the map gives O(1) access to any node. Strong candidates explain why a singly-linked list does not work for O(1) deletion, implement dummy head/tail sentinels, and handle the edge case where a key already exists in put. Microsoft often extends this to ask about thread safety.

Reference implementation (python)

class Node:
    def __init__(self, k=0, v=0):
        self.key, self.val = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

Expect these follow-ups

• How would you make this cache thread-safe for concurrent reads and writes?
• How would you extend this to an LFU (Least Frequently Used) cache?

As asked

Given the root of a binary tree, return its nodes' values grouped by level, from left to right. So the output is a list of lists. What traversal strategy do you use and why? Then write clean, runnable code.

Sample answer outline

The candidate should choose BFS with a queue, not DFS. A strong answer explains why BFS is natural here, uses a deque for efficiency, and snapshots the queue length at the start of each level iteration so they know how many nodes belong to that level. Microsoft interviewers commonly ask a follow-up about zigzag or right-side-view after this passes.

Reference implementation (python)

from collections import deque

def level_order(root):
    if not root:
        return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

Expect these follow-ups

• Now return only the rightmost node from each level (right side view).
• How would you do this if the tree could have up to 10^6 nodes?

As asked

Notion's server caches recently fetched block trees in memory to speed up page loads. Implement a fixed-capacity LRU (Least Recently Used) cache that supports O(1) get(key) and put(key, value) operations. When the cache is full and a new key is inserted, evict the least recently used entry. Show me the data structure you would use and code it up.

Sample answer outline

The canonical solution uses a doubly linked list (for O(1) removal and reordering) combined with a hash map from key to list node (for O(1) lookup). The head of the list tracks the most recently used item and the tail tracks the least recently used. On get, the node is moved to the head. On put, if the key exists it is updated and moved to head; if the cache is full, the tail node is evicted before inserting. Strong candidates also discuss thread safety and whether a move-to-front on every read is acceptable in high-throughput scenarios where many users open the same shared page simultaneously.

Reference implementation (typescript)

class LRUCache {
  private capacity: number;
  // your fields here

  constructor(capacity: number) {
    this.capacity = capacity;
    // initialize
  }

  get(key: number): number {
    // return value or -1 if not found
  }

  put(key: number, value: number): void {
    // insert or update, evict if needed
  }
}

Expect these follow-ups

• How would you make this thread-safe for concurrent reads and writes in a Node.js context?
• If reads are much more frequent than writes, what optimization would you consider?

As asked

Implement an LRU cache that supports get and put in O(1) time. The cache has a fixed capacity. When full, it evicts the least recently used entry before inserting a new one.

Sample answer outline

A strong answer uses a doubly linked list plus a hash map. The list maintains order by recency (most recent at head, least recent at tail). The hash map stores key to list node for O(1) lookup. On get, move the accessed node to the head. On put, if the key exists update and move to head; if not, insert at head and remove the tail if at capacity. The candidate should handle the edge case where capacity is 0 or 1, and discuss why a singly linked list is not sufficient without a tail pointer. In Python, OrderedDict achieves this with move_to_end but the interviewer may want the explicit implementation.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> node
        self.head, self.tail = Node(0,0), Node(0,0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key):
        if key in self.cache:
            self._move_to_front(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key, val):
        if key in self.cache:
            self.cache[key].val = val
            self._move_to_front(self.cache[key])
        else:
            node = Node(key, val)
            self.cache[key] = node
            self._insert_front(node)
            if len(self.cache) > self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

Expect these follow-ups

• How would you make this thread-safe for concurrent access?
• How would you extend this to an LFU cache?

As asked

Oracle Cloud services rely on in-memory caching for session state and metadata lookups. Design and implement a Least Recently Used cache that supports get(key) and put(key, value) operations, both in O(1) time. The cache has a fixed capacity and evicts the least recently used entry when full. Walk me through your data structure choice before writing any code.

Sample answer outline

The correct approach combines a doubly-linked list (to support O(1) move-to-front and O(1) eviction from tail) with a hash map (key to list node pointer for O(1) lookup). The candidate should draw or describe the structure before coding, handle the edge cases of capacity 1 and updating an existing key, and confirm that both operations are O(1) amortized.

Reference implementation (typescript)

class LRUCache {
  private capacity: number;
  private map: Map<number, { key: number; val: number; prev: any; next: any }>;
  private head: any;
  private tail: any;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = {}; this.tail = {};
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  // get, put, removeNode, addToFront methods here
}

Expect these follow-ups

• How would you make this cache thread-safe in a multi-threaded Java application?
• What changes if you need to support expiry of entries after a fixed TTL?

As asked

Tree traversals appear regularly in Oracle coding rounds because they exercise both recursion and iterative BFS, patterns common in Oracle's internal tooling. Given the root of a binary tree, return a list where each element is a list of node values at that level, from left to right. Explain your approach, write the code, and state the time and space complexity.

Sample answer outline

BFS using a queue is the natural fit. At each step, record the current queue length (nodes at the current level), dequeue that many nodes, collect their values, and enqueue their children. Time and space are both O(n). The candidate should also mention the DFS recursive alternative using a depth parameter.

Reference implementation (typescript)

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level: number[] = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Expect these follow-ups

• How would you print the tree in zigzag order, alternating left-to-right and right-to-left per level?
• How does your solution change if the tree can have up to 10 million nodes?

As asked

Implement a cache that evicts entries both when capacity is exceeded (LRU policy) and when an entry's time-to-live has expired. All operations should be O(1) average. How would you handle the expiry check: on every get, lazily, or with a background thread?

Sample answer outline

The core LRU is a doubly linked list plus a hash map. TTL adds a deadline field per node. On get, check if the entry has expired and treat it as a cache miss. For lazy expiry this is sufficient. A background thread can sweep expired entries to reclaim memory. The candidate should discuss the thread-safety implications of the background sweep and whether the use case requires a precise TTL or an approximate one.

Reference implementation (python)

from collections import OrderedDict
import time

class LRUCacheWithTTL:
    def __init__(self, capacity: int, ttl_seconds: float):
        self.cap = capacity
        self.ttl = ttl_seconds
        self.cache: OrderedDict[str, tuple] = OrderedDict()  # key -> (value, expiry)

    def get(self, key: str):
        if key not in self.cache:
            return None
        value, expiry = self.cache[key]
        if time.monotonic() > expiry:
            del self.cache[key]
            return None
        self.cache.move_to_end(key)
        return value

    def put(self, key: str, value) -> None:
        expiry = time.monotonic() + self.ttl
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = (value, expiry)
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

Expect these follow-ups

• How would you make this safe for concurrent access from multiple goroutines?
• If the cache holds 50 million entries, how does your expiry strategy change?