HashedIn interview questions & answers

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

CodingEasyHashedInSoftware Engineer

1. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyHashedInSoftware Engineer

2. Longest Common Prefix (LeetCode)

Model answer

The task

Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.

Key idea

Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.

Approach

  1. If the list is empty, return an empty string.
  2. Scan each character of the first string from left to right.
  3. For each position, compare that character with the character at the same position in every other string.
  4. If a string is too short or a character differs, return the matching prefix before that position.
  5. If all positions match, return the first string.
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Complexity:

  • Time: O(S), where S is the total number of characters inspected.
  • Space: O(1) auxiliary space, excluding the returned prefix.

Common follow-ups

  • How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
  • Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
  • What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.
CodingMediumHashedInSoftware Engineer

3. Restore IP Addresses (LeetCode)

Model answer

The task

Given a string of digits, insert three dots to form all valid IPv4 addresses. Each address has four numeric parts from 0 to 255, and a part may not have leading zeros unless it is exactly "0".

Key idea

Build the address one part at a time with backtracking. Each part can contain only one to three digits, so there are at most three choices per step; reject invalid parts immediately.

Approach

  1. Start at the beginning of the string with no parts selected.
  2. Before branching, check whether the remaining digits can fit into the remaining parts.
  3. Try taking one, two, or three digits for the next part.
  4. Skip parts with leading zeros or values above 255.
  5. When four parts are selected, add the address if all digits were used.
class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        result = []
        parts = []

        def backtrack(start: int) -> None:
            parts_left = 4 - len(parts)
            digits_left = len(s) - start

            # Each remaining part must use 1 to 3 digits.
            if not (parts_left <= digits_left <= 3 * parts_left):
                return

            if parts_left == 0:
                if start == len(s):
                    result.append(".".join(parts))
                return

            for length in range(1, 4):
                end = start + length
                if end > len(s):
                    break

                part = s[start:end]

                # Multi-digit parts cannot start with zero.
                if length > 1 and part[0] == "0":
                    continue
                if int(part) > 255:
                    continue

                parts.append(part)
                backtrack(end)
                parts.pop()

        backtrack(0)
        return result

Complexity:

  • Time: O(R), where R is the number of returned addresses; only four parts are chosen, each with at most three candidate lengths.
  • Space: O(R) for the results, plus O(1) auxiliary space because the recursion depth is at most four.

Common follow-ups

  • How would you count addresses without returning them? Increment a counter at each valid complete address instead of storing it.
  • Can the pruning be improved? The bounds check already rejects states where the remaining digits cannot fit into the remaining parts.
  • What if the address format changes? Parameterize the number of parts, maximum part length, and maximum numeric value.
  • How would you support IPv6? Use the same backtracking pattern, but validate hexadecimal groups and the IPv6-specific formatting rules.
CodingMediumHashedInSoftware Engineer

4. Number of Islands (LeetCode)

Model answer

The task

Given a grid of land and water, count the groups of connected land cells. Cells connect horizontally or vertically, not diagonally.

Key idea

Each group is one island. Scan the grid, and whenever an unvisited land cell is found, count a new island and explore its entire connected region. Mark cells as visited when adding them to the search queue so no cell is processed more than once.

Approach

  1. Return 0 if the grid is empty.
  2. Scan every cell in the grid.
  3. When a land cell is found, increment the island count and start a breadth-first search from it.
  4. During the search, mark each discovered land cell as water and add its in-bounds land neighbors to the queue.
  5. Return the island count after the scan is complete.
from collections import deque
from typing import List

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

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

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1":
                    continue

                islands += 1
                grid[row][col] = "0"
                queue = deque([(row, col)])

                while queue:
                    current_row, current_col = queue.popleft()

                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_row = current_row + dr
                        next_col = current_col + dc

                        if (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                            and grid[next_row][next_col] == "1"
                        ):
                            # Mark when enqueuing to avoid duplicate work.
                            grid[next_row][next_col] = "0"
                            queue.append((next_row, next_col))

        return islands

Complexity: Time: O(rows * cols), since each cell is examined at most a constant number of times.

Complexity: Space: O(rows * cols) in the worst case for the BFS queue.

Common follow-ups

  • Preserve the input grid? Track visited cells in a separate set instead of changing land cells to water.
  • Use depth-first search instead? Recursively or iteratively explore the four neighbors; iterative DFS avoids recursion-depth concerns.
  • Count diagonally connected land as part of the same island? Include the four diagonal directions in the neighbor list.
