Accolite interview questions & answers

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

CodingEasyAccoliteSoftware 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.
CodingEasyAccoliteSoftware Engineer

2. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyAccoliteSoftware Engineer

3. Climbing Stairs (LeetCode)

Model answer

The task

Count how many distinct ways there are to reach the top of a staircase with n steps when each move advances either one or two steps.

Key idea

To reach step i, the last move must come from step i - 1 or i - 2. Thus the number of ways to reach i is the sum of the ways to reach those two earlier steps. Only the previous two counts are needed, so there is no need to store a full table.

Approach

  1. Set the number of ways to reach step 0 to 1, representing the single empty sequence of moves.
  2. Set the number of ways to reach step 1 to 1.
  3. For each step from 2 through n, add the counts for the preceding two steps.
  4. Return the count for step n.
class Solution:
    def climbStairs(self, n: int) -> int:
        # Ways to reach steps 0 and 1.
        two_back = 1
        one_back = 1

        # Build the count using the two preceding results.
        for _ in range(2, n + 1):
            current = two_back + one_back
            two_back = one_back
            one_back = current

        return one_back

Complexity:

  • Time: O(n), since each step is processed once.
  • Space: O(1), since only two prior counts are retained.

Common follow-ups

  • What if each move can advance 1, 2, or 3 steps? Sum the counts for the previous three steps.
  • What if the result must be returned modulo a number? Apply the modulus after each addition.
  • What if some steps are forbidden? Set their ways count to zero and use dynamic programming for the allowed steps.
CodingMediumAccoliteSoftware Engineer

4. Minimum Jumps to Reach Home (LeetCode)

Model answer

The task

Find the fewest jumps needed to reach position x from 0, using fixed forward and backward jump lengths. Some positions are forbidden, and you cannot make backward jumps consecutively.

Key idea

Use BFS over states (position, last_jump_was_backward). The same position can have different future options depending on the previous jump, so both parts belong in the visited state.

Approach

  1. Put the forbidden positions in a set.
  2. Start BFS from position 0, with no previous backward jump.
  3. For each state, try a forward jump if it stays within the search bound and avoids forbidden positions.
  4. Try a backward jump only if the last jump was not backward and the new position is nonnegative and allowed.
  5. Return the jump count when a state reaches x; if BFS ends first, return -1.
from collections import deque
from typing import List

class Solution:
    def minimumJumps(
        self, forbidden: List[int], a: int, b: int, x: int
    ) -> int:
        blocked = set(forbidden)

        if x == 0:
            return 0

        # The problem's bounds allow a safe fixed cap of 6000.
        limit = 6000

        # Each state records whether the previous jump was backward.
        queue = deque([(0, False, 0)])
        visited = {(0, False)}

        while queue:
            position, last_was_backward, jumps = queue.popleft()

            forward = position + a
            forward_state = (forward, False)
            if (
                forward <= limit
                and forward not in blocked
                and forward_state not in visited
            ):
                if forward == x:
                    return jumps + 1
                visited.add(forward_state)
                queue.append((forward, False, jumps + 1))

            backward = position - b
            backward_state = (backward, True)
            if (
                not last_was_backward
                and backward >= 0
                and backward not in blocked
                and backward_state not in visited
            ):
                if backward == x:
                    return jumps + 1
                visited.add(backward_state)
                queue.append((backward, True, jumps + 1))

        return -1

Complexity:

  • Time: O(L), where L is the position limit; each state is processed at most once.
  • Space: O(L) for the queue and visited states.

Common follow-ups

  • Why track the previous jump direction? Reaching the same position with different previous moves allows different legal next moves.
  • Why use BFS? Every jump costs one move, so BFS visits states in order of minimum jump count.
  • Can the search bound be changed? Yes; derive a safe bound from the problem’s input limits, ensuring paths that overshoot the target remain reachable.
CodingMediumAccoliteSoftware Engineer

5. Asteroid Collision (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

        for asteroid in asteroids:
            alive = True

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

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

            if alive:
                survivors.append(asteroid)

        return survivors

Complexity:

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

Common follow-ups

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

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

7. Merge Operations to Turn Array Into a Palindrome (LeetCode)

Model answer

The task

Find the fewest adjacent-merge operations needed to make the array a palindrome. Each operation replaces two neighboring values with their sum.

Key idea

Compare the sums at the two ends of the unprocessed portion. If they match, both ends are settled. Otherwise, merge on the side with the smaller sum: it must grow to have a chance of matching the other side.

Approach

  1. Set pointers at the first and last elements and initialize the operation count to zero.
  2. If the pointed-to values match, move both pointers inward.
  3. If the left value is smaller, merge it into its right neighbor, then advance the left pointer.
  4. Otherwise, merge the right value into its left neighbor, then retreat the right pointer.
  5. Continue until the pointers meet; return the number of merges.
from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        operations = 0

        while left < right:
            if nums[left] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] < nums[right]:
                # Grow the left-side sum toward the larger right-side sum.
                nums[left + 1] += nums[left]
                left += 1
                operations += 1
            else:
                # Grow the right-side sum toward the larger left-side sum.
                nums[right - 1] += nums[right]
                right -= 1
                operations += 1

        return operations

