Verkada interview questions & answers

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

CodingEasyVerkadaSoftware Engineer

1. Merge Sorted Array (LeetCode)

Model answer

The task

Combine two already sorted arrays into one sorted array, placing the result in the first array. The first array has enough spare capacity to hold all elements from both arrays.

Key idea

Fill the first array from right to left. Comparing the largest remaining elements avoids overwriting values in the first array that have not yet been processed.

Approach

  1. Set pointers to the last valid elements of both arrays.
  2. Set a write pointer to the last slot in the first array.
  3. While the second array still has elements, compare the values at the two read pointers.
  4. Write the larger value at the write pointer, then move the corresponding read pointer and the write pointer left.
  5. Any remaining elements from the second array are copied into the first. Remaining elements from the first are already in place.
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        """Merge nums2 into nums1 in-place, keeping nums1 sorted."""
        i = m - 1          # Last initialized element in nums1
        j = n - 1          # Last element in nums2
        write = m + n - 1  # Last available position in nums1

        # Fill from the back so unread nums1 elements are not overwritten.
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write] = nums1[i]
                i -= 1
            else:
                nums1[write] = nums2[j]
                j -= 1
            write -= 1

Complexity:

  • Time: O(m + n), since each element is considered at most once.
  • Space: O(1), because the merge modifies the first array directly.

Common follow-ups

  • What if the arrays are sorted in descending order? Reverse the comparison or adapt the traversal direction.
  • What if the result must go into a separate array? Use two forward pointers and allocate O(m + n) extra space.
  • What if either array is empty? The loop naturally handles it; if the second is empty, the first is already complete.
  • Why merge from the end? Writing from the front could overwrite unprocessed elements in the first array.
CodingEasyVerkadaSoftware Engineer

2. Diameter of Binary Tree (LeetCode)

Model answer

The task

Find the diameter of a binary tree: the largest number of edges on a path between any two nodes. The path does not have to pass through the root.

Key idea

At each node, the longest path that passes through it has length left_height + right_height. A postorder depth-first search computes child heights and updates the best diameter along the way.

Approach

  1. Keep a variable for the largest diameter seen so far.
  2. Recursively compute the height of each subtree, using zero for an empty subtree.
  3. At each node, combine its left and right heights to get the path length through it.
  4. Update the best diameter, then return the node’s height to its parent.
  5. Return the recorded diameter after visiting the tree.
# The TreeNode type is provided by the platform.
class Solution:
    def diameterOfBinaryTree(self, root):
        diameter = 0

        def height(node):
            nonlocal diameter

            if node is None:
                return 0

            left_height = height(node.left)
            right_height = height(node.right)

            # The path through this node uses one edge per level
            # from each child subtree.
            diameter = max(diameter, left_height + right_height)

            # Return this subtree's height in nodes.
            return 1 + max(left_height, right_height)

        height(root)
        return diameter

Complexity:

  • Time: O(n), because each node is visited once.
  • Space: O(h), for the recursion stack, where h is the tree height.

Common follow-ups

  • What if the diameter should be measured in nodes? Add one to the edge count for a non-empty tree.
  • How does a skewed tree affect recursion space? Its height is O(n), so recursion may use O(n) stack space.
  • Can this be done iteratively? Yes; use an explicit stack and process nodes in postorder while storing subtree heights.
CodingEasyVerkadaSoftware Engineer

3. Transpose Matrix (LeetCode)

Model answer

The task

Given a rectangular matrix, return a new matrix with its rows and columns swapped. The result has one row for each original column.

Key idea

An element at position (r, c) moves to (c, r). Allocate the result with reversed dimensions, then copy each element to its new position.

Approach

  1. Return an empty matrix if the input has no rows.
  2. Get the input’s row and column counts.
  3. Allocate a result with columns rows and rows columns.
  4. Copy each element from (r, c) to (c, r).
  5. Return the result.
from typing import List

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

        rows = len(matrix)
        columns = len(matrix[0])

        # The transposed matrix has reversed dimensions.
        result = [[0] * rows for _ in range(columns)]

        for r in range(rows):
            for c in range(columns):
                result[c][r] = matrix[r][c]

        return result

