Zeta interview questions & answers

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

CodingEasyZetaSoftware Engineer

1. Count Equal and Divisible Pairs in an Array (LeetCode)

Model answer

The task

Count pairs of indices i < j whose array values are equal and whose index product is divisible by k.

Key idea

Check each possible pair once. A pair counts only when both its values match and i * j is divisible by k.

Approach

  1. Initialize a counter to zero.
  2. For each index i, visit every later index j.
  3. Increment the counter when the values match and i * j has remainder zero upon division by k.
  4. Return the counter.
from typing import List

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        count = 0

        # Each pair is considered exactly once, with i < j.
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j] and (i * j) % k == 0:
                    count += 1

        return count

Complexity:

  • Time: O(n²), checking each pair of indices once.
  • Space: O(1), using only a counter and loop variables.

Common follow-ups

  • Can this be faster for large arrays? Group indices by value, then count qualifying index pairs within each group; the worst case remains quadratic.
  • Does the method handle negative array values? Yes; equality comparison works the same, and the divisibility test applies only to indices.
  • What if k is zero? The divisibility test is undefined, so the input must require a positive k or specify a different rule.
CodingMediumZetaSoftware Engineer

2. Partition to K Equal Sum Subsets (LeetCode)

Model answer

The task

Determine whether the numbers can be divided into k nonempty groups that all have the same sum.

Key idea

The target sum is sum(nums) // k; any number larger than it makes a valid partition impossible. Use a bitmask to record which numbers are used, and backtrack to fill one group at a time. For a given mask, the current group’s sum is determined by the sum of the used numbers modulo the target.

Approach

  1. Reject invalid k, a non-divisible total, or a number larger than the target.
  2. Sort the numbers in descending order to try larger numbers first.
  3. Recursively select an unused number that fits in the current group.
  4. When a group reaches the target, start filling the next one.
  5. Memoize failed masks; skip duplicate values and stop exploring equivalent first choices.
class Solution:
    def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
        if k <= 0 or k > len(nums):
            return False

        total = sum(nums)
        if total % k != 0:
            return False

        target = total // k
        nums.sort(reverse=True)

        if nums[0] > target:
            return False

        # With nonnegative values and target zero, all values are zero.
        if target == 0:
            return True

        full_mask = (1 << len(nums)) - 1
        failed = set()

        def search(mask: int, group_sum: int) -> bool:
            if mask == full_mask:
                return True

            # Start the next group once this one is complete.
            if group_sum == target:
                return search(mask, 0)

            if mask in failed:
                return False

            previous = None

            for i, value in enumerate(nums):
                bit = 1 << i

                if mask & bit or value == previous:
                    continue

                if group_sum + value <= target:
                    if search(mask | bit, group_sum + value):
                        return True

                previous = value

                # No other choice can start this group more effectively.
                if group_sum == 0:
                    break

            failed.add(mask)
            return False

        return search(0, 0)

Complexity:

  • Time: O(n · 2ⁿ), with up to 2ⁿ masks and up to n choices per state.
  • Space: O(2ⁿ), for memoized masks and recursion state.

Common follow-ups

  • What if groups may be empty? Adjust the validity checks and account for the changed partition rules.
  • Can you reduce memory? A bottom-up bitmask DP still generally uses O(2ⁿ) state.
  • How would you handle duplicate-heavy inputs? Group equal values into counts to reduce redundant choices.
  • What if n is large? The exponential approach may be impractical; discuss constraints or specialized approximations.
CodingMediumZetaSoftware Engineer

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

4. Guess Number Higher or Lower II (LeetCode)

Model answer

The task

Determine the minimum amount of money needed to guarantee winning a number-guessing game when each incorrect guess costs the guessed number. The hidden number is an integer in a known range, and each guess tells you whether the answer is higher or lower.

Key idea

For any interval of possible answers, choose a guess that minimizes the worst-case cost. Guessing x costs x, then the answer lies either below or above x; the required budget is the larger of those two subproblems’ costs.

Approach

  1. Let dp[left][right] be the minimum guaranteed cost for the inclusive interval from left to right.
  2. Compute intervals in order of increasing length, so smaller subintervals are already solved.
  3. For each interval, try every possible guess x.
  4. Its worst-case cost is x + max(dp[left][x - 1], dp[x + 1][right]).
  5. Store the smallest such cost. Empty intervals cost zero.
