Roku interview questions & answers

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

CodingEasyRokuSoftware Engineer

1. Valid Palindrome II (LeetCode)

Model answer

The task

Determine whether a string can become a palindrome after removing at most one character.

Key idea

Compare characters from both ends, moving inward while they match. At the first mismatch, the one allowed removal must skip either the left character or the right character; check whether either remaining range is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. While the pointed-to characters match, move both pointers inward.
  3. If the pointers meet, the string is already a palindrome.
  4. Otherwise, check the two ranges formed by skipping either mismatched character.
  5. Return true if at least one range is a palindrome.
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left: int, right: int) -> bool:
            # Check whether this inclusive range reads the same both ways.
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        left, right = 0, len(s) - 1

        while left < right:
            if s[left] != s[right]:
                # Use the one allowed deletion on either mismatched end.
                return (
                    is_palindrome(left + 1, right)
                    or is_palindrome(left, right - 1)
                )
            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), since at most two linear range checks are performed.
  • Space: O(1), excluding the input string; the checks use only pointers.

Common follow-ups

  • What if up to k characters may be removed? Use recursion or dynamic programming to track the remaining deletion budget; the simple one-mismatch check no longer suffices.
  • What if the input is a linked list? Use a stack or find the midpoint and reverse part of the list, depending on whether extra space is allowed.
  • Should comparison ignore capitalization or punctuation? Normalize or skip irrelevant characters while moving the two pointers inward.
CodingEasyRokuSoftware Engineer

2. Backspace String Compare (LeetCode)

Model answer

The task

Compare two strings after applying backspaces: each # removes the most recent character when one exists. Return whether the resulting strings are equal.

Key idea

Scan both strings from right to left. Count how many characters each backspace should skip, so the strings can be compared without building their edited versions.

Approach

  1. Start a pointer at the end of each string.
  2. For each string, move left while tracking pending backspaces.
  3. Skip a character if a backspace is pending; otherwise it is the next visible character.
  4. Compare the next visible characters. If they differ, return False.
  5. Continue until both strings have no visible characters left, then return True.
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def next_visible(text: str, index: int) -> tuple[str | None, int]:
            """Return the next character not erased by a backspace, and its index."""
            skips = 0

            while index >= 0:
                if text[index] == "#":
                    skips += 1
                elif skips > 0:
                    skips -= 1
                else:
                    return text[index], index - 1

                index -= 1

            return None, -1

        i, j = len(s) - 1, len(t) - 1

        while i >= 0 or j >= 0:
            char_s, i = next_visible(s, i)
            char_t, j = next_visible(t, j)

            if char_s != char_t:
                return False

        return True

Complexity:

  • Time: O(m + n), where m and n are the string lengths; each character is visited at most once.
  • Space: O(1), excluding the helper’s constant-size state.

Common follow-ups

  • What if backspace is represented by a different character? Pass it into the helper or replace the "#" check.
  • How would you implement this with a stack? Build each edited string by appending ordinary characters and popping on backspace, then compare.
  • What happens when a backspace appears with nothing to erase? It is ignored, as handled by the skip count.
CodingMediumRokuSoftware Engineer

3. 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.
CodingMediumRokuSoftware Engineer

4. Asteroid Collision (LeetCode)

Model answer

The task

Given a sequence of signed asteroid sizes, simulate their movement and collisions. Return the asteroids that remain, in their original order.

Key idea

A collision can happen only when a right-moving asteroid is followed by a left-moving one. Keep surviving asteroids in a stack; resolve each possible collision with the stack’s most recent survivor.

Approach

  1. Start with an empty stack.
  2. Process asteroids from left to right.
  3. While the stack’s top moves right and the current asteroid moves left, compare their sizes.
  4. Remove the smaller asteroid; if they are equal, remove both. Stop resolving if the current asteroid is destroyed.
  5. Add the current asteroid if it survives, then return the stack.
