Mitsogo interview questions & answers

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

CodingEasyMitsogoSoftware Engineer

1. Shortest Subarray With OR at Least K I (LeetCode)

Model answer

The task

Find the length of the shortest non-empty contiguous subarray whose bitwise OR is at least k. Return -1 if no such subarray exists.

Key idea

A sliding window works because adding elements can only add set bits to its OR, but removing an element may clear a bit only if no other window element has it. Track how many times each bit appears so the window OR can be updated correctly as its left edge moves.

Approach

  1. Keep a count for each bit position and the OR of the current window.
  2. Expand the window one element at a time, adding its set bits to the counts.
  3. While the window OR is at least k, record its length and remove its leftmost element.
  4. When a bit’s count drops to zero, clear that bit from the window OR.
  5. Return the shortest length found, or -1 if none was found.
from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if not nums:
            return -1

        bit_count = [0] * max(1, max(nums).bit_length())
        window_or = 0
        left = 0
        shortest = len(nums) + 1

        for right, value in enumerate(nums):
            # Add this value's set bits to the window.
            for bit in range(len(bit_count)):
                mask = 1 << bit
                if value & mask:
                    bit_count[bit] += 1
                    window_or |= mask

            # Shrink while the current window satisfies the target.
            while left <= right and window_or >= k:
                shortest = min(shortest, right - left + 1)

                outgoing = nums[left]
                for bit in range(len(bit_count)):
                    mask = 1 << bit
                    if outgoing & mask:
                        bit_count[bit] -= 1
                        if bit_count[bit] == 0:
                            window_or &= ~mask

                left += 1

        return shortest if shortest <= len(nums) else -1

Complexity:

  • Time: O(nB), where B is the number of bit positions needed for the input values.
  • Space: O(B) for the per-bit counts.

Common follow-ups

  • What if the condition were OR equal to k? Track qualifying windows carefully; “at least” no longer gives the same shrink condition.
  • Can bit updates be made faster? Iterate only over set bits of each value rather than over all B positions.
  • What if the operation were bitwise AND? Maintain per-bit counts and consider how bits change as the window expands and shrinks.
CodingEasyMitsogoSoftware Engineer

2. Find the Integer Added to Array I (LeetCode)

Model answer

The task

Given two arrays where every element in the second array is the corresponding element in the first array plus the same integer, return that integer.

Key idea

The smallest value in the second array is the smallest value in the first array shifted by that integer. Subtract the two minima to recover the shift.

Approach

  1. Find the minimum value in each array.
  2. Return the second array’s minimum minus the first array’s minimum.
from typing import List

class Solution:
    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        # Every value is shifted by the same amount, so the minima shift too.
        return min(nums2) - min(nums1)

Complexity:

  • Time: O(n), to find the minima.
  • Space: O(1), using only a fixed amount of extra space.

Common follow-ups

  • What if the arrays are sorted? Subtract their first elements in O(1).
  • What if the arrays have different lengths? The stated correspondence no longer holds; define how elements relate before choosing an approach.
  • Can you avoid scanning both arrays? Not for unsorted arrays without additional information such as precomputed minima.
CodingMediumMitsogoSoftware Engineer

3. Find the Integer Added to Array II (LeetCode)

Model answer

The task

Remove exactly two elements from nums1, then add the same integer to every remaining element. Return the smallest integer that can make the resulting values equal nums2, regardless of order.

Key idea

Sort both arrays: adding one constant preserves the order of the remaining values. The first value of sorted nums2 must match one of the first three values of sorted nums1, since at most two values can be removed before it.

Approach

  1. Sort both arrays.
  2. Try each of the first three values in nums1 as the value that maps to nums2[0].
  3. For each candidate, scan both arrays in order.
  4. Skip a nums1 value if it is too small to match the current nums2 value; reject the candidate if it is too large.
  5. Keep the smallest candidate that matches every value in nums2 while skipping at most two values.
