GEICO interview questions & answers

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

CodingEasyGEICOSoftware Engineer

1. Remove All Adjacent Duplicates In String (LeetCode)

Model answer

The task

Given a string, repeatedly remove any pair of equal characters that are next to each other. Return the string left after no such pair remains.

Key idea

Process the characters from left to right using a stack. The stack represents the reduced string so far: if the next character matches its top, remove the top; otherwise, add the character.

Approach

  1. Start with an empty stack.
  2. Visit each character in the input string.
  3. If it matches the stack’s top, pop the top.
  4. Otherwise, push the character.
  5. Join the stack to produce the result.

Each decision leaves the processed prefix fully reduced. Removing a pair can expose a new adjacent pair, but the stack handles that naturally when later characters are processed.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []

        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

Complexity:

  • Time: O(n), since each character is pushed at most once and popped at most once.
  • Space: O(n), for the stack in the worst case.

Common follow-ups

  • What if each character must be removed when it appears in a run of at least k equal characters? Store character counts on the stack and pop a group when its count reaches k.
  • Can this be done in place on a mutable character array? Use a write index as a stack pointer, overwriting the processed prefix.
  • What if removals follow a specified priority or multiple different patterns? Clarify the rules first; a stack may still work, but the match and removal logic may need to change.
CodingMediumGEICOSoftware Engineer

2. Minimum Moves to Spread Stones Over Grid (LeetCode)

Model answer

The task

Given a 3×3 grid containing nine stones in total, find the fewest adjacent-cell moves needed to leave exactly one stone in every cell.

Key idea

Each stone above the first in a cell must fill an initially empty cell. Moving a stone between two cells costs their Manhattan distance, so the problem is to find the minimum-cost assignment between surplus stones and empty cells.

Approach

  1. Record every empty cell as a destination.
  2. Record each surplus stone as a separate source at its cell’s coordinates.
  3. Use a bitmask to represent which destinations have been filled.
  4. Recursively assign the next source to each unfilled destination, adding the Manhattan distance.
  5. Return the minimum total cost.
from functools import lru_cache
from typing import List

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        sources = []
        destinations = []

        for row in range(3):
            for col in range(3):
                count = grid[row][col]

                if count == 0:
                    destinations.append((row, col))
                elif count > 1:
                    # Each stone beyond the first is a separate source.
                    sources.extend([(row, col)] * (count - 1))

        size = len(destinations)

        @lru_cache(None)
        def assign(mask: int) -> int:
            source_index = mask.bit_count()

            if source_index == size:
                return 0

            source_row, source_col = sources[source_index]
            best = float("inf")

            for target_index, (target_row, target_col) in enumerate(destinations):
                if mask & (1 << target_index):
                    continue

                distance = abs(source_row - target_row) + abs(source_col - target_col)
                best = min(
                    best,
                    distance + assign(mask | (1 << target_index)),
                )

            return best

        return assign(0)

Complexity:

  • Time: O(k · 2^k), where k is the number of empty cells.
  • Space: O(2^k) for the cached states.

Common follow-ups

  • What if the grid dimensions vary? Use the same assignment DP; compute coordinates and Manhattan distances for the new dimensions.
  • What if moving diagonally is allowed? Replace Manhattan distance with the appropriate distance for the permitted moves.
  • What if there are many destinations? The bitmask DP grows exponentially; consider a minimum-cost bipartite matching algorithm instead.
CodingMediumGEICOSoftware Engineer

3. Path With Maximum Minimum Value (LeetCode)

Model answer

The task

Given a grid of values, find a path from the top-left cell to the bottom-right cell that maximizes the smallest value encountered along the path. Movement is allowed between cells sharing an edge.

Key idea

Treat each path’s minimum value as its score. A max-heap lets us expand the path with the best current score first, similar to Dijkstra’s algorithm but maximizing a bottleneck value instead of minimizing distance.

Approach

  1. Set the best known score for the start cell to its value; initialize all other cells as unreachable.
  2. Push the start cell into a max-heap, represented with negative scores.
  3. Pop the cell with the highest score. Skip it if this heap entry is outdated.
  4. For each unvisited neighbor, compute the new path score as the minimum of the current score and the neighbor’s value.
  5. Update the neighbor if this score improves its best known score, and push it into the heap.
  6. Return the score when the destination is popped.