from typing import List

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        survivors: List[int] = []

        for asteroid in asteroids:
            alive = True

            # Only a right-moving survivor can collide with a left-moving one.
            while (
                alive
                and asteroid < 0
                and survivors
                and survivors[-1] > 0
            ):
                top = survivors[-1]

                if top < -asteroid:
                    # The top asteroid is smaller and is destroyed.
                    survivors.pop()
                elif top == -asteroid:
                    # Both asteroids are destroyed.
                    survivors.pop()
                    alive = False
                else:
                    # The current asteroid is smaller and is destroyed.
                    alive = False

            if alive:
                survivors.append(asteroid)

        return survivors

Complexity:

  • Time: O(n), since each asteroid is pushed and popped at most once.
  • Space: O(n) for the stack of surviving asteroids.

Common follow-ups

  • How would you handle zero-sized asteroids? Define their movement and collision behavior, then adjust the collision rules accordingly.
  • Can the result be computed in place? Yes, use the input list’s prefix as the stack, if modifying the input is allowed.
  • What if collisions occur in multiple dimensions? A single stack is no longer sufficient; the model needs spatial positions and directions.
CodingMediumRokuSoftware Engineer

5. Valid Parenthesis String (LeetCode)

Model answer

The task

Given a string containing (, ), and *, decide whether the * characters can be interpreted so the resulting parentheses are balanced. Each * may represent an opening parenthesis, a closing parenthesis, or nothing.

Key idea

Track the range of possible counts of unmatched opening parentheses after each character. The lowest count assumes stars close parentheses when possible; the highest assumes stars open them. If the highest count becomes negative, no interpretation can work.

Approach

  1. Initialize the minimum and maximum possible unmatched opening counts to zero.
  2. For (, increment both counts.
  3. For ), decrement both counts.
  4. For *, decrement the minimum and increment the maximum.
  5. Clamp the minimum to zero, since unmatched openings cannot be negative.
  6. Reject if the maximum is negative; after scanning, accept only if the minimum is zero.
class Solution:
    def checkValidString(self, s: str) -> bool:
        # Range of possible unmatched opening-parenthesis counts.
        low = 0
        high = 0

        for ch in s:
            if ch == "(":
                low += 1
                high += 1
            elif ch == ")":
                low -= 1
                high -= 1
            else:  # "*" may be "(", ")", or empty
                low -= 1
                high += 1

            # No interpretation can have fewer than zero unmatched opens.
            low = max(low, 0)

            # Even interpreting every star as "(" cannot fix this prefix.
            if high < 0:
                return False

        # A valid interpretation must be able to leave no unmatched opens.
        return low == 0

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(1), using only two counters.

Common follow-ups

  • How would you return one valid interpretation? Track choices or use a stack of parenthesis and star indices, then match remaining openings with later stars.
  • Can dynamic programming solve it? Yes; track reachable balance counts, though it uses O(n²) time and O(n) space.
  • What if there are multiple wildcard types with different allowed meanings? Update the reachable balance range or use a more general DP if the possible balances are not contiguous.
CodingMediumRokuSoftware Engineer

6. 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.
CodingMediumRokuSoftware Engineer

7. Max Area of Island (LeetCode)

Model answer

The task

Given a grid of land and water cells, find the size of the largest connected group of land cells. Connectivity is orthogonal: diagonal cells are not connected.

Key idea

Each land cell belongs to exactly one island. Traverse the grid, and when an unvisited land cell is found, explore its whole island while counting its cells. Mark cells as visited so each is processed only once.

Approach

  1. Return 0 if the grid has no rows or columns.
  2. Scan every cell in the grid.
  3. For each unvisited land cell, start an iterative depth-first search.
  4. Mark land cells when adding them to the stack, and count them as they are removed.
  5. Keep the largest island size seen.
from typing import List

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

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

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue

                # Explore this island, marking cells as visited in place.
                grid[r][c] = 0
                stack = [(r, c)]
                area = 0

                while stack:
                    row, col = stack.pop()
                    area += 1

                    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
                        ):
                            grid[nr][nc] = 0
                            stack.append((nr, nc))

                largest = max(largest, area)

        return largest

Complexity:

  • Time: O(mn), where each cell is checked and visited at most once.
  • Space: O(mn) in the worst case for the DFS stack.