class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # dp[left][right] is the minimum guaranteed cost for [left, right].
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        # Build answers for increasingly large intervals.
        for length in range(2, n + 1):
            for left in range(1, n - length + 2):
                right = left + length - 1
                best = float("inf")

                # Try each number as the next guess.
                for guess in range(left, right + 1):
                    worst_case = guess + max(
                        dp[left][guess - 1],
                        dp[guess + 1][right],
                    )
                    best = min(best, worst_case)

                dp[left][right] = best

        return dp[1][n]

Complexity:

  • Time: O(n³), considering each interval and each possible guess.
  • Space: O(n²), for the interval DP table.

Common follow-ups

  • Can you reduce the space complexity? Not substantially for this direct interval DP; it relies on storing results for many subintervals.
  • How does the recurrence change if a wrong guess has a different cost? Replace guess with that guess’s cost.
  • What if the goal is to minimize expected cost instead of guaranteed cost? Use a probability-weighted expectation rather than taking the maximum of the two branches.
CodingMediumZetaSoftware Engineer

5. Distribute Coins in Binary Tree (LeetCode)

Model answer

The task

Given a binary tree whose nodes hold coins, find the minimum number of moves needed to leave exactly one coin at each node. A move transfers one coin between two directly connected nodes.

Key idea

For any subtree, its balance is the number of coins it has beyond (or short of) the one coin required per node. That balance must cross the edge connecting the subtree to its parent, so the edge costs the absolute value of the balance.

Approach

  1. Traverse the tree with depth-first search.
  2. For each node, obtain the coin balances of its left and right subtrees.
  3. Add the absolute values of those balances to the move count.
  4. Return the node’s balance: its coins plus its children’s balances, minus one for itself.
  5. Return the accumulated move count after processing the root.
# Definition for a binary tree node:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        moves = 0

        def balance(node: Optional[TreeNode]) -> int:
            nonlocal moves

            if node is None:
                return 0

            left_balance = balance(node.left)
            right_balance = balance(node.right)

            # Each child subtree must send or receive its imbalance
            # across the edge connecting it to this node.
            moves += abs(left_balance) + abs(right_balance)

            # Coins in this subtree minus the one coin needed per node.
            return node.val + left_balance + right_balance - 1

        balance(root)
        return moves

Complexity:

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

Common follow-ups

  • What if the tree is highly skewed? The recursion stack can grow to O(n); an iterative postorder traversal avoids recursion-depth limits.
  • How would you check whether distribution is possible? The total number of coins must equal the number of nodes.
  • Can moves be directed or weighted differently by edge? Track subtree balance as before, but charge each edge according to its transfer cost.
CodingMediumZetaSoftware Engineer

6. Minimize the Maximum Difference of Pairs (LeetCode)

Model answer

The task

Choose p disjoint pairs from the array so that the largest absolute difference among the chosen pairs is as small as possible. Return that smallest possible largest difference.

Key idea

For a candidate limit d, sort the values and greedily pair adjacent values whose difference is at most d. This gives the maximum number of valid disjoint pairs for that limit, so feasibility is monotonic and can be binary-searched.

Approach

  1. Sort the values.
  2. Binary-search the candidate maximum difference from 0 to the difference between the largest and smallest values.
  3. For each candidate, scan from left to right.
  4. When adjacent values are within the candidate, pair them and skip both; otherwise, move to the next value.
  5. A candidate is feasible once the scan forms at least p pairs.
from typing import List

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:
            return 0

        nums.sort()
        low = 0
        high = nums[-1] - nums[0]

        def can_form_pairs(limit: int) -> bool:
            pairs = 0
            i = 0

            while i + 1 < len(nums):
                if nums[i + 1] - nums[i] <= limit:
                    pairs += 1
                    if pairs >= p:
                        return True
                    i += 2  # Both values are now used.
                else:
                    i += 1

            return False

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

        return low

Complexity:

  • Time: O(n log n + n log(D + 1)), where D is the difference between the largest and smallest values.
  • Space: O(n) for Python’s in-place sort.