from typing import List

class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        a = sorted(nums1)
        b = sorted(nums2)
        best = None

        # At most two values can precede the first retained value.
        for i in range(3):
            shift = b[0] - a[i]
            p = q = 0
            skipped = 0

            while p < len(a) and q < len(b):
                adjusted = a[p] + shift

                if adjusted == b[q]:
                    p += 1
                    q += 1
                elif adjusted < b[q]:
                    # This nums1 value cannot match any later nums2 value.
                    p += 1
                    skipped += 1
                else:
                    # The current nums1 value has already passed b[q].
                    skipped = 3
                    break

            # Any remaining nums1 values must also be removed.
            skipped += len(a) - p

            if q == len(b) and skipped == 2:
                if best is None or shift < best:
                    best = shift

        return best

Complexity:

  • Time: O(n log n), for sorting; the three scans take O(n).
  • Space: O(n), for the sorted copies.

Common follow-ups

  • What if the number of removed elements is k? Try the first k + 1 possible matches and allow k skips.
  • Can sorting be avoided? Not generally; without sorted order, matching a translated multiset needs a different counting-based approach.
  • Why must the candidate come from the first three values? At most two earlier nums1 values can be removed before the first matched value.
CodingMediumMitsogoSoftware Engineer

4. Shortest Subarray With OR at Least K II (LeetCode)

Model answer

The task

Find the length of the shortest non-empty contiguous subarray whose bitwise OR is at least k. Return -1 if no such subarray exists.

Key idea

OR values can only gain set bits as a window expands, but removing an element makes it hard to update the OR directly. Track how many window elements contain each bit; a bit can be cleared when its count reaches zero.

Approach

  1. Keep a sliding window and a count for each bit position used by the input values.
  2. When adding a value, increment the counts of its set bits and set those bits in the window OR.
  3. Whenever the window OR is at least k, record its length and remove its leftmost value.
  4. Clear a bit from the OR only when its count drops to zero.
  5. Return the shortest recorded length, or -1 if no valid window was found.
from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if not nums:
            return -1

        bit_count = [0] * max(1, max(nums).bit_length())
        window_or = 0
        left = 0
        best = len(nums) + 1

        for right, value in enumerate(nums):
            # Add value to the window.
            for bit in range(len(bit_count)):
                if value & (1 << bit):
                    bit_count[bit] += 1
                    window_or |= 1 << bit

            # Shrink while the current window satisfies the condition.
            while left <= right and window_or >= k:
                best = min(best, right - left + 1)
                removed = nums[left]

                for bit in range(len(bit_count)):
                    if removed & (1 << bit):
                        bit_count[bit] -= 1
                        if bit_count[bit] == 0:
                            window_or &= ~(1 << bit)

                left += 1

        return best if best <= len(nums) else -1

Complexity:

  • Time: O(nB), where B is the number of bit positions in the largest value.
  • Space: O(B) for the per-bit counts.

Common follow-ups

  • Why use bit counts instead of recomputing the OR? They allow removing the leftmost value without rescanning the whole window.
  • Can the bit loop be optimized? Iterate only over set bits of each value, using value & -value to extract them.
  • What if the condition were OR equal to k? The same window state works, but the shrinking logic needs a different strategy because OR is not monotonic toward equality.
CodingMediumMitsogoSoftware Engineer

5. Minimum Substring Partition of Equal Character Frequency (LeetCode)

Model answer

The task

Partition a string into the fewest contiguous pieces such that, within each piece, every distinct character appears the same number of times. Return the minimum number of pieces.

Key idea

Use dynamic programming over prefixes. For each possible piece ending at a position, grow it backward while tracking character counts; a piece is valid when its length equals its number of distinct characters times its largest frequency.