Common follow-ups

  • What if the grid must not be modified? Track visited cells in a separate set.
  • What if diagonal cells also connect? Add the four diagonal directions to the neighbor list.
  • How would you return the number of islands too? Increment a counter each time a new DFS begins.
CodingMediumRokuSoftware Engineer

8. 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.
CodingMediumRokuSoftware Engineer

9. Multiply Strings (LeetCode)

Model answer

The task

Return the product of two non-negative integers given as digit strings. Compute the result without converting either entire string to a built-in integer.

Key idea

Simulate grade-school multiplication, storing each digit’s contribution in an array of length len(num1) + len(num2). For each digit pair, add its product to the appropriate positions and propagate the carry.

Approach

  1. If either string represents zero, return "0".
  2. Create an array to hold the product digits.
  3. Visit digit pairs from right to left, adding each product and existing value at that position.
  4. Store the ones digit and add the carry to the preceding position.
  5. Skip leading zeroes in the result and join the remaining digits.
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        n, m = len(num1), len(num2)
        result = [0] * (n + m)

        # Multiply each pair of digits, moving from right to left.
        for i in range(n - 1, -1, -1):
            digit1 = ord(num1[i]) - ord("0")

            for j in range(m - 1, -1, -1):
                digit2 = ord(num2[j]) - ord("0")
                position = i + j + 1

                total = digit1 * digit2 + result[position]
                result[position] = total % 10
                result[position - 1] += total // 10

        # Remove leading zeroes before building the output string.
        start = 0
        while start < len(result) - 1 and result[start] == 0:
            start += 1

        return "".join(str(digit) for digit in result[start:])

Complexity:

  • Time: O(nm), for every pair of digits.
  • Space: O(n + m), for the result array.

Common follow-ups

  • How would you support negative numbers? Track the signs separately, multiply absolute values, then apply the result sign.
  • How would you handle decimal strings? Track decimal places, multiply the digit sequences, then place the decimal point.
  • Can very long numbers be multiplied faster? For sufficiently large inputs, use divide-and-conquer methods such as Karatsuba multiplication.
CodingMediumRokuSoftware Engineer

10. Minimum Cost For Tickets (LeetCode)

Model answer

The task

Given the days you need to travel and the prices of one-day, seven-day, and thirty-day passes, find the lowest total cost that covers every travel day.

Key idea

Process travel days from earliest to latest. For each day, consider buying each pass and jump to the first travel day it does not cover; dynamic programming records the cheapest cost of reaching each such position.

Approach

  1. Store dp[i] as the minimum cost to cover all travel days before index i.
  2. Initialize dp[0] to zero; all other positions start unreachable.
  3. For each reachable index, try each pass duration and its matching price.
  4. Use binary search to find the first travel day at or after the pass’s expiration.
  5. Update the cost at that position and return the cost for all days.
from bisect import bisect_left
from typing import List

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        durations = (1, 7, 30)

        # dp[i] is the minimum cost to cover days before index i.
        dp = [float("inf")] * (n + 1)
        dp[0] = 0

        for i in range(n):
            if dp[i] == float("inf"):
                continue

            for duration, price in zip(durations, costs):
                # A pass bought on days[i] covers through days[i] + duration - 1.
                next_index = bisect_left(days, days[i] + duration)
                dp[next_index] = min(dp[next_index], dp[i] + price)

        return dp[n]

Complexity:

  • Time: O(n log n), for up to three binary searches per travel day.
  • Space: O(n), for the dynamic programming array.

Common follow-ups

  • Can the time be reduced to O(n)? Yes; maintain a moving pointer for each pass duration as the travel days are processed.
  • What if the pass durations differ? Replace the duration list with the available pass lengths and apply the same transitions.
  • What if travel days are not sorted? Sort them first, removing duplicates if needed.
  • What if the calendar is small and fixed? Use day-by-day dynamic programming, carrying the best cost forward on non-travel days.
CodingMediumRokuSoftware Engineer

11. Top K Frequent Elements (LeetCode)

Model answer

The task

Given an integer array and a value k, return the k values that occur most often. Their order does not matter.

Key idea