Common follow-ups

  • What if p is zero? The answer is 0, since no pairs need to be selected.
  • Why does the greedy scan maximize the pair count? Taking a valid adjacent pair uses the smallest available values; skipping it cannot enable more pairs.
  • How would you return the actual pairs? Record each adjacent pair when the greedy scan selects it.
CodingMediumZetaSoftware Engineer

7. Heaters (LeetCode)

Model answer

The task

Find the smallest common coverage radius so every house lies within that distance of at least one heater.

Key idea

For each house, only its nearest heater matters. After sorting heater positions, binary search locates the first heater at or to the right of a house; the nearest heater must be that one or its predecessor.

Approach

  1. Sort the heater positions.
  2. For each house, use binary search to find its insertion position among the heaters.
  3. Compute the distance to the heater on each available side.
  4. Record the house’s nearest-heater distance.
  5. Return the largest such distance, since that radius covers every house.
from bisect import bisect_left
from typing import List

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        # The problem guarantees that at least one heater exists.
        sorted_heaters = sorted(heaters)
        required_radius = 0

        for house in houses:
            index = bisect_left(sorted_heaters, house)
            nearest_distance = float("inf")

            # The first heater at or to the right of the house.
            if index < len(sorted_heaters):
                nearest_distance = sorted_heaters[index] - house

            # The heater immediately to the left, if one exists.
            if index > 0:
                nearest_distance = min(
                    nearest_distance,
                    house - sorted_heaters[index - 1],
                )

            required_radius = max(required_radius, nearest_distance)

        return required_radius

Complexity:

  • Time: O(T log T + H log T), for sorting T heaters and searching for each of H houses.
  • Space: O(T), for the sorted heater list.

Common follow-ups

  • Can this be solved with two pointers? Yes: sort both lists, then advance through heaters while the next heater is at least as close to the current house.
  • What if heaters arrive unsorted? Sorting them first, as above, handles that.
  • How can you avoid sorting for repeated queries? Preprocess heaters into a sorted structure and use binary search for each query.
CodingMediumZetaSoftware Engineer

8. Find All Possible Recipes from Given Supplies (LeetCode)

Model answer

The task

Given recipe names, each recipe’s required ingredients, and the items already available, find the recipes that can eventually be made. A newly made recipe can also be used as an ingredient.

Key idea

Model each ingredient requirement as a dependency edge from ingredient to recipe. Track how many required ingredients each recipe still lacks, then use a queue to propagate newly available items.

Approach

  1. Build a graph from each ingredient to the recipes that need it.
  2. Record each recipe’s number of required ingredients.
  3. Start with the supplied items in a queue.
  4. When an item is processed, reduce the remaining count for every recipe that needs it.
  5. When a recipe has no remaining requirements, add it to the result and process it as a newly available item.
  6. Recipes whose ingredients can’t all be reached remain unavailable, including those involved in dependency cycles.
from collections import defaultdict, deque
from typing import List

class Solution:
    def findAllRecipes(
        self,
        recipes: List[str],
        ingredients: List[List[str]],
        supplies: List[str],
    ) -> List[str]:
        # Map each ingredient to the recipes that depend on it.
        dependents = defaultdict(list)
        remaining = {}

        for recipe, required in zip(recipes, ingredients):
            remaining[recipe] = len(required)
            for item in required:
                dependents[item].append(recipe)

        available = set(supplies)
        queue = deque(available)
        result = []
        made = set()

        # Handle recipes that require no ingredients.
        for recipe in recipes:
            if remaining[recipe] == 0:
                made.add(recipe)
                result.append(recipe)
                if recipe not in available:
                    available.add(recipe)
                    queue.append(recipe)

        # Propagate each available item through the dependency graph.
        while queue:
            item = queue.popleft()

            for recipe in dependents[item]:
                remaining[recipe] -= 1

                if remaining[recipe] == 0 and recipe not in made:
                    made.add(recipe)
                    result.append(recipe)

                    if recipe not in available:
                        available.add(recipe)
                        queue.append(recipe)

        return result

Complexity:

  • Time: O(R + I + S), where R is the number of recipes, I is the total number of ingredient entries, and S is the number of supplies.
  • Space: O(R + I + S) for the graph, counts, queue, and sets.

