Susquehanna (SIG) interview questions & answers

10 real Susquehanna (SIG) interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (10 Susquehanna (SIG) questions in total).

CodingMediumSusquehanna (SIG)Software Engineer

1. 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.
CodingMediumSusquehanna (SIG)Software Engineer

2. Restore the Array From Adjacent Pairs (LeetCode)

Model answer

The task

Reconstruct an array from the unordered pairs of values that were next to each other in it. Either of the two possible orientations is acceptable.

Key idea

Treat each pair as an undirected edge in a graph. Since the original array forms a path, its endpoints are the vertices with only one neighbor; start at either endpoint and walk along the path.

Approach

  1. Build an adjacency list from the pairs.
  2. Find a value with exactly one neighbor and use it as the starting value.
  3. Append the current value, then move to its neighbor other than the previous value.
  4. Stop when there is no next neighbor.
from collections import defaultdict
from typing import List

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        graph = defaultdict(list)

        for a, b in adjacentPairs:
            graph[a].append(b)
            graph[b].append(a)

        # A path has two endpoints, each with exactly one neighbor.
        start = next(value for value, neighbors in graph.items()
                     if len(neighbors) == 1)

        result = []
        previous = None
        current = start

        while True:
            result.append(current)

            # Each vertex has at most two neighbors; skip the one just visited.
            next_value = next(
                (neighbor for neighbor in graph[current]
                 if neighbor != previous),
                None,
            )
            if next_value is None:
                break

            previous, current = current, next_value

        return result

Complexity:

  • Time: O(n), where n is the number of values; each edge is processed a constant number of times.
  • Space: O(n) for the adjacency list and the returned array.

Common follow-ups

  • What if either orientation is required? Start from the other endpoint to produce the reversed array.
  • How can you verify the input forms one path? Check that exactly two vertices have degree one, all others have degree two, and a traversal visits every vertex.
  • Can the traversal be recursive? Yes, but an iterative walk avoids recursion-depth limits on long paths.
CodingMediumSusquehanna (SIG)Software Engineer

3. Number of Black Blocks (LeetCode)

Model answer

The task

For a grid with some black cells, count how many 2×2 subgrids contain exactly 0, 1, 2, 3, or 4 black cells. Return those five counts in order.

Key idea

A black cell can affect at most four 2×2 subgrids. Count black cells only for those subgrids, then calculate the number of zero-black subgrids from the total.

Approach

  1. Consider each black cell and the four possible top-left corners of a 2×2 subgrid containing it.
  2. Ignore corners that would place the subgrid outside the grid.
  3. Use a hash map to count black cells for each valid top-left corner.
  4. Initialize the zero-black count using the total number of possible subgrids.
  5. Add each recorded subgrid to the count matching its number of black cells.
from collections import defaultdict
from typing import List

class Solution:
    def countBlackBlocks(
        self, m: int, n: int, coordinates: List[List[int]]
    ) -> List[int]:
        black_count = defaultdict(int)

        for row, col in coordinates:
            # Each valid top-left corner defines a 2x2 block
            # that contains this black cell.
            for top in (row - 1, row):
                for left in (col - 1, col):
                    if 0 <= top < m - 1 and 0 <= left < n - 1:
                        black_count[(top, left)] += 1

        total_blocks = max(0, m - 1) * max(0, n - 1)
        result = [0] * 5
        result[0] = total_blocks - len(black_count)

        for count in black_count.values():
            result[count] += 1

        return result

Complexity:

  • Time: O(k), where k is the number of black cells; each checks at most four blocks.
  • Space: O(k), for the counts of affected 2×2 blocks.

Common follow-ups

  • What if black-cell coordinates may repeat? Deduplicate them first so a cell is not counted more than once.
  • What if the grid is very large but sparse? This method already avoids storing or scanning the full grid.
  • What if blocks have a different fixed size? Enumerate each valid block that can contain a given cell; the number checked depends on the block dimensions.
CodingMediumSusquehanna (SIG)Software Engineer

4. Rotating the Box (LeetCode)

Model answer

The task

Given a grid containing stones, obstacles, and empty cells, let the stones fall to the right within their obstacle-separated row segments, then return the grid rotated clockwise.

Key idea

Apply gravity before rotation: in each row, compact stones to the right without moving them past obstacles. Then map each cell to its position in the clockwise-rotated grid.

