Coupang interview questions & answers

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

CodingEasyCoupangSoftware Engineer

1. Find Pivot Index (LeetCode)

Model answer

The task

Given an integer array, return the leftmost index where the sum of the elements before it equals the sum of the elements after it. Return -1 if no such index exists.

Key idea

Compute the total sum once, then scan from left to right while maintaining the sum to the left. At each index, the right sum is the total minus the left sum and the current element.

Approach

  1. Sum all elements to get the total.
  2. Initialize the running left sum to zero.
  3. For each index, compare the left sum with total - left_sum - nums[index].
  4. Return the index when the sums match; otherwise, add the current value to the left sum.
  5. Return -1 if the scan finishes without a match.
from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0

        for i, value in enumerate(nums):
            right_sum = total - left_sum - value

            if left_sum == right_sum:
                return i

            left_sum += value

        return -1

Complexity:

  • Time: O(n), for one pass through the array after summing it.
  • Space: O(1), using only a fixed number of extra variables.

Common follow-ups

  • What if there are multiple pivot indices? The left-to-right scan returns the first; collect each matching index instead if all are required.
  • Can this handle negative values? Yes. The equality check relies on sums, not on values being positive.
  • What if the array is updated repeatedly? A single update changes the sums for many indices; a Fenwick tree or segment tree can support range-sum queries and updates more efficiently.
CodingEasyCoupangSoftware Engineer

2. Split Strings by Separator (LeetCode)

Model answer

The task

Given a list of strings and a separator, split each string wherever that separator occurs. Return the nonempty pieces in their original order.

Key idea

Process the strings in order and use the separator-aware string split operation. Filter out empty pieces, which can occur when separators are adjacent or at a string’s edge.

Approach

  1. Create an empty result list.
  2. For each string, split it using the given separator.
  3. Append each nonempty piece to the result.
  4. Return the result.
from typing import List

class Solution:
    def splitWordsBySeparator(
        self, words: List[str], separator: str
    ) -> List[str]:
        result = []

        for word in words:
            for part in word.split(separator):
                if part:
                    result.append(part)

        return result

Complexity:

  • Time: O(n), where n is the total number of characters across all input strings.
  • Space: O(n) for the returned pieces; apart from the result, splitting uses temporary space.

Common follow-ups

  • What if empty pieces should be preserved? Append every piece without checking whether it is empty.
  • What if the separator is a regular expression? Use a regex split operation and account for regex-specific behavior.
  • How would you handle input too large to keep the result in memory? Yield nonempty pieces incrementally instead of collecting them in a list.
CodingEasyCoupangSoftware Engineer

3. Largest Positive Integer That Exists With Its Negative (LeetCode)

Model answer

The task

Given an integer array, return the largest positive value whose negative also appears in the array. Return -1 if no such value exists.

Key idea

Store the values in a set for fast membership checks. For each positive value x, check whether -x is present and keep the largest qualifying x.

Approach

  1. Convert the array to a set.
  2. Initialize the answer to -1.
  3. Scan the array, considering only positive values.
  4. If a value’s negative is in the set, update the answer.
  5. Return the answer.
from typing import List

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        values = set(nums)
        largest = -1

        for value in nums:
            if value > 0 and -value in values:
                largest = max(largest, value)

        return largest

Complexity:

  • Time: O(n), for building the set and scanning the array.
  • Space: O(n), for storing the values in the set.

Common follow-ups

  • Can sorting be used instead? Yes; sort the array and use two pointers to compare the smallest and largest values.
  • What if the array contains duplicates? The set handles them naturally, and duplicates do not change the result.
  • How would you return all matching positive values? Collect each qualifying positive value in a set, then return the set or its sorted contents.
CodingMediumCoupangSoftware Engineer

4. 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.
CodingMediumCoupangSoftware Engineer

5. Maximum Number of Alloys (LeetCode)

Model answer

The task