from heapq import heappop, heappush
from typing import List

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        best = [[-1] * cols for _ in range(rows)]
        best[0][0] = grid[0][0]

        # Store negative scores to simulate a max-heap.
        heap = [(-grid[0][0], 0, 0)]

        while heap:
            neg_score, row, col = heappop(heap)
            score = -neg_score

            # Ignore an entry superseded by a better route.
            if score != best[row][col]:
                continue

            if row == rows - 1 and col == cols - 1:
                return score

            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    candidate = min(score, grid[nr][nc])
                    if candidate > best[nr][nc]:
                        best[nr][nc] = candidate
                        heappush(heap, (-candidate, nr, nc))

        return -1  # The grid is connected, so this is unreachable.

Complexity:

  • Time: O(mn log(mn)), where each cell can be added to the heap when its score improves.
  • Space: O(mn) for the best-score table and heap.

Common follow-ups

  • How could binary search solve this? Search a candidate minimum value and use BFS/DFS to check whether the destination is reachable using only cells at least that value.
  • How could Union-Find solve it? Process cells in descending value order, activating them and unioning active neighbors until the start and destination are connected.
  • What if paths also have a length cost? Track both objectives explicitly; a single bottleneck score may no longer capture the required trade-off.
CodingMediumGEICOSoftware Engineer

4. Largest Palindromic Number (LeetCode)

Model answer

The task

Rearrange the supplied digit string into the numerically largest palindrome possible, using each digit no more times than it appears. Return the result as a string, without unnecessary leading zeros.

Key idea

A palindrome is determined by its left half and optional center digit. Use as many pairs as possible, placing larger digits first; if there is a choice of center digit, use the largest available one.

Approach

  1. Count how many times each digit occurs.
  2. Build the left half from digits 9 down to 0, taking count // 2 copies of each.
  3. Do not start the left half with zeros; skip zero pairs if no nonzero pair has been used.
  4. Choose the largest digit with an odd count as the center.
  5. If both halves are empty, return "0"; otherwise mirror the left half around the center.
from collections import Counter

class Solution:
    def largestPalindromic(self, num: str) -> str:
        counts = Counter(num)
        left_parts = []

        # Build the largest possible left half.
        for digit in range(9, -1, -1):
            pairs = counts[str(digit)] // 2

            # Leading zeros would make the number smaller.
            if digit == 0 and not left_parts:
                continue

            if pairs:
                left_parts.append(str(digit) * pairs)

        left = "".join(left_parts)

        # The center can use any digit with an odd remaining count.
        center = ""
        for digit in range(9, -1, -1):
            if counts[str(digit)] % 2:
                center = str(digit)
                break

        # No nonzero digits can form a palindrome larger than zero.
        if not left and not center:
            return "0"

        return left + center + left[::-1]

Complexity:

  • Time: O(n), to count the digits and construct the result.
  • Space: O(n), for the output; the digit counts use O(1) space.

Common follow-ups

  • What if the input is extremely long? Build the halves in chunks and stream them if the output need not be held in memory.
  • Why skip zero pairs only when the left half is empty? Once a nonzero leading digit exists, zeros can safely appear later in the half.
  • What if no digits can be paired? Return the largest available single digit, or "0" if the only possible result is zero.
CodingMediumGEICOSoftware Engineer

5. Number of Spaces Cleaning Robot Cleaned (LeetCode)

Model answer

The task

Simulate a robot moving through an obstacle-filled room. It cleans each open cell it enters and stops once it repeats a position and direction; return the number of distinct cells cleaned.

Key idea

A robot’s future behavior is determined by its cell and facing direction. There are at most four states per cell, so record each state to detect when the simulation must stop.

Approach

  1. Start at the top-left cell, facing right.
  2. Track visited (row, column, direction) states and distinct cleaned cells.
  3. If the current state was seen before, stop; otherwise record it and clean the cell.
  4. Move forward if the next cell is inside the room and open; otherwise turn right.
  5. Return the number of distinct cleaned cells.
from typing import List, Set, Tuple

class Solution:
    def numberOfCleanRooms(self, room: List[List[int]]) -> int:
        rows, cols = len(room), len(room[0])

        # Directions are ordered clockwise: right, down, left, up.
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        row = col = direction = 0

        seen_states: Set[Tuple[int, int, int]] = set()
        cleaned: Set[Tuple[int, int]] = set()

        while (row, col, direction) not in seen_states:
            seen_states.add((row, col, direction))
            cleaned.add((row, col))

            dr, dc = directions[direction]
            next_row, next_col = row + dr, col + dc

            if (
                0 <= next_row < rows
                and 0 <= next_col < cols
                and room[next_row][next_col] == 0
            ):
                row, col = next_row, next_col
            else:
                direction = (direction + 1) % 4

        return len(cleaned)

Complexity:

  • Time: O(rows × cols), since each position-and-direction state is processed at most once.
  • Space: O(rows × cols), for the visited states and cleaned cells.

