ML engineer algorithms interview questions

As asked

Given a list of 2D points and an integer K, return the K points closest to the origin (0, 0). You do not need to return them in sorted order. Now walk me through the time complexity of each approach you can think of.

Sample answer outline

Three viable approaches: sort all points by Euclidean distance in O(n log n), use a max-heap of size K in O(n log K) which is better when K is much smaller than n, or use QuickSelect (partition-based) for O(n) average time. A strong answer compares all three and picks the right one based on the constraints given. The candidate should also note they can compare squared distances to avoid the sqrt computation.

Reference implementation (python)

import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max-heap of size k: negate distance to simulate max-heap with Python's min-heap
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negated squared distance
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

Expect these follow-ups

• What if K were very large, close to N?
• How would you handle streaming points arriving one at a time?

As asked

Write a function that takes an integer array and a target, and returns all unique pairs of indices whose values sum to the target. Then, given this problem ran across 1,000 elements on a GPU where each thread handles one element, explain how you would partition the work across wavefronts without redundant pair checking.

Sample answer outline

The CPU answer uses a hash map for O(n) time. For the GPU extension, a strong answer partitions rows across wavefronts (each wavefront owns a row of the lower triangle in the O(n^2) pair space), uses warp/wavefront-level ballot or reduction to avoid redundant work, and notes that atomic operations or prefix sums would be needed to compact results to a global output buffer without race conditions.

Reference implementation (python)

def two_sum_pairs(nums: list[int], target: int) -> list[tuple[int, int]]:
    seen = {}
    pairs = []
    for i, val in enumerate(nums):
        complement = target - val
        if complement in seen:
            pairs.append((seen[complement], i))
        seen[val] = i
    return pairs

Expect these follow-ups

• How would you handle duplicate values in the input array to keep the output unique pairs?
• If the array were 10 million elements and the result set were sparse, how would you estimate the output buffer size before launching the kernel?

As asked

You have a directed acyclic graph representing software module dependencies. Given a source module and a target module, write code to find the shortest dependency path between them. What is the time and space complexity?

Sample answer outline

A strong answer implements BFS with a queue, a visited set, and a parent map for path reconstruction. Time is O(V + E) and space is O(V). The candidate should handle the cases where the target is unreachable and where the graph has cycles in the non-DAG version. They should also mention that for a DAG they could use topological sort as an alternative but BFS is simpler and equally efficient for shortest path in unweighted graphs.

Reference implementation (python)

from collections import deque

def shortest_path(graph: dict, src: str, dst: str) -> list[str]:
    q = deque([[src]])
    visited = {src}
    while q:
        path = q.popleft()
        node = path[-1]
        if node == dst:
            return path
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(path + [neighbor])
    return []

Expect these follow-ups

• How would you modify this if the graph had weights on edges representing build times?
• How would you detect a cycle if the graph is not guaranteed to be a DAG?

As asked

Implement a data structure that supports two operations: addNum(int num) adds a number from a data stream, and findMedian() returns the median of all numbers added so far. The solution must support both operations in better than O(n) time.

Sample answer outline

The canonical solution uses two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half. After each insertion, rebalance so the heaps differ in size by at most one. findMedian returns the top of the larger heap (odd total) or the average of both tops (even total). addNum is O(log n) and findMedian is O(1). Candidates should handle the rebalancing invariant correctly and consider edge cases like a single element.

Reference implementation (python)

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        # move largest of lo to hi
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # rebalance sizes
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2.0

Expect these follow-ups

• How would you extend this to return the p90 percentile instead of the median?
• If numbers arrive from multiple Spark partitions in parallel, how would you compute the approximate median at scale?

As asked

You are profiling a Databricks SQL warehouse and want to find the most common query patterns. Given an integer array representing query-type IDs and an integer k, return the k most frequent IDs in any order. Your solution must be better than O(n log n) time complexity.

Sample answer outline

