General Motors interview questions & answers

14 real General Motors interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (14 General Motors questions in total).

CodingMediumGeneral MotorsSoftware Engineer

1. Number of Islands (LeetCode)

Model answer

The task

Given a grid of land and water, count the groups of connected land cells. Cells connect horizontally or vertically, not diagonally.

Key idea

Each group is one island. Scan the grid, and whenever an unvisited land cell is found, count a new island and explore its entire connected region. Mark cells as visited when adding them to the search queue so no cell is processed more than once.

Approach

  1. Return 0 if the grid is empty.
  2. Scan every cell in the grid.
  3. When a land cell is found, increment the island count and start a breadth-first search from it.
  4. During the search, mark each discovered land cell as water and add its in-bounds land neighbors to the queue.
  5. Return the island count after the scan is complete.
from collections import deque
from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        islands = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1":
                    continue

                islands += 1
                grid[row][col] = "0"
                queue = deque([(row, col)])

                while queue:
                    current_row, current_col = queue.popleft()

                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_row = current_row + dr
                        next_col = current_col + dc

                        if (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                            and grid[next_row][next_col] == "1"
                        ):
                            # Mark when enqueuing to avoid duplicate work.
                            grid[next_row][next_col] = "0"
                            queue.append((next_row, next_col))

        return islands

Complexity: Time: O(rows * cols), since each cell is examined at most a constant number of times.

Complexity: Space: O(rows * cols) in the worst case for the BFS queue.

Common follow-ups

  • Preserve the input grid? Track visited cells in a separate set instead of changing land cells to water.
  • Use depth-first search instead? Recursively or iteratively explore the four neighbors; iterative DFS avoids recursion-depth concerns.
  • Count diagonally connected land as part of the same island? Include the four diagonal directions in the neighbor list.
CodingMediumGeneral MotorsSoftware Engineer

2. Implement Trie (Prefix Tree) (LeetCode)

Model answer

The task

Design a prefix tree that supports inserting strings, checking whether a complete string has been inserted, and checking whether any inserted string begins with a given prefix.

Key idea

Represent each character as an edge to a child node. Mark the node at the end of each inserted string, so a path can indicate a prefix without necessarily representing a complete word.

Approach

  1. Give each node a map from characters to child nodes and a flag indicating whether a word ends there.
  2. For insertion, create any missing nodes along the string’s path.
  3. Mark the final node as the end of a word.
  4. For both searches, follow the path character by character; if a child is missing, return False.
  5. A full-word search also checks the final node’s end-of-word flag; a prefix search only checks that the path exists.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, text: str):
        node = self.root

        for char in text:
            if char not in node.children:
                return None
            node = node.children[char]

        return node

Complexity:

  • Time: O(L) per operation, where L is the length of the word or prefix being processed.
  • Space: O(S) for the trie, where S is the total number of characters stored across distinct paths.

Common follow-ups

  • How would you delete a word? Clear its end-of-word flag, then remove nodes that are no longer needed.
  • How would you support case-insensitive matching? Normalize strings consistently, such as by converting them to lowercase.
  • How can you reduce memory use for sparse or large alphabets? Use compact child storage, such as a radix trie or a sorted edge list.
CodingMediumGeneral MotorsSoftware Engineer

3. LRU Cache (LeetCode)

Model answer

The task

Design a cache with a fixed capacity that supports retrieving and inserting key-value pairs. When an insertion exceeds capacity, evict the item that has gone unused for the longest time.

Key idea

Use a hash map for direct key lookup and a doubly linked list to track recency. Keep the most recently used item at the front; the least recently used item is at the back.

Approach

  1. Create a map from keys to their linked-list nodes.
  2. Use dummy head and tail nodes so items can be added or removed without special cases at the ends.
  3. On a successful get, move the node to the front and return its value; return -1 if the key is absent.
  4. On put, update and promote an existing node, or add a new node at the front.
  5. If the cache is over capacity, remove the node just before the tail and delete its key from the map.