Count each value’s occurrences, then group values by frequency. Since no frequency can exceed the array length, scan these groups from highest frequency down until k values are collected.

Approach

  1. Build a frequency map from each value to its count.
  2. Create buckets indexed by frequency.
  3. Put each distinct value into the bucket for its count.
  4. Scan buckets from highest to lowest, collecting values until there are k.
from collections import defaultdict
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count occurrences of each value.
        frequency = defaultdict(int)
        for value in nums:
            frequency[value] += 1

        # Bucket each value by its frequency.
        buckets = [[] for _ in range(len(nums) + 1)]
        for value, count in frequency.items():
            buckets[count].append(value)

        # Collect values from most frequent to least frequent.
        result = []
        for count in range(len(nums), 0, -1):
            for value in buckets[count]:
                result.append(value)
                if len(result) == k:
                    return result

        return result

Complexity:

  • Time: O(n), where n is the array length; counting and scanning the buckets take linear time.
  • Space: O(n), for the frequency map and buckets.

Common follow-ups

  • How would you solve it with a heap? Keep a size-k heap of distinct values, giving O(n + m log k) time, where m is the number of distinct values.
  • What if results must be ordered by frequency? Sort the selected values by their counts, or collect them in descending bucket order.
  • What if the data arrives as a stream? Maintain approximate counts with a streaming frequency sketch, or use a bounded candidate structure when exact counts are not feasible.
CodingMediumRokuSoftware Engineer

12. Maximum Points You Can Obtain from Cards (LeetCode)

Model answer

The task

Given an array of card values and an integer k, find the greatest total obtainable by taking exactly k cards from either end of the array.

Key idea

Taking cards from the two ends leaves one contiguous segment of n - k cards untouched. So maximize the score by subtracting the smallest possible sum of such a segment from the total sum.

Approach

  1. Compute the sum of all card values.
  2. Set the length of the untouched segment to n - k.
  3. Use a sliding window to find the minimum sum of any segment of that length.
  4. Return the total minus that minimum. If the segment length is zero, return the total.
from typing import List

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        window_size = n - k

        # Taking every card leaves nothing untouched.
        if window_size == 0:
            return sum(cardPoints)

        # Sum the first candidate segment.
        window_sum = sum(cardPoints[:window_size])
        min_window_sum = window_sum

        # Slide the segment across the array, updating its sum in O(1).
        for right in range(window_size, n):
            window_sum += cardPoints[right] - cardPoints[right - window_size]
            min_window_sum = min(min_window_sum, window_sum)

        return sum(cardPoints) - min_window_sum

Complexity:

  • Time: O(n), for the sliding-window scan and total sum.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if k is zero? Return 0; no cards are taken.
  • Can this be solved by tracking cards taken from each end? Yes: start with k from the left, then swap leftmost selections for rightmost ones.
  • What if card values can be negative? The method still works, since it finds the minimum sum among all untouched segments.
CodingHardRokuSoftware Engineer

13. 24 Game (LeetCode)

Model answer

The task

Determine whether the four given numbers can be combined, using each exactly once and the arithmetic operations +, -, *, and /, to make 24.

Key idea

Every valid expression can be built by combining two numbers or intermediate results at a time. Try each pair and each valid operation, then recursively check whether the reduced set of values can reach 24.

Approach

  1. Store the numbers as floating-point values.
  2. If only one value remains, check whether it is close enough to 24.
  3. Otherwise, choose each pair of values and remove them from the current list.
  4. Try adding each possible result of applying an operation to that pair.
  5. Recurse with the reduced list; return True if any choice succeeds.
from typing import List

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        tolerance = 1e-6

        def search(values: List[float]) -> bool:
            if len(values) == 1:
                return abs(values[0] - 24.0) < tolerance

            # Try combining every pair of current values.
            for i in range(len(values)):
                for j in range(i + 1, len(values)):
                    a, b = values[i], values[j]
                    remaining = [
                        values[k] for k in range(len(values))
                        if k != i and k != j
                    ]

                    # Addition and multiplication are commutative.
                    results = [a + b, a * b]

                    # Subtraction and division are not commutative.
                    results.extend([a - b, b - a])
                    if b != 0:
                        results.append(a / b)
                    if a != 0:
                        results.append(b / a)

                    for result in results:
                        if search(remaining + [result]):
                            return True

            return False

        return search([float(card) for card in cards])