Approach

  1. For each row, scan from right to left and track the next position where a stone can settle.
  2. When an obstacle is found, reset that position to just left of the obstacle.
  3. When a stone is found, move it to the tracked position and advance the position left.
  4. Allocate a grid with swapped dimensions and copy each cell to its rotated position.
from typing import List

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        rows, cols = len(box), len(box[0])

        # Let each row's stones fall to the right, within obstacle segments.
        for r in range(rows):
            write = cols - 1

            for c in range(cols - 1, -1, -1):
                if box[r][c] == "*":
                    write = c - 1
                elif box[r][c] == "#":
                    box[r][c] = "."
                    box[r][write] = "#"
                    write -= 1

        # Rotate the settled box clockwise.
        rotated = [[""] * rows for _ in range(cols)]
        for r in range(rows):
            for c in range(cols):
                rotated[c][rows - 1 - r] = box[r][c]

        return rotated

Complexity:

  • Time: O(rows × cols), since each cell is processed a constant number of times.
  • Space: O(rows × cols) for the returned rotated grid.

Common follow-ups

  • Preserve the input grid: make a copy before applying gravity.
  • Rotate counterclockwise: change the cell-to-output index mapping.
  • Reduce extra space: discuss an in-place rotation when the matrix is square; gravity and rectangular dimensions still need consideration.
CodingMediumSusquehanna (SIG)Software Engineer

5. Find the Length of the Longest Common Prefix (LeetCode)

Model answer

The task

Given two arrays of integers, find the greatest length of a decimal prefix shared by an integer from each array. Return 0 if no pair shares a prefix.

Key idea

A shared prefix is also a prefix of some number in the first array. Store those prefixes in a hash set, then check prefixes of numbers in the second array. The longest match found is the answer.

Approach

  1. Convert each number in the first array to a string.
  2. Add each nonempty prefix of each string to a set.
  3. Convert each number in the second array to a string.
  4. Check its prefixes against the set and track the greatest matching length.
  5. Return the greatest length, or 0 if there was no match.
class Solution:
    def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
        # Record every decimal prefix found in the first array.
        prefixes = set()
        for number in arr1:
            text = str(number)
            for end in range(1, len(text) + 1):
                prefixes.add(text[:end])

        longest = 0

        # Check prefixes from the second array against the recorded set.
        for number in arr2:
            text = str(number)
            for end in range(1, len(text) + 1):
                if text[:end] in prefixes:
                    longest = max(longest, end)

        return longest

Complexity:

  • Time: O(D), where D is the total number of digits across both arrays; creating prefixes copies strings, but the numbers have bounded digit length.
  • Space: O(D), for the stored prefixes.

Common follow-ups

  • Can a trie solve this? Yes; insert numbers from one array and walk each number from the other, tracking the deepest match.
  • What if the arrays are highly imbalanced? Build prefixes from the array with fewer total digits to reduce stored space.
  • What if numbers can be negative? Define whether the sign participates in prefixes, then normalize or handle the sign separately before comparing digits.
CodingMediumSusquehanna (SIG)Software Engineer

6. Minimum Absolute Difference Between Elements With Constraint (LeetCode)

Model answer

The task

Find the smallest absolute difference between two values whose indices are at least x apart. The two indices must be distinct.

Key idea

Sweep through the array, keeping a frequency structure of values at indices that are far enough behind the current index. For each value, only its nearest eligible predecessor and successor in sorted value order can give the smallest difference.

Approach

  1. Coordinate-compress the values so they can be stored in a Fenwick tree.
  2. Sweep indices from left to right, adding newly eligible earlier values to the tree.
  3. Use Fenwick prefix counts to locate the nearest stored value at or below the current value, and the nearest one above it.
  4. Update the minimum difference using those candidates.