The optimal approach uses bucket sort: count frequencies with a hash map (O(n)), then create n buckets indexed by frequency and place each number in its frequency bucket (O(n)). Iterate buckets from highest to lowest, collecting elements until you have k. This is O(n) overall. A simpler but slightly less optimal approach uses a min-heap of size k (O(n log k)). The candidate should explain why bucket sort achieves O(n) and verify correctness on a small example.

Reference implementation (python)

from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for i in range(len(buckets) - 1, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Expect these follow-ups

• How would you compute the top-k frequent elements across a distributed dataset without collecting everything to the driver?
• What changes if elements have equal frequency and you need a stable tie-breaking rule?

As asked

A Databricks job scheduler stores job priority IDs in a sorted array, but a failover event rotated the array at an unknown pivot. Given this rotated array of distinct integers and a target job ID, return the index of the target or -1 if it is not present. Your solution must run in O(log n) time.

Sample answer outline

The candidate should use binary search but determine at each step which half is sorted. If nums[left] <= nums[mid], the left half is sorted. If the target is within [nums[left], nums[mid]], search left; otherwise search right. If the right half is sorted, apply the symmetric logic. Candidates should handle the edge case where left == mid (array of length 2) and verify on examples like [4,5,6,7,0,1,2] with target=0.

Reference implementation (python)

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Expect these follow-ups

• How does your approach change if the array can contain duplicates?
• Can you extend this to find the rotation pivot index itself?

As asked

Intel's compilers and performance libraries (such as Intel MKL) rely heavily on fast array searches. Given a sorted integer array, write a function that returns the index of the first element strictly greater than a given target. If no such element exists, return -1. Do it in O(log n) time and explain how this pattern appears in cache-line or threshold lookup tables used in performance tuning.

Sample answer outline

A correct answer uses a binary search variant (upper bound). The candidate should handle the edge cases where all elements are less than or equal to target (return -1) and where all elements are greater (return 0). A strong candidate names this the upper_bound pattern and explains the loop invariant: lo is always a candidate, hi is the first known non-candidate.

Reference implementation (python)

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

Expect these follow-ups

• How would you modify this to return the last element less than the target?
• What happens when the array contains duplicates of the target value?

As asked

Chip floorplanning and PCB routing at Intel require finding shortest paths through grids with obstacles. Given an m x n binary grid where 0 is open and 1 is blocked, find the length of the shortest path from the top-left cell to the bottom-right cell, moving only up, down, left, or right. Return -1 if no path exists. After coding the solution, describe how you would extend it to handle weighted traversal costs per cell, as you might see when routing around different material layers.

Sample answer outline

A correct answer uses BFS from (0,0) and explores the four cardinal directions, marking cells visited on first touch to avoid revisiting. The BFS layer count is the path length. The candidate should handle the edge cases where start or end is blocked and discuss why BFS guarantees the shortest path in an unweighted graph, as opposed to DFS which would not.

Reference implementation (python)

from collections import deque

def shortest_path(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] or grid[m-1][n-1]:
        return -1
    q = deque([(0, 0, 1)])
    visited = {(0, 0)}
    while q:
        r, c, dist = q.popleft()
        if r == m-1 and c == n-1:
            return dist
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<m and 0<=nc<n and not grid[nr][nc] and (nr,nc) not in visited:
                visited.add((nr,nc))
                q.append((nr,nc,dist+1))
    return -1

Expect these follow-ups

• How would you solve this if the grid were very large and sparse?
• How would you modify the algorithm to return the actual path, not just its length?

As asked

Given a binary tree and two node values p and q, return their lowest common ancestor. The tree is not a BST. What is your approach and what is the time and space complexity?

Sample answer outline

A strong answer describes a recursive post-order DFS: at each node, recurse left and right. If a subtree returns a non-null result for p or q, propagate that result upward. If both left and right return non-null, the current node is the LCA. Time complexity is O(N) and space is O(H) for the call stack where H is tree height. Edge cases to mention: one node being an ancestor of the other, nodes not existing in the tree (if that is possible per the problem), and handling null nodes.

Reference implementation (python)

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)
    if left and right:
        return root
    return left if left else right

Expect these follow-ups