Complexity:

  • Time: O(n), since each pointer moves inward at most n times.
  • Space: O(1) extra space; the input array is modified in place.

Common follow-ups

  • Can the original array be preserved? Yes. Copy it first, using O(n) additional space.
  • Can the merged palindrome also be returned? Yes. Track the resulting groups or merge ranges alongside the count.
  • What if values can be negative? This greedy rule relies on positive values; with negatives, merging may not grow a side’s sum predictably.
CodingMediumAccoliteSoftware Engineer

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

9. Gas Station (LeetCode)

Model answer

The task

Given circular arrays of fuel available and fuel required for each leg, find a starting station from which a vehicle can complete the full loop, or return -1 if no such start exists.

Key idea

If the total fuel is less than the total cost, no start can work. Otherwise, when the running fuel balance becomes negative, none of the stations in the current candidate segment can be a valid start, so begin a new candidate at the next station.

Approach

  1. Track the total fuel surplus across all stations.
  2. Track the surplus from the current candidate start.
  3. At each station, add its fuel minus its travel cost to both totals.
  4. If the candidate’s running surplus drops below zero, discard that segment and set the next station as the candidate.
  5. Return the candidate if the total surplus is nonnegative; otherwise, return -1.
class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total_surplus = 0
        current_surplus = 0
        start = 0

        for i in range(len(gas)):
            surplus = gas[i] - cost[i]
            total_surplus += surplus
            current_surplus += surplus

            # No station in the current segment can be a valid start.
            if current_surplus < 0:
                start = i + 1
                current_surplus = 0

        return start if total_surplus >= 0 else -1

Complexity:

  • Time: O(n), where n is the number of stations; each station is processed once.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • Why can the candidate segment be discarded after the balance goes negative? Starting at any station within that segment leaves less fuel by the time it reaches the failure point, so it cannot succeed.
  • What if multiple valid starts exist? The algorithm returns one valid start; uniqueness is not guaranteed.
  • Can this be solved without storing prefix sums? Yes. The running surplus and total surplus are sufficient, as shown above.
CodingMediumAccoliteSoftware Engineer

10. 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.
CodingMediumAccoliteSoftware Engineer

11. Replace the Substring for Balanced String (LeetCode)

Model answer

The task

Given a string made of Q, W, E, and R, find the shortest substring that can be replaced so each character occurs equally often in the resulting string.

Key idea

A substring is sufficient when every character left outside it appears no more than n / 4 times. A sliding window can find the shortest substring with that property.

Approach

  1. Count each character in the full string.
  2. Expand a window from left to right, decrementing counts to represent characters now inside it.
  3. Whenever all outside counts are at most n / 4, record the window length.
  4. Shrink the window from the left while the condition remains true.
class Solution:
    def balancedString(self, s: str) -> int:
        target = len(s) // 4
        outside = {ch: 0 for ch in "QWER"}

        for ch in s:
            outside[ch] += 1

        left = 0
        shortest = len(s)

        for right, ch in enumerate(s):
            # This character is now part of the replaceable window.
            outside[ch] -= 1

            while all(count <= target for count in outside.values()):
                shortest = min(shortest, right - left + 1)

                # Try a smaller window by moving its left edge.
                outside[s[left]] += 1
                left += 1

        return shortest

Complexity:

  • Time: O(n), since each pointer moves across the string at most once; checking four counts is constant time.
  • Space: O(1), since the count map contains only four characters.

Common follow-ups

  • What if the alphabet has k characters? Use a target of n / k and track counts for all k characters.
  • What if the string is already balanced? The algorithm returns 0, since the empty window satisfies the condition.
  • Can the replacement characters always be chosen to balance the string? Yes: the window has exactly enough positions to supply the deficits of the outside counts.
CodingMediumAccoliteSoftware Engineer

12. 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.
CodingMediumAccoliteSoftware Engineer

13. Rotate Non Negative Elements (LeetCode)

Model answer

The task

The title suggests rotating the non-negative values in an array while leaving negative values in their original positions. It does not specify the rotation direction or amount, so the solution below uses a signed shift: positive shifts rotate right, negative shifts rotate left.

Key idea

Record the positions and values of the non-negative elements. Rotate just those values, then write them back to the recorded positions.

Approach

  1. Find the indices containing non-negative values.
  2. Collect the values at those indices.
  3. Normalize the shift modulo the number of collected values.
  4. Rotate the collected values right by that amount.
  5. Write the rotated values back into their original eligible positions.
def rotate_non_negative(nums: list[int], shift: int) -> list[int]:
    """Rotate non-negative values; positive shift means rotate right."""
    indices = [i for i, value in enumerate(nums) if value >= 0]
    values = [nums[i] for i in indices]

    if not values:
        return nums

    amount = shift % len(values)
    if amount:
        values = values[-amount:] + values[:-amount]

    for index, value in zip(indices, values):
        nums[index] = value

    return nums