CodingMediumHashedInSoftware Engineer

5. Next Permutation (LeetCode)

Model answer

The task

Rearrange the array in place to produce the next lexicographically greater ordering of its values. If no greater ordering exists, wrap around to the smallest ordering.

Key idea

The suffix after the rightmost position where the sequence increases is in descending order, so it is already the largest arrangement of those values. Swap that position with the smallest value in the suffix that is still larger, then reverse the suffix to make it as small as possible.

Approach

  1. Scan from right to left to find the rightmost index whose value is smaller than the value after it.
  2. If such an index exists, scan from the end to find the rightmost value larger than the pivot, then swap them.
  3. Reverse the portion after the pivot. This also handles the case where no pivot exists: the whole array becomes ascending.
  4. Mutate the input list directly.
from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)

        # Find the rightmost position that can be increased.
        pivot = n - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            # The suffix is descending; its rightmost value greater
            # than the pivot is the smallest value that can replace it.
            successor = n - 1
            while nums[successor] <= nums[pivot]:
                successor -= 1

            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        # Reverse the suffix to make it the smallest possible ordering.
        left, right = pivot + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Complexity:

  • Time: O(n), with a constant number of linear scans.
  • Space: O(1), since the rearrangement is done in place.

Common follow-ups

  • Why choose the rightmost pivot? It preserves the longest possible prefix, making the next ordering as close as possible.
  • How are duplicate values handled? The strict comparisons skip equal values and still select the correct next ordering.
  • What if the input is already in descending order? No pivot exists, so reversing the full array produces the smallest ordering.
  • How would you return a new list instead? Copy the input first, then apply the same in-place algorithm to the copy.
CodingMediumHashedInSoftware Engineer

6. Maximum Points Inside the Square (LeetCode)

Model answer

The task

Choose a square centered at the origin, with sides parallel to the axes, so that the characters associated with points inside it are all distinct. Return the largest number of points such a square can contain.

Key idea

A point first enters the square when its distance max(abs(x), abs(y)) is reached. Process points in increasing distance, adding a whole equal-distance group only if its characters are new; a duplicate means that group cannot be included.

Approach

  1. Compute each point’s distance from the origin using the Chebyshev metric.
  2. Sort the points by that distance.
  3. Process points with equal distances as a group.
  4. If a group repeats a character already seen or repeats one within itself, stop before adding the group.
  5. Otherwise, add the group’s points and characters to the running result.
from typing import List

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        # A point is inside a square of half-side length r when
        # max(|x|, |y|) <= r.
        ordered = sorted(
            (max(abs(x), abs(y)), s[i])
            for i, (x, y) in enumerate(points)
        )

        seen = set()
        answer = 0
        i = 0

        while i < len(ordered):
            distance = ordered[i][0]
            j = i

            # Collect every point at this same distance. The square
            # cannot include only part of this group.
            chars = []
            while j < len(ordered) and ordered[j][0] == distance:
                chars.append(ordered[j][1])
                j += 1

            if len(set(chars)) != len(chars) or any(c in seen for c in chars):
                break

            seen.update(chars)
            answer += len(chars)
            i = j

        return answer

Complexity:

  • Time: O(n log n), for sorting the points.
  • Space: O(n), for the sorted points and character set.

Common follow-ups

  • Can sorting be avoided? Track each character’s two smallest distances, then count points strictly before the smallest second occurrence.
  • How do equal-distance points affect the result? The square includes all points at that distance together, so a duplicate in the group excludes the entire group.
  • What if the square’s center changes? Recompute each point’s distance using its maximum absolute coordinate difference from the new center.
CodingMediumHashedInSoftware Engineer

7. Edit Distance (LeetCode)

Model answer

The task

Given two strings, find the fewest single-character insertions, deletions, or replacements needed to change one into the other.

Key idea

Let dp[j] represent the edit distance between the processed prefix of the first string and the first j characters of the second. For each character pair, either keep matching characters at no cost or choose the cheapest insertion, deletion, or replacement.