• How would you change this if the tree had parent pointers?
• What if you needed to find the LCA of k nodes instead of just two?

As asked

Given a list of intervals represented as pairs of integers, merge all overlapping intervals and return the result. For example, [[1,3],[2,6],[8,10],[15,18]] returns [[1,6],[8,10],[15,18]]. What is your approach and complexity?

Sample answer outline

A strong answer sorts the intervals by start time in O(N log N), then iterates through them. For each interval, if its start is less than or equal to the current merged interval's end, extend the merged interval's end to the maximum of the two ends. Otherwise, push the current merged interval to the result and start a new one. Time complexity is O(N log N) for the sort plus O(N) for the merge pass. Space is O(N) for the output. Edge cases: empty input, single interval, all intervals overlapping, identical intervals.

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

• How would you handle the case where intervals are given as inclusive vs exclusive ranges?
• What if the input is already sorted? What is the complexity then?

As asked

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

Sample answer outline

A strong answer uses BFS or DFS: iterate over the grid. When a '1' is found, increment the island count and flood-fill the entire connected component by marking visited cells (e.g., setting them to '0' or using a visited array). BFS uses a queue and visits all 4-directional neighbors. Time complexity is O(M times N) and space is O(min(M,N)) for the BFS queue in the worst case. The candidate should discuss whether to mutate the input grid or use a separate visited array, and handle edge cases like empty grid or grid with no land.

Reference implementation (python)

from collections import deque
def numIslands(grid):
    if not grid: return 0
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                count += 1
                q = deque([(r, c)])
                grid[r][c] = '0'
                while q:
                    row, col = q.popleft()
                    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nr, nc = row+dr, col+dc
                        if 0<=nr<len(grid) and 0<=nc<len(grid[0]) and grid[nr][nc]=='1':
                            q.append((nr,nc))
                            grid[nr][nc] = '0'
    return count

Expect these follow-ups

• How would you count islands if diagonal connections also count?
• How would you modify the solution to return the size of the largest island?

As asked

In a distributed logging pipeline for OpenAI's API, each shard produces a sorted stream of log entries by timestamp. You need to merge K sorted linked lists of log entries into a single sorted list. What is the most efficient algorithm you can use, and what is its time complexity?

Sample answer outline

The candidate should land on a min-heap solution: push the head of each list, then repeatedly pop the minimum node, append it to the result, and push that node's next if it exists. Time complexity is O(N log K) where N is total nodes and K is number of lists. They should also mention the divide-and-conquer approach using pairwise merge, which has the same complexity but different constant factors.

Reference implementation (python)

import heapq

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

Expect these follow-ups

• What is the space complexity of the heap approach vs the divide-and-conquer approach?
• How would you adapt this if the lists were streams arriving over the network rather than in memory?

As asked

Implement vanilla gradient descent in TypeScript or Python for a simple linear regression problem. No ML libraries. Then explain how you would extend it to mini-batch SGD with momentum.

Sample answer outline

Define the loss (MSE). Compute the analytical gradient with respect to weights and bias. Update parameters by subtracting learning_rate * gradient. Loop until convergence or N iterations. For mini-batch SGD: shuffle and chunk the data; for momentum: maintain a velocity vector that decays each step and accumulates the gradient. Discuss why momentum helps in valleys with high curvature in one direction.

Reference implementation (typescript)

function trainLinReg(xs: number[], ys: number[], lr = 0.01, epochs = 1000) {
  let w = 0, b = 0;
  for (let e = 0; e < epochs; e++) {
    let dw = 0, db = 0;
    for (let i = 0; i < xs.length; i++) {
      const pred = w * xs[i]! + b;
      const err = pred - ys[i]!;
      dw += err * xs[i]!;
      db += err;
    }
    w -= (lr * dw) / xs.length;
    b -= (lr * db) / xs.length;
  }
  return { w, b };
}

Expect these follow-ups

• How would you implement Adam in 10 more lines?
• What is the role of learning rate scheduling?
• When does vanilla SGD beat Adam in practice?

As asked

