Hudson River Trading interview questions & answers

16 real Hudson River Trading interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (16 Hudson River Trading questions in total).

CodingEasyHudson River TradingSoftware Engineer

1. Shortest Word Distance (LeetCode)

Model answer

The task

Given a list of words and two distinct words that occur in it, find the smallest difference between their positions.

Key idea

Scan the list once, remembering the most recent position of each target word. Whenever you see either word and have already seen the other, update the best distance.

Approach

  1. Initialize the latest positions and the best distance.
  2. Visit each word with its index.
  3. If it matches one target, update that target’s latest position.
  4. When both positions are known, update the best distance.
  5. Return the smallest distance found.
from typing import List

class Solution:
    def shortestDistance(
        self, wordsDict: List[str], word1: str, word2: str
    ) -> int:
        index1 = -1
        index2 = -1
        best = len(wordsDict)

        for i, word in enumerate(wordsDict):
            if word == word1:
                index1 = i
            elif word == word2:
                index2 = i

            if index1 != -1 and index2 != -1:
                best = min(best, abs(index1 - index2))

        return best

Complexity:

  • Time: O(n), where n is the number of words; each word is checked once.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if both target words can be the same? Track consecutive occurrences of that word and compare their indices.
  • What if there are many distance queries on the same list? Precompute each word’s sorted list of positions, then search those lists for each query.
  • What if the list is too large to fit in memory? Stream through it once while retaining the latest target positions and the best distance found so far.
CodingEasyHudson River TradingSoftware Engineer

2. Longest Common Prefix (LeetCode)

Model answer

The task

Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.

Key idea

Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.

Approach

  1. If the list is empty, return an empty string.
  2. Scan each character of the first string from left to right.
  3. For each position, compare that character with the character at the same position in every other string.
  4. If a string is too short or a character differs, return the matching prefix before that position.
  5. If all positions match, return the first string.
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Complexity:

  • Time: O(S), where S is the total number of characters inspected.
  • Space: O(1) auxiliary space, excluding the returned prefix.

Common follow-ups

  • How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
  • Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
  • What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.
CodingEasyHudson River TradingSoftware Engineer

3. Convert Integer to the Sum of Two No-Zero Integers (LeetCode)

Model answer

The task

Given a positive integer n, find two positive integers that add up to n and whose decimal representations contain no zero digits. Return the pair.

Key idea

Try each possible first addend and check whether both it and the resulting second addend contain only nonzero digits. The input’s constraints make this direct search practical.

Approach

  1. Iterate over candidate values from 1 through n - 1.
  2. Set the other addend to n - candidate.
  3. Check that neither number’s decimal representation contains '0'.
  4. Return the first valid pair.
class Solution:
    def getNoZeroIntegers(self, n: int) -> list[int]:
        # Check whether every decimal digit is nonzero.
        def has_no_zero_digits(value: int) -> bool:
            return "0" not in str(value)

        for first in range(1, n):
            second = n - first

            if has_no_zero_digits(first) and has_no_zero_digits(second):
                return [first, second]

        # The problem guarantees a valid pair exists.
        return []

Complexity:

  • Time: O(n log n), checking up to O(n) pairs and converting each to a string.
  • Space: O(log n), for the temporary decimal strings.

Common follow-ups

  • Can digit checking avoid string conversion? Yes; repeatedly take value % 10 and divide by 10, rejecting any zero digit.
  • How can the search be made faster for large n? Use problem-specific digit construction or pruning; the simple search is suited to the stated constraints.
  • Does the order of the returned pair matter? No; swapping the two valid addends preserves the sum.
CodingEasyHudson River TradingSoftware Engineer

4. Detect Pattern of Length M Repeated K or More Times (LeetCode)

Model answer

The task

Determine whether some contiguous block of length m appears consecutively at least k times in the array.

Key idea

For a repeated pattern, each element must match the element m positions later. So we can scan those comparisons and look for m * (k - 1) consecutive matches.