Given several alloy recipes, available metal stocks, per-metal purchase costs, and a budget, find the greatest number of identical alloys that can be made using any one recipe.

Key idea

For a fixed recipe, the cost to make a target quantity is easy to calculate: buy only the ingredients that exceed available stock. Feasibility is monotonic—a quantity that fits the budget implies every smaller quantity does too—so binary search the maximum for each recipe.

Approach

  1. Set an upper bound of budget + sum(stock): each alloy uses at least one unit of metal, and each purchased unit costs at least one.
  2. For each recipe, binary search between zero and that bound.
  3. For a candidate quantity, sum the purchase cost of each metal’s shortage.
  4. Stop checking a candidate as soon as its cost exceeds the budget.
  5. Return the largest feasible quantity found across recipes.
from typing import List

class Solution:
    def maxNumberOfAlloys(
        self,
        n: int,
        k: int,
        budget: int,
        composition: List[List[int]],
        stock: List[int],
        cost: List[int],
    ) -> int:
        # With positive ingredient costs and recipe quantities, this is
        # a safe exclusive upper bound on the number of alloys.
        upper = budget + sum(stock) + 1

        def feasible(recipe: List[int], count: int) -> bool:
            total_cost = 0

            for metal in range(n):
                shortage = max(0, recipe[metal] * count - stock[metal])
                total_cost += shortage * cost[metal]

                if total_cost > budget:
                    return False

            return True

        best = 0

        for recipe in composition:
            low, high = 0, upper  # low is feasible; high is exclusive

            while low + 1 < high:
                mid = (low + high) // 2

                if feasible(recipe, mid):
                    low = mid
                else:
                    high = mid

            best = max(best, low)

        return best

Complexity:

  • Time: O(k · n · log(budget + sum(stock))) — binary search each recipe, checking up to n metals per step.
  • Space: O(1) — uses only a few counters beyond the input.

Common follow-ups

  • What if the budget differs by recipe? Run the same search with that recipe’s budget.
  • What if some metals have zero cost? The upper bound may no longer be finite; handle unbounded production or derive a bound from the problem’s constraints.
  • Can recipes be processed in parallel? Yes; each recipe’s search is independent, and the answer is the maximum across them.
CodingMediumCoupangSoftware Engineer

6. Snapshot Array (LeetCode)

Model answer

The task

Implement an array that supports updates, saving snapshots, and reading an index’s value as it was at a particular snapshot.

Key idea

For each index, store only the values that were explicitly set, tagged with the current snapshot ID. These IDs are ordered, so a binary search finds the most recent update no later than the requested snapshot.

Approach

  1. Keep a history list for each index and a counter for the next snapshot ID.
  2. On set, overwrite that index’s last history entry if it belongs to the current snapshot; otherwise, append a new entry.
  3. On snap, return the current ID and advance the counter.
  4. On get, binary-search the index’s history for the last entry whose ID is at most the requested ID.
  5. Return 0 if that index has no earlier recorded update.
class SnapshotArray:
    def __init__(self, length: int):
        self.histories = [[] for _ in range(length)]
        self.current_snap_id = 0

    def set(self, index: int, val: int) -> None:
        history = self.histories[index]

        # Only the final value set in a snapshot needs to be recorded.
        if history and history[-1][0] == self.current_snap_id:
            history[-1] = (self.current_snap_id, val)
        else:
            history.append((self.current_snap_id, val))

    def snap(self) -> int:
        snap_id = self.current_snap_id
        self.current_snap_id += 1
        return snap_id

    def get(self, index: int, snap_id: int) -> int:
        history = self.histories[index]

        # Find the first history entry with an ID greater than snap_id.
        low, high = 0, len(history)
        while low < high:
            mid = (low + high) // 2
            if history[mid][0] <= snap_id:
                low = mid + 1
            else:
                high = mid

        # The preceding entry is the latest update visible in this snapshot.
        return history[low - 1][1] if low > 0 else 0