Explain the self-attention mechanism in a transformer. Cover the math, why it works, and where it gets expensive.

Sample answer outline

For each token, compute Q, K, V vectors by linear projection. Attention weights = softmax(Q · K^T / sqrt(d_k)), then weighted sum of V. Multi-head: do this in parallel with different projections, concatenate, project back. Why it works: each token can attend to any other token in one step, regardless of distance - unlike RNNs which need many steps for long-range dependencies. Cost: O(n^2) in sequence length, both compute and memory. Mitigation: flash attention (fuse the kernel to avoid materializing the full matrix), sliding-window attention (linear), Mamba-style state-space models (linear).

Expect these follow-ups

• What problem does multi-head attention solve over single-head?
• How does flash attention change asymptotic vs constant factors?
• Why divide by sqrt(d_k) in the softmax?

As asked

Implement a prefix sum (inclusive scan) on an array. Then explain how you would implement an efficient parallel prefix sum on a GPU and what algorithm name is used for the parallel version.

Sample answer outline

The sequential version is a simple left-to-right accumulation in O(n). For the parallel version, the candidate should name the Blelloch (work-efficient) parallel scan with two phases: up-sweep (reduce) and down-sweep, achieving O(n) work and O(log n) depth on an SIMD machine. On AMD hardware this maps naturally to wavefront reductions using __shfl or ds_swizzle intrinsics. The candidate should mention that a naive prefix sum is work-inefficient at O(n log n) total operations.

Reference implementation (python)

# Sequential O(n)
def prefix_sum(arr: list[int]) -> list[int]:
    result = arr[:]
    for i in range(1, len(arr)):
        result[i] += result[i - 1]
    return result

# Blelloch parallel scan pseudocode:
# Up-sweep: for d in range(log n): for k with stride 2^(d+1): A[k-1] += A[k-1-2^d]
# Down-sweep: A[n-1]=0; for d in range(log n, 0): swap and add with stride

Expect these follow-ups

• What is the difference between an inclusive and exclusive scan, and how do you convert one to the other?
• How do you handle inputs larger than a single wavefront in the parallel version?

As asked

Given an integer array and a window size k, return the maximum value in each window as the window slides from left to right. Write the most efficient solution you can.

Sample answer outline

The optimal solution uses a monotonic deque in O(n) time, O(k) space. The candidate should explain that the deque stores indices, not values, and that elements are removed from the front when they fall out of the window and from the back when a new element is larger (maintaining a decreasing order). The interviewer at AMD often follows this with a parallel variant: how would you compute rolling maxima across all positions simultaneously on GPU hardware.

Reference implementation (python)

from collections import deque

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    dq = deque()  # stores indices
    result = []
    for i, val in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Expect these follow-ups

• What is the naive O(n*k) approach and in what input size range is it acceptable?
• How would you generalize this to 2D sliding window maximum, such as for image convolution?

As asked

Databricks Workflows can model job dependencies as a directed acyclic graph, but in general pipeline routing problems the graph may have cycles and weights. Given a list of edges as (source, destination, weight) tuples and a start node, implement Dijkstra's algorithm to find the shortest distance from the start node to every other node in the graph.

Sample answer outline

The candidate should use a min-heap (priority queue) initialized with (0, start). At each step, pop the minimum distance node, skip it if already visited, then relax all outgoing edges. The algorithm terminates when the heap is empty. Distance to unvisited nodes is initialized to infinity. Candidates should handle disconnected nodes and negative weights (Dijkstra does not work with negative weights, Bellman-Ford does).

Reference implementation (python)

import heapq
from collections import defaultdict

def dijkstra(edges, n, start):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((w, v))

    dist = {i: float('inf') for i in range(n)}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for w, v in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

Expect these follow-ups

• What is the time complexity of your implementation, and how does the choice of priority queue affect it?
• How would you compute the actual shortest path, not just the distance?

As asked

You are monitoring executor CPU metrics sampled every second in a Databricks cluster and want to report the peak usage over every k-second window. Given an integer array nums of CPU samples and an integer k, return an array of the maximum value in each sliding window of size k as the window moves from left to right.