class _Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}

        # Items are stored between these sentinels.
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _make_most_recent(self, node: _Node) -> None:
        self._remove(node)
        self._add_to_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._make_most_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)

        if node is not None:
            node.value = value
            self._make_most_recent(node)
            return

        node = _Node(key, value)
        self.nodes[key] = node
        self._add_to_front(node)

        if len(self.nodes) > self.capacity:
            least_recent = self.tail.prev
            self._remove(least_recent)
            del self.nodes[least_recent.key]

Complexity:

  • Time: O(1) for get and put; map and list operations take constant time.
  • Space: O(capacity); the map and list store at most the cache’s capacity of entries.

Common follow-ups

  • How would you make the cache thread-safe? Protect operations with a lock.
  • What if entries expire after a time-to-live? Track expiration times and remove expired entries during access or with a cleanup mechanism.
  • How would you support eviction by frequency instead of recency? Track access counts and organize entries by frequency.
CodingMediumGeneral MotorsSoftware Engineer

4. Number of Connected Components in an Undirected Graph (LeetCode)

Model answer

The task

Given an undirected graph with vertices numbered from 0 to n - 1 and a list of edges, return the number of connected components. Isolated vertices each count as their own component.

Key idea

Traverse the graph, starting a new DFS whenever an unvisited vertex is found. Each such traversal visits exactly one connected component.

Approach

  1. Build an adjacency list from the edges.
  2. Create a set of vertices already visited and initialize the component count to zero.
  3. For each vertex, skip it if it has already been visited.
  4. Otherwise, increment the count and use an iterative DFS to mark every reachable vertex.
  5. Return the count.
class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        # Build an adjacency list for the undirected graph.
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()
        components = 0

        for start in range(n):
            if start in visited:
                continue

            # This vertex begins a new connected component.
            components += 1
            stack = [start]
            visited.add(start)

            while stack:
                node = stack.pop()
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)

        return components

Complexity:

  • Time: O(n + m), where m is the number of edges; each vertex and edge is processed a constant number of times.
  • Space: O(n + m), for the adjacency list, visited set, and DFS stack.

Common follow-ups

  • How would you use Union-Find instead? Union the endpoints of each edge, then count the remaining distinct roots.
  • What if edges are added between queries? Use Union-Find to maintain connectivity efficiently as edges arrive.
  • What if the graph is directed? Clarify whether the goal is weakly connected components or strongly connected components; use an appropriate traversal algorithm.
CodingMediumGeneral MotorsSoftware Engineer

5. Dot Product of Two Sparse Vectors (LeetCode)

Model answer

The task

Create a sparse-vector representation that can compute the dot product of two vectors efficiently. Most entries may be zero, so avoid processing zero values during each query.

Key idea

Store only nonzero values, keyed by their indices. For a dot product, iterate over the smaller stored map and look up each index in the larger one; only shared indices contribute.

Approach

  1. On construction, scan the input vector and store each nonzero value with its index.
  2. In dotProduct, choose the smaller of the two maps to iterate over.
  3. For each stored index, multiply its value by the other vector’s value at that index, if present.
  4. Sum the products and return the result.
class SparseVector:
    def __init__(self, nums: list[int]):
        # Store only nonzero entries: index -> value.
        self.values = {
            index: value
            for index, value in enumerate(nums)
            if value != 0
        }

    def dotProduct(self, vec: "SparseVector") -> int:
        # Iterate over fewer entries and probe the other vector.
        smaller, larger = (
            (self.values, vec.values)
            if len(self.values) <= len(vec.values)
            else (vec.values, self.values)
        )

        total = 0
        for index, value in smaller.items():
            total += value * larger.get(index, 0)

        return total

Complexity:

  • Time: O(min(k1, k2)) per dot product, where k1 and k2 are the nonzero counts; hash lookups are expected O(1).
  • Space: O(k) per vector, where k is its number of nonzero entries.

Common follow-ups

  • What if the nonzero entries are stored as sorted index-value pairs? Use two pointers to match indices in O(k1 + k2) time.
  • What if one vector is dense? Iterate over the sparse vector and index directly into the dense one.
  • What if many dot products use the same vectors? Keep the sparse representation and reuse it; consider caching results for repeated vector pairs.
