Full-stack 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 an array of integers and a target value, return the indices of the two numbers that add up to the target. You may not use the same index twice. Now: can you do it in O(n) time? And if memory is extremely tight, what is the best space complexity you can achieve?

Sample answer outline

O(n) time with a hash map, O(n) space. For the space-constrained version, a sorted array plus two pointers gives O(n log n) time and O(1) space, but requires the original indices to be stored alongside values. A strong answer explains the trade-off clearly: sorting destroys original indices unless you save them, and O(1) space means O(n log n) time. Interviewers often follow up to force the candidate to articulate why they cannot do better than O(n) time with O(1) space for the general case.

Reference implementation (python)

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

Expect these follow-ups

• What if the array were already sorted?
• What if you needed to return all pairs, not just one?

As asked

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

Sample answer outline

This is a connected-components problem solvable with DFS, BFS, or Union-Find. The DFS approach is simplest: iterate every cell, and when you find a '1', increment the count and recursively mark all connected land as visited by setting cells to '0'. Time complexity O(M*N), space O(M*N) for recursion stack in the worst case. A strong candidate also mentions the BFS alternative to avoid stack overflow on very large grids, and discusses Union-Find for cases where the grid is dynamic (cells turning from water to land).

Reference implementation (python)

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Expect these follow-ups

• How does your approach change if diagonal connections also count?
• How would you solve this if the grid were so large it did not fit in memory?

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 points on a 2D plane, return the k closest points to the origin. You do not need to sort the result. What is the most efficient approach and its time complexity?

Sample answer outline

The interviewer is looking for the candidate to discuss multiple approaches: sorting in O(n log n), a max-heap of size k in O(n log k), and QuickSelect in O(n) average time. A strong candidate implements the heap solution for correctness first, then explains QuickSelect and its O(n^2) worst case. They should note that floating-point square roots are unnecessary since we only compare distances.

Expect these follow-ups

• When would you prefer QuickSelect over the heap approach?
• How would this change if the points arrive as a stream?

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

You are given a network topology represented as an adjacency list where each edge has a latency weight in milliseconds. Write a function that returns the minimum-latency path between two devices by name. The function should return both the total latency and the list of device names on the path.

Sample answer outline

This is a straightforward Dijkstra's algorithm problem. A strong answer uses a min-heap (heapq in Python), initializes distances to infinity except the source, relaxes neighbors on each pop, and tracks predecessors to reconstruct the path. The candidate should mention the time complexity O((V + E) log V) and note that since latency is non-negative, Dijkstra is correct here (Bellman-Ford would be needed for negative weights). Cisco networking contexts often make this problem more concrete by asking about OSPF cost calculation, which is exactly Dijkstra.

Reference implementation (python)

import heapq
from collections import defaultdict

def shortest_path(graph: dict, src: str, dst: str):
    dist = defaultdict(lambda: float('inf'))
    dist[src] = 0
    prev = {}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        if u == dst: break
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    path, node = [], dst
    while node in prev:
        path.append(node)
        node = prev[node]
    path.append(src)
    return dist[dst], list(reversed(path))

Expect these follow-ups

• How would you modify this to return all paths with equal minimum latency?
• What changes if the graph has multiple edges between the same pair of devices?

As asked

Cloudflare's edge products (KV, Cache, Durable Objects) rely on efficient in-memory caching internally. Implement an LRU (Least Recently Used) cache class with get and put operations, 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. Explain how you would extend this toward a TTL-aware cache suitable for a CDN edge node.

Sample answer outline

A correct answer uses a doubly linked list combined with a hash map. The map gives O(1) lookup of list nodes by key. Moving a node to the front of the list on access and removing from the tail on eviction are both O(1) because we have direct node pointers. Candidates should handle edge cases: capacity of 1, getting a non-existent key, and putting a key that already exists (update value and move to front without inserting a duplicate).

Reference implementation (javascript)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // doubly linked list with sentinel head and tail
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  get(key) { /* TODO */ }
  put(key, value) { /* TODO */ }
  _remove(node) { /* TODO */ }
  _insertFront(node) { /* TODO */ }
}

Expect these follow-ups

• How would you make this thread-safe for concurrent access?
• How would you extend this to support TTL expiry per entry?

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

DoorDash caches restaurant menus in memory so API servers don't hit Postgres on every request. Implement an LRU cache class in Python or TypeScript with O(1) get and put operations. The cache should evict the least recently used entry when it reaches capacity. Then explain how you would extend this to handle per-restaurant TTL expiry.

Sample answer outline

A correct implementation uses a doubly linked list plus a hash map: the map gives O(1) lookup, and the list maintains access order for O(1) eviction at the tail. The candidate should explain why a singly linked list makes tail removal O(n). For TTL, each node stores a timestamp; get() checks staleness before returning, and a background sweep or lazy deletion on access handles expired entries.

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: int):
        self.cap = capacity
        self.cache = {}
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _insert(self, node):
        node.prev, node.next = self.head, self.head.next
        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 use across concurrent request handlers?
• If two Dasher app servers each run this cache, how do you handle a menu update invalidating both?

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 an array of intervals where each interval is [start, end], merge all overlapping intervals and return the resulting array. For example, given [[1,3],[2,6],[8,10],[15,18]], return [[1,6],[8,10],[15,18]]. Walk me through your approach and then code it up.

Sample answer outline

Sort by start time, then iterate once keeping a running merge. O(n log n) time, O(n) space. Strong candidates handle edge cases: single interval, all overlapping, no overlapping, and intervals that share only an endpoint. Should also discuss what 'overlap' means when end == next start.

Reference implementation (typescript)

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const result: number[][] = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      result.push(intervals[i]);
    }
  }
  return result;
}

Expect these follow-ups

• What if the input is already sorted? Does your solution change?
• How would you extend this to find the union of two separate sorted interval lists efficiently?

As asked

Given a directed graph with non-negative edge weights and two nodes, source and destination, find the shortest path between them. Implement the algorithm and explain the time and space complexity in terms of V vertices and E edges.

Sample answer outline

A strong answer implements Dijkstra's algorithm using a min-heap for O((V + E) log V) time. The candidate explains why BFS is insufficient for weighted graphs, walks through the relaxation step, and handles the edge case where the destination is unreachable. They should also know that with negative weights you need Bellman-Ford, and with all equal weights BFS gives O(V + E) which is better.

Reference implementation (python)

import heapq

def dijkstra(graph, src, dst, n):
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist[dst] if dist[dst] < float('inf') else -1

Expect these follow-ups

• Why does Dijkstra fail with negative edge weights?
• How would you reconstruct the actual path, not just the distance?

As asked

Given an array of coin denominations and a target amount, return the minimum number of coins needed to make up that amount. You may use each coin denomination an unlimited number of times. If the amount cannot be made, return -1.

Sample answer outline

A strong candidate correctly identifies this as a DP problem, defines dp[i] as the minimum coins to reach amount i, and builds it bottom-up in O(amount * len(coins)) time. They handle the base case dp[0] = 0, initialize the rest to infinity, and return -1 if dp[amount] is still infinity. Greedy does not work in general (example: coins [1,3,4], amount 6: greedy picks 4+1+1 but 3+3 is better), and a strong candidate can cite this counterexample.

Reference implementation (python)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Expect these follow-ups

• How would you reconstruct which coins were actually used?
• What changes if each coin can only be used once?