Complexity:

  • Time: O(6^(n-1) n! (n-1)!) in a loose upper bound, from trying pairs and operations at each level.
  • Space: O(n), for recursion depth and temporary value lists.

Common follow-ups

  • How would you avoid exploring equivalent states? Canonicalize and memoize sorted value lists, taking care with floating-point representations.
  • How would you support a different target? Pass the target into the search and compare against it at the base case.
  • How would you handle more input numbers? The same recursion works, though the search grows quickly; memoization can help when states repeat.
CodingHardRokuSoftware Engineer

14. Vertical Order Traversal of a Binary Tree (LeetCode)

Model answer

The task

Group the nodes of a binary tree into vertical columns, ordered from left to right. Within each column, order nodes by depth, and when nodes share both a column and depth, order them by value.

Key idea

Assign each node coordinates (row, column): the root is (0, 0), a left child moves to (row + 1, column - 1), and a right child to (row + 1, column + 1). Sort all recorded coordinates by column, then row, then value; collect values with the same column.

Approach

  1. Return an empty list if the tree is empty.
  2. Traverse the tree and record each node as (column, row, value).
  3. Sort the records lexicographically, which applies all three required ordering rules.
  4. Scan the sorted records and start a new result list whenever the column changes.
from collections import deque
from typing import List, Optional

# Assumes the usual TreeNode definition:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def verticalTraversal(self, root: Optional["TreeNode"]) -> List[List[int]]:
        if root is None:
            return []

        records = []
        queue = deque([(root, 0, 0)])  # node, row, column

        while queue:
            node, row, column = queue.popleft()
            records.append((column, row, node.val))

            if node.left is not None:
                queue.append((node.left, row + 1, column - 1))
            if node.right is not None:
                queue.append((node.right, row + 1, column + 1))

        records.sort()

        result = []
        previous_column = None

        for column, row, value in records:
            if column != previous_column:
                result.append([])
                previous_column = column
            result[-1].append(value)

        return result

Complexity:

  • Time: O(n log n), due to sorting the n node records.
  • Space: O(n), for the traversal queue, records, and result.

Common follow-ups

  • Can sorting be avoided? Use a structure keyed by column and row, but equal-coordinate values still need sorting.
  • Does traversal order affect correctness? No; the final sort fully determines the output order.
  • What if equal-position nodes should retain traversal order? Add a traversal sequence number as a tie-breaker instead of sorting by value.
  • How would you handle a very large tree? Stream records to external sorting if they do not fit in memory.
CodingHardRokuSoftware Engineer

15. Three Equal Parts (LeetCode)

Model answer

The task

Split a binary array into three nonempty contiguous parts whose binary values are equal. Leading zeros do not change a part’s value.

Key idea

If the array has nonzero entries, each part must contain the same number of 1s. Compare the portions from each part’s first 1 through the array’s last 1; zeros after that last 1 matter only as padding.

Approach

  1. Count the 1s. If there are none, any two valid cut positions work.
  2. If the count is not divisible by three, equal parts are impossible.
  3. Find the first 1 in each of the three equal groups of 1s.
  4. Compare equal-length portions from those positions, ending at the last 1.
  5. If they match, cut immediately after the first and second portions; otherwise return [-1, -1].
from typing import List

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        total_ones = sum(arr)

        # With no ones, all three parts represent zero.
        if total_ones == 0:
            return [0, 2]

        if total_ones % 3 != 0:
            return [-1, -1]

        ones_per_part = total_ones // 3
        starts = []
        seen_ones = 0

        for index, bit in enumerate(arr):
            if bit == 1:
                seen_ones += 1
                if seen_ones in (1, ones_per_part + 1, 2 * ones_per_part + 1):
                    starts.append(index)

        first, second, third = starts
        last_one = len(arr) - 1 - arr[::-1].index(1)
        length = last_one - third + 1

        # The significant binary patterns must match.
        if not (
            arr[first:first + length]
            == arr[second:second + length]
            == arr[third:third + length]
        ):
            return [-1, -1]

        return [first + length - 1, second + length - 1]