Approach

  1. Make the second string the shorter one to keep the DP row small.
  2. Initialize distances for converting the empty first prefix into each prefix of the second string.
  3. Process the first string one character at a time, keeping the previous row’s diagonal value.
  4. Update each cell using the matching-character case or the minimum of the three edit operations.
  5. Return the final row value.
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # Keep the DP row as short as possible.
        if len(word2) > len(word1):
            word1, word2 = word2, word1

        # Distances from an empty prefix of word1 to prefixes of word2.
        dp = list(range(len(word2) + 1))

        for i, char1 in enumerate(word1, start=1):
            # Distance from the current word1 prefix to an empty word2 prefix.
            diagonal = dp[0]
            dp[0] = i

            for j, char2 in enumerate(word2, start=1):
                above = dp[j]

                if char1 == char2:
                    dp[j] = diagonal
                else:
                    # Insert, delete, or replace one character.
                    dp[j] = 1 + min(
                        dp[j - 1],  # Insert
                        above,      # Delete
                        diagonal,   # Replace
                    )

                diagonal = above

        return dp[-1]

Complexity:

  • Time: O(mn), where m and n are the string lengths; each pair of characters is processed once.
  • Space: O(min(m, n)), for the DP row.

Common follow-ups

  • How would you reconstruct the actual edits? Store the full DP table, then backtrack from the final cell.
  • What if insertion, deletion, and replacement have different costs? Use those costs in the recurrence.
  • Can the time be reduced when the strings are very different in length? A length difference greater than the allowed edit limit can rule out a result within that limit.
CodingMediumHashedInSoftware 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.
CodingMediumHashedInSoftware Engineer

9. Longest Palindromic Substring (LeetCode)

Model answer

The task

Given a string, return its longest contiguous substring that reads the same forward and backward. If several substrings have the same maximum length, returning any of them is acceptable.

Key idea

Every palindrome has a center: either a character (odd length) or the gap between two characters (even length). Expand outward from each possible center while the characters match, keeping track of the longest range found.

Approach

  1. Initialize the best range to an empty substring.
  2. For each character position, expand from that position to check odd-length palindromes.
  3. Also expand from the gap after that position to check even-length palindromes.
  4. When an expansion finds a longer palindrome, save its start and end indices.
  5. Return the substring covered by the saved range.
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_start = 0
        best_length = 0

        def expand(left: int, right: int) -> None:
            nonlocal best_start, best_length

            # Keep expanding while the current range is a palindrome.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                length = right - left + 1
                if length > best_length:
                    best_start = left
                    best_length = length
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)      # Odd-length palindromes
            expand(center, center + 1)  # Even-length palindromes

        return s[best_start:best_start + best_length]

Complexity:

  • Time: O(n²), since each of the O(n) centers can expand across O(n) characters.
  • Space: O(1), excluding the returned substring.

Common follow-ups

  • How can this be made linear time? Use Manacher’s algorithm to reuse information from previously explored centers.
  • How would you return all longest palindromic substrings? Track every range tied for the maximum length.
  • What if the input is empty? The method returns an empty string.
  • How would you count all palindromic substrings? Count each successful expansion instead of only saving the longest range.
CodingMediumHashedInSoftware Engineer

10. Beautiful Arrangement (LeetCode)

Model answer

The task

Count the permutations of the integers from 1 through n where each value is compatible with its 1-based position: either divides that position or is divisible by it.

Key idea

Build the permutation one position at a time and remember which values have already been used in a bitmask. The mask uniquely identifies the remaining choices, so memoization avoids recomputing the same partial arrangements.

Approach

  1. Represent used values with an n-bit mask.
  2. Derive the next position from the number of set bits in the mask.
  3. Try each unused value that satisfies the divisibility condition at that position.
  4. Recursively count completions and cache the result for each mask.
  5. Return the count starting from the empty mask.
from functools import lru_cache

class Solution:
    def countArrangement(self, n: int) -> int:
        @lru_cache(maxsize=None)
        def count(mask: int) -> int:
            # Positions are 1-based; the number already placed
            # determines the next position.
            position = mask.bit_count() + 1

            if position > n:
                return 1

            total = 0

            for value in range(1, n + 1):
                bit = 1 << (value - 1)

                if mask & bit:
                    continue

                if position % value == 0 or value % position == 0:
                    total += count(mask | bit)

            return total

        return count(0)

Complexity:

  • Time: O(n * 2^n) — at most 2^n masks, each checking up to n values.
  • Space: O(2^n) — memoized results for masks, plus recursion depth of at most n.

Common follow-ups

  • How can candidate checks be reduced? Precompute compatible values for each position, then iterate only those.
  • Can the search be pruned with a better ordering? Fill the most constrained positions first; track positions explicitly since they are no longer implied by the mask.
  • How would you return an arrangement, not just the count? Store a successful choice during the search and reconstruct it from the masks.
CodingMediumHashedInSoftware Engineer