Sample answer outline

The optimal O(n) solution uses a monotonic deque that stores indices in decreasing order of their values. For each new element, remove indices from the back of the deque that are smaller than the current element (they can never be a future window maximum). Remove from the front any index that is outside the current window. The front of the deque always holds the index of the maximum for the current window. Candidates should verify on [1,3,-1,-3,5,3,6,7] with k=3 to get [3,3,5,5,6,7].

Reference implementation (python)

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, front = max
    result = []
    for i, num in enumerate(nums):
        # remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # maintain decreasing order
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Expect these follow-ups

• How would you adapt this to return the minimum instead of maximum?
• If the window size k changes dynamically, how would your approach need to change?

As asked

Given a Dasher's current GPS coordinates and a radius in kilometers, write a function that returns all active orders whose pickup restaurant is within that radius. You have a list of Order objects each containing a restaurant_lat and restaurant_lng. Optimize for the case where there are 100,000 active orders.

Sample answer outline

A working answer first uses the Haversine formula for accurate great-circle distance, then discusses why naive O(n) scanning breaks at 100k orders. The optimized approach pre-partitions by geographic cell (H3 or Geohash) so only nearby cells are scanned. The candidate should mention that Haversine has edge cases at the poles and date line, and that a database solution (PostGIS ST_DWithin) is preferable in production over in-memory filtering.

Reference implementation (python)

import math

def haversine_km(lat1, lon1, lat2, lon2):
    R = 6371
    dlat = math.radians(lat2 - lat1)
    dlon = math.radians(lon2 - lon1)
    a = math.sin(dlat/2)**2 + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon/2)**2
    return R * 2 * math.asin(math.sqrt(a))

def orders_in_radius(orders, dasher_lat, dasher_lng, radius_km):
    return [
        o for o in orders
        if haversine_km(dasher_lat, dasher_lng, o.restaurant_lat, o.restaurant_lng) <= radius_km
    ]

Expect these follow-ups

• How does your approach change if Dashers move and the query runs thousands of times per second?
• What precision of Geohash or H3 resolution would you choose and why?

As asked

Resource allocation problems similar to knapsack appear in compiler register allocation and in Intel VTune's hotspot prioritization. You have n items each with a weight and a value, and a knapsack of capacity W. Find the maximum value you can fit in the knapsack. Implement the O(n x W) time solution and then optimize the space to O(W). Explain the right-to-left iteration invariant and when a greedy fractional approach would apply instead.

Sample answer outline

A correct solution builds the standard DP table and then recognizes that each row depends only on the previous row, so the table can be reduced to a single array by iterating capacity from W down to the item weight. The candidate should explain why iterating right-to-left prevents using the same item twice and connect this to the 0/1 constraint. A strong candidate also discusses when the fractional knapsack greedy approach would apply instead.

Reference implementation (python)

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]

Expect these follow-ups

• How would you recover the actual items chosen, not just the max value, using the space-optimized version?
• How does the time complexity change if weights are very large (e.g., up to 10^9)?

As asked

Sliding window maximum appears in hardware performance counter analysis, where Intel VTune aggregates the peak metric value over a rolling sample window. Given an integer array and a window size k, return an array of the maximum value in each window as the window slides one step at a time from left to right. Solve it in O(n) time using a monotonic deque and walk through the invariant on a small example.

Sample answer outline

A correct answer uses a monotonic deque (collections.deque in Python) that stores indices of elements in decreasing order of their values. Before processing each element, the algorithm removes the front of the deque if its index has left the window, and removes from the back any index whose value is less than the current element. The front of the deque is always the maximum for the current window. The candidate should walk through a small example to show the invariant holds.

Reference implementation (python)

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] <= n:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Expect these follow-ups

• How would you adapt this to find the minimum instead of the maximum?
• What is the space complexity and can you reduce it further?

As asked

You have a weighted directed graph that may have negative edge weights but no negative cycles. Write an algorithm to find the shortest path from a source node to all other nodes. Explain why Dijkstra fails here and what you use instead.