Complexity:

  • Time: O(n), to find and collect eligible values.
  • Space: O(m), where m is the number of non-negative values.

Common follow-ups

  • How would you rotate left instead? Use a negative shift, or convert a left shift to an equivalent right shift.
  • What if the array contains no non-negative values? Return it unchanged.
  • Can the extra space be reduced? Yes; use in-place permutation cycles, though the implementation is more involved.
  • What if zeros should not be rotated? Change the eligibility test from value >= 0 to value > 0.
CodingMediumAccoliteSoftware Engineer

14. Remove Duplicates from Sorted Array II (LeetCode)

Model answer

The task

Given a sorted array, modify it in place so each value appears at most twice. Return the length of the retained prefix; values beyond that prefix do not matter.

Key idea

Because the array is sorted, duplicates are adjacent. Keep a value only if fewer than two values have already been written, or if it differs from the value two positions behind the write pointer.

Approach

  1. Use write to track the next position in the retained prefix.
  2. Scan each value from left to right.
  3. Accept it when write < 2 or it differs from nums[write - 2].
  4. Write accepted values at nums[write] and advance write.
  5. Return write.
from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # The first two values can always be kept.
        write = 0

        for value in nums:
            # Keep the value only if it would not make three equal
            # values consecutive in the retained, sorted prefix.
            if write < 2 or value != nums[write - 2]:
                nums[write] = value
                write += 1

        return write

Complexity:

  • Time: O(n), where n is the array length; each value is examined once.
  • Space: O(1), since the array is updated in place.

Common follow-ups

  • Allow each value at most m times: Compare with nums[write - m], accepting unconditionally while write < m.
  • What if the input is not sorted? This adjacent-value check no longer works; use a frequency map if extra space is allowed.
  • Can the same approach remove all duplicates? Yes. Keep a value only when it differs from the last retained value.
CodingMediumAccoliteSoftware Engineer

15. 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.
CodingMediumAccoliteSoftware Engineer

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

17. Create Maximum Number (LeetCode)

Model answer

The task

Choose k digits from two arrays, preserving the order within each array, and interleave them to form the largest possible sequence.

Key idea

Try every valid split of the k chosen digits between the arrays. For each split, greedily take the largest subsequence from each array, then merge them by repeatedly choosing from the lexicographically greater remaining suffix.

Approach

  1. Enumerate how many digits to take from the first array, within the limits imposed by both array lengths.
  2. Build the maximum subsequence of each required length using a monotonic stack.
  3. Merge the two subsequences, comparing their remaining suffixes lexicographically.
  4. Keep the largest merged sequence across all splits.
from typing import List

class Solution:
    def maxNumber(
        self, nums1: List[int], nums2: List[int], k: int
    ) -> List[int]:
        def max_subsequence(nums: List[int], length: int) -> List[int]:
            # Remove smaller earlier digits whenever a larger digit can replace them.
            drop = len(nums) - length
            stack = []

            for digit in nums:
                while drop and stack and stack[-1] < digit:
                    stack.pop()
                    drop -= 1
                stack.append(digit)

            return stack[:length]

        def suffix_is_greater(
            first: List[int], i: int, second: List[int], j: int
        ) -> bool:
            # Compare the unconsumed suffixes lexicographically.
            while i < len(first) and j < len(second):
                if first[i] != second[j]:
                    return first[i] > second[j]
                i += 1
                j += 1

            # If one suffix is a prefix of the other, the longer one is greater.
            return i < len(first)

        def merge(first: List[int], second: List[int]) -> List[int]:
            result = []
            i = j = 0

            while i < len(first) or j < len(second):
                if j == len(second) or (
                    i < len(first)
                    and suffix_is_greater(first, i, second, j)
                ):
                    result.append(first[i])
                    i += 1
                else:
                    result.append(second[j])
                    j += 1

            return result

        best = []
        min_from_first = max(0, k - len(nums2))
        max_from_first = min(k, len(nums1))

        for take_first in range(min_from_first, max_from_first + 1):
            first = max_subsequence(nums1, take_first)
            second = max_subsequence(nums2, k - take_first)
            candidate = merge(first, second)

            if candidate > best:
                best = candidate

        return best

Complexity:

  • Time: O(s * (m + n + k²)), where s is the number of valid splits; suffix comparisons can take O(k) for each of up to k merge steps.
  • Space: O(k) for the subsequences, merged candidate, and result.

Common follow-ups

  • How can suffix comparisons be made faster? Precompute suffix ranks or longest-common-prefix information for each split.
  • What if digits can repeat? The suffix comparison handles ties by looking beyond equal leading digits.
  • How can the subsequence step be justified? A larger later digit should replace a smaller earlier one whenever enough digits remain to reach the requested length.

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