11. Container With Most Water (LeetCode)

Model answer

The task

Given nonnegative heights arranged along a line, choose two positions to form a container with the greatest possible area. Its area is the distance between the positions multiplied by the shorter of their two heights.

Key idea

Start with the widest possible pair, at the two ends. The shorter side limits the area, so moving the taller side inward cannot improve that limiting height and only reduces the width. Move the shorter side instead, hoping to find a taller boundary.

Approach

  1. Set pointers to the first and last positions.
  2. Compute the area using their distance and the shorter height; update the best area.
  3. Move the pointer at the shorter height inward by one position.
  4. Repeat until the pointers meet.
  5. Return the greatest area seen.
from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        best_area = 0

        while left < right:
            width = right - left
            limiting_height = min(height[left], height[right])
            best_area = max(best_area, width * limiting_height)

            # The shorter side limits this container's area.
            # Moving the taller side inward cannot improve that limit.
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return best_area

Complexity:

  • Time: O(n), because each pointer moves inward at most n times.
  • Space: O(1), since only a few variables are used.

Common follow-ups

  • What if heights can be negative? A negative height does not describe a valid container; clarify the input rules, or treat invalid heights as unusable.
  • Why is it safe to discard the shorter side? With the same shorter boundary, every inward pair has less width, so it cannot produce a larger area.
  • Can this be done with extra memory? Not usefully for this objective; the two-pointer scan already processes the candidates in linear time with constant space.
CodingMediumHashedInSoftware Engineer

12. Jump Game II (LeetCode)

Model answer

The task

Given an array where each value is the maximum distance you can jump forward from that position, find the fewest jumps needed to reach the final index.

Key idea

Treat all indices reachable with the same number of jumps as a layer. While scanning a layer, track the farthest index the next jump can reach; when the current layer ends, commit one jump and move to the next layer.

Approach

  1. If the array has at most one element, return 0.
  2. Track the current layer’s end and the farthest index reachable while scanning it.
  3. When the scan reaches the layer’s end, increment the jump count and set the next layer’s end to the farthest reach.
  4. Stop once the final index is reachable. Return -1 if progress stalls and the end cannot be reached.
from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0

        jumps = 0
        layer_end = 0
        farthest = 0

        # The final index needs no further scan: reaching it is sufficient.
        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])

            if i == layer_end:
                # Finish this layer and take one jump into the next.
                if farthest == layer_end:
                    return -1  # Unreachable input.
                jumps += 1
                layer_end = farthest

                if layer_end >= n - 1:
                    return jumps

        return -1

Complexity:

  • Time: O(n), because each index is scanned once.
  • Space: O(1), because only a few counters are stored.

Common follow-ups

  • Return the actual jump path? Store a predecessor when extending the farthest reach, then backtrack from the final index.
  • What if some indices are unreachable? The implementation returns -1 if the scan cannot extend its reachable range.
  • Can the same method count jumps to any target index? Yes; treat that target as the end and stop when its layer becomes reachable.
CodingMediumHashedInSoftware Engineer

13. Sort Colors (LeetCode)

Model answer

The task

Rearrange an array containing only 0, 1, and 2 so the values appear in ascending order. Modify the array in place.

Key idea

Use three pointers to divide the array into regions: 0s at the front, 2s at the back, and 1s in between. Each step places one value into its correct region, so the array is processed in one pass without extra storage.

Approach

  1. Set low to the start and high to the end of the array.
  2. Scan with current, starting at the beginning.
  3. If the current value is 0, swap it with low, then advance both pointers.
  4. If it is 1, advance current.
  5. If it is 2, swap it with high and move high left. Do not advance current, since the swapped-in value still needs inspection.
  6. Stop when current passes high.
class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """Sort nums in place; return no value."""
        low = 0
        current = 0
        high = len(nums) - 1

        while current <= high:
            if nums[current] == 0:
                nums[low], nums[current] = nums[current], nums[low]
                low += 1
                current += 1
            elif nums[current] == 1:
                current += 1
            else:  # nums[current] == 2
                nums[current], nums[high] = nums[high], nums[current]
                high -= 1

Complexity:

  • Time: O(n), where n is the number of values; each pointer moves only across the array.
  • Space: O(1), since the rearrangement is in place.

Common follow-ups

  • What if there are k distinct values? Use counting or a generalized partitioning strategy; the best approach depends on whether extra passes or storage are allowed.
  • Must the sort be stable? This in-place partitioning is not stable; preserving the order of equal values may require extra space or a different algorithm.
  • What if values outside 0, 1, and 2 appear? Validate or define their placement, then adapt the partitioning logic accordingly.
