Frontend 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 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

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

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

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

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

Given a linked list and an integer k, reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes stay in their original order.

Sample answer outline

The clean solution iterates through the list, collects k nodes, reverses that group by relinking pointers, then connects the reversed group to the previous group's tail and recurse or loop. The tricky part is tracking the previous group's last node so you can connect after reversal. A strong candidate writes this iteratively to avoid O(n/k) recursion depth, handles the edge case where the remaining nodes are fewer than k (leave them as-is), and achieves O(n) time O(1) extra space.

Reference implementation (python)

def reverseKGroup(head, k):
    # count available nodes
    count, node = 0, head
    while node and count < k:
        node = node.next
        count += 1
    if count < k:
        return head
    # reverse k nodes
    prev, cur = None, head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    # head is now tail; connect to rest
    head.next = reverseKGroup(cur, k)
    return prev

Expect these follow-ups

• How do you verify the node count before reversing without using extra space?
• What changes if you need to reverse alternate groups of k?

As asked

Confluence pages can link to each other forming a directed graph. Given a reference to a node in a connected directed page graph where each node has a page ID and a list of linked pages, return a deep copy of the graph. Each node has a unique value from 1 to n.

Sample answer outline

Use DFS or BFS with a hash map from original node to cloned node. When visiting a node, if it is already in the map return the clone. Otherwise create a new node, add it to the map, then recursively clone each neighbor. This handles cycles correctly because the map check prevents infinite recursion. Time and space are both O(V + E).

Reference implementation (python)

def cloneGraph(node):
    if not node:
        return None
    visited = {}
    def dfs(n):
        if n in visited:
            return visited[n]
        clone = Node(n.val)
        visited[n] = clone
        for neighbor in n.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
    return dfs(node)

Expect these follow-ups

• How does your cycle-handling change if the graph can have self-loops?
• How would you serialize and deserialize this graph to JSON instead?

As asked

Atlassian needs to persist Confluence's page hierarchy, which is a binary tree of page nodes, to a flat string for caching and restore it later. Design an algorithm to serialize a binary tree to a string and deserialize that string back to a tree. Your serialization format is your choice but it must round-trip correctly for any valid binary tree, including trees with duplicate values and null nodes.

Sample answer outline

BFS level-order serialization is easiest to explain: output node values separated by commas using 'null' for missing children. Deserialization reads tokens into a queue and uses another queue of parent nodes to assign left and right children. Pre-order DFS with null markers also works and deserializes cleanly with a pointer into the token list. The candidate should prove round-trip correctness with a skewed tree example.

Expect these follow-ups

• How does your approach change if the tree is a BST? Can you use a more compact format?
• How would you serialize a general n-ary tree instead?

As asked

Lyft's internal tooling stores ride decision trees that need to be persisted and restored. Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. Your encode and decode functions must be inverses of each other. There is no restriction on the format of the encoded string.

Sample answer outline

Strong answers use a preorder traversal where null children are represented as a sentinel like '#', split on a delimiter to reconstruct, and track position with an index or iterator during deserialization. They verify the approach handles edge cases: empty tree, single node, trees with only left children.

Reference implementation (python)

class Codec:
    def serialize(self, root):
        res = []
        def dfs(node):
            if not node:
                res.append('#')
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(res)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            v = next(vals)
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

Expect these follow-ups

• How would your solution change for an N-ary tree?
• If you had to make the serialized format human-readable and editable, how would you change it?

As asked

Analysts type entity names into a search bar. You need to return all matching entity names that begin with the typed prefix, ranked by historical query frequency, in under 50 ms. The entity dictionary has 20 million entries. Design and implement the core data structure.

Sample answer outline

A trie with frequency counts at each terminal node supports prefix lookup in O(k) where k is the prefix length. For ranking, a min-heap of the top N results while traversing the subtree avoids scoring all matches. For 20 million entries, the candidate should discuss the memory cost of a plain trie versus a compressed trie or DAFSA, and whether a cache layer over the raw trie makes sense given that a small number of prefixes are queried repeatedly.

Reference implementation (python)

class TrieNode:
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.freq: int = 0
        self.is_end: bool = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str, freq: int = 1) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
        node.freq = freq

    def starts_with(self, prefix: str) -> list[tuple[int, str]]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        results: list[tuple[int, str]] = []
        self._dfs(node, prefix, results)
        return sorted(results, reverse=True)

    def _dfs(self, node: TrieNode, current: str, results: list) -> None:
        if node.is_end:
            results.append((node.freq, current))
        for ch, child in node.children.items():
            self._dfs(child, current + ch, results)

Expect these follow-ups

• How would you update the frequency scores in real time as analysts run queries?
• A new entity is added to the dictionary. How quickly must it appear in autocomplete results?

As asked

Given a string containing only '(', ')', '{', '}', '[', ']', determine if the input string is valid. A valid string has every opening bracket closed by the correct type in the correct order. How would you handle this efficiently?

Sample answer outline

Strong answers use a stack without prompting, push opening brackets, and pop when a closing bracket is encountered to verify it matches. Edge cases to cover: empty string (valid), string that starts with a closing bracket, string with only opening brackets. Time is O(n), space is O(n). The candidate should also mention the single-character optimization: if the length is odd, immediately return false.

Reference implementation (typescript)

function isValid(s: string): boolean {
  const stack: string[] = [];
  const map: Record<string, string> = { ')': '(', '}': '{', ']': '[' };
  for (const c of s) {
    if (map[c]) {
      if (stack.pop() !== map[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0;
}

Expect these follow-ups

• How would you find the minimum number of brackets to remove to make the string valid?
• What if the string could also contain wildcard characters that match any bracket?

As asked

When migrating Confluence content between spaces, you want to detect page sub-trees that have been accidentally duplicated. Given a binary tree of page nodes, find all subtrees that appear more than once. Two subtrees are the same if they have the same structure and node values. Return the root node of each duplicate subtree (return only one representative per duplicate pair).

Sample answer outline

Serialize each subtree using post-order traversal, building a string like 'left#right#val'. Store serializations in a hash map counting occurrences. When a serialization is seen for the second time, add the current node to the result. Time and space are O(n^2) in the worst case due to string concatenation; using integer IDs for subtrees via a second map reduces this to O(n). The candidate should also handle null nodes in the serialization to avoid false matches.

Expect these follow-ups

• How does your serialization handle trees with negative values?
• Can you reduce the worst-case time complexity beyond O(n^2)?