Approach

  1. Let dp[i] be the minimum pieces needed to partition the first i characters.
  2. Set dp[0] = 0; initialize all other entries to infinity.
  3. For each endpoint, scan possible starting positions backward, updating frequencies, distinct-character count, and maximum frequency.
  4. When the current piece is valid, update dp using the best partition before its start.
  5. Return the value for the full string.
class Solution:
    def minimumSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [float("inf")] * (n + 1)
        dp[0] = 0

        for end in range(n):
            counts = {}
            distinct = 0
            max_frequency = 0

            # Grow a candidate substring backward, ending at `end`.
            for start in range(end, -1, -1):
                char = s[start]
                counts[char] = counts.get(char, 0) + 1

                if counts[char] == 1:
                    distinct += 1
                max_frequency = max(max_frequency, counts[char])

                length = end - start + 1

                # All counts equal max_frequency exactly when the
                # total length is distinct * max_frequency.
                if length == distinct * max_frequency:
                    dp[end + 1] = min(dp[end + 1], dp[start] + 1)

        return dp[n]

Complexity:

  • Time: O(n²), considering every possible substring ending position.
  • Space: O(n + k), for the DP array and frequency map, where k is the number of distinct characters.

Common follow-ups

  • How would you handle a restricted alphabet? Use a fixed-size frequency array instead of a hash map.
  • Can the worst-case time be improved? The direct DP checks quadratically many substrings; exploiting special input structure may help, but a general exact solution uses this enumeration.
  • What if the pieces need a different frequency condition? Change the substring-validity check while keeping the prefix DP structure.
CodingMediumMitsogoSoftware Engineer

6. Maximum Total Reward Using Operations I (LeetCode)

Model answer

The task

Choose rewards so that each chosen reward is strictly greater than the total collected so far, adding it to that total. Return the largest total that can be reached.

Key idea

Track reachable totals in a bitset: bit t is set if total t is achievable. For reward x, only totals below x can use it; shift those states by x and merge them into the bitset.

Approach

  1. Sort and deduplicate the rewards; duplicate values cannot help produce additional totals.
  2. Start with only total 0 reachable.
  3. For each reward x, keep only reachable totals below x, shift them by x, and merge the results.
  4. Return the index of the highest set bit.
class Solution:
    def maxTotalReward(self, rewardValues: list[int]) -> int:
        # Bit t is set when total t is reachable.
        reachable = 1

        for reward in sorted(set(rewardValues)):
            # Keep totals strictly less than reward, then add reward to each.
            below_reward = reachable & ((1 << reward) - 1)
            reachable |= below_reward << reward

        return reachable.bit_length() - 1

Complexity:

  • Time: O(n log n + nM / w), where n is the number of rewards, M is the maximum reward, and w is the machine word size; sorting costs O(n log n), and bitset operations scan O(M / w) words per reward.
  • Space: O(M) bits, since any newly reached total is less than twice the maximum reward.

Common follow-ups

  • Why can rewards be deduplicated? Using a reward twice is impossible: after choosing it, the running total is already at least that reward.
  • Why process rewards in ascending order? Each reward uses only states from earlier rewards, so one pass applies each value once without reusing it.
  • Can this be done without a bitset? Yes. Store reachable totals in a set and add total + reward for each reachable total < reward, though this is often slower.
CodingMediumMitsogoSoftware Engineer

7. Right Triangles (LeetCode)

Model answer

The task

Given a binary grid, count triples of cells containing 1 that form a right triangle with its perpendicular sides parallel to the grid’s rows and columns.

Key idea

For each 1 cell, treat it as the right-angle corner. The other two vertices can be chosen independently from the other 1s in its row and column.

Approach

  1. Count the 1s in every row and column.
  2. Visit each cell containing 1.
  3. Multiply the number of other 1s in its row by the number of other 1s in its column.
  4. Add that product to the answer.