Complexity:

  • Time: set and snap are O(1); get is O(log H), where H is the history length for that index.
  • Space: O(W), where W is the number of recorded writes across all indices.

Common follow-ups

  • How can memory be reduced when values often repeat? Skip recording a set when it matches the most recent value.
  • How would you support undoing snapshots? Use a persistent structure or retain version roots so earlier states remain addressable.
  • What if reads are much more frequent than writes? The per-index histories already make reads efficient, with logarithmic lookup.
CodingMediumCoupangSoftware Engineer

7. Open the Lock (LeetCode)

Model answer

The task

Find the fewest single-wheel turns needed to change the lock from 0000 to a target combination. Some combinations are forbidden; return -1 if the target cannot be reached.

Key idea

Model each four-digit combination as a graph node, with edges to combinations formed by turning one wheel up or down. Breadth-first search visits nodes in order of their distance from the start, so the first time the target is reached gives the minimum number of turns.

Approach

  1. Put the forbidden combinations in a set for constant-time checks.
  2. If the start is forbidden, return -1; if the target is the start, return 0.
  3. Run BFS from 0000, tracking each combination’s distance and marking it visited when enqueued.
  4. For each combination, generate its eight one-turn neighbors.
  5. Return the target’s distance when found, or -1 if BFS runs out of combinations.
from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        start = "0000"
        forbidden = set(deadends)

        if start in forbidden:
            return -1
        if target == start:
            return 0

        queue = deque([(start, 0)])
        visited = {start}

        while queue:
            combination, turns = queue.popleft()

            for i in range(4):
                digit = int(combination[i])

                # Turning a wheel down or up wraps around between 0 and 9.
                for next_digit in ((digit - 1) % 10, (digit + 1) % 10):
                    neighbor = (
                        combination[:i]
                        + str(next_digit)
                        + combination[i + 1:]
                    )

                    if neighbor in forbidden or neighbor in visited:
                        continue
                    if neighbor == target:
                        return turns + 1

                    visited.add(neighbor)
                    queue.append((neighbor, turns + 1))

        return -1

Complexity:

  • Time: O(D + S), where D is the number of forbidden combinations and S is the number of reachable combinations; each combination has at most eight neighbors.
  • Space: O(D + S) for the forbidden set, visited set, and BFS queue.

Common follow-ups

  • How can bidirectional BFS help? Search outward from both the start and target, expanding the smaller frontier each time.
  • What if wheel positions have different costs? Use Dijkstra’s algorithm instead of BFS.
  • How would you handle a lock with more wheels? Generate two neighbors per wheel; the state space grows exponentially with the number of wheels.
CodingMediumCoupangSoftware Engineer

8. Shopping Offers (LeetCode)

Model answer

The task

Given item prices, bundle offers that specify item quantities and a total cost, and a list of quantities to buy, find the minimum total cost. Each offer may be used repeatedly, and any remaining items can be bought individually.

Key idea

Memoize the cheapest cost for each remaining-needs vector. From a state, either buy everything left at regular prices or apply any offer that fits and solve the smaller state.

Approach

  1. Store each needs vector as a tuple so it can be used as a memoization key.
  2. Set the baseline cost to buying all remaining items individually.
  3. For each offer that fits, subtract its quantities and consider its cost plus the cached cost of the remainder.
  4. Ignore offers that contain no items, so every recursive offer application makes progress.
  5. Return the minimum cost.
from functools import cache
from typing import List