Common follow-ups

  • What if the robot starts in a different direction? Initialize direction to that direction’s index.
  • Can the cleaned-cell set be avoided? Yes; use a boolean matrix and increment a counter only when a cell is first cleaned.
  • Why track direction as well as position? The same cell with a different facing direction can lead to a different next move.
CodingMediumGEICOSoftware Engineer

6. Cinema Seat Allocation (LeetCode)

Model answer

The task

Given the number of cinema rows and the reserved seats, find the maximum number of four-person families that can be seated. Each family must occupy four consecutive seats in one of the permitted blocks.

Key idea

An empty row can fit two families, one on each side. In a row with reservations, check whether the left, middle, and right blocks are free; two families fit only when both side blocks are free.

Approach

  1. Start with two families per row.
  2. For each row containing reservations, build a bitmask of its reserved seats.
  3. Check the three possible four-seat blocks against that mask.
  4. Replace that row’s baseline contribution with its actual maximum.
class Solution:
    def maxNumberOfFamilies(
        self, n: int, reservedSeats: list[list[int]]
    ) -> int:
        # Bits 0 through 7 represent seats 2 through 9.
        occupied_by_row = {}
        for row, seat in reservedSeats:
            if 2 <= seat <= 9:
                occupied_by_row[row] = (
                    occupied_by_row.get(row, 0) | (1 << (seat - 2))
                )

        left = 0b00001111    # Seats 2-5
        middle = 0b00111100  # Seats 4-7
        right = 0b11110000   # Seats 6-9

        total = 2 * n
        for occupied in occupied_by_row.values():
            left_free = (occupied & left) == 0
            middle_free = (occupied & middle) == 0
            right_free = (occupied & right) == 0

            if left_free and right_free:
                families = 2
            elif left_free or middle_free or right_free:
                families = 1
            else:
                families = 0

            # Replace this row's initial allocation of two families.
            total += families - 2

        return total

Complexity:

  • Time: O(m), where m is the number of reserved-seat entries.
  • Space: O(r), where r is the number of rows with relevant reservations.

Common follow-ups

  • What if there are multiple queries on the same reservations? Cache each row’s mask and computed contribution.
  • What if seats can be assigned in any consecutive block? Generate the valid block masks and test each.
  • How should duplicate reservations be handled? Bitwise OR naturally records a seat as occupied only once.
CodingMediumGEICOSoftware Engineer

7. Maximum Number of Potholes That Can Be Fixed (LeetCode)

Model answer

The task

Given a road string where x marks a pothole, find the most potholes that can be repaired within a budget. Repairing a consecutive stretch of k potholes costs k + 1.

Key idea

Each uninterrupted run of potholes can be repaired as one stretch, paying a one-unit setup cost plus one unit per pothole. Repair longer runs first: they yield more potholes for each setup cost.

Approach

  1. Scan the road and record the lengths of all consecutive x runs.
  2. Sort the run lengths from largest to smallest.
  3. For each run, repair it completely if the remaining budget covers its cost.
  4. If the budget cannot cover the next whole run, use what remains to repair a partial stretch, if possible, then stop.
class Solution:
    def maxPotholes(self, road: str, budget: int) -> int:
        # Find the lengths of all consecutive pothole runs.
        runs = []
        current = 0

        for char in road:
            if char == "x":
                current += 1
            elif current:
                runs.append(current)
                current = 0

        if current:
            runs.append(current)

        # Prioritize runs that yield the most repairs per setup cost.
        runs.sort(reverse=True)

        repaired = 0

        for length in runs:
            cost = length + 1

            if budget >= cost:
                budget -= cost
                repaired += length
            else:
                # A partial stretch also requires the one-unit setup cost.
                if budget > 1:
                    repaired += min(length, budget - 1)
                break

        return repaired

Complexity:

  • Time: O(n + r log r), where n is the road length and r is the number of pothole runs.
  • Space: O(r) to store run lengths.

Common follow-ups

  • Return the repaired sections too? Track each run’s start and end, then record the full or partial interval selected.
  • What if repair costs vary by pothole? Rank feasible stretches by how many repairs they provide for their total cost; the simple run-length greedy may no longer apply.
  • What if the road is too large to store? Process it in a stream to collect run lengths, then sort them if the run count fits in memory.
CodingMediumGEICOSoftware Engineer

8. Best Time to Buy and Sell Stock with Cooldown (LeetCode)

Model answer

The task

Given daily stock prices, find the largest profit possible when you may complete multiple buy-sell transactions, but must wait one day after selling before buying again.

Key idea