Complexity:

  • Time: O(rows × columns), since every element is copied once.
  • Space: O(rows × columns) for the returned matrix.

Common follow-ups

  • Can a square matrix be transposed in place? Yes; swap elements across the diagonal.
  • What if the matrix is sparse? Store only nonzero entries and swap their row and column indices.
  • What if rows have different lengths? The approach assumes a rectangular matrix; ragged rows need separate handling.
CodingEasyVerkadaSoftware Engineer

4. Number of 1 Bits (LeetCode)

Model answer

The task

Count how many bits are set to 1 in a nonnegative integer.

Key idea

Each operation n & (n - 1) clears the rightmost set bit. Repeating it until n becomes zero takes one iteration per set bit.

Approach

  1. Initialize a counter to zero.
  2. While n is nonzero, clear its rightmost set bit.
  3. Increment the counter for each cleared bit.
  4. Return the counter.
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        # Each iteration removes one set bit.
        while n:
            n &= n - 1
            count += 1

        return count

Complexity:

  • Time: O(k), where k is the number of set bits.
  • Space: O(1), using only a counter.

Common follow-ups

  • How would you count bits in a negative integer? Specify a bit width, convert to that width’s two’s-complement representation, then count its set bits.
  • What is a simple alternative? Check the least significant bit repeatedly and shift right; this takes O(b) time for a b-bit value.
  • How can this be optimized in Python? Use n.bit_count() when a built-in solution is allowed.
CodingMediumVerkadaSoftware Engineer

5. 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.
CodingMediumVerkadaSoftware Engineer

6. Basic Calculator II (LeetCode)

Model answer

The task

Evaluate a string containing nonnegative integers, spaces, and the operators +, -, *, and /. Multiplication and division take precedence over addition and subtraction, and division truncates toward zero.

Key idea

Scan the expression once, applying each operator when the next operator is reached. Keep addition and subtraction terms in a stack; immediately combine multiplication and division with the stack’s last term. Summing the stack at the end gives the result.

Approach

  1. Accumulate consecutive digits into the current number, ignoring spaces.
  2. On an operator—or a final sentinel—apply the previous operator to that number.
  3. For + and -, push the signed number; for * and /, update the top stack value.
  4. Implement division with absolute values and a sign check, since Python’s // rounds negative results down.
  5. Return the sum of the stack.
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        number = 0
        previous_operator = "+"

        # A final sentinel ensures the last number is processed.
        for char in s + "+":
            if char.isdigit():
                number = number * 10 + int(char)
            elif char == " ":
                continue
            else:
                if previous_operator == "+":
                    stack.append(number)
                elif previous_operator == "-":
                    stack.append(-number)
                elif previous_operator == "*":
                    stack[-1] *= number
                else:  # Division, truncated toward zero.
                    left = stack[-1]
                    quotient = abs(left) // abs(number)
                    stack[-1] = -quotient if (left < 0) != (number < 0) else quotient

                previous_operator = char
                number = 0

        return sum(stack)

Complexity:

  • Time: O(n), where n is the expression length.
  • Space: O(n) in the worst case for the stack of additive terms.

Common follow-ups

  • Support parentheses? Use a recursive descent parser or an operator/value stack to handle nested expressions.
  • Support unary operators? Track whether the parser expects an operand, then handle leading or repeated signs accordingly.
  • Reduce auxiliary space? Maintain a running total and the current term instead of storing all additive terms.
  • Handle malformed expressions? Validate token order, parentheses, and division by zero while parsing.
CodingMediumVerkadaSoftware Engineer

7. Interval List Intersections (LeetCode)

Model answer

The task

Given two lists of closed intervals, each sorted by start time and internally non-overlapping, return all intervals where an interval from one list overlaps an interval from the other.

Key idea

For the current pair, their overlap runs from the later start to the earlier end. Once the interval that ends first is exhausted, it cannot overlap any later interval in the other list, so advance that pointer.

Approach

  1. Start pointers at the beginning of both lists.
  2. For the current intervals, compute the later start and earlier end.
  3. If the overlap is nonempty, add it to the result.
  4. Advance the pointer for whichever interval ends first. If they end together, advance either one (this solution advances the first).
  5. Continue until one list is exhausted.