class Solution:
    def shoppingOffers(
        self,
        price: List[int],
        special: List[List[int]],
        needs: List[int],
    ) -> int:
        item_count = len(price)

        # Keep only offers that actually provide at least one item.
        offers = [
            (tuple(offer[:item_count]), offer[item_count])
            for offer in special
            if any(offer[:item_count])
        ]

        @cache
        def min_cost(remaining: tuple[int, ...]) -> int:
            # Buy every remaining item at its regular unit price.
            best = sum(
                quantity * unit_price
                for quantity, unit_price in zip(remaining, price)
            )

            for quantities, offer_cost in offers:
                if all(
                    quantities[i] <= remaining[i]
                    for i in range(item_count)
                ):
                    next_needs = tuple(
                        remaining[i] - quantities[i]
                        for i in range(item_count)
                    )
                    best = min(best, offer_cost + min_cost(next_needs))

            return best

        return min_cost(tuple(needs))

Complexity:

  • Time: O(P · S · n), where P is the number of reachable needs vectors, S is the number of offers, and n is the number of item types.
  • Space: O(P · n) for memoized needs vectors, plus recursion depth.

Common follow-ups

  • How can dominated offers be pruned? Remove an offer if its cost is no lower than buying the same quantities individually.
  • What if there are many item types but few reachable states? Keep the memoized search; it explores only states reached by fitting offers.
  • Could this be iterative? Yes. Enumerate needs vectors in increasing order and compute each state from smaller vectors.
CodingMediumCoupangSoftware Engineer

9. Course Schedule (LeetCode)

Model answer

The task

Given a number of courses and prerequisite pairs, decide whether it’s possible to complete every course. A prerequisite pair means one course must be taken before another.

Key idea

Represent courses as a directed graph, with an edge from each prerequisite to the course that depends on it. A cycle means the courses in that cycle depend on one another, so not all courses can be completed.

Use Kahn’s topological-sort algorithm: repeatedly take courses with no remaining prerequisites and remove their outgoing edges.

Approach

  1. Create an adjacency list and count each course’s prerequisites (its indegree).
  2. Add every course with indegree zero to a queue.
  3. Remove courses from the queue, counting each as completed.
  4. Decrease the indegree of each dependent course; enqueue it when its indegree reaches zero.
  5. Return whether the number completed equals the total number of courses.
from collections import deque
from typing import List

class Solution:
    def canFinish(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> bool:
        # Edges point from prerequisite to the course that depends on it.
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1

        # Begin with courses that have no prerequisites.
        ready = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )

        completed = 0

        while ready:
            course = ready.popleft()
            completed += 1

            for dependent in graph[course]:
                indegree[dependent] -= 1
                if indegree[dependent] == 0:
                    ready.append(dependent)

        return completed == numCourses

Complexity:

  • Time: O(V + E), where V is the number of courses and E is the number of prerequisite pairs.
  • Space: O(V + E) for the graph, indegrees, and queue.

Common follow-ups

  • How can you return a valid course order? Record courses as they are removed from the queue; return the order if it includes every course.
  • How can DFS detect a cycle? Track nodes as unvisited, visiting, or finished; reaching a visiting node reveals a cycle.
  • What if there are no courses? The algorithm returns True, since zero courses can all be completed.
CodingMediumCoupangSoftware Engineer

10. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumCoupangSoftware Engineer

11. Shortest Bridge (LeetCode)

Model answer

The task

Given a binary grid containing two islands, find the fewest water cells that must be flipped to connect them.

Key idea

Mark every cell in one island, then expand outward from all its cells at once using BFS. The first time the search reaches the other island, the BFS distance is the minimum number of water cells to flip.

Approach

  1. Find any land cell and use iterative DFS to mark its entire island.
  2. Add all cells of that island to a BFS queue.
  3. Expand the queue one layer at a time, marking water cells as visited when enqueuing them.
  4. If a neighbor belongs to the other island, return the current layer’s distance.
from collections import deque
from typing import List

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = None

        # Find a cell in the first island.
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    start = (r, c)
                    break
            if start is not None:
                break

        # Mark the first island and collect all its cells.
        queue = deque()
        stack = [start]
        grid[start[0]][start[1]] = 2
        queue.append(start)

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

        while stack:
            r, c = stack.pop()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n
                        and grid[nr][nc] == 1):
                    grid[nr][nc] = 2
                    stack.append((nr, nc))
                    queue.append((nr, nc))

        # Expand from the first island until reaching the second.
        flips = 0
        while queue:
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1:
                            return flips
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2
                            queue.append((nr, nc))
            flips += 1

        return -1