Common follow-ups

  • What if dependencies contain a cycle? Recipes in the cycle remain unavailable unless their requirements can be satisfied through other available items.
  • How would you return a valid cooking order? Keep the recipes in the order they are added to the result.
  • What if supplies arrive over time? Continue processing newly received items through the same queue until no more recipes become available.
CodingMediumZetaSoftware Engineer

9. 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.
CodingMediumZetaSoftware Engineer

10. Shifting Letters II (LeetCode)

Model answer

The task

Given a lowercase string and range operations that shift letters forward or backward through the alphabet, apply every operation and return the resulting string. Shifts wrap around between a and z.

Key idea

Represent each operation as a signed change over an interval. A difference array records only the changes at each interval’s boundaries; a prefix sum then gives the net shift for each character.

Approach

  1. Create a difference array with one extra slot for the right boundary.
  2. For each operation, choose +1 for a forward shift or -1 for a backward shift.
  3. Add that signed change at the interval’s start and subtract it just after the interval’s end.
  4. Scan the string while accumulating the net shift.
  5. Apply each shift modulo 26 and build the result.
class Solution:
    def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
        n = len(s)
        diff = [0] * (n + 1)

        # Each operation is [start, end, direction]:
        # direction 1 shifts forward; direction 0 shifts backward.
        for start, end, direction in shifts:
            amount = 1 if direction == 1 else -1
            diff[start] += amount
            diff[end + 1] -= amount

        result = []
        net_shift = 0

        for i, char in enumerate(s):
            net_shift += diff[i]
            original = ord(char) - ord("a")
            shifted = (original + net_shift) % 26
            result.append(chr(ord("a") + shifted))

        return "".join(result)

Complexity:

  • Time: O(n + m), where n is the string length and m is the number of operations.
  • Space: O(n), for the difference array and the result.

Common follow-ups

  • What if an operation shifts by more than one position? Store its signed shift amount in the difference array.
  • What if shifts are requested for many substrings after preprocessing? Build prefix sums over the difference array to answer each range’s net shift efficiently.
  • How can this be done in place? The string is immutable in Python, so use a mutable character list and join it at the end.
CodingMediumZetaSoftware Engineer

11. Capacity To Ship Packages Within D Days (LeetCode)

Model answer

The task

Find the smallest ship capacity that can transport all packages within the given number of days, shipping packages in their original order.

Key idea

If a capacity works, any larger capacity also works, so feasibility is monotonic and can be searched with binary search. For a candidate capacity, greedily load each day as many consecutive packages as fit.

Approach

  1. The capacity must be at least the heaviest package.
  2. The sum of all weights is always sufficient, since it can ship everything in one day.
  3. Binary-search this range.
  4. For each candidate, greedily count how many days are needed, starting a new day when the next package would exceed capacity.
  5. Keep the candidate if the required days are within the limit; otherwise, increase the capacity.
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            used_days = 1
            load = 0

            for weight in weights:
                if load + weight > capacity:
                    used_days += 1
                    load = 0

                load += weight

            return used_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            capacity = (left + right) // 2

            if can_ship(capacity):
                right = capacity
            else:
                left = capacity + 1

        return left

Complexity:

  • Time: O(n log(sum(weights) - max(weights) + 1)), for the binary search and feasibility checks.
  • Space: O(1), excluding the input.

Common follow-ups

  • What if packages can be reordered? The greedy check changes; for positive weights, packing the largest packages first may help, but the original-order constraint is essential to this solution.
  • Can you return the day-by-day assignments too? Record each greedy day’s packages during a final feasibility pass.
  • What if the number of days is very large? The same bounds and binary search apply; capacities below the heaviest package remain impossible.
CodingMediumZetaSoftware Engineer

12. Power Grid Maintenance (LeetCode)

Model answer

The task

Given a power grid’s stations and connections, process queries that either take a station offline or ask which station can handle maintenance. A station can only be served by an online station in the same connected grid.

Key idea

The connections never change, so find each station’s connected component once with Union-Find. Keep a min-heap of station IDs per component; when a station goes offline, mark it, and discard offline stations from a heap whenever that heap is needed.