Approach

  1. If k is 1, any available block of length m is enough.
  2. If the array is too short to fit k blocks, return False.
  3. Scan indices where both arr[i] and arr[i + m] exist.
  4. Extend a streak when they match; reset it on a mismatch.
  5. Return True once the streak reaches the required length.
class Solution:
    def containsPattern(self, arr: list[int], m: int, k: int) -> bool:
        n = len(arr)

        if k == 1:
            return m <= n
        if m * k > n:
            return False

        needed = m * (k - 1)
        streak = 0

        for i in range(n - m):
            if arr[i] == arr[i + m]:
                streak += 1
                if streak >= needed:
                    return True
            else:
                streak = 0

        return False

Complexity:

  • Time: O(n), with one pass through the array.
  • Space: O(1), using only a few counters.

Common follow-ups

  • What if the pattern must repeat exactly k times? Check a matching window of exactly m * k elements.
  • What if the array is streamed? Keep a rolling buffer of the most recent m elements and track matching offsets.
  • What if m or k is invalid? Define input behavior explicitly, such as returning False for non-positive values.
CodingEasyHudson River TradingSoftware Engineer

5. Maximum 69 Number (LeetCode)

Model answer

The task

Given a positive integer whose digits are all 6 or 9, change at most one digit from 6 to 9 to get the largest possible value.

Key idea

The most significant digit has the greatest impact on the number. So, if a 6 exists, changing its first occurrence to 9 gives the maximum result; if not, leave the number unchanged.

Approach

  1. Convert the integer to a string so its digits can be inspected from left to right.
  2. Find the first 6.
  3. Replace it with 9 and stop.
  4. Convert the resulting string back to an integer.
class Solution:
    def maximum69Number(self, num: int) -> int:
        # Work with digits from most significant to least significant.
        digits = list(str(num))

        # The first 6 gives the greatest increase when changed to 9.
        for i, digit in enumerate(digits):
            if digit == "6":
                digits[i] = "9"
                break

        return int("".join(digits))

Complexity:

  • Time: O(d), where d is the number of digits, for scanning and constructing the result.
  • Space: O(d), for the digit list.

Common follow-ups

  • What if more than one digit may be changed? Change every 6 to 9.
  • What if the allowed change is from 9 to 6 and the goal is to minimize the number? Change the first 9 to 6.
  • What if the digits can be arbitrary, and one digit may be increased? Scan from left to right and choose the change with the greatest place-value gain.
CodingEasyHudson River TradingSoftware Engineer

6. Number of Steps to Reduce a Number to Zero (LeetCode)

Model answer

The task

Given a nonnegative integer, count how many times it takes to reach zero by halving it when it is even or subtracting one when it is odd.

Key idea

Follow the required operation directly until the number is zero. Each operation reduces the number, so the process terminates.

Approach

  1. Initialize a counter to zero.
  2. While the number is positive, check whether it is even.
  3. If even, divide it by two; otherwise, subtract one.
  4. Increment the counter after each operation.
  5. Return the counter.
class Solution:
    def numberOfSteps(self, num: int) -> int:
        steps = 0

        while num > 0:
            if num % 2 == 0:
                num //= 2
            else:
                num -= 1
            steps += 1

        return steps

Complexity:

  • Time: O(log n) for positive n; the number of operations is bounded by a constant times its bit length.
  • Space: O(1), using only a few variables.

Common follow-ups

  • Can you express the count using bit operations? For positive n, it is n.bit_length() - 1 + n.bit_count() - 1; return zero when n is zero.
  • What happens for n = 0? The loop does not run, so the answer is zero.
  • How would you handle very large integers? The same loop works with arbitrary-precision integers, though each arithmetic operation may take more than constant time.
CodingMediumHudson River TradingSoftware Engineer

7. Design Memory Allocator (LeetCode)

Model answer

The task

Design a fixed-size memory allocator that assigns contiguous free cells to an allocation ID and releases every cell belonging to a given ID. An allocation should use the first available contiguous region large enough, or report failure.

Key idea

Store each cell’s allocation ID in an array, using 0 to represent a free cell. Scan from left to right to find the first sufficiently long free run; freeing an ID is a single pass over the array.