from typing import List

class Solution:
    def intervalIntersection(
        self,
        firstList: List[List[int]],
        secondList: List[List[int]]
    ) -> List[List[int]]:
        intersections = []
        i = j = 0

        while i < len(firstList) and j < len(secondList):
            first_start, first_end = firstList[i]
            second_start, second_end = secondList[j]

            # The overlap, if any, is bounded by the later start
            # and the earlier end.
            start = max(first_start, second_start)
            end = min(first_end, second_end)

            # Closed intervals also intersect when start == end.
            if start <= end:
                intersections.append([start, end])

            # The interval that ends first cannot overlap later
            # intervals from the other list.
            if first_end <= second_end:
                i += 1
            else:
                j += 1

        return intersections

Complexity:

  • Time: O(m + n), where m and n are the lengths of the lists; each pointer only moves forward.
  • Space: O(1) auxiliary space, excluding the output list.

Common follow-ups

  • How should endpoint-only contact be handled? For closed intervals, retain start <= end; for half-open intervals, the overlap test may need to be strict.
  • What if the lists are not sorted? Sort them first, then merge overlaps within each list before applying the two-pointer scan.
  • Can the result be streamed? Yes; emit each overlap as it is found instead of storing it, if the caller can consume results incrementally.
CodingMediumVerkadaSoftware Engineer

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

9. Time Based Key-Value Store (LeetCode)

Model answer

The task

Design a key-value store that records values with timestamps. A lookup for a key and time returns the value from the latest timestamp not later than the requested time, or an empty string if none exists.

Key idea

Keep each key’s timestamps and values in parallel, ordered by timestamp. Since timestamps for a key arrive in increasing order, writes append in constant time, and lookups use binary search.

Approach

  1. Map each key to a pair of lists: timestamps and corresponding values.
  2. On set, append the timestamp and value to that key’s lists.
  3. On get, use binary search to find the first timestamp greater than the requested time.
  4. Return the value immediately before that position, or an empty string if the position is zero or the key is missing.
from bisect import bisect_right

class TimeMap:
    def __init__(self):
        # Each key maps to its ordered timestamps and matching values.
        self.data: dict[str, tuple[list[int], list[str]]] = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = ([], [])

        timestamps, values = self.data[key]
        timestamps.append(timestamp)
        values.append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""

        timestamps, values = self.data[key]
        # The insertion position is just after the latest eligible timestamp.
        index = bisect_right(timestamps, timestamp) - 1

        if index < 0:
            return ""
        return values[index]

Complexity:

  • Time: set is O(1); get is O(log n), where n is the number of entries for that key.
  • Space: O(N), storing all N key-value-timestamp entries.

Common follow-ups

  • What if timestamps arrive out of order? Insert each record at its sorted position, which takes O(n) per write, or use a balanced search tree.
  • How would you reduce memory usage? Expire old records when they can no longer be queried, or compress retained history if the API permits.
  • How would you handle many concurrent reads and writes? Protect updates with synchronization, or use immutable snapshots for read-heavy workloads.
CodingMediumVerkadaSoftware Engineer

10. Valid Sudoku (LeetCode)

Model answer

The task

Given a partially filled 9×9 Sudoku board, determine whether its filled cells obey the rules: no digit appears more than once in any row, column, or 3×3 box. Empty cells do not affect validity.

Key idea

Track the digits already seen in each row, column, and box. When a filled cell repeats a digit in any of its three groups, the board is invalid.