Approach

  1. Use Union-Find to connect stations joined by each connection.
  2. Group station IDs into heaps by their final component.
  3. Start every station as online.
  4. For an offline query, mark the station offline.
  5. For a maintenance query, return the station itself if online. Otherwise, remove offline stations from its component’s heap and return the smallest remaining ID, or -1.
from collections import defaultdict
from heapq import heapify, heappop
from typing import List

class Solution:
    def processQueries(
        self,
        c: int,
        connections: List[List[int]],
        queries: List[List[int]]
    ) -> List[int]:
        parent = list(range(c + 1))
        rank = [0] * (c + 1)

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a, root_b = find(a), find(b)
            if root_a == root_b:
                return
            if rank[root_a] < rank[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            if rank[root_a] == rank[root_b]:
                rank[root_a] += 1

        for a, b in connections:
            union(a, b)

        # Each component's heap contains its station IDs.
        heaps = defaultdict(list)
        for station in range(1, c + 1):
            heaps[find(station)].append(station)
        for heap in heaps.values():
            heapify(heap)

        online = [True] * (c + 1)
        answers = []

        for query_type, station in queries:
            if query_type == 2:
                online[station] = False
                continue

            if online[station]:
                answers.append(station)
                continue

            heap = heaps[find(station)]
            while heap and not online[heap[0]]:
                heappop(heap)

            answers.append(heap[0] if heap else -1)

        return answers

Complexity:

  • Time: O((c + q) α(c) + c log c), where q is the number of queries; each station is removed from a heap at most once.
  • Space: O(c + q), including the answer list; the data structures use O(c).

Common follow-ups

  • What if stations can come back online? Use an ordered set per component to support both insertion and removal.
  • What if connections can change? Recompute components, or use a dynamic connectivity structure if updates are frequent.
  • Can we avoid heaps? A sorted set per component also gives the smallest online station, with updates on each status change.
CodingMediumZetaSoftware Engineer

13. Task Scheduler (LeetCode)

Model answer

The task

Find the fewest time slots needed to run all tasks when identical task types must be separated by at least n slots. A slot may be left idle.

Key idea

The most frequent task types determine the minimum schedule length. Put copies of a most frequent type into frames of length n + 1; other tasks can fill the gaps. If there are enough other tasks to fill every gap, no idle slots are needed.

Approach

  1. Count how many times each task type appears.
  2. Find the largest frequency, max_freq.
  3. Count how many types occur exactly max_freq times.
  4. Compute the frame-based length: (max_freq - 1) * (n + 1) + max_count.
  5. Return the larger of that length and the total number of tasks.
from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequencies = Counter(tasks)
        max_freq = max(frequencies.values())
        max_count = sum(
            frequency == max_freq
            for frequency in frequencies.values()
        )

        # The most frequent tasks establish the frame-based schedule.
        frame_length = (max_freq - 1) * (n + 1) + max_count

        # Other tasks may fill idle slots, but cannot reduce below task count.
        return max(len(tasks), frame_length)

Complexity:

  • Time: O(m + k), to count m tasks and scan k task types.
  • Space: O(k), for the task-frequency counts.

Common follow-ups

  • What if n is zero? The formula returns the task count, since no cooldown is required.
  • What if several task types share the highest frequency? Include all of them in the last frame, as max_count does.
  • How could you construct an actual schedule? Greedily run the most frequent available task, tracking cooldowns with a max-heap and a queue.
  • What if tasks have different cooldowns? The simple formula no longer applies; model each task’s next available time and schedule with a priority queue.
CodingMediumZetaSoftware Engineer

14. Remove K Digits (LeetCode)

Model answer

The task

Given a nonnegative integer as a digit string, remove exactly k digits while keeping the remaining digits in their original order. Return the smallest possible resulting number, without leading zeroes; use "0" if no nonzero digits remain.

Key idea

Build the result from left to right using a monotonic increasing stack. When a new digit is smaller than the stack’s last digit, removing that larger digit makes the number smaller, so greedily remove it while removals remain.

Approach

  1. Start with an empty stack of digits.
  2. For each digit, pop larger digits from the stack while k > 0.
  3. Push the current digit.
  4. If removals remain after processing all digits, remove them from the end.
  5. Strip leading zeroes; return "0" if nothing remains.
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for digit in num:
            # A smaller current digit is better in an earlier position.
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)

        # If the digits were nondecreasing, remove from the right.
        if k > 0:
            stack = stack[:-k]

        # Normalize leading zeroes and handle an empty result.
        result = "".join(stack).lstrip("0")
        return result if result else "0"