Complexity:

  • Time: O(n²), since each grid cell is visited at most once.
  • Space: O(n²), for the DFS stack and BFS queue in the worst case.

Common follow-ups

  • What if there are more than two islands? Find components first, then consider multi-source expansion or a graph-based approach.
  • Can the grid remain unchanged? Keep a separate visited matrix instead of marking cells in the grid.
  • Why mark water when enqueuing? It prevents the same cell from being added to the queue multiple times.
CodingMediumCoupangSoftware Engineer

12. Number of Distinct Islands (LeetCode)

Model answer

The task

Count the different island shapes in a binary grid. Two islands are considered the same when one can be shifted to match the other; rotations and reflections do not count as matches.

Key idea

Represent each island by the coordinates of its cells relative to a fixed cell in that island. Sorting those relative coordinates gives a consistent signature regardless of the order in which the island is traversed.

Approach

  1. Scan every grid cell.
  2. When an unvisited land cell is found, traverse its island with DFS.
  3. Record each cell’s row and column offsets from the island’s starting cell.
  4. Sort the offsets and use the resulting tuple as the island’s signature.
  5. Count the number of unique signatures.
from typing import List, Set, Tuple

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

        rows, cols = len(grid), len(grid[0])
        visited: Set[Tuple[int, int]] = set()
        shapes = set()

        for start_row in range(rows):
            for start_col in range(cols):
                if grid[start_row][start_col] != 1:
                    continue
                if (start_row, start_col) in visited:
                    continue

                # Traverse this island and store coordinates relative to its start.
                stack = [(start_row, start_col)]
                visited.add((start_row, start_col))
                cells = []

                while stack:
                    row, col = stack.pop()
                    cells.append((row - start_row, col - start_col))

                    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
                            and grid[nr][nc] == 1
                            and (nr, nc) not in visited
                        ):
                            visited.add((nr, nc))
                            stack.append((nr, nc))

                shapes.add(tuple(sorted(cells)))

        return len(shapes)

Complexity:

  • Time: O(mn log L), where each cell is visited once and each island’s coordinates are sorted; L is the largest island size.
  • Space: O(mn) for visited cells and stored island signatures.

Common follow-ups

  • How would rotations or reflections count as equivalent? Generate signatures for all transformations and choose a canonical one.
  • Can the grid be modified instead of using a visited set? Yes; mark land as water when it is visited.
  • How can memory use be reduced? Process islands one at a time and store only their canonical signatures, while still tracking visited cells.
CodingMediumCoupangSoftware Engineer

13. Palindrome Partitioning (LeetCode)

Model answer

The task

Return every way to split a string into nonempty contiguous pieces where each piece is a palindrome.

Key idea

Precompute whether each substring is a palindrome, making each candidate check constant time. Backtracking then tries each possible next piece and recurses only when that piece is palindromic.

Approach

  1. Build a table recording whether each substring is a palindrome.
  2. Fill it from shorter substrings to longer ones: the endpoints must match, and the interior must be a palindrome.
  3. Starting at the current position, try each possible ending position.
  4. If the substring is palindromic, add it to the current partition and recurse from the next position.
  5. When the end of the string is reached, save a copy of the partition.
class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)

        # is_palindrome[start][end] indicates whether s[start:end + 1]
        # is a palindrome.
        is_palindrome = [[False] * n for _ in range(n)]
        for end in range(n):
            for start in range(end, -1, -1):
                is_palindrome[start][end] = (
                    s[start] == s[end]
                    and (
                        end - start <= 2
                        or is_palindrome[start + 1][end - 1]
                    )
                )

        result = []
        path = []

        def backtrack(start: int) -> None:
            if start == n:
                result.append(path.copy())
                return

            for end in range(start, n):
                if is_palindrome[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1)
                    path.pop()

        backtrack(0)
        return result