CodingMediumGeneral MotorsSoftware Engineer

6. Merge Intervals (LeetCode)

Model answer

The task

Given a collection of intervals, combine every pair that overlaps and return the resulting non-overlapping intervals. The result should be ordered by starting point.

Key idea

Sort intervals by their start. Then scan once, keeping the most recently merged interval; each next interval either extends it or starts a new one.

Approach

  1. Sort the intervals by their start value.
  2. Initialize the result with the first interval, if any.
  3. For each remaining interval, compare its start with the end of the last result interval.
  4. If they overlap, update that end to the larger of the two ends.
  5. Otherwise, append the interval as a new result.
from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        intervals.sort(key=lambda interval: interval[0])
        merged = [intervals[0]]

        for start, end in intervals[1:]:
            # The intervals overlap, so extend the last merged interval.
            if start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                # No overlap: this interval begins a new merged range.
                merged.append([start, end])

        return merged

Complexity: Time: O(n log n), dominated by sorting n intervals.

Complexity: Space: O(n) for the merged result; sorting may also use up to O(n) space.

Common follow-ups

  • What if intervals that only touch at an endpoint should remain separate? Use start < merged[-1][1] as the overlap test.
  • How would you merge intervals as they arrive in sorted order? Skip sorting and apply the same scan, processing each interval once.
  • What if intervals are inserted one at a time into an already merged collection? Use binary search to find the insertion point, then merge neighboring overlaps.
CodingMediumGeneral MotorsSoftware Engineer

7. Minimum Path Sum (LeetCode)

Model answer

The task

Find the minimum total of the cell values along a path from the top-left to the bottom-right of a grid. Each step can move only right or down.

Key idea

The best path to any cell must arrive from either the cell above or the cell to its left. Keep only one row of dynamic-programming values, updating it as the grid is traversed.

Approach

  1. Return 0 if the grid is empty.
  2. Create a one-dimensional DP array, initialized so that only the starting position is reachable.
  3. Visit cells row by row, adding each cell’s value to the smaller reachable path total from above or the left.
  4. Return the DP value for the bottom-right cell.
class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        if not grid or not grid[0]:
            return 0

        columns = len(grid[0])
        # dp[j] stores the minimum path sum to the current row's column j.
        dp = [float("inf")] * columns
        dp[0] = 0

        for row in grid:
            for j, value in enumerate(row):
                from_left = dp[j - 1] if j > 0 else float("inf")
                # Before this update, dp[j] is the value from above.
                dp[j] = value + min(dp[j], from_left)

        return dp[-1]

Complexity:

  • Time: O(mn), where m and n are the grid dimensions; each cell is processed once.
  • Space: O(n), for the DP array holding one row of values.

Common follow-ups

  • What if moves in all four directions are allowed? Use a shortest-path algorithm such as Dijkstra’s, since the simple topological DP no longer applies.
  • What if the grid is too wide for memory? If allowed, reuse the grid itself for DP and use O(1) extra space.
  • How would you return the actual path, not just its sum? Store each cell’s chosen predecessor, then backtrack from the destination.
CodingMediumGeneral MotorsSoftware Engineer

8. Number of Steps to Reduce a Number in Binary Representation to One (LeetCode)

Model answer

The task

Given a number as a binary string, count the operations needed to reduce it to one. An even value is halved; an odd value is increased by one.

Key idea

Avoid converting the string to an integer, which may be too large. Scan from the least significant bit toward the leading 1, tracking whether an increment has carried into the current bit.

Approach

  1. Start with zero operations and no carry.
  2. Visit each bit except the leading bit, moving right to left.
  3. Add the carry to the current bit to determine its effective value.
  4. If it is odd (1), incrementing and then halving takes two operations; keep the carry.
  5. Otherwise, halving takes one operation.
  6. Add one final operation if a carry remains at the leading bit.
class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0

        # The leading 1 is handled by the final carry check.
        for i in range(len(s) - 1, 0, -1):
            bit_with_carry = int(s[i]) + carry

            if bit_with_carry == 1:
                # Odd: increment, then divide by two.
                steps += 2
                carry = 1
            else:
                # Even: divide by two.
                steps += 1

        return steps + carry