Complexity:

  • Time: O(n), where n is the number of digits; each digit is pushed and popped at most once.
  • Space: O(n) for the stack holding the remaining digits.

Common follow-ups

  • What if k is at least the number of digits? The algorithm removes everything and returns "0".
  • Why remove larger digits before smaller ones? Earlier positions have greater place value, so reducing an earlier digit gives the largest improvement.
  • Can this be done without a stack? A mutable character list with a write index simulates the same greedy process.
CodingMediumZetaSoftware Engineer

15. Apply Operations to Make Two Strings Equal (LeetCode)

Model answer

The task

Given two binary strings, find the minimum cost to make them equal. An operation flips two bits: the positions can be arbitrary at cost x, or adjacent at cost 1.

Key idea

Only positions where the strings differ need to be corrected, and each operation flips two bits, so their count must be even. For two mismatches, pairing them costs either x directly or the distance between them using adjacent flips. A dynamic program pairs consecutive mismatches optimally.

Approach

  1. Collect the indices where the strings differ.
  2. If there are an odd number, return -1.
  3. Let dp[k] be the minimum cost to fix the first k mismatch positions.
  4. Pair the last two: the cost is the smaller of x and their distance.
  5. Return the cost for all mismatches.
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        # Positions that must be flipped an odd number of times.
        mismatch = [
            i for i, (a, b) in enumerate(zip(s1, s2))
            if a != b
        ]

        count = len(mismatch)
        if count % 2:
            return -1

        # dp[k] is the minimum cost to fix the first k mismatches.
        dp = [0] * (count + 1)

        for k in range(2, count + 1, 2):
            distance = mismatch[k - 1] - mismatch[k - 2]
            pair_cost = min(x, distance)
            dp[k] = dp[k - 2] + pair_cost

        return dp[count]

Complexity:

  • Time: O(n), where n is the string length.
  • Space: O(n) for the mismatch positions and DP array.

Common follow-ups

  • What if the mismatch count is odd? Return -1, since every operation flips exactly two bits.
  • Can the extra space be reduced? Yes; retain only the previous even-count DP value while processing mismatch pairs.
  • What if adjacent flips have different costs? Use the corresponding path cost between each pair of mismatch positions in the DP.
CodingMediumZetaSoftware Engineer

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

17. Count Univalue Subtrees (LeetCode)

Model answer

The task

Count the nodes whose rooted subtree contains only nodes with the same value. A single node always counts.

Key idea

Use a postorder DFS that reports whether each subtree is univalue. A node qualifies when both child subtrees qualify and each existing child has the node’s value.

Approach

  1. Keep a counter for qualifying subtrees.
  2. Treat an empty child as univalue.
  3. Recursively check the left and right subtrees.
  4. If both qualify and their values match the current node when present, increment the counter.
  5. Return whether the current subtree is univalue, then return the final count.
from __future__ import annotations

class Solution:
    def countUnivalSubtrees(self, root: TreeNode | None) -> int:
        count = 0

        def is_univalue(node: TreeNode | None) -> bool:
            nonlocal count

            if node is None:
                return True

            left_ok = is_univalue(node.left)
            right_ok = is_univalue(node.right)

            if not left_ok or not right_ok:
                return False

            if node.left is not None and node.left.val != node.val:
                return False

            if node.right is not None and node.right.val != node.val:
                return False

            count += 1
            return True

        is_univalue(root)
        return count

Complexity:

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

Common follow-ups

  • How would you avoid recursion for a very deep tree? Use an explicit stack with postorder traversal and store each node’s univalue result.
  • What if the tree is empty? The traversal returns immediately and the count is zero.
  • Can you also return the largest univalue subtree? Track its size alongside the boolean result during the same DFS.
CodingMediumZetaSoftware Engineer

18. Maximum Subarray (LeetCode)

Model answer

The task