Approach

  1. Initialize an array of n zeroes.
  2. For an allocation, scan for a run of size consecutive zeroes.
  3. When found, fill that run with mID and return its starting index.
  4. If no such run exists, return -1.
  5. To free an ID, replace every matching cell with zero and return how many cells were released.
class Allocator:
    def __init__(self, n: int):
        # Zero denotes an unallocated cell.
        self.memory = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        run_start = -1
        run_length = 0

        for index, owner in enumerate(self.memory):
            if owner == 0:
                if run_length == 0:
                    run_start = index
                run_length += 1

                if run_length == size:
                    for cell in range(run_start, run_start + size):
                        self.memory[cell] = mID
                    return run_start
            else:
                run_length = 0

        return -1

    def free(self, mID: int) -> int:
        released = 0

        for index, owner in enumerate(self.memory):
            if owner == mID:
                self.memory[index] = 0
                released += 1

        return released

Complexity:

  • Time: O(n) per operation; allocation scans the array and may mark the selected cells, while freeing scans the entire array.
  • Space: O(n) for the memory array.

Common follow-ups

  • How could allocation be faster for frequent requests? Track free intervals in an ordered structure, merging adjacent intervals when memory is freed.
  • What if a request can span noncontiguous cells? Scan for any size free cells rather than requiring a consecutive run.
  • How would you handle very large memory spaces? Use interval-based storage so work depends more on the number of allocated regions than on total capacity.
CodingMediumHudson River TradingSoftware Engineer

8. Count Unguarded Cells in the Grid (LeetCode)

Model answer

The task

Given a grid with guards and walls, count the empty cells that no guard can see. A guard sees along its row and column until a wall or another guard blocks the view.

Key idea

Mark each cell visible from a guard by scanning in four directions. Keep guards and walls distinguishable from visible cells so scans pass through already-visible cells but stop at obstacles.

Approach

  1. Create a grid to record empty cells, guards, walls, and visible cells.
  2. For each guard, scan up, down, left, and right.
  3. Mark empty cells as visible; stop a scan when it reaches a guard or wall.
  4. Count cells that are still empty.
class Solution:
    def countUnguarded(self, m: int, n: int, guards: list[list[int]],
                       walls: list[list[int]]) -> int:
        EMPTY, GUARD, WALL, VISIBLE = 0, 1, 2, 3
        grid = [[EMPTY] * n for _ in range(m)]

        for r, c in guards:
            grid[r][c] = GUARD
        for r, c in walls:
            grid[r][c] = WALL

        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        for r, c in guards:
            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                while 0 <= nr < m and 0 <= nc < n:
                    if grid[nr][nc] in (GUARD, WALL):
                        break

                    grid[nr][nc] = VISIBLE
                    nr += dr
                    nc += dc

        return sum(
            grid[r][c] == EMPTY
            for r in range(m)
            for c in range(n)
        )

Complexity:

  • Time: O(mn + G(m + n)), for initializing and counting the grid, plus directional scans from G guards.
  • Space: O(mn), for the grid.

Common follow-ups

  • How would you reduce repeated scanning in dense layouts? Consider directional sweeps that track whether a guard is currently watching each row or column.
  • What if guards had a limited viewing distance? Stop each directional scan after that many cells.
  • How should cells occupied by guards or walls affect the final count? They are obstacles, not empty cells, so exclude them.
CodingMediumHudson River TradingSoftware Engineer

9. Apply Operations to Make All Array Elements Equal to Zero (LeetCode)

Model answer

The task

Given a nonnegative integer array and a window length k, determine whether repeatedly decrementing every element in a chosen length-k subarray can make the entire array zero.

Key idea

Process positions from left to right. Once earlier choices are fixed, the current value determines exactly how many operations must begin here. Track how those operations affect later positions using a difference array.

Approach

  1. Keep a running total of the changes caused by operations already in progress.
  2. At each index, compute its remaining value after those changes.
  3. If the remaining value is negative, return False.
  4. If it is positive, start that many operations here. If a full window cannot fit, return False.
  5. Record where those operations stop affecting the array.
  6. If every position is handled, return True.