from typing import List

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0]) if rows else 0

        row_ones = [sum(grid[r][c] for c in range(cols)) for r in range(rows)]
        col_ones = [sum(grid[r][c] for r in range(rows)) for c in range(cols)]

        triangles = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    # Choose one other 1 in the same row and one in the same column.
                    triangles += (row_ones[r] - 1) * (col_ones[c] - 1)

        return triangles

Complexity:

  • Time: O(mn), to count row and column totals and scan the grid.
  • Space: O(m + n), for the row and column counts.

Common follow-ups

  • What if the grid is sparse and very large? Store the positions of 1s by row and column, then process only those positions.
  • What if cells have weights? Define how weights affect a triangle’s contribution, then aggregate the needed row and column values accordingly.
  • Can triangles with other orientations be counted? This method counts only triangles whose perpendicular sides align with the grid axes; other orientations need different geometric checks.
CodingMediumMitsogoSoftware Engineer

8. Delayed Count of Equal Elements (LeetCode)

Model answer

The task

The title suggests counting repeated values in an array, but it does not specify what “delayed” means. The code below shows the general frequency-counting core; a precise delay rule is needed to give the full solution.

Key idea

A hash table stores how many times each value occurs. If the delay determines when an element becomes eligible to count, eligibility must be applied before updating its frequency.

Approach

  1. Start with an empty frequency map.
  2. Visit each value in the array.
  3. Increment that value’s count.
  4. Use the resulting map to answer frequency-based queries.
  5. Apply any delay rule during the scan once its meaning is defined.
from collections import defaultdict
from typing import Dict, Hashable, Iterable, TypeVar

T = TypeVar("T", bound=Hashable)

def frequency_counts(values: Iterable[T]) -> Dict[T, int]:
    """Return the number of occurrences of each value."""
    counts: Dict[T, int] = defaultdict(int)

    for value in values:
        counts[value] += 1

    return dict(counts)

Complexity:

  • Time: O(n), where n is the number of values.
  • Space: O(u), where u is the number of distinct values.

Common follow-ups

  • Count equal pairs instead of occurrences: for each value seen, add its current frequency to the pair total, then increment it.
  • Count only values eligible after a delay: define the delay condition, then update the frequency map when each value becomes eligible.
  • Handle a streaming input: maintain the frequency map as values arrive; memory remains proportional to distinct values.
  • Support removals or a sliding window: decrement counts when values leave the window and remove zero-count entries.
CodingHardMitsogoSoftware Engineer

9. Maximum Total Reward Using Operations II (LeetCode)

Model answer

The task

Choose rewards so that each chosen value is greater than the total collected so far. Return the largest total that can be collected.

Key idea

Represent all reachable totals as bits in one integer: bit s is set when total s is possible. For reward x, only totals strictly below x may use it, so shift those bits left by x and merge them into the reachable set.

Process distinct rewards in sorted order. Any reward used later must be larger than the current total, so the chosen rewards naturally increase; sorting lets one pass capture every valid sequence.

Approach

  1. Sort the distinct reward values.
  2. Start with only total zero reachable.
  3. For each reward x, keep the reachable totals below x.
  4. Shift those totals by x and merge them with the existing totals.
  5. Return the index of the highest set bit.
from typing import List

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        # Bit s is set exactly when total s is reachable.
        reachable = 1

        for reward in sorted(set(rewardValues)):
            # Keep only totals strictly less than reward.
            eligible = reachable & ((1 << reward) - 1)

            # Taking this reward adds it to every eligible total.
            reachable |= eligible << reward

        # The highest set bit gives the maximum reachable total.
        return reachable.bit_length() - 1

Complexity:

  • Time: O(nM / w) machine-word operations, where n is the number of distinct rewards, M is the largest reward, and w is the integer bit width.
  • Space: O(M) bits for the reachable totals and intermediate bitsets.

Common follow-ups

  • Why are duplicate rewards removed? Using the same value twice is impossible: after taking it once, the total is already at least that value.
  • Can the bitset be bounded? Yes. A valid next reward must exceed the current total, so after taking reward x, the new total is less than 2x; larger bits cannot be needed.
  • How could the solution return the chosen rewards too? Store predecessor information for newly reached totals, then trace backward from the maximum total.