Complexity:

  • Time: O(n), where n is the length of the binary string.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if the string has leading zeros? Strip them first, while treating an all-zero input according to the desired input rules.
  • Why not parse the string as an integer? The value may exceed the range supported by fixed-width integer types.
  • Can this be processed as a stream? Yes; retain the relevant carry state while processing bits from least significant to most significant.
CodingMediumGeneral MotorsSoftware Engineer

9. Minimum Deletions to Make Character Frequencies Unique (LeetCode)

Model answer

The task

Given a string, delete as few characters as possible so that every character remaining in it has a different frequency. A character may be deleted entirely.

Key idea

Process character frequencies from largest to smallest. For each frequency, reduce it only until it is positive and not already used; this preserves larger frequencies when choices conflict.

Approach

  1. Count each character’s frequency.
  2. Sort the frequencies in descending order.
  3. Track frequencies already assigned to a character.
  4. For each frequency, decrement it while it conflicts with a used frequency.
  5. Count each decrement as a deletion, and record the remaining positive frequency.
from collections import Counter

class Solution:
    def minDeletions(self, s: str) -> int:
        frequencies = sorted(Counter(s).values(), reverse=True)
        used = set()
        deletions = 0

        for frequency in frequencies:
            while frequency > 0 and frequency in used:
                frequency -= 1
                deletions += 1

            if frequency > 0:
                used.add(frequency)

        return deletions

Complexity:

  • Time: O(n + k log k), where counting takes O(n) and sorting takes O(k log k) for k distinct characters.
  • Space: O(k), for the frequency counts and set of used frequencies.

Common follow-ups

  • What if deleting a character entirely is forbidden? Keep frequencies at least 1 and check whether a unique assignment is possible.
  • Can the same method handle a fixed small alphabet? Yes; count frequencies in an array and sort its nonzero entries.
  • Why process frequencies in descending order? It gives larger counts priority, avoiding deletions that could be saved by reducing a smaller count instead.
CodingHardGeneral MotorsSoftware Engineer

10. Guess the Word (LeetCode)

Model answer

The task

Guess a hidden word by making a limited number of guesses. After each guess, the game reports how many characters match the hidden word in the same positions.

Key idea

Choose each guess to split the remaining candidates as evenly as possible. For every possible guess, count how many candidates would produce each feedback score; minimize the size of the largest group.

Approach

  1. Start with every word as a possible hidden word.
  2. For each turn, score every remaining candidate as a guess by finding its largest feedback group.
  3. Guess the candidate with the smallest such group.
  4. Use the returned score to discard candidates that would not produce the same feedback.
  5. Stop if the guess is correct or the turn limit is reached.
from typing import List

class Solution:
    def findSecretWord(self, wordlist: List[str], master: "Master") -> None:
        candidates = wordlist[:]
        word_length = len(wordlist[0])

        for _ in range(10):
            best_guess = None
            smallest_largest_group = float("inf")

            # Find the guess whose worst possible feedback leaves
            # the fewest remaining candidates.
            for guess in candidates:
                groups = [0] * (word_length + 1)

                for candidate in candidates:
                    matches = sum(
                        a == b for a, b in zip(guess, candidate)
                    )
                    groups[matches] += 1

                worst_group = max(groups)
                if worst_group < smallest_largest_group:
                    smallest_largest_group = worst_group
                    best_guess = guess

            score = master.guess(best_guess)

            if score == word_length:
                return

            # Keep only words consistent with the observed feedback.
            candidates = [
                word for word in candidates
                if sum(a == b for a, b in zip(best_guess, word)) == score
            ]

Complexity:

  • Time: O(G · N² · L), where G is the turn limit, N is the number of candidates, and L is the word length.
  • Space: O(N), for the candidate list and feedback-group counts.

Common follow-ups

  • What if multiple guesses tie? Choose randomly among them to vary the search strategy.
  • Can repeated comparisons be avoided? Precompute pairwise match counts, trading O(N²) space for faster turn processing.
  • Could guesses come from outside the candidate set? Yes; evaluate all allowed words as guesses while grouping only the remaining candidates.