from typing import List

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        changes = [0] * (n + 1)
        running_change = 0

        for i, value in enumerate(nums):
            # Apply the net change from operations starting or ending here.
            running_change += changes[i]
            remaining = value + running_change

            if remaining < 0:
                return False

            if remaining > 0:
                # Each required operation must cover the current index.
                if i + k > n:
                    return False

                # Start enough windows to reduce this position to zero.
                running_change -= remaining
                changes[i + k] += remaining

        return True

Complexity:

  • Time: O(n), processing each array position once.
  • Space: O(n), for the difference array.

Common follow-ups

  • Can the extra space be reduced? Yes; use a single expiration array or maintain queued operation counts.
  • What if operations increase values instead? The same sweep applies, with the required operation direction and feasibility checks adjusted.
CodingMediumHudson River TradingSoftware Engineer

10. Maximum Total Importance of Roads (LeetCode)

Model answer

The task

Assign each city a distinct importance value from 1 to n. The importance of a road is the sum of the values of its two endpoint cities; maximize the total across all roads.

Key idea

A city’s value contributes once for each road connected to it, so its total contribution is its degree multiplied by its assigned value. To maximize the sum, assign larger values to cities with higher degrees.

Approach

  1. Count the number of roads connected to each city.
  2. Sort the degrees in ascending order.
  3. Pair them with values 1 through n in ascending order.
  4. Sum each degree times its paired value. Sorting both sets in the same order maximizes the sum.
class Solution:
    def maximumImportance(self, n: int, roads: list[list[int]]) -> int:
        # Count each city's degree.
        degree = [0] * n
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1

        # Pair higher degrees with higher importance values.
        degree.sort()
        return sum((i + 1) * d for i, d in enumerate(degree))

Complexity:

  • Time: O(n log n + m), where m is the number of roads; counting takes O(m) and sorting takes O(n log n).
  • Space: O(n) for the degree array and its sorted order.

Common follow-ups

  • What if importance values are arbitrary distinct numbers? Sort the values and degrees in the same order, then pair them.
  • What if the graph changes over time? Maintain degrees as edges are added or removed, then recompute the assignment when needed.
  • Can sorting be avoided? Since degrees are integers from 0 to n - 1, use degree buckets to group cities and assign values in bucket order.
CodingMediumHudson River TradingSoftware Engineer

11. Largest Combination With Bitwise AND Greater Than Zero (LeetCode)

Model answer

The task

Choose the largest subset of the given integers whose bitwise AND is nonzero.

Key idea

The AND is nonzero exactly when some bit is set in every chosen number. For each bit position, count how many numbers have that bit set; the largest such count is the answer.

Approach

  1. Find the maximum bit width among the numbers.
  2. Count the set bits at each position across all numbers.
  3. Return the largest count.
from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        if not candidates:
            return 0

        width = max(value.bit_length() for value in candidates)
        bit_counts = [0] * width

        for value in candidates:
            for bit in range(width):
                if value & (1 << bit):
                    bit_counts[bit] += 1

        return max(bit_counts, default=0)

Complexity:

  • Time: O(nW), where n is the number of values and W is the maximum bit width.
  • Space: O(W) for the per-bit counts.

Common follow-ups

  • How can this work for a stream of values? Maintain a running count for each bit and track the largest count as values arrive.
  • What if values can be negative? Specify a fixed-width integer representation first, since negative integers have different bitwise semantics across languages.
  • Can values be added and removed dynamically? Keep per-bit counts; update them when a value changes, and recompute the maximum count when needed.
CodingHardHudson River TradingSoftware Engineer

12. Maximum Score From Grid Operations (LeetCode)

Model answer

The task

The title suggests maximizing a score produced by operations on a grid. The operation rules and the exact condition for earning score are not available here, so I can’t reliably give a problem-specific solution.

Key idea

For a grid problem with operation-dependent scoring, a common strategy is to encode the relevant boundary or operation choices as DP states. Prefix sums can then make the score of a candidate region or transition efficient to calculate.