Track three states after each day: holding a stock, having sold today, or resting without a stock. A buy can follow only a resting day, which enforces the cooldown.

Approach

  1. Initialize the holding state from buying on the first day; initialize the other states to zero or an impossible value.
  2. For each later day, update the holding state from either continuing to hold or buying after resting.
  3. Update the sold state by selling a stock held the previous day.
  4. Update the resting state from either continuing to rest or resting after a sale.
  5. Return the better of the sold and resting states, since a profitable plan need not end holding a stock.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0

        # Profit after day i in each state.
        hold = -prices[0]
        sold = float("-inf")
        rest = 0

        for price in prices[1:]:
            # Save prior states so updates use only the previous day.
            previous_hold = hold
            previous_sold = sold
            previous_rest = rest

            hold = max(previous_hold, previous_rest - price)
            sold = previous_hold + price
            rest = max(previous_rest, previous_sold)

        return max(sold, rest)

Complexity:

  • Time: O(n), where n is the number of daily prices.
  • Space: O(1), using a fixed number of state variables.

Common follow-ups

  • What if there is a transaction fee? Subtract the fee when selling, or equivalently when buying.
  • What if there is a cooldown of k days? Track recent sale states or use a DP array to enforce the longer delay.
  • Can the answer be negative? No; resting throughout yields zero profit.
  • What if the input is empty or has one day? Return zero, since no sale can produce profit.
CodingMediumGEICOSoftware Engineer

9. Minimum Number of Food Buckets to Feed the Hamsters (LeetCode)

Model answer

The task

Given a row of hamsters (H) and empty spaces (.), place the fewest buckets on empty spaces so every hamster has a bucket immediately to its left or right. Return -1 if that cannot be done.

Key idea

Scan from left to right, handling each hamster that is not already fed by a bucket on its left. Place a bucket to its right when possible: it feeds the current hamster and may also feed the next one.

Approach

  1. Copy the string into a mutable list so bucket placements can be marked.
  2. For each hamster, skip it if the previous position contains a bucket.
  3. Otherwise, place a bucket on the right if that position is empty.
  4. If not, place one on the left if possible; if neither side is empty, return -1.
  5. Return the number of buckets placed.
class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        row = list(hamsters)
        count = 0

        for i, cell in enumerate(row):
            if cell != "H":
                continue

            # A bucket placed earlier already feeds this hamster.
            if i > 0 and row[i - 1] == "B":
                continue

            # Prefer the right: this bucket may also feed the next hamster.
            if i + 1 < len(row) and row[i + 1] == ".":
                row[i + 1] = "B"
                count += 1
            elif i > 0 and row[i - 1] == ".":
                row[i - 1] = "B"
                count += 1
            else:
                return -1

        return count

Complexity:

  • Time: O(n), where n is the length of the row.
  • Space: O(n), for the mutable copy used to mark buckets.

Common follow-ups

  • Return bucket positions too: collect each chosen index when placing a bucket.
  • Handle a circular row: account for adjacency between the first and last positions.
  • Minimize bucket cost when positions have different prices: use dynamic programming rather than this greedy choice.
  • Test impossible layouts: a hamster with no adjacent empty space cannot be fed.
CodingMediumGEICOSoftware Engineer

10. Integer to Roman (LeetCode)

Model answer

The task

Convert a positive integer into its standard Roman numeral representation, using subtractive forms such as IV and CM where appropriate.

Key idea

Process Roman numeral values from largest to smallest, including the six subtractive combinations as single entries. At each value, emit it as many times as possible, then continue with the remainder.

Approach

  1. List the values and their Roman numeral symbols in descending order.
  2. For each value, use integer division to determine how many times it fits in the remaining number.
  3. Append that many copies of its symbol.
  4. Subtract the represented amount and continue.
  5. Join the symbols to form the result.
class Solution:
    def intToRoman(self, num: int) -> str:
        # Include subtractive pairs alongside the ordinary symbols.
        values = [
            (1000, "M"),
            (900, "CM"),
            (500, "D"),
            (400, "CD"),
            (100, "C"),
            (90, "XC"),
            (50, "L"),
            (40, "XL"),
            (10, "X"),
            (9, "IX"),
            (5, "V"),
            (4, "IV"),
            (1, "I"),
        ]

        result = []

        for value, symbol in values:
            count, num = divmod(num, value)
            result.append(symbol * count)

        return "".join(result)

Complexity:

  • Time: O(1) for the standard bounded integer range; each of the fixed 13 values is checked.
  • Space: O(1) auxiliary space; the result uses O(1) space for the bounded output.