CodingHardMitsogoSoftware Engineer

10. Construct String with Minimum Cost (LeetCode)

Model answer

The task

Build a target string by concatenating available words, where using a word incurs its associated cost. Return the minimum total cost, or -1 if the target cannot be formed.

Key idea

Group words by length and keep only the minimum cost for each distinct word of that length. Then use dynamic programming over target positions, checking which word lengths match at each position with double rolling hashes.

If the total number of characters across all words is S, there can be at most O(√S) distinct word lengths: having K distinct lengths requires at least 1 + 2 + ... + K characters across one word of each length.

Approach

  1. Compute prefix hashes and powers for the target.
  2. For each word, compute its hash and record the cheapest cost for that hash and length.
  3. Let dp[i] be the minimum cost to build the first i target characters.
  4. For each reachable position, check each distinct length that fits and relax the matching transition.
  5. Return dp[n], or -1 if it remains unreachable.
from typing import List

class Solution:
    def minimumCost(
        self, target: str, words: List[str], costs: List[int]
    ) -> int:
        mod1, mod2 = 1_000_000_007, 1_000_000_009
        base1, base2 = 911_382_323, 972_663_749

        def prefix_hash(text: str, base: int, mod: int) -> List[int]:
            """Return polynomial prefix hashes for text."""
            prefix = [0] * (len(text) + 1)
            for i, char in enumerate(text):
                prefix[i + 1] = (
                    prefix[i] * base + ord(char)
                ) % mod
            return prefix

        n = len(target)
        target_h1 = prefix_hash(target, base1, mod1)
        target_h2 = prefix_hash(target, base2, mod2)

        # Store powers so substring hashes can be normalized.
        pow1 = [1] * (n + 1)
        pow2 = [1] * (n + 1)
        for length in range(1, n + 1):
            pow1[length] = pow1[length - 1] * base1 % mod1
            pow2[length] = pow2[length - 1] * base2 % mod2

        # For each length, map each word hash to its cheapest cost.
        by_length = {}
        for word, cost in zip(words, costs):
            length = len(word)
            if length > n:
                continue

            word_h1 = prefix_hash(word, base1, mod1)[-1]
            word_h2 = prefix_hash(word, base2, mod2)[-1]
            key = (word_h1, word_h2)

            costs_for_length = by_length.setdefault(length, {})
            costs_for_length[key] = min(
                costs_for_length.get(key, float("inf")), cost
            )

        lengths = list(by_length)
        infinity = float("inf")
        dp = [infinity] * (n + 1)
        dp[0] = 0

        # Every transition moves forward, so dp[i] is final when processed.
        for start in range(n):
            if dp[start] == infinity:
                continue

            for length in lengths:
                end = start + length
                if end > n:
                    continue

                hash1 = (
                    target_h1[end] - target_h1[start] * pow1[length]
                ) % mod1
                hash2 = (
                    target_h2[end] - target_h2[start] * pow2[length]
                ) % mod2

                word_cost = by_length[length].get((hash1, hash2))
                if word_cost is not None:
                    dp[end] = min(dp[end], dp[start] + word_cost)

        return -1 if dp[n] == infinity else dp[n]

Complexity:

  • Time: O(nK + S), where K is the number of distinct word lengths and S is the total length of the words.
  • Space: O(n + S), for prefix hashes, DP, and stored word hashes.

Common follow-ups

  • How can hash collisions be avoided entirely? Use a deterministic string-matching structure, such as a suffix array with LCP queries.
  • What if many words share the same spelling? Keep only the cheapest cost for that spelling.
  • What if some word lengths exceed the target length? Ignore them, since they cannot be used.
  • Why is the length scan bounded? K distinct positive lengths require at least K(K+1)/2 total word 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