Approach

  1. Create a set for each row, column, and 3×3 box.
  2. Visit each cell in the board.
  3. Skip empty cells.
  4. Compute the box index from the cell’s row and column.
  5. Return False if the digit is already in any corresponding set; otherwise add it to all three.
  6. If every cell passes, return True.
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                digit = board[r][c]
                if digit == ".":
                    continue

                # Each 3×3 box has an index from 0 through 8.
                box = (r // 3) * 3 + (c // 3)

                if (
                    digit in rows[r]
                    or digit in cols[c]
                    or digit in boxes[box]
                ):
                    return False

                rows[r].add(digit)
                cols[c].add(digit)
                boxes[box].add(digit)

        return True

Complexity:

  • Time: O(1) for a fixed 9×9 board; more generally, O(n²) for an n×n board.
  • Space: O(1) for a fixed board; more generally, O(n²) for the stored digits.

Common follow-ups

  • How would you handle boards of arbitrary valid Sudoku size? Derive the box dimensions and index formula from the board size.
  • Could you reduce set overhead? Use bit masks to track which digits have appeared in each group.
  • Does a valid board need to be solvable? No; this check only verifies that no current row, column, or box contains duplicates.
CodingMediumVerkadaSoftware Engineer

11. Integer to Roman (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

        result = []

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

        return "".join(result)

Complexity:

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

Common follow-ups

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

12. Merge Intervals (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

        return merged

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

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

Common follow-ups

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

13. Remove Sub-Folders from the Filesystem (LeetCode)

Model answer

The task

Given a list of folder paths, remove every path that is nested beneath another path in the list. Return only the paths that are not subfolders of any other listed path.

Key idea

Sort paths lexicographically so a parent folder comes before its descendants. A path is a subfolder of a retained path only if it starts with that path followed by /; the separator prevents confusing paths such as /a and /ab.

Approach

  1. Sort the paths.
  2. Iterate through them in sorted order.
  3. Keep the first path.
  4. For each next path, compare it with the most recently kept path.
  5. Keep it only if it does not begin with that path plus /.
from typing import List

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # Sorting places each folder before its descendants.
        folder.sort()
        result = []

        for path in folder:
            if not result or not path.startswith(result[-1] + "/"):
                result.append(path)

        return result

Complexity:

  • Time: O(n log n + L), where sorting costs O(n log n) comparisons and L is the total number of path characters checked.
  • Space: O(n) for sorting and the returned list.

Common follow-ups

  • How would you handle paths with repeated or trailing separators? Normalize paths before sorting and checking.
  • How would you solve this with a trie? Insert path components and mark terminal folders; skip descendants of any terminal node.
  • What if the paths arrive as a stream? A single pass is not generally enough to identify all parents; sort externally or buffer and sort the paths.
CodingMediumVerkadaSoftware Engineer

14. Non-overlapping Intervals (LeetCode)

Model answer

The task

Given intervals, find the fewest to remove so that the remaining intervals do not overlap. Intervals that meet at an endpoint are compatible.

Key idea

Instead of choosing which intervals to remove, greedily keep as many as possible. Always keep the interval that ends earliest; it leaves the most room for later intervals.

Approach

  1. Sort intervals by their end time.
  2. Track the end time of the last interval kept.
  3. Keep an interval if its start is at least that end time.
  4. Return the total number of intervals minus the number kept.
from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Earliest-finishing intervals leave the most room for what follows.
        intervals.sort(key=lambda interval: interval[1])

        kept = 0
        last_end = float("-inf")

        for start, end in intervals:
            # Touching endpoints do not count as an overlap.
            if start >= last_end:
                kept += 1
                last_end = end

        return len(intervals) - kept

Complexity:

  • Time: O(n log n), for sorting the intervals.
  • Space: O(n) in the worst case for the sorting implementation.

Common follow-ups

  • What if each interval has a removal cost? Use weighted interval scheduling with dynamic programming.
  • How would you return the intervals to remove? Track the intervals kept by the greedy scan, then report the rest.
  • What if intervals sharing an endpoint count as overlapping? Change the compatibility check from start >= last_end to start > last_end.
CodingHardVerkadaSoftware Engineer

15. Guess the Word (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

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

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

            score = master.guess(best_guess)

            if score == word_length:
                return

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

Complexity:

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

Common follow-ups

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

16. Maximum Profit in Job Scheduling (LeetCode)

Model answer

The task

Choose a set of jobs, each with a start time, end time, and profit, so that no chosen jobs overlap and total profit is maximized. A job may start when another chosen job ends.

Key idea

Sort jobs by start time and use dynamic programming over that order. For each job, compare skipping it with taking it and adding the best profit from the first job that can start after it finishes.

Approach

  1. Pair each job’s start, end, and profit, then sort the jobs by start time.
  2. Store the sorted start times for binary searches.
  3. Process jobs from right to left, so the best profit from any later job is already known.
  4. Use binary search to find the first compatible next job.
  5. Record the better of skipping the current job or taking it.
from bisect import bisect_left
from typing import List

class Solution:
    def jobScheduling(
        self,
        startTime: List[int],
        endTime: List[int],
        profit: List[int],
    ) -> int:
        jobs = sorted(zip(startTime, endTime, profit))
        starts = [job[0] for job in jobs]
        n = len(jobs)

        # dp[i] is the best profit using jobs from index i onward.
        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            start, end, value = jobs[i]

            # Find the first later job that does not overlap this one.
            next_job = bisect_left(starts, end, lo=i + 1)

            take = value + dp[next_job]
            skip = dp[i + 1]
            dp[i] = max(take, skip)

        return dp[0]

Complexity:

  • Time: O(n log n), for sorting and one binary search per job.
  • Space: O(n), for the sorted jobs, start times, and DP table.

Common follow-ups

  • What if jobs may have a setup or cooldown time between them? Search for the first job starting at or after the current end plus that time.
  • How would you reconstruct the selected jobs? Store each DP decision and follow those choices from the first job.
  • Can jobs have negative profit? The skip option lets the algorithm avoid choosing unprofitable jobs.
  • What if jobs arrive online rather than all at once? The sorting-based method no longer directly applies; an online solution needs additional structure and assumptions.
CodingHardVerkadaSoftware Engineer

17. Basic Calculator III (LeetCode)

Model answer

The task

Evaluate an arithmetic expression containing integers, +, -, *, /, parentheses, and optional whitespace. Division should truncate toward zero.

Key idea

Use recursive descent with separate parsing levels for expressions, terms, unary signs, and parenthesized values. This naturally enforces precedence and lets parentheses recurse; implement division explicitly to avoid Python’s floor-rounding behavior.

Approach

  1. Keep a cursor into the expression and skip whitespace whenever reading a token.
  2. Parse an expression as terms combined by + or -.
  3. Parse a term as unary values combined by * or /.
  4. Parse repeated unary signs, then either an integer or a parenthesized expression.
  5. For division, divide absolute values and restore the sign to truncate toward zero.
class Solution:
    def calculate(self, s: str) -> int:
        i = 0
        n = len(s)

        def skip_spaces() -> None:
            nonlocal i
            while i < n and s[i].isspace():
                i += 1

        def parse_primary() -> int:
            nonlocal i
            skip_spaces()

            if s[i] == "(":
                i += 1
                value = parse_expression()
                skip_spaces()
                i += 1  # Consume ')'.
                return value

            value = 0
            while i < n and s[i].isdigit():
                value = value * 10 + int(s[i])
                i += 1
            return value

        def parse_unary() -> int:
            nonlocal i
            sign = 1
            skip_spaces()

            while i < n and s[i] in "+-":
                if s[i] == "-":
                    sign = -sign
                i += 1
                skip_spaces()

            return sign * parse_primary()

        def trunc_div(a: int, b: int) -> int:
            quotient = abs(a) // abs(b)
            return -quotient if (a < 0) != (b < 0) else quotient

        def parse_term() -> int:
            nonlocal i
            value = parse_unary()

            while True:
                skip_spaces()
                if i == n or s[i] not in "*/":
                    return value

                op = s[i]
                i += 1
                right = parse_unary()

                if op == "*":
                    value *= right
                else:
                    value = trunc_div(value, right)

        def parse_expression() -> int:
            nonlocal i
            value = parse_term()

            while True:
                skip_spaces()
                if i == n or s[i] not in "+-":
                    return value

                op = s[i]
                i += 1
                right = parse_term()
                value = value + right if op == "+" else value - right

        return parse_expression()

Complexity:

  • Time: O(n), where n is the expression length.
  • Space: O(d), for recursive calls up to parenthesis nesting depth d.

Common follow-ups

  • How would you support exponentiation? Add a parsing level with the correct precedence and associativity.
  • How would you report malformed input? Validate tokens and closing parentheses, then raise a parsing error.
  • What if nesting is extremely deep? Replace recursive parenthesis parsing with an explicit stack.

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