Approach

  1. Identify what information about processed rows or columns affects future choices.
  2. Define a DP state for that information.
  3. Use grid prefix sums to calculate contributions without rescanning cells.
  4. Try each valid next operation and update the corresponding state.
  5. Return the best completed state.
from typing import Callable, Iterable, TypeVar

State = TypeVar("State")

def maximize_grid_score(
    initial_states: Iterable[State],
    transitions: Callable[[State], Iterable[tuple[State, int]]],
    is_complete: Callable[[State], bool],
) -> int:
    """Generic max-score DP over states.

    A problem-specific solution must define the states, valid transitions,
    and transition scores from the operation and scoring rules.
    """
    best = {state: 0 for state in initial_states}

    # This form assumes transitions advance through an acyclic state graph.
    # Process states in a valid topological order for the specific problem.
    pending = list(best)
    index = 0

    while index < len(pending):
        state = pending[index]
        index += 1

        for next_state, gain in transitions(state):
            candidate = best[state] + gain
            if candidate > best.get(next_state, float("-inf")):
                if next_state not in best:
                    pending.append(next_state)
                best[next_state] = candidate

    answers = [score for state, score in best.items() if is_complete(state)]
    return max(answers, default=0)

Complexity:

  • Time: O(V + E), where V is the number of states and E is the number of valid transitions.
  • Space: O(V) for the DP scores and state list.

Common follow-ups

  • How can prefix sums help? They compute region sums in constant time after preprocessing.
  • What if the DP has cycles? The state model must be changed or solved with an appropriate graph algorithm.
  • How can memory be reduced? Keep only states from the previous layer if transitions advance one layer at a time.
  • What information is needed for a precise solution? The legal operation and the rule determining which cells contribute to the score.
CodingHardHudson River TradingSoftware Engineer

13. Longest Path With Different Adjacent Characters (LeetCode)

Model answer

The task

Given a tree rooted at node 0 and a character for each node, find the number of nodes in the longest path where every pair of adjacent nodes has different characters. The path may begin and end anywhere in the tree.

Key idea

For each node, compute the longest valid downward path starting there. A path passing through a node can combine its two longest valid branches from children with different characters from that node.

Approach

  1. Build a list of children for each node from the parent array.
  2. Traverse from the root to record nodes in parent-before-child order.
  3. Process that order in reverse so each node’s children are handled first.
  4. For each node, keep the two longest downward branches whose child character differs from its own.
  5. Update the best path through the node, and store its longest single branch for its parent.
class Solution:
    def longestPath(self, parent: list[int], s: str) -> int:
        n = len(parent)
        children = [[] for _ in range(n)]

        for node in range(1, n):
            children[parent[node]].append(node)

        # A parent-before-child traversal; reversing it gives postorder.
        order = [0]
        for node in order:
            order.extend(children[node])

        # down[node] is the longest valid downward path starting at node.
        down = [1] * n
        longest = 1

        for node in reversed(order):
            best1 = best2 = 0

            for child in children[node]:
                if s[child] == s[node]:
                    continue

                length = down[child]
                if length > best1:
                    best1, best2 = length, best1
                elif length > best2:
                    best2 = length

            down[node] = 1 + best1
            longest = max(longest, 1 + best1 + best2)

        return longest

Complexity:

  • Time: O(n), where n is the number of nodes; each node and edge is processed a constant number of times.
  • Space: O(n), for the children lists, traversal order, and downward-path values.

Common follow-ups

  • How would you return the actual path? Store which child produced each of the two best branches, then reconstruct both sides through the best center.
  • What if characters are replaced by arbitrary labels? Compare labels for equality in the same way.
  • What if edges have weights? Track the best two valid weighted downward branches and maximize their sum through each node.
CodingHardHudson River TradingSoftware Engineer

14. Text Justification (LeetCode)

Model answer

The task

Format a sequence of words into lines of a fixed width. Fully justify each line except the final line, which is left-justified.

Key idea

Greedily place as many words as possible on each line, counting at least one space between adjacent words. Once a line is chosen, distribute its remaining spaces as evenly as possible; any extras go into the leftmost gaps.