Complexity:

  • Time: O(n² + n · P), where P is the number of returned partitions; storing each partition takes O(n) time.
  • Space: O(n² + n), for the palindrome table and recursion state, excluding the returned partitions.

Common follow-ups

  • Can the palindrome table be avoided? Yes; check each candidate substring directly, trading memory for repeated checks.
  • How would you return only the number of partitions? Use dynamic programming to count ways to reach each index.
  • How would you find the minimum number of pieces? Use DP over palindromic substrings to minimize the pieces needed for each prefix.
CodingMediumCoupangSoftware Engineer

14. Insert Delete GetRandom O(1) (LeetCode)

Model answer

The task

Design a collection that supports adding and removing values, plus returning a uniformly random stored value. Each operation should take average O(1) time.

Key idea

Store values in a list for constant-time random indexing, and map each value to its index for fast lookup. To remove an item without shifting the list, swap it with the last item and then pop.

Approach

  1. Keep a list of stored values and a dictionary from value to its list index.
  2. For insertion, return False if the value is already present; otherwise append it and record its index.
  3. For removal, return False if absent. Otherwise, move the last value into the removed value’s slot, update its index, then pop and delete the removed value from the dictionary.
  4. For random selection, choose a uniformly random index in the list.
  5. Assume random selection is called only when the collection is nonempty.