Sample answer outline

A strong answer explains that Dijkstra's greedy assumption, once a node is settled its distance is final, breaks with negative edges because a later negative edge could produce a shorter path to an already-settled node. The correct algorithm is Bellman-Ford, which relaxes all edges V minus 1 times, guaranteeing the shortest path is found since any simple path has at most V minus 1 edges. Time complexity is O(V times E). The candidate should explain how to detect a negative cycle: if any edge can still be relaxed after V minus 1 iterations, a negative cycle exists. SPFA is a queue-based optimization but has worst-case O(V times E) as well.

Expect these follow-ups

• How do you detect a negative cycle with Bellman-Ford?
• Where would you use Bellman-Ford in a real system rather than Dijkstra?

As asked

Given a string s and a dictionary of words, return true if s can be segmented into a sequence of dictionary words. For example, s = 'leetcode', dictionary = ['leet','code'] returns true.

Sample answer outline

A strong answer describes a DP approach where dp[i] is true if the substring s[0:i] can be segmented. Initialize dp[0] = true (empty string). For each i from 1 to len(s), check all j from 0 to i: if dp[j] is true and s[j:i] is in the dictionary, set dp[i] = true. Time complexity is O(N squared times M) where N is the string length and M is average word length for the hash set lookup (O(M) for hashing). The candidate should also consider a trie-based approach that reduces the inner loop constant, and discuss the memoized recursion alternative. Edge cases: empty string, dictionary with empty string, very long strings requiring memo.

Reference implementation (python)

def wordBreak(s, wordDict):
    words = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

Expect these follow-ups

• How would you return all valid segmentation strings, not just true/false?
• How does the time complexity change if you use a trie instead of a hash set?

As asked

A fuzzy token-matching component at OpenAI needs to find the minimum number of single-character substitutions to transform one vocabulary token into another, where every intermediate token must also exist in a known vocabulary. Given two words and a dictionary, return the length of the shortest such transformation sequence, or 0 if none exists.

Sample answer outline

The candidate should identify this as a BFS problem on an implicit graph where nodes are words and edges connect words that differ by one character. They should preprocess the word list into a pattern map (e.g., *ot -> [hot, dot, lot]) to avoid O(N*L) neighbor lookup per step. Time complexity is O(M^2 * N) where M is word length and N is dictionary size. A strong answer also considers bidirectional BFS to halve the search space.

Reference implementation (python)

from collections import defaultdict, deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    L = len(beginWord)
    pattern_map = defaultdict(list)
    for word in wordList:
        for i in range(L):
            pattern_map[word[:i] + '*' + word[i+1:]].append(word)
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, steps = queue.popleft()
        for i in range(L):
            for neighbor in pattern_map[word[:i] + '*' + word[i+1:]]:
                if neighbor == endWord:
                    return steps + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, steps + 1))
    return 0

Expect these follow-ups

• How does bidirectional BFS improve performance here?
• How would you modify the solution to return all shortest paths, not just the length?

As asked

OpenAI's eval pipeline runs N tasks labeled 0 through N-1. Some tasks depend on others: if task A depends on task B, you must complete B before A. Given a list of dependency pairs, return a valid order to run all tasks, or indicate that no valid order exists due to a cycle.

Sample answer outline

The candidate should identify this as topological sort. Kahn's algorithm (BFS-based) is often cleaner to implement under pressure: build an adjacency list and in-degree array, enqueue all zero-in-degree nodes, process them, decrement in-degrees of neighbors, enqueue newly zero-in-degree nodes. If the result contains fewer than N nodes, a cycle exists. DFS-based approach with a visited/cycle detection is an equally valid alternative.

Reference implementation (python)

from collections import deque

def find_order(num_tasks, prerequisites):
    adj = [[] for _ in range(num_tasks)]
    in_degree = [0] * num_tasks
    for a, b in prerequisites:
        adj[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(num_tasks) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_tasks else []

Expect these follow-ups

• How do you detect a cycle in this approach?
• How would you modify this to return all valid topological orderings, not just one?