Complexity:

  • Time: O(n), for counting, locating starts, and comparing portions.
  • Space: O(1), excluding the returned list.

Common follow-ups

  • Why ignore zeros after the last 1? They are trailing zeros in the array’s third part and do not affect the significant pattern being compared.
  • What if all entries are zero? Any two cuts creating three nonempty parts are valid.
  • Can the array be split into more than three equal-value parts? Use the same idea: each part needs an equal share of the 1s, then compare each significant pattern.
CodingHardRokuSoftware Engineer

16. Longest Valid Parentheses (LeetCode)

Model answer

The task

Given a string of opening and closing parentheses, find the length of its longest contiguous substring that forms a correctly balanced sequence.

Key idea

Keep a stack of indices marking positions that cannot belong to the current valid substring. A sentinel index of -1 handles valid substrings that start at the beginning of the string.

Approach

  1. Initialize the stack with -1 and the best length with zero.
  2. For each character, push its index if it is an opening parenthesis.
  3. For a closing parenthesis, pop the top index.
  4. If the stack is empty, push the current index as the new boundary.
  5. Otherwise, the current valid suffix spans from one position after the stack’s top through the current index; update the best length.
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Indices in the stack mark invalid boundaries.
        stack = [-1]
        longest = 0

        for i, char in enumerate(s):
            if char == "(":
                stack.append(i)
            else:
                stack.pop()

                if not stack:
                    # This closing parenthesis cannot be matched.
                    stack.append(i)
                else:
                    # The segment after the boundary is valid.
                    longest = max(longest, i - stack[-1])

        return longest

Complexity:

  • Time: O(n), where n is the string length; each index is pushed and popped at most once.
  • Space: O(n), for the stack of boundary and opening-parenthesis indices.

Common follow-ups

  • How can this be solved with dynamic programming? Track the longest valid suffix ending at each index, using prior suffix lengths to connect matching pairs.
  • Can the extra space be reduced to O(1)? Scan in both directions, tracking opening and closing counts; reverse the roles on the second scan.
  • What if the input contains multiple bracket types? A stack can match bracket types, but the boundary logic must ensure only correctly nested substrings contribute.
CodingHardRokuSoftware Engineer

17. Shortest Path to Get All Keys (LeetCode)

Model answer

The task

Given a grid with walls, keys, locks, and a starting cell, find the fewest moves needed to collect every key. Return -1 if collecting them all is impossible.

Key idea

A position alone is not enough to describe the search: whether a lock is passable depends on which keys have been collected. Run BFS over states (row, column, key_mask), where the bitmask records the keys in hand.

Approach

  1. Scan the grid to find the start and assign a bit to each distinct key.
  2. Start BFS at the initial cell with an empty mask; track visited position-mask pairs.
  3. For each move, skip cells outside the grid or blocked by a wall.
  4. For a lock, proceed only if its matching key exists and has been collected.
  5. Add a key’s bit when entering its cell; return the distance once the mask contains every key.
  6. If BFS finishes first, return -1.
from collections import deque
from typing import List

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        rows, cols = len(grid), len(grid[0])
        start = None
        key_bits = {}

        # Assign compact bit positions to the keys present in the grid.
        for r in range(rows):
            for c in range(cols):
                cell = grid[r][c]
                if cell == "@":
                    start = (r, c)
                elif cell.islower():
                    key_bits[cell] = len(key_bits)

        all_keys = (1 << len(key_bits)) - 1
        if all_keys == 0:
            return 0

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

        while queue:
            r, c, mask, distance = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < rows and 0 <= nc < cols):
                    continue

                cell = grid[nr][nc]
                if cell == "#":
                    continue

                if cell.isupper():
                    bit_index = key_bits.get(cell.lower())
                    # A lock without a matching key can never be opened.
                    if bit_index is None or not (mask & (1 << bit_index)):
                        continue

                next_mask = mask
                if cell.islower():
                    next_mask |= 1 << key_bits[cell]

                if next_mask == all_keys:
                    return distance + 1

                state = (nr, nc, next_mask)
                if state not in visited:
                    visited.add(state)
                    queue.append((nr, nc, next_mask, distance + 1))

        return -1