from typing import List

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

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

    def prefix_sum(self, index: int) -> int:
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def find_by_order(self, order: int) -> int:
        """Return the 1-based index of the order-th stored value."""
        index = 0
        step = 1 << (self.size.bit_length() - 1)

        while step:
            next_index = index + step
            if next_index <= self.size and self.tree[next_index] < order:
                index = next_index
                order -= self.tree[next_index]
            step >>= 1

        return index + 1

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        values = sorted(set(nums))
        ranks = {value: i + 1 for i, value in enumerate(values)}
        counts = FenwickTree(len(values))

        best = float("inf")
        inserted_through = -1
        total_stored = 0

        for i, value in enumerate(nums):
            # Only earlier indices are eligible; this also handles x == 0.
            cutoff = min(i - x, i - 1)
            while inserted_through < cutoff:
                inserted_through += 1
                counts.add(ranks[nums[inserted_through]], 1)
                total_stored += 1

            if total_stored == 0:
                continue

            rank = ranks[value]
            at_or_below = counts.prefix_sum(rank)

            if at_or_below:
                candidate_rank = counts.find_by_order(at_or_below)
                best = min(best, value - values[candidate_rank - 1])

            if at_or_below < total_stored:
                candidate_rank = counts.find_by_order(at_or_below + 1)
                best = min(best, values[candidate_rank - 1] - value)

        return best

Complexity:

  • Time: O(n log n), for coordinate compression and Fenwick operations.
  • Space: O(n), for compressed values and Fenwick counts.

Common follow-ups

  • How would you implement this with an ordered set? Insert eligible values and query the lower bound and its predecessor.
  • What if the index gap must be exactly x? Compare only with nums[i - x].
  • Can duplicates be handled? Yes; the Fenwick tree stores frequencies, so repeated values are preserved.
CodingMediumSusquehanna (SIG)Software Engineer

7. Rotate Image (LeetCode)

Model answer

The task

Rotate a square matrix 90 degrees clockwise, modifying the matrix in place.

Key idea

A clockwise rotation can be split into two operations: transpose the matrix, then reverse each row. Together, these move every value to its rotated position without allocating another matrix.

Approach

  1. Transpose the matrix by swapping entries across its main diagonal.
  2. Visit each row and reverse it in place.
  3. Return nothing; the input matrix holds the result.
class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)

        # Transpose across the main diagonal.
        for row in range(n):
            for col in range(row + 1, n):
                matrix[row][col], matrix[col][row] = (
                    matrix[col][row],
                    matrix[row][col],
                )

        # Reverse each row to complete the clockwise rotation.
        for row in matrix:
            row.reverse()

Complexity:

  • Time: O(n²), since each matrix entry is processed a constant number of times.
  • Space: O(1), because the rotation is performed in place.

Common follow-ups

  • How would you rotate 90 degrees counterclockwise? Transpose, then reverse each column instead of each row.
  • How would you rotate 180 degrees? Reverse the order of rows and reverse each row.
  • What if the matrix is not square? A rectangular matrix generally cannot be rotated in place without changing its dimensions; use a new matrix or a more involved cycle-based method when dimensions permit.
CodingHardSusquehanna (SIG)Software Engineer

8. 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.
CodingHardSusquehanna (SIG)Software Engineer

9. Find Median from Data Stream (LeetCode)

Model answer

The task

Design a data structure that accepts numbers one at a time and can return the median of all numbers seen so far. The median is the middle value for an odd count, or the average of the two middle values for an even count.

Key idea

Keep the lower half of the values in a max-heap and the upper half in a min-heap. Maintain heap sizes so the lower half has either the same number of elements as the upper half or exactly one more.

Approach

  1. Store the lower half as negated values in Python’s min-heap; store the upper half normally.
  2. Insert each new value into the lower heap.
  3. Move the largest lower-half value to the upper heap to preserve ordering.
  4. If the upper heap becomes larger, move its smallest value back to the lower heap.
  5. Return the lower heap’s top for an odd count, or average the two heap tops for an even count.
import heapq

class MedianFinder:
    def __init__(self):
        # Negated values make this a max-heap.
        self.lower = []
        # A regular min-heap.
        self.upper = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        # Ensure every value in lower is <= every value in upper.
        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        # Keep lower the same size as upper, or one element larger.
        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def findMedian(self) -> float:
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

Complexity:

  • Time: addNum is O(log n) due to heap operations; findMedian is O(1).
  • Space: O(n) to store all numbers across the two heaps.

Common follow-ups

  • How would you support removing values? Use lazy deletion with delayed removals, pruning heap tops as needed.
  • What if numbers arrive in a bounded integer range? A frequency array can track counts and locate the middle ranks.
  • Can this be distributed across machines? Maintain ordered partitions or quantile summaries, then combine counts to find the middle ranks.
CodingHardSusquehanna (SIG)Software Engineer

10. 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