Given an integer array, find the largest sum obtainable from a nonempty contiguous subarray. The array may contain only negative numbers.

Key idea

At each position, the best subarray ending there either starts at the current value or extends the best subarray ending just before it. Track that running best and the largest sum seen so far; this naturally handles all-negative arrays.

Approach

  1. Initialize both the running sum and overall maximum to the first value.
  2. Scan the remaining values from left to right.
  3. For each value, either start a new subarray there or extend the previous one.
  4. Update the overall maximum whenever the running sum improves.
  5. Return the overall maximum.
from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # The subarray must be nonempty, so start with the first element.
        current_sum = best_sum = nums[0]

        for value in nums[1:]:
            # Either begin at this value or extend the prior subarray.
            current_sum = max(value, current_sum + value)
            best_sum = max(best_sum, current_sum)

        return best_sum

Complexity:

  • Time: O(n), where n is the number of array elements; each is processed once.
  • Space: O(1), since only two running sums are stored.

Common follow-ups

  • How would you return the subarray’s start and end indices? Track the current start index and record both indices whenever the overall maximum improves.
  • What if the input can be empty? Define the desired empty-input result, then handle it before accessing the first element.
  • How does divide and conquer solve this? Recursively compute the best sum on each half, plus the best suffix on the left and prefix on the right; combine the three results.
CodingMediumZetaSoftware Engineer

19. Longest Substring Without Repeating Characters (LeetCode)

Model answer

The task

Find the length of the longest contiguous section of a string in which every character appears at most once.

Key idea

Maintain a sliding window with no repeated characters. When a character repeats within the window, move the left edge just past its previous occurrence.

Approach

  1. Track each character’s most recent index in a dictionary.
  2. Keep left as the window’s starting index and best as its longest length so far.
  3. For each character, move left forward if its previous occurrence is inside the current window.
  4. Record the character’s current index and update best using the window length.
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0

        for right, char in enumerate(s):
            # Skip past a repeated character if it is in the current window.
            if char in last_seen and last_seen[char] >= left:
                left = last_seen[char] + 1

            last_seen[char] = right
            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), because each character is processed once.
  • Space: O(k), where k is the number of distinct characters encountered.

Common follow-ups

  • Return the substring itself: store the best window’s start and end indices when updating best.
  • Handle a stream of characters: keep the same window state and process each arriving character incrementally.
  • Use a fixed-size character set: replace the dictionary with an array of last-seen indices.
CodingHardZetaSoftware Engineer

20. Minimum Window Substring (LeetCode)

Model answer

The task

Given strings s and t, return the shortest contiguous substring of s that contains every character in t, including repeated characters. Return an empty string if no such substring exists.

Key idea

Use a sliding window and character counts. Expand the right edge until the window contains all required character frequencies, then move the left edge rightward as far as possible while keeping the window valid.

Approach

  1. Count the required characters in t.
  2. Move the right edge across s, updating counts for relevant characters.
  3. Track how many distinct required characters have reached their needed frequencies.
  4. Whenever all are satisfied, record the window if it is shorter than the best found.
  5. Shrink from the left until the window is no longer valid, then continue expanding.
from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        need = Counter(t)
        window = defaultdict(int)
        required = len(need)
        formed = 0

        best_start = 0
        best_length = float("inf")
        left = 0

        for right, char in enumerate(s):
            if char in need:
                window[char] += 1
                if window[char] == need[char]:
                    formed += 1

            # Shrink while all required character counts are satisfied.
            while formed == required:
                length = right - left + 1
                if length < best_length:
                    best_start = left
                    best_length = length

                left_char = s[left]
                if left_char in need:
                    if window[left_char] == need[left_char]:
                        formed -= 1
                    window[left_char] -= 1
                left += 1

        if best_length == float("inf"):
            return ""
        return s[best_start:best_start + best_length]

Complexity:

  • Time: O(|s| + |t|), since each pointer advances at most the length of s.
  • Space: O(d), where d is the number of distinct characters in t.

Common follow-ups

  • What if t is empty? Return an empty string immediately, as handled above.
  • Can you return all shortest windows? Keep each window matching the minimum length instead of only one.
  • How does this scale to a stream? Maintain counts and window positions, while accounting for the storage needed to retain candidate characters.

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