CodingMediumHashedInSoftware Engineer

14. Koko Eating Bananas (LeetCode)

Model answer

The task

Given pile sizes and a fixed number of hours, find the smallest integer eating speed that lets Koko finish all the bananas in time. Each pile is handled separately, and any leftover bananas in a pile still take a full hour.

Key idea

Feasibility is monotonic: if a speed works, any faster speed works too. Binary-search the range from 1 to the largest pile, checking each candidate speed by summing the hours needed for every pile.

Approach

  1. Set the search bounds to 1 and the largest pile size.
  2. For a candidate speed, compute each pile’s hours with ceiling division: (pile + speed - 1) // speed.
  3. If the total hours fit within the limit, record the speed and search lower.
  4. Otherwise, search higher.
  5. Return the smallest feasible speed.
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left, right = 1, max(piles)

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

            # Check whether this speed finishes all piles in time.
            hours = sum((pile + speed - 1) // speed for pile in piles)

            if hours <= h:
                right = speed
            else:
                left = speed + 1

        return left

Complexity:

  • Time: O(n log m), where n is the number of piles and m is the largest pile; each binary-search check scans the piles.
  • Space: O(1), excluding the input; the check uses only a constant amount of extra space.

Common follow-ups

  • What if the hours limit is smaller than the number of piles? No speed can finish in time, since each nonempty pile takes at least one hour.
  • Can the search bounds be tightened? A lower bound can be derived from total bananas divided by available hours, rounded up.
  • What if piles can be processed in parallel? The feasibility calculation changes to account for concurrent work; this binary search applies when piles are eaten sequentially.
CodingMediumHashedInSoftware Engineer

15. Coin Change (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

Complexity:

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

Common follow-ups

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

16. Maximum Product Subarray (LeetCode)

Model answer

The task

Given an integer array, find the largest product of any nonempty contiguous subarray.

Key idea

A negative number can turn a very small product into the largest one, so track both the maximum and minimum product ending at the current position. Update both for each number, then keep the best maximum seen overall.

Approach

  1. Initialize the ending maximum, ending minimum, and overall answer to the first number.
  2. For each remaining number, save the old ending maximum.
  3. Update the ending maximum and minimum from the number alone or from multiplying it by either saved product.
  4. Update the overall answer with the new ending maximum.
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        # The best subarray must include at least one element.
        ending_max = ending_min = answer = nums[0]

        for value in nums[1:]:
            previous_max = ending_max

            # Multiplication by a negative can swap the roles of max and min.
            ending_max = max(value, value * previous_max, value * ending_min)
            ending_min = min(value, value * previous_max, value * ending_min)

            answer = max(answer, ending_max)

        return answer

Complexity:

  • Time: O(n), processing each array element once.
  • Space: O(1), storing only a fixed number of values.

Common follow-ups

  • How would you return the subarray’s indices too? Track the start index associated with each ending maximum and save its range whenever the overall best improves.
  • What changes if the array may be empty? Define the desired empty-input result, then check for emptiness before accessing the first element.
  • How would you handle floating-point values? Use the same recurrence, while accounting for precision and the desired comparison tolerance.
CodingMediumHashedInSoftware Engineer

17. Minimum Time to Repair Cars (LeetCode)

Model answer

The task

Given mechanics with different repair rates, find the smallest time in which they can collectively repair at least the requested number of cars. A mechanic with rank r takes r * k² time to repair k cars.

Key idea

For a proposed time t, a mechanic of rank r can repair isqrt(t // r) cars. The total number repairable is therefore monotonic in t, so binary search finds the minimum feasible time.

Approach

  1. Use min(ranks) * cars² as an upper bound: the fastest mechanic could do all the work alone.
  2. Binary search the time range from 0 to that upper bound.
  3. For each midpoint, sum the cars each mechanic can repair.
  4. If the sum reaches the target, search smaller times; otherwise, search larger ones.
  5. Return the smallest feasible time.
from math import isqrt
from typing import List

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        low = 0
        high = min(ranks) * cars * cars

        while low < high:
            time = (low + high) // 2

            repaired = sum(isqrt(time // rank) for rank in ranks)

            if repaired >= cars:
                high = time
            else:
                low = time + 1

        return low

Complexity:

  • Time: O(n log U), where n is the number of mechanics and U = min(ranks) * cars².
  • Space: O(1) auxiliary space.

Common follow-ups

  • What if mechanics can repair different types of items? Adjust the per-mechanic capacity calculation to match each mechanic’s work-time formula.
  • Can the feasibility check stop early? Yes; stop summing as soon as the total reaches the target.
  • How would you handle very large time values? Use integer arithmetic throughout, as with isqrt(time // rank), to avoid floating-point precision issues.
CodingMediumHashedInSoftware Engineer

18. Subarray Sums Divisible by K (LeetCode)

Model answer

The task

Count the nonempty contiguous ranges of an integer array whose sums are divisible by a given integer k.

Key idea

If two prefix sums have the same remainder when divided by k, their difference is divisible by k. Track how often each remainder has appeared; each occurrence adds that many valid ranges ending at the current position.

Approach

  1. Initialize the frequency of remainder 0 to one, accounting for ranges that start at the beginning.
  2. Scan the array, accumulating a prefix sum.
  3. Compute its remainder modulo k.
  4. Add the number of earlier prefix sums with that remainder to the answer.
  5. Record the current remainder and return the total.
from typing import List

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # The empty prefix has sum 0 and remainder 0.
        remainder_counts = {0: 1}
        prefix_sum = 0
        answer = 0

        for value in nums:
            prefix_sum += value
            remainder = prefix_sum % k

            # Each earlier matching remainder forms a divisible-sum range.
            answer += remainder_counts.get(remainder, 0)
            remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1

        return answer

Complexity:

  • Time: O(n), with one pass through the array.
  • Space: O(min(n, k)), for the distinct remainders recorded.

Common follow-ups

  • What if k is negative? Use abs(k) as the modulus; the set of divisible sums is unchanged.
  • Can the method return the ranges, not just their count? Store prior indices for each remainder and pair them with the current index.
  • What if the array is streamed? Maintain the prefix remainder, remainder frequencies, and running answer incrementally.
CodingMediumHashedInSoftware Engineer

19. Jump Game (LeetCode)

Model answer

The task

Given an array where each value is the maximum distance you may jump forward from that position, determine whether you can reach the final position starting at the first.

Key idea

Track the farthest position reachable so far. If you encounter an index beyond that boundary, it cannot be reached; otherwise, use its jump length to extend the boundary.

Approach

  1. Initialize the farthest reachable index to zero.
  2. Scan the array from left to right.
  3. If the current index is beyond the farthest reachable index, return False.
  4. Extend the farthest reachable index using the current jump.
  5. Return True once the final index is reachable.
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0

        for index, jump in enumerate(nums):
            # This position cannot be reached from any earlier position.
            if index > farthest:
                return False

            farthest = max(farthest, index + jump)

            # No need to inspect positions beyond the destination.
            if farthest >= len(nums) - 1:
                return True

        return True

Complexity:

  • Time: O(n), where n is the number of positions scanned.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if you need the minimum number of jumps? Track the current jump range and the farthest reach of the next range.
  • How would you return an actual path of positions? Store predecessor information as positions first become reachable.
  • What if jumps can go both forward and backward? The reachable set may no longer be represented by a single forward boundary; use graph traversal or a suitable interval-based method.
CodingMediumHashedInSoftware Engineer

20. Group Anagrams (LeetCode)

Model answer

The task

Partition the input strings into groups so that strings in the same group contain the same characters with the same frequencies. The order of the groups does not matter.

Key idea

Sort the characters of each string to create a canonical key. Anagrams produce the same key, so a hash table can collect them together.

Approach

  1. Create a mapping from canonical keys to lists of original strings.
  2. For each string, sort its characters and use the result as its key.
  3. Append the string to the list for that key.
  4. Return all grouped lists.
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for word in strs:
            # Anagrams have identical sorted-character representations.
            key = "".join(sorted(word))
            groups[key].append(word)

        return list(groups.values())

Complexity:

  • Time: O(n · k log k), where n is the number of strings and k is the maximum string length.
  • Space: O(n · k) to store the grouped strings and their keys.

Common follow-ups

  • Can this be faster for a fixed alphabet? Use a character-frequency tuple as the key, computing it in O(k) per string.
  • Does this work with uppercase letters or Unicode? Yes; sorting characters works for any Python strings.
  • Can groups be returned in a deterministic order? Sort the groups, or their keys, before returning them.
  • What if memory is limited? Consider processing input in batches or grouping externally by canonical key.

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