Complexity:

  • Time: O(mn · 2^k) — at most mn · 2^k states, each with four transitions.
  • Space: O(mn · 2^k) — the queue and visited set can hold all states.

Common follow-ups

  • What if there are no keys? Return 0, since all keys are already collected.
  • Why include the mask in visited? The same cell can lead to different paths depending on which locks are now passable.
  • Can the search use less memory? A* can sometimes explore fewer states, though it still tracks position and key mask.
  • What if key counts are large? The state space grows exponentially in the number of keys, so pruning or problem-specific structure may be needed.
CodingHardRokuSoftware Engineer

18. Max Stack (LeetCode)

Model answer

The task

Design a stack that supports ordinary stack operations as well as finding and removing the maximum value. If the maximum occurs multiple times, remove the one closest to the top.

Key idea

Keep stack order in a doubly linked list so the top can be accessed or removed in constant time. Track maximum candidates in a max-heap; unique insertion IDs break ties in favor of the most recently pushed item. Entries for items removed from the list are discarded lazily when they reach the heap’s top.

Approach

  1. Add each item to the linked list and push its value and unique ID onto the heap.
  2. Keep the IDs of currently present items in a set.
  3. For pop and popMax, remove the chosen node from the linked list and its ID from the set.
  4. Before reading or removing the maximum, discard heap entries whose IDs are no longer active.
  5. Use the linked-list tail for top; raise an error when an operation requires an item but the stack is empty.
import heapq

class _Node:
    def __init__(self, value=0, item_id=-1):
        self.value = value
        self.item_id = item_id
        self.prev = None
        self.next = None

class MaxStack:
    def __init__(self):
        self.left = _Node()   # Bottom sentinel
        self.right = _Node()  # Top sentinel
        self.left.next = self.right
        self.right.prev = self.left

        self.max_heap = []  # (-value, -item_id)
        self.active = set()
        self.nodes = {}
        self.next_id = 0

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _clean_heap(self):
        while self.max_heap and -self.max_heap[0][1] not in self.active:
            heapq.heappop(self.max_heap)

    def push(self, x: int) -> None:
        item_id = self.next_id
        self.next_id += 1

        node = _Node(x, item_id)
        node.prev = self.right.prev
        node.next = self.right
        self.right.prev.next = node
        self.right.prev = node

        self.nodes[item_id] = node
        self.active.add(item_id)
        heapq.heappush(self.max_heap, (-x, -item_id))

    def pop(self) -> int:
        if self.left.next is self.right:
            raise IndexError("pop from empty MaxStack")

        node = self.right.prev
        self._unlink(node)
        self.active.remove(node.item_id)
        return node.value

    def top(self) -> int:
        if self.left.next is self.right:
            raise IndexError("top of empty MaxStack")
        return self.right.prev.value

    def peekMax(self) -> int:
        if not self.active:
            raise IndexError("peekMax on empty MaxStack")
        self._clean_heap()
        return -self.max_heap[0][0]

    def popMax(self) -> int:
        if not self.active:
            raise IndexError("popMax from empty MaxStack")

        self._clean_heap()
        _, negative_id = heapq.heappop(self.max_heap)
        item_id = -negative_id
        node = self.nodes[item_id]

        self._unlink(node)
        self.active.remove(item_id)
        return node.value

Complexity:

  • Time: push, pop, and top are O(1); maximum operations are O(log P) amortized, where P is the number of pushes.
  • Space: O(P) for heap entries and node records; removed heap entries may remain until cleaned.

Common follow-ups

  • How can stale heap entries be bounded? Rebuild the heap periodically from active items.
  • Can maximum operations be worst-case O(log n) with O(n) space? Use a balanced ordered set keyed by (value, insertion_id).
  • How should empty-stack operations behave? Define a consistent policy, such as raising an exception or returning a sentinel.

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