Frontend engineer algorithms interview questions

As asked

Given the head of a linked list, determine whether the list contains a cycle. If it does, return the node where the cycle begins. You must solve this without allocating additional data structures proportional to the size of the list.

Sample answer outline

Floyd's tortoise-and-hare algorithm: two pointers, one moving one step and one moving two steps at a time. If they meet, a cycle exists. To find the start, reset one pointer to head and advance both one step at a time until they meet again; that node is the cycle entry. Time O(n), space O(1). A complete answer explains WHY the meeting point math works (the distance from head to cycle start equals the distance from meeting point to cycle start, modulo cycle length).

Reference implementation (python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Expect these follow-ups

• What if the list is doubly linked? Does your algorithm change?
• How would you solve this if the list were stored on disk and too large to fit in memory?

As asked

Given a list of intervals where each interval is a pair [start, end], merge all overlapping intervals and return the resulting list. For example, given [[1,3],[2,6],[8,10],[15,18]], return [[1,6],[8,10],[15,18]].

Sample answer outline

Sort by start time, then scan and merge when the current interval's start is less than or equal to the previous interval's end. Update the end to max(current end, previous end). Time O(n log n) due to sorting, space O(n) for output. A strong candidate also handles edge cases: empty input, a single interval, all intervals overlapping into one, and intervals that touch but do not overlap (e.g., [1,3] and [3,5]).

Reference implementation (python)

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• Now find the total covered length after merging. How does your solution change?
• If new intervals are inserted one at a time into an already-merged set, how do you maintain the merged state efficiently?

As asked

Given a list of booking intervals for Airbnb experiences, where each interval has a start and end time, return the minimum number of rooms (or hosts) needed so no two overlapping bookings share the same room. Walk me through your approach before coding.

Sample answer outline

The optimal approach sorts start times and uses a min-heap of end times. For each new start time, if the earliest-ending meeting has already finished, reuse that room (pop and push). Otherwise add a new room. Time complexity O(n log n). The candidate should also mention the line-sweep / two-pointer variant and when each is clearer.

Reference implementation (python)

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []  # stores end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

Expect these follow-ups

• What if you also need to output which specific bookings go into which room?
• How does this extend to finding the maximum number of overlapping bookings at any single point?

As asked

Given a string, find the length of the longest substring without repeating characters. What is the optimal time and space complexity, and can you implement it in a single pass?

Sample answer outline

The optimal solution uses a sliding window with a hash map storing the most recent index of each character. The left pointer jumps to max(left, last_seen[char] + 1) when a duplicate is found, avoiding a slow re-scan. This gives O(n) time and O(min(n, alphabet_size)) space. A common mistake is moving the left pointer one step at a time, which is O(n) but with a higher constant factor, or using a set that requires moving left one step at a time. The strong candidate also handles the empty string edge case.

Reference implementation (python)

def length_of_longest_substring(s: str) -> int:
    last_seen = {}  # char -> most recent index
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

Expect these follow-ups

• What if you need to return the actual substring, not just the length?
• How does the solution change if the string contains Unicode characters?

As asked

Given an array of integers and a target, return the indices of the two numbers that add up to the target. You may assume exactly one solution exists. Now, how does your approach change if the array is sorted? And what if there can be duplicates in the output?

Sample answer outline

The unsorted version uses a hash map for O(n) time and O(n) space. For the sorted version, a two-pointer approach achieves O(n) time and O(1) space. The candidate should recognize these as distinct approaches, not just the same solution applied twice. For duplicates in output, the hash map approach needs a slight adjustment to handle the case where the same element satisfies the complement check against itself.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        diff = target - n
        if diff in seen:
            return [seen[diff], i]
        seen[n] = i
    return []

Expect these follow-ups

• What if you need all pairs that sum to the target, not just one?
• How does the solution change for Three Sum?

As asked

In Jira, a user can have multiple active sprint date ranges and you need to merge any overlapping ranges before displaying them. Given a list of date intervals where each interval is [start, end] as integers, write a function that merges all overlapping intervals and returns the result sorted. For example, given [[1,3],[2,6],[8,10],[15,18]], return [[1,6],[8,10],[15,18]].

Sample answer outline

Sort by start time in O(n log n), then iterate once comparing each interval's start to the previous merged interval's end. If they overlap, extend the end. Otherwise push the current interval. Result is O(n log n) time and O(n) space. Edge cases: empty input, single interval, all intervals overlapping, adjacent intervals [1,2],[2,3].

Reference implementation (python)

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• How would you modify this to insert a new interval into an already sorted, non-overlapping list?
• What if intervals represent calendar events and you want to find the minimum number of meeting rooms needed?

As asked

Given two strings s and t, return the minimum window substring of s that contains every character of t, including duplicates. If no such window exists, return an empty string. What is the time and space complexity of your solution?

Sample answer outline

A strong answer implements the two-pointer sliding window with a character frequency map, expands the right pointer until all required characters are covered, then contracts the left pointer to minimize the window. The candidate handles duplicate characters correctly using counts rather than a set. Time complexity is O(|s| + |t|), space is O(|t|). Edge cases include t longer than s and characters in t not present in s.

Reference implementation (python)

def min_window(s: str, t: str) -> str:
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1
    missing = len(t)
    left = start = end = 0
    for right, c in enumerate(s, 1):
        if need.get(c, 0) > 0:
            missing -= 1
        need[c] = need.get(c, 0) - 1
        if missing == 0:
            while need.get(s[left], 0) < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[start:end]

Expect these follow-ups

• How would you extend this to find all minimum windows, not just one?
• If s is a stream and t is fixed, how do you handle the problem efficiently?

As asked

Given an array of non-negative integers representing the height of bars in a histogram, compute how much water it can trap after raining. For example, [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of water.

Sample answer outline

A strong answer starts with the O(n) two-pointer approach: maintain left and right pointers and left_max and right_max variables, accumulating water where the bar is shorter than the limiting side. The candidate should explain why this works (the water at any position is determined by the minimum of the max heights to its left and right). They should also mention the O(n) space DP precomputation approach as a stepping stone, and the O(n^2) brute force they rejected.

Expect these follow-ups

• What changes if the histogram can have negative bar heights?
• How would you solve the 2D version of this problem (trapping rain water in a 3D grid)?

As asked

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically.

Sample answer outline

The standard solution uses BFS or DFS to flood-fill each unvisited land cell, marking visited cells in-place (or with a visited set) to avoid double-counting. Each time we start a new flood-fill, we increment the island count. Time and space are both O(m * n). The candidate should handle the case where mutating the input is not allowed (use a separate visited array). Union-Find is an alternative worth mentioning for follow-up variants.

Expect these follow-ups

• How would you count islands if the grid is too large to fit in memory?
• How does your solution change if diagonal connections also count as adjacent?

As asked

You are given n courses labeled 0 to n-1 and a list of prerequisite pairs where [a, b] means you must take course b before course a. Determine whether it is possible to finish all courses. Then extend your solution to return a valid course ordering if one exists.

Sample answer outline

The candidate should recognize this as a cycle detection problem on a directed graph, solvable with either DFS (coloring nodes as unvisited, in-progress, done) or Kahn's algorithm (topological sort using BFS with in-degree counts). Kahn's naturally produces the ordering as a byproduct. The candidate should handle disconnected graphs correctly (process all nodes, not just those reachable from node 0) and explain why DFS cycle detection requires three states, not just two.

Expect these follow-ups

• How do you output all valid topological orderings, not just one?
• If some courses have parallel prerequisites (multiple orderings are valid), how do you choose the lexicographically smallest ordering?

As asked

Coinbase's price-alert service caches the latest price for each asset so it can evaluate alert thresholds without hitting the database on every tick. Implement an LRU cache class in TypeScript with get(key) and put(key, value) methods, both in O(1) time. The cache has a fixed capacity. When it is full and a new key is inserted, evict the least recently used entry.

Sample answer outline

The canonical solution uses a doubly linked list for O(1) eviction from head and promotion to tail, plus a Map for O(1) key lookup pointing to the list node. The candidate should explain why a plain object or Map alone is not enough (no O(1) ordering), handle the edge case where capacity is 1, and discuss why JavaScript's Map preserves insertion order but that does not give O(1) eviction without the list. In the Coinbase context, they might also note that a real cache would need a TTL per key so stale prices expire.

Reference implementation (typescript)

class LRUCache {
  private capacity: number;
  // hint: doubly linked list + Map

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

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

  put(key: number, value: number): void {
    // evict LRU if over capacity
  }
}

Expect these follow-ups

• How would you make this thread-safe if multiple async operations could access it concurrently in Node.js?
• How would you extend this to support a TTL per key?

As asked

You have an array of daily BTC closing prices sorted in ascending order. Given a target gain, find all pairs of prices (buy_price, sell_price) where sell_price minus buy_price equals the target gain. Return them as pairs. What is the time and space complexity of your approach?

Sample answer outline

The two-pointer solution runs in O(n) time and O(1) space by placing one pointer at the start and one at the end and moving them inward based on whether the current difference is too small or too large. The candidate should also mention the hash set approach (O(n) time, O(n) space) and explain why the sorted property makes the two-pointer approach strictly better here. Edge cases: empty array, no valid pairs, duplicate prices.

Reference implementation (python)

def find_gain_pairs(prices: list[int], target: int) -> list[tuple[int, int]]:
    # prices is sorted ascending
    # return all (buy, sell) pairs where sell - buy == target
    result = []
    left, right = 0, len(prices) - 1
    # your solution here
    return result

Expect these follow-ups

• How does your answer change if the array is not sorted and sorting it yourself is too expensive?
• What if you need all unique pairs and there are duplicate prices in the array?

As asked

Given a list of trading session time intervals (each with a start and end timestamp in milliseconds), merge all overlapping intervals and return the resulting merged list sorted by start time.

Sample answer outline

Sort by start time first, then iterate with a running merge window. If the current interval starts before the end of the window, extend the window end to max of both ends. Otherwise push the window and start a new one. Time complexity O(n log n) dominated by sort. The candidate should handle edge cases: empty input, single interval, all intervals disjoint, all intervals fully overlapping.

Reference implementation (python)

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• How does your solution change if intervals can have equal start times?
• What is the memory usage if you sort in place versus building a new result array?

As asked

You have a sorted array of hourly BTC prices over the past year (8,760 entries). Find the index of the first price that is greater than or equal to a given target. If no such price exists, return -1. Implement this with the minimum number of comparisons.

Sample answer outline

Classic binary search variant (leftmost insertion point / lower_bound). The candidate should implement it iteratively with low and high pointers, move high down when mid >= target to narrow toward the leftmost qualifying index, and return -1 if the final candidate does not meet the condition. They should handle empty array and all-below-target edge cases. Time complexity O(log n), space O(1). Bonus: explain why this is equivalent to Python's bisect_left.

Reference implementation (python)

def first_price_above(prices: list[int], target: int) -> int:
    lo, hi = 0, len(prices) - 1
    result = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] >= target:
            result = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return result

Expect these follow-ups

• How would you modify this to find the last price below the target?
• What if prices are not strictly sorted because of data quality issues, and up to 1% of adjacent entries are swapped?

As asked

Figma documents are represented as a tree of nodes: frames contain groups, groups contain shapes, and each node has a local transform relative to its parent. Write a function that takes the root of this tree and returns a flat list of all leaf nodes with their absolute (world-space) positions.

Sample answer outline

A strong answer uses depth-first traversal, accumulating a running transform matrix as the stack descends. The candidate should handle the case where a node has no children (leaf case), and correctly compose parent-to-world transforms using matrix multiplication. A great answer mentions that Figma nodes can have rotation and scale in addition to translation, so a proper solution uses affine matrix composition rather than simple coordinate addition. The candidate should also consider tree depth and whether recursion or an explicit stack is better for very deep scenes.

Reference implementation (typescript)

interface Node {
  id: string;
  x: number;
  y: number;
  rotation: number; // degrees
  children?: Node[];
}

interface AbsoluteNode {
  id: string;
  absX: number;
  absY: number;
}

function flattenSceneGraph(root: Node): AbsoluteNode[] {
  const result: AbsoluteNode[] = [];
  // your implementation here
  return result;
}

Expect these follow-ups

• How does your solution handle rotation? Show me the matrix multiplication.
• If the tree has 500,000 nodes and you need to run this on every frame at 60fps, what optimizations would you make?

As asked

Given the root of a Figma document node tree, return a list of lists where each inner list contains all nodes at the same depth level. The root is at depth 0.

Sample answer outline

This is a standard BFS level-order traversal. A strong answer initializes a queue with the root, processes nodes level by level using queue size as the boundary marker, and builds the output list without sorting or repeated traversal. The candidate should handle nodes with undefined or empty children arrays without crashing, and note the space complexity is O(n) in the worst case when all nodes are at the same level. A great candidate also discusses how this could be used in a Figma plugin to implement 'select all on layer N' functionality.

Reference implementation (typescript)

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

function levelOrder(root: FigmaNode): FigmaNode[][] {
  // your implementation
}

Expect these follow-ups

• How would you modify this to return only nodes whose type is FRAME at each level?
• What changes if the tree is a DAG (a node can appear in multiple parent groups via component instances) rather than a strict tree?

As asked

Given a list of time intervals representing a LinkedIn member's availability slots, write a function that merges all overlapping intervals and returns a sorted, non-overlapping list. Assume intervals are given as pairs of integers representing start and end minutes from midnight.

Sample answer outline

Sort by start time, then iterate and either extend the current interval or push a new one. The candidate should handle edge cases: empty input, a single interval, intervals that share only an endpoint, and intervals that are already non-overlapping. Time O(n log n), space O(n) for output. A good follow-up discussion touches on stability and whether input modification is acceptable.

Reference implementation (python)

def merge_intervals(intervals: list[tuple[int,int]]) -> list[tuple[int,int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged

Expect these follow-ups

• How would you find the complement: the intervals when the member is NOT available?
• How does this extend to finding the intersection of two members' availability for scheduling?

As asked

You have an array of integers representing normalized skill scores for LinkedIn members. Write a function that returns all unique pairs of indices (i, j) where i < j and scores[i] + scores[j] equals a given target value.

Sample answer outline

The candidate should use a hash set or hash map to achieve O(n) time, tracking complements as they iterate. They should clarify uniqueness requirements (index pairs vs value pairs), handle duplicates correctly, and discuss the brute-force O(n^2) solution before the optimized one. A strong answer also addresses what happens when the same value appears multiple times in the array.

Reference implementation (python)

def find_pairs(scores: list[int], target: int) -> list[tuple[int, int]]:
    seen = {}  # value -> first index
    result = []
    for i, score in enumerate(scores):
        complement = target - score
        if complement in seen:
            result.append((seen[complement], i))
        if score not in seen:
            seen[score] = i
    return result

Expect these follow-ups

• How would you extend this to three numbers summing to a target?
• What if the array is sorted? Does that change your approach?

As asked

Given a list of intervals representing driver availability windows, each as a pair [start, end], merge all overlapping intervals and return the list of merged intervals. For example, [[1,3],[2,6],[8,10],[15,18]] returns [[1,6],[8,10],[15,18]].

Sample answer outline

Strong answers sort by start time, iterate once, and merge by comparing each interval's start to the current merged interval's end. Time complexity O(n log n) for the sort. Edge cases: empty list, single interval, all intervals overlapping, adjacent but not overlapping intervals like [1,2] and [2,3].

Reference implementation (python)

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• How would you solve this if the intervals arrive in a stream and you need to maintain the merged set incrementally?
• What if intervals can be added and removed, and you need to query the merged set at any time?

As asked

Given the root of a binary tree and two nodes p and q, find their lowest common ancestor. The tree is not necessarily a BST. Walk me through your approach and write the code.

Sample answer outline

A strong answer explains the recursive postorder approach: return the node itself if it equals p or q, recurse on both children, and if both sides return non-null the current node is the LCA. The candidate handles edge cases including when one node is an ancestor of the other. Time O(n), space O(h) for the call stack.

Reference implementation (python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if left and right else left or right

Expect these follow-ups

• How does your solution change if the tree can have a million nodes and you need to answer many LCA queries offline?
• What if the nodes are not guaranteed to exist in the tree?

As asked

Given an array of integers and a target sum, return the indices of the two numbers that add up to the target. You can assume exactly one solution exists and you cannot use the same element twice. What is the optimal approach, and what is its time and space complexity?

Sample answer outline

The candidate should move from brute-force O(n^2) to a single-pass hash map solution in O(n) time and O(n) space. Microsoft uses this as a warm-up to see if the candidate explains reasoning aloud, handles the complement lookup correctly, and discusses edge cases like duplicate values or an empty array. Code should be clean and the hash map approach should be explained before written.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

Expect these follow-ups

• What if the array is sorted, can you do it in O(1) space?
• What if you need to find all pairs, not just one?

As asked

Notion documents are modeled as a tree of blocks. Each block has a type, optional rich-text content, and an array of children. Write a function that accepts the root block and returns all plain-text content in depth-first order, one string per block, skipping blocks with no text. The input shape is: { id: string, type: string, rich_text?: Array<{ plain_text: string }>, children?: Block[] }.

Sample answer outline

A correct answer uses recursive DFS or an iterative stack, collects plain_text by joining the rich_text array for each block, and skips blocks where rich_text is missing or empty. Strong candidates handle cycles defensively (Notion's API does not produce them, but noting the assumption is good) and discuss the iterative vs recursive tradeoff for deeply nested documents. A follow-up typically pushes toward breadth-first ordering or filtering by block type.

Reference implementation (typescript)

interface Block {
  id: string;
  type: string;
  rich_text?: Array<{ plain_text: string }>;
  children?: Block[];
}

function extractText(root: Block): string[] {
  // your implementation here
}

Expect these follow-ups

• How would you change this to return blocks in breadth-first order instead?
• If a document had 50,000 blocks, what would you change to avoid blowing the call stack?

As asked

Oracle's coding screens commonly open with a warm-up problem. Given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume exactly one solution exists and you cannot use the same element twice. What is the most efficient approach, and what is its time and space complexity?

Sample answer outline

The optimal solution uses a hash map to store each number and its index in one pass. For each element, check whether target minus the current number is already in the map. Time complexity is O(n), space is O(n). The candidate should handle the case of not reusing the same element and discuss the brute-force O(n^2) alternative as a baseline.

Reference implementation (typescript)

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

Expect these follow-ups

• How does your solution change if the array is sorted and you need O(1) extra space?
• What if there can be multiple valid pairs and you need to return all of them?

As asked

Given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume exactly one solution exists and you cannot use the same element twice. What is the time and space complexity of your solution, and how does it behave with very large arrays?

Sample answer outline

A strong answer produces the O(n) hash map solution without prompting, correctly handles negative numbers and duplicate values, and explains why the brute-force O(n^2) approach is rejected. The candidate should also discuss the edge case where the same value appears twice (e.g. [3, 3] targeting 6) and confirm the map lookup correctly handles it by checking index inequality.

Reference implementation (typescript)

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

Expect these follow-ups

• What if the array is sorted? Can you use O(1) space?
• What if you need to return all pairs, not just one?

As asked

You have an array of track durations in seconds and a target time T in seconds. Find all unique pairs of tracks (by index) whose combined duration equals exactly T. Return the indices of both tracks in each pair. What is the time and space complexity of your solution?

Sample answer outline

A strong answer uses a hash map to store each duration seen so far with its index, then for each new duration checks whether (T - duration) is in the map. Time O(n), space O(n). The candidate handles the edge case where a track is paired with itself (T = 2 * duration) by checking the index is different. They also clarify whether the problem expects all pairs or just one.

Reference implementation (python)

def find_pairs(durations, target):
    seen = {}  # duration -> index
    pairs = []
    for i, d in enumerate(durations):
        complement = target - d
        if complement in seen and seen[complement] != i:
            pairs.append((seen[complement], i))
        seen[d] = i
    return pairs

Expect these follow-ups

• How does your solution change if T is a range (T_min to T_max) instead of an exact value?
• How would you extend this to find triples of tracks that fit a longer time slot?