CodingHardGeneral MotorsSoftware Engineer

11. Minimum Possible Maximum Waiting Time (LeetCode)

Model answer

The task

The title suggests choosing among feasible decisions to minimize the largest waiting time. The title and tags don’t specify what the decisions or waiting-time rules are, so a problem-specific recurrence or function signature would be guesswork.

Key idea

A common formulation is a minimax dynamic program: for each state, choose the option whose worst waiting time is smallest. If an option incurs waiting time w and leads to another state, its total cost is max(w, cost_of_next_state).

Approach

  1. Represent each state’s legal choices as transitions to other states, each labeled with its waiting time.
  2. Use memoization so each state is solved once.
  3. For each transition, combine its waiting time with the best result from the next state using max.
  4. Choose the transition with the smallest combined value.
  5. This generic version assumes the state graph is acyclic; the exact problem may require different states or transitions.
from functools import lru_cache
from math import inf
from typing import Sequence

def minimum_bottleneck_wait(
    transitions: Sequence[Sequence[tuple[int, int]]],
    start: int,
    goal: int,
) -> float:
    """Find the minimum possible maximum edge wait on a path from start to goal.

    Each transitions[state] entry is (next_state, waiting_time).
    This is a generic minimax-DP pattern, not a problem-specific signature.
    """
    visiting = set()

    @lru_cache(maxsize=None)
    def solve(state: int) -> float:
        if state == goal:
            return 0

        if state in visiting:
            raise ValueError("The transition graph must be acyclic")

        visiting.add(state)
        best = inf

        for next_state, waiting_time in transitions[state]:
            remainder = solve(next_state)
            best = min(best, max(waiting_time, remainder))

        visiting.remove(state)
        return best

    return solve(start)

Complexity:

  • Time: O(V + E), with each state and transition processed once.
  • Space: O(V + E), including memoized results, recursion, and the transition representation.

Common follow-ups

  • What if the state graph has cycles? Use a minimax shortest-path algorithm, such as Dijkstra’s algorithm with max as the path-combination operation.
  • What if choices depend on earlier decisions? Include the relevant history in the DP state.
  • How can the actual schedule be recovered? Store the minimizing transition for each state and follow those choices from the start.
CodingHardGeneral MotorsSoftware Engineer

12. Serialize and Deserialize Binary Tree (LeetCode)

Model answer

The task

Design a reversible encoding for a binary tree: convert it to a string, then reconstruct the same tree from that string. The encoding must preserve both node values and the shape of the tree.

Key idea

Use preorder traversal and include a special marker for every missing child. Those markers make the structure unambiguous, even when nodes have one child or values repeat.

Approach

  1. Traverse the tree in preorder: node, left, right.
  2. Append each node’s value to the output; append # for a missing node.
  3. Join the tokens with commas to produce the serialized string.
  4. To deserialize, read tokens in order. A # represents an empty subtree; otherwise, create a node.
  5. Recursively build that node’s left and right subtrees from the following tokens.
class Codec:
    def serialize(self, root):
        """Encode a tree as comma-separated preorder tokens."""
        tokens = []

        def preorder(node):
            if node is None:
                tokens.append("#")
                return

            tokens.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return ",".join(tokens)

    def deserialize(self, data):
        """Reconstruct a tree from preorder tokens."""
        tokens = iter(data.split(","))

        def build():
            token = next(tokens)
            if token == "#":
                return None

            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node

        return build()

Complexity:

  • Time: O(n), where n is the number of nodes; each node and null child is processed once.
  • Space: O(n) for the serialized tokens, with O(h) recursive call space for tree height h.

Common follow-ups

  • How would you use breadth-first traversal instead? Emit nodes level by level, including null markers, and parse them with a queue.
  • What if node values can contain commas or the null marker? Use an escaping scheme or a length-prefixed token format.
  • How would you handle malformed serialized data? Validate token counts and structure, and report an error for missing or unused tokens.