import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index_by_value = {}

    def insert(self, val: int) -> bool:
        if val in self.index_by_value:
            return False

        self.index_by_value[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_by_value:
            return False

        index = self.index_by_value[val]
        last_value = self.values[-1]

        # Fill the removed value's slot with the last value.
        self.values[index] = last_value
        self.index_by_value[last_value] = index

        self.values.pop()
        del self.index_by_value[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)

Complexity:

  • Time: O(1) average per operation; dictionary operations are expected O(1).
  • Space: O(n), for the list and index map storing n values.

Common follow-ups

  • How would you support duplicates? Store each value’s set of indices and update that set during swaps.
  • What if random selection must be weighted? Maintain cumulative weights and use binary search, or use a dynamic weighted-sampling structure.
  • What happens if getRandom is called when empty? Define a clear error or sentinel behavior; the implementation assumes at least one value exists.
CodingMediumCoupangSoftware Engineer

15. Kth Largest Element in an Array (LeetCode)

Model answer

The task

Find the value that would appear in position k when the array is sorted from largest to smallest. Duplicate values count as separate positions.

Key idea

The answer is the element at index len(nums) - k in ascending order. Quickselect partitions the array around pivots, then continues only in the partition that contains that index.

Approach

  1. Convert k to its target index in ascending order.
  2. Choose a random pivot to reduce the chance of consistently poor partitions.
  3. Partition into values smaller than, equal to, and greater than the pivot.
  4. Narrow the search to the partition containing the target, or return the pivot if the target lies among the equal values.
import random
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        left, right = 0, len(nums) - 1

        while left <= right:
            pivot = nums[random.randint(left, right)]

            # Three-way partition:
            # nums[left:lt] < pivot
            # nums[lt:gt + 1] == pivot
            # nums[gt + 1:right + 1] > pivot
            lt, i, gt = left, left, right
            while i <= gt:
                if nums[i] < pivot:
                    nums[lt], nums[i] = nums[i], nums[lt]
                    lt += 1
                    i += 1
                elif nums[i] > pivot:
                    nums[i], nums[gt] = nums[gt], nums[i]
                    gt -= 1
                else:
                    i += 1

            if target < lt:
                right = lt - 1
            elif target > gt:
                left = gt + 1
            else:
                return pivot

        raise ValueError("k must be within the array's valid range")

Complexity:

  • Time: O(n) on average, since each partition discards the portions that cannot contain the answer.
  • Space: O(1) auxiliary space; the partitioning is in place.

Common follow-ups

  • What if worst-case time must be bounded? Use a min-heap of size k for O(n log k) time.
  • How do duplicates affect the result? Each occurrence occupies its own rank; the three-way partition handles equal values together.
  • Can the input remain unchanged? Make a copy before partitioning, at the cost of O(n) extra space.
CodingMediumCoupangSoftware Engineer

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

17. Decode String (LeetCode)

Model answer

The task

Decode a string where a number before brackets indicates how many times to repeat the bracketed section. Sections may be nested.

Key idea

Parse the input into a compact tree of literal fragments and repeat nodes instead of expanding nested sections immediately. Then traverse that tree to produce the decoded string, avoiding repeated copying of large intermediate strings.

Approach

  1. Scan the input, accumulating each repetition count.
  2. On an opening bracket, save the current fragment list and count, then start a new list.
  3. On a closing bracket, wrap the current list in a repeat node and add it to its parent.
  4. Traverse the resulting structure with an explicit stack, yielding literal fragments as they are needed.
  5. Join the yielded fragments into the result.
class Solution:
    def decodeString(self, s: str) -> str:
        # Each repeat node is a (count, fragments) tuple.
        current = []
        stack = []
        count = 0

        for char in s:
            if "0" <= char <= "9":
                count = count * 10 + int(char)
            elif char == "[":
                stack.append((current, count))
                current = []
                count = 0
            elif char == "]":
                parent, repeat = stack.pop()
                # Omit zero repetitions so traversal skips empty sections.
                if repeat:
                    parent.append((repeat, current))
                current = parent
            else:
                current.append(char)

        def fragments():
            # Frames contain a fragment list, its next index, and
            # how many times to traverse that list.
            frames = [[current, 0, 1]]

            while frames:
                parts, index, remaining = frames[-1]

                if index == len(parts):
                    remaining -= 1
                    if remaining == 0:
                        frames.pop()
                    else:
                        frames[-1][1] = 0
                        frames[-1][2] = remaining
                    continue

                node = parts[index]
                frames[-1][1] += 1

                if isinstance(node, str):
                    yield node
                else:
                    repeat, nested = node
                    frames.append([nested, 0, repeat])

        return "".join(fragments())

Complexity:

  • Time: O(n + m), where n is the encoded length and m is the decoded length.
  • Space: O(n + m) for the parsed structure and returned string.

Common follow-ups

  • How would you handle malformed input? Validate bracket balance and ensure each opening bracket has a preceding count.
  • How could this support streaming output? Yield decoded fragments to a consumer instead of joining them into one string.
  • What if the grammar adds escaping or other operators? Extend the parser with explicit rules and represent each operation as a distinct node.
CodingMediumCoupangSoftware Engineer

18. Maximum Good Subarray Sum (LeetCode)

Model answer

The task

Find the largest sum among contiguous subarrays whose first and last values differ by exactly k. Return 0 if no such subarray exists.

Key idea

For each value, keep the smallest prefix sum seen just before an occurrence of that value. When the current value is x, a valid subarray can start at a prior x - k or x + k; subtracting the smallest stored prefix gives the best sum ending here.

Approach

  1. Track the prefix sum before the current position.
  2. Look up prior occurrences of x - k and x + k.
  3. Use their minimum prefix sums to update the best valid subarray sum.
  4. Record the current prefix sum as a possible starting point for future subarrays.
  5. Return 0 if no valid subarray was found.
from typing import List

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        # Smallest prefix sum before an occurrence of each value.
        min_prefix = {}

        prefix = 0
        best = None

        for x in nums:
            # Query before recording this position, so the subarray is nonempty.
            for start_value in (x - k, x + k):
                if start_value in min_prefix:
                    subarray_sum = prefix + x - min_prefix[start_value]
                    if best is None or subarray_sum > best:
                        best = subarray_sum

            # This position may be the start of a future valid subarray.
            if x not in min_prefix or prefix < min_prefix[x]:
                min_prefix[x] = prefix

            prefix += x

        return 0 if best is None else best

Complexity:

  • Time: O(n), with expected O(1) hash-map operations per element.
  • Space: O(n), for the prefix minimum stored for each distinct value.

Common follow-ups

  • What if k is zero? The same lookup works; querying before updating ensures the endpoints are at different positions.
  • Can this be solved without storing all distinct values? Not generally in one pass, since a future endpoint may match any earlier value.
  • What if the answer must include the subarray indices? Store the index alongside each minimum prefix and retain the best pair of endpoints.
CodingMediumCoupangSoftware Engineer

19. Split BST (LeetCode)

Model answer

The task

Split a BST into two BSTs: one contains values at most the target, and the other contains values greater than it. Reuse the existing nodes and preserve their relative structure.

Key idea

At each node, only one subtree can contain values on the other side of the split. Recursively split that subtree, then reconnect the piece that belongs with the current node.

Approach

  1. If the current node is None, return two empty trees.
  2. If its value is at most the target, split its right subtree.
  3. Attach the left result of that split as the current node’s right child; return the current node and the other result.
  4. Otherwise, split its left subtree.
  5. Attach the right result of that split as the current node’s left child; return the other result and the current node.
from typing import List, Optional

class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def splitBST(
        self, root: Optional[TreeNode], target: int
    ) -> List[Optional[TreeNode]]:
        """Return the roots of the <= target tree and the > target tree."""
        if root is None:
            return [None, None]

        if root.val <= target:
            lower, upper = self.splitBST(root.right, target)
            root.right = lower
            return [root, upper]

        lower, upper = self.splitBST(root.left, target)
        root.left = upper
        return [lower, root]

Complexity:

  • Time: O(h), where h is the tree height; only one search path is visited.
  • Space: O(h) for the recursion stack.

Common follow-ups

  • Can this be done iteratively? Yes; walk one search path while building the two result trees with tail pointers.
  • What is the worst-case complexity for a skewed tree? h can be n, so both time and recursion space can be O(n).
  • How should duplicates be handled? Specify which result owns values equal to the target, then adjust the comparison accordingly.
CodingMediumCoupangSoftware Engineer

20. Word Break (LeetCode)

Model answer

The task

Given a string and a dictionary of words, determine whether the string can be formed by concatenating dictionary words. Words may be reused.

Key idea

Track which string positions are reachable after forming a sequence of words. From each reachable position, follow the dictionary trie through the string; every terminal trie node marks another reachable position.

Approach

  1. Build a trie from the dictionary, marking the end of each word.
  2. Initialize position 0 as reachable.
  3. For each reachable position, walk the trie along the string from that position.
  4. Mark positions reached at the end of a dictionary word.
  5. Return whether the end of the string is reachable.
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        # None marks the end of a word in the trie.
        trie: dict = {}

        for word in wordDict:
            node = trie
            for char in word:
                node = node.setdefault(char, {})
            node[None] = True

        reachable = [False] * (len(s) + 1)
        reachable[0] = True

        for start in range(len(s)):
            if not reachable[start]:
                continue

            node = trie
            end = start

            while end < len(s) and s[end] in node:
                node = node[s[end]]
                end += 1

                if None in node:
                    reachable[end] = True

        return reachable[len(s)]

Complexity:

  • Time: O(nL), where n is the string length and L is the longest dictionary word.
  • Space: O(D + n), where D is the total number of characters across dictionary words.

Common follow-ups

  • How can you return one valid segmentation? Store a predecessor position whenever a position first becomes reachable, then backtrack from the end.
  • How can you return all valid segmentations? Use memoization to collect possible suffix segmentations from each position.
  • What if the dictionary changes frequently? Consider a data structure that supports efficient updates, such as maintaining the trie incrementally.

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