Common follow-ups

  • How would you convert a Roman numeral back to an integer? Scan symbols and subtract a value when it is less than the next symbol.
  • What if the input can exceed the standard Roman numeral range? Define an extension convention, such as overlines for thousands, before adapting the mapping.
  • How would you validate a Roman numeral string? Parse it, convert it to an integer, then convert that integer back and compare with the original.
CodingMediumGEICOSoftware Engineer

11. Coin Change (LeetCode)

Model answer

The task

Given coin denominations that can be used any number of times, find the fewest coins needed to make the target amount. Return -1 if no combination can make it.

Key idea

Let dp[x] be the minimum number of coins needed to form amount x. For each coin, update larger amounts in ascending order so that the same coin can be reused.

Approach

  1. Initialize all states as unreachable, except dp[0] = 0.
  2. Process each coin denomination.
  3. For each amount from that coin through the target, use the coin if the preceding amount is reachable.
  4. Return the target state, or -1 if it remains unreachable.
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # amount + 1 is larger than any possible answer using positive coins.
        unreachable = amount + 1
        dp = [unreachable] * (amount + 1)
        dp[0] = 0

        # Ascending amounts allow each denomination to be used repeatedly.
        for coin in coins:
            for current in range(coin, amount + 1):
                if dp[current - coin] != unreachable:
                    dp[current] = min(
                        dp[current],
                        dp[current - coin] + 1,
                    )

        return dp[amount] if dp[amount] != unreachable else -1

Complexity:

  • Time: O(n × amount), where n is the number of denominations.
  • Space: O(amount) for the dynamic programming array.

Common follow-ups

  • How can the actual coins be returned? Store the last coin used whenever a state improves, then backtrack from the target.
  • Could breadth-first search solve it? Yes; treat each amount as a node and each coin as an edge, and find the shortest path from zero to the target.
  • What changes if each coin has a limited supply? Track the remaining inventory or use a bounded-knapsack method instead of the unlimited reuse update.
CodingMediumGEICOSoftware Engineer

12. 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.
CodingMediumGEICOSoftware Engineer

13. 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.
CodingMediumGEICOSoftware Engineer

14. Remove All Occurrences of a Substring (LeetCode)

Model answer

The task

Given strings s and part, repeatedly remove occurrences of part from s until none remain, then return the resulting string.

Key idea

Build the result from left to right using a stack. Whenever the stack ends with part, remove those characters immediately; this also handles matches that form after earlier removals.

Approach

  1. Store characters from s in a list.
  2. After each character is added, check whether the list’s suffix matches part.
  3. If it does, remove that suffix.
  4. Join the remaining characters and return them.
class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack = []
        part_length = len(part)

        for char in s:
            stack.append(char)

            # Remove a complete match at the end of the built result.
            if (
                len(stack) >= part_length
                and "".join(stack[-part_length:]) == part
            ):
                del stack[-part_length:]

        return "".join(stack)

Complexity:

  • Time: O(n · m), where n is the length of s and m is the length of part; each suffix check may inspect up to m characters.
  • Space: O(n), for the stack containing the intermediate result.

Common follow-ups

  • How can suffix checks be made more efficient? Use a KMP-style matcher to track partial matches while processing characters.
  • What if part has length one? The same stack approach removes each matching character as it is encountered.
  • Does the order of removals matter? The approach removes matches as they appear in the evolving result, including matches created by previous removals.
CodingMediumGEICOSoftware Engineer

15. Best Time to Buy and Sell Stock II (LeetCode)

Model answer

The task

Given a sequence of daily stock prices, compute the greatest profit possible when you may make multiple buy-and-sell transactions. You must sell before buying again and cannot hold more than one share at a time.

Key idea

Every upward move between consecutive days can contribute to the total profit. Summing all positive day-to-day increases captures the profit from each rising stretch without needing to choose its endpoints explicitly.

Approach

  1. Start with zero profit.
  2. Walk through each pair of consecutive prices.
  3. If the price rises, add that increase to the profit.
  4. Return the accumulated amount.
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        # Collect each positive one-day price increase.
        for previous, current in zip(prices, prices[1:]):
            if current > previous:
                profit += current - previous

        return profit

Complexity:

  • Time: O(n), where n is the number of prices; each price is examined once.
  • Space: O(1), excluding the temporary iterator used to traverse the prices.

Common follow-ups

  • What if each sale has a transaction fee? Track holding and not-holding states, subtracting the fee when selling.
  • What if there is a cooldown after selling? Use dynamic programming states that track whether buying is currently allowed.
  • What if only k transactions are allowed? Use dynamic programming over the number of completed transactions and holding status.
CodingHardGEICOSoftware Engineer

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