CodingHardGeneral MotorsSoftware Engineer

13. Maximum Sum of 3 Non-Overlapping Subarrays (LeetCode)

Model answer

The task

Choose three non-overlapping subarrays, each of length k, whose total sum is as large as possible. Return their starting indices in increasing order, choosing the lexicographically smallest triple if several choices have the same sum.

Key idea

Compute the sum of every length-k window. For each possible middle window, precompute the best window to its left and the best window to its right. On ties, retain the earliest starting index.

Approach

  1. Use prefix sums to get every window sum in O(1).
  2. Build left[i], the best window ending at or before window index i.
  3. Build right[i], the best window starting at or after index i.
  4. Try each valid middle window and combine it with the best compatible left and right windows.
  5. Update the answer only for a strictly larger total; iteration order and tie handling preserve the lexicographically smallest triple.
from typing import List

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        # Prefix sums let us compute each length-k window sum in O(1).
        prefix = [0] * (n + 1)
        for i, value in enumerate(nums):
            prefix[i + 1] = prefix[i] + value

        window_count = n - k + 1
        window_sums = [
            prefix[i + k] - prefix[i]
            for i in range(window_count)
        ]

        # left[i] is the earliest best window among indices 0..i.
        left = [0] * window_count
        for i in range(1, window_count):
            previous = left[i - 1]
            left[i] = i if window_sums[i] > window_sums[previous] else previous

        # right[i] is the earliest best window among indices i..end.
        right = [0] * window_count
        right[-1] = window_count - 1
        for i in range(window_count - 2, -1, -1):
            later = right[i + 1]
            right[i] = i if window_sums[i] >= window_sums[later] else later

        best_total = float("-inf")
        answer = [0, 0, 0]

        # The middle window must leave room for both other windows.
        for middle in range(k, window_count - k):
            first = left[middle - k]
            third = right[middle + k]
            total = (
                window_sums[first]
                + window_sums[middle]
                + window_sums[third]
            )

            if total > best_total:
                best_total = total
                answer = [first, middle, third]

        return answer

Complexity:

  • Time: O(n), to compute window sums and scan candidate middle windows.
  • Space: O(n), for prefix sums, window sums, and best-index arrays.

Common follow-ups

  • What if there are m subarrays instead of three? Use dynamic programming over the number of chosen windows and positions.
  • Can the extra space be reduced? A streaming DP can reduce auxiliary storage, though tie-breaking needs careful handling.
  • What if ties need a different rule? Adjust comparisons and candidate-selection logic to match the required ordering.
CodingHardGeneral MotorsSoftware Engineer

14. First Missing Positive (LeetCode)

Model answer

The task

Given an integer array, return the smallest positive integer that does not appear in it. The answer must be found in linear time using constant extra space.

Key idea

For an array of length n, the answer must be between 1 and n + 1. Place each value x in the slot at index x - 1 whenever x is in the range 1..n. Then the first slot that does not contain its expected value reveals the answer.

Approach

  1. Let n be the array length.
  2. Scan the array and place each in-range value into its corresponding slot.
  3. Skip values already in the correct slot to avoid looping on duplicates.
  4. Scan again; return the first index whose value is not index + 1.
  5. If every slot matches, return n + 1.
from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0

        # Put each value x in the slot at index x - 1, when possible.
        while i < n:
            value = nums[i]
            target = value - 1

            if 1 <= value <= n and nums[target] != value:
                nums[i], nums[target] = nums[target], nums[i]
            else:
                i += 1

        # The first misplaced value indicates the missing positive.
        for i, value in enumerate(nums):
            if value != i + 1:
                return i + 1

        return n + 1

Complexity:

  • Time: O(n), since each successful swap places a value in its final slot.
  • Space: O(1), using the input array for rearrangement.

Common follow-ups

  • What if the input must remain unchanged? Copy it first, using O(n) extra space.
  • Why can values larger than n be ignored? The smallest missing positive is at most n + 1.
  • What happens with duplicates? The swap condition skips a value already in its target slot.
  • Can the array be rearranged arbitrarily? Yes; the required result depends only on which positive values are present.

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