Approach

  1. Start a line with the next unformatted word and keep adding words while they fit with one space between each pair.
  2. If the line is the final line, or contains just one word, join with single spaces and pad on the right.
  3. Otherwise, divide the available spaces evenly across the gaps.
  4. Give one additional space to each of the leftmost gaps until the remainder is used.
  5. Repeat until all words are formatted.
from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0

        while i < len(words):
            # Find the largest group of words that fits on this line,
            # counting one mandatory space between each pair.
            j = i
            letters = 0

            while j < len(words) and letters + len(words[j]) + (j - i) <= maxWidth:
                letters += len(words[j])
                j += 1

            gaps = j - i - 1
            is_last_line = j == len(words)

            if is_last_line or gaps == 0:
                # The final line and single-word lines are left-justified.
                line = " ".join(words[i:j])
                line += " " * (maxWidth - len(line))
            else:
                total_spaces = maxWidth - letters
                spaces_per_gap, extra_spaces = divmod(total_spaces, gaps)

                parts = []
                for gap in range(gaps):
                    parts.append(words[i + gap])
                    # Earlier gaps receive any leftover spaces.
                    spaces = spaces_per_gap + (1 if gap < extra_spaces else 0)
                    parts.append(" " * spaces)

                parts.append(words[j - 1])
                line = "".join(parts)

            result.append(line)
            i = j

        return result

Complexity:

  • Time: O(n + L × W), where n is the total number of input characters, L is the number of output lines, and W is the line width.
  • Space: O(L × W) for the returned lines; O(W) additional space to build a line.

Common follow-ups

  • What if words may be hyphenated? Split long words into width-limited pieces before packing.
  • What if the last line must also be fully justified? Apply the regular gap-distribution rule to it.
  • How can this handle a streaming word source? Buffer words for the current line, then emit it as soon as the next word no longer fits.
CodingHardHudson River TradingSoftware Engineer

15. Add Edges to Make Degrees of All Nodes Even (LeetCode)

Model answer

The task

Given an undirected graph, determine whether adding at most two edges that are not already present can make every node’s degree even. Added edges cannot be self-loops.

Key idea

Adding an edge toggles the degree parity of its two endpoints. Since the number of odd-degree nodes is always even, only 0, 2, or 4 odd-degree nodes can possibly be fixed with two edges. Check the possible pairings while ensuring each proposed edge is new.

Approach

  1. Build the degree counts and a set of existing edges.
  2. If there are no odd-degree nodes, return True.
  3. If there are two, try adding the edge between them; alternatively, try connecting each to the same third node.
  4. If there are four, test all three ways to pair them, requiring both edges in a pairing to be absent.
  5. Return False if none of these options works.
class Solution:
    def isPossible(self, n: int, edges: list[list[int]]) -> bool:
        degree = [0] * (n + 1)
        existing = set()

        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
            existing.add((min(u, v), max(u, v)))

        odd = [node for node in range(1, n + 1) if degree[node] % 2]

        def has_edge(u: int, v: int) -> bool:
            return (min(u, v), max(u, v)) in existing

        if not odd:
            return True

        if len(odd) == 2:
            u, v = odd

            # One new edge fixes both odd degrees.
            if not has_edge(u, v):
                return True

            # Two new edges can connect both to a common third node.
            for x in range(1, n + 1):
                if x != u and x != v and not has_edge(u, x) and not has_edge(v, x):
                    return True
            return False

        if len(odd) == 4:
            a, b, c, d = odd
            pairings = [
                ((a, b), (c, d)),
                ((a, c), (b, d)),
                ((a, d), (b, c)),
            ]

            return any(
                not has_edge(*first) and not has_edge(*second)
                for first, second in pairings
            )

        # Two edges can fix at most four odd-degree nodes.
        return False

Complexity:

  • Time: O(n + m), where m is the number of existing edges.
  • Space: O(n + m) for degree counts and the edge set.

Common follow-ups

  • What if more edges may be added? The search becomes a larger parity-correction problem; model candidate added edges as parity changes and consider matching or flow techniques.
  • What if added edges have different costs? Optimize the choice of parity-correcting edges, typically by reducing the problem to a minimum-cost matching formulation.
  • Why can there not be an odd number of odd-degree nodes? The sum of all degrees equals twice the number of edges, so it is even.
CodingHardHudson River TradingSoftware Engineer

16. Block Placement Queries (LeetCode)

Model answer

The task

Process queries that add obstacle points on a number line or ask whether a block of a given size can fit within the interval from 0 to a specified coordinate without covering an obstacle. Return a Boolean answer for each placement query.

Key idea

Keep the free gap ending at each obstacle, and track the maximum such gap with a segment tree. For a placement query, also check the final gap from the last obstacle at or before the limit to the limit itself.

Approach

  1. Coordinate-compress all coordinates mentioned in the queries.
  2. Use a Fenwick tree to track which compressed coordinates currently contain obstacles.
  3. On insertion, find the neighboring obstacles; update the gap ending at the new obstacle and the gap ending at its successor.
  4. For a placement query, take the maximum stored gap up to its coordinate and compare it with the trailing gap.
from typing import List

class Fenwick:
    def __init__(self, n: int) -> None:
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, end: int) -> int:
        """Count in indices [0, end)."""
        total = 0
        while end > 0:
            total += self.tree[end]
            end -= end & -end
        return total

    def kth(self, rank: int) -> int:
        """Index of the rank-th active item, using 1-based rank."""
        index = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            candidate = index + step
            if candidate <= self.n and self.tree[candidate] < rank:
                index = candidate
                rank -= self.tree[candidate]
            step >>= 1
        return index

class MaxSegmentTree:
    def __init__(self, n: int) -> None:
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

    def set(self, index: int, value: int) -> None:
        index += self.size
        self.tree[index] = value
        index //= 2
        while index:
            self.tree[index] = max(self.tree[2 * index],
                                   self.tree[2 * index + 1])
            index //= 2

    def query(self, left: int, right: int) -> int:
        """Maximum over indices in [left, right)."""
        left += self.size
        right += self.size
        result = 0
        while left < right:
            if left & 1:
                result = max(result, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result = max(result, self.tree[right])
            left //= 2
            right //= 2
        return result

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        coords = sorted({query[1] for query in queries})
        index_of = {x: i for i, x in enumerate(coords)}
        n = len(coords)

        active = Fenwick(n)
        gaps = MaxSegmentTree(n)
        answers = []

        for query in queries:
            if query[0] == 1:
                x = query[1]
                i = index_of[x]

                # Ignore a repeated insertion.
                if active.prefix_sum(i + 1) == active.prefix_sum(i):
                    before = active.prefix_sum(i)
                    total = active.prefix_sum(n)

                    pred_i = active.kth(before) if before else None
                    succ_i = active.kth(before + 1) if before < total else None

                    prev_x = coords[pred_i] if pred_i is not None else 0
                    gaps.set(i, x - prev_x)

                    if succ_i is not None:
                        gaps.set(succ_i, coords[succ_i] - x)

                    active.add(i, 1)

            else:
                x, size = query[1], query[2]
                i = index_of[x]

                # Last obstacle at or before x determines the trailing gap.
                count = active.prefix_sum(i + 1)
                prev_i = active.kth(count) if count else None
                prev_x = coords[prev_i] if prev_i is not None else 0
                trailing_gap = x - prev_x

                best_gap = max(gaps.query(0, i + 1), trailing_gap)
                answers.append(best_gap >= size)

        return answers

Complexity:

  • Time: O(q log q), for coordinate compression and logarithmic tree operations per query.
  • Space: O(q), for compressed coordinates and the trees.

Common follow-ups

  • How would you handle obstacle removal? Update the two affected neighboring gaps when removing an obstacle.
  • What if coordinates are too large to compress offline? Use a dynamic segment tree over the coordinate range.
  • What if blocks must fit in a specified subinterval? Query gaps intersecting that interval and account for its clipped boundaries.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions