Tekion interview questions & answers

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

CodingEasyTekionSoftware 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.
CodingMediumTekionSoftware Engineer

2. Longest Balanced Substring After One Swap (LeetCode)

Model answer

The task

The title does not specify what makes a substring “balanced.” The solution below assumes the common binary-string definition: a substring is balanced when it contains equal numbers of 0 and 1.

Key idea

A single swap can change a substring’s zero/one difference by at most one, and only if the swap crosses the substring’s boundary. So a substring can be made balanced if its counts are already equal, or differ by one and the outside contains a character that can be swapped in.

Approach

  1. Build prefix counts of 1s so each substring’s counts can be computed in constant time.
  2. Enumerate every substring and find its counts of 0s and 1s.
  3. Accept it if the counts are equal.
  4. If they differ by one, accept it only if the complementary character exists outside the substring.
  5. Track the longest accepted substring.
def longest_balanced_after_swap(s: str) -> int:
    """Assumes s is binary and balanced means equal counts of '0' and '1'."""
    n = len(s)

    # Prefix counts let us count ones in any interval in O(1).
    ones_prefix = [0] * (n + 1)
    for i, char in enumerate(s):
        ones_prefix[i + 1] = ones_prefix[i] + (char == "1")

    total_ones = ones_prefix[n]
    total_zeros = n - total_ones
    best = 0

    for left in range(n):
        for right in range(left + 1, n + 1):
            ones = ones_prefix[right] - ones_prefix[left]
            length = right - left
            zeros = length - ones

            if ones == zeros:
                best = max(best, length)
            elif ones == zeros + 1:
                # Swap an inside '1' with an outside '0'.
                outside_zeros = total_zeros - zeros
                if outside_zeros > 0:
                    best = max(best, length)
            elif zeros == ones + 1:
                # Swap an inside '0' with an outside '1'.
                outside_ones = total_ones - ones
                if outside_ones > 0:
                    best = max(best, length)

    return best

Complexity:

  • Time: O(n²), checking all substrings with O(1) count queries.
  • Space: O(n), for the prefix-count array.

Common follow-ups

  • What if “balanced” has a different definition? First define its balance condition; the counting test may change.
  • Can this be faster? The quadratic enumeration may be improved by grouping prefix counts and tracking eligible outside characters.
  • What if multiple swaps are allowed? The required count difference and availability conditions depend on the swap limit.
CodingMediumTekionSoftware Engineer

3. Rotting Oranges (LeetCode)

Model answer

The task

Given a grid of empty cells, fresh oranges, and rotten oranges, find the minimum number of minutes until no fresh oranges remain. Each minute, a rotten orange makes any fresh orange directly above, below, left, or right of it rotten; return -1 if some fresh oranges can never be reached.

Key idea

Use multi-source breadth-first search: all initially rotten oranges spread at the same time, so put them all in the queue at the start. Process the queue one minute at a time, counting newly rotten oranges to detect whether any fresh ones remain unreachable.

Approach

  1. Count the fresh oranges and enqueue every initially rotten orange.
  2. If there are no fresh oranges, return 0.
  3. For each BFS layer, rot adjacent fresh oranges, decrement the fresh count, and enqueue them.
  4. Count each processed layer as one minute.
  5. Return the minutes if all fresh oranges rotted; otherwise return -1.
from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh = 0

        # Gather all initial sources and count oranges that still need to rot.
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        while queue and fresh > 0:
            # Process exactly the oranges rotten before this minute began.
            for _ in range(len(queue)):
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and grid[nr][nc] == 1
                    ):
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

            minutes += 1

        return minutes if fresh == 0 else -1

Complexity:

  • Time: O(rows × cols), since each cell is visited at most once.
  • Space: O(rows × cols) for the BFS queue in the worst case.

Common follow-ups

  • What if diagonal neighbors also spread rot? Add the four diagonal directions to the neighbor list.
  • Can the original grid be preserved? Copy it first, or track visited cells separately.
  • How would you return which oranges rot each minute? Store each BFS layer’s cells or record a rot-time value per cell.
CodingMediumTekionSoftware Engineer

4. Ways to Split Array Into Three Subarrays (LeetCode)

Model answer

The task

Count the ways to divide the array into three nonempty contiguous parts such that the left part’s sum is no greater than the middle part’s, and the middle part’s sum is no greater than the right part’s. Return the count modulo \(10^9+7\).

Key idea

Use prefix sums to express both conditions as bounds on the prefix sum at the end of the middle part. As the left boundary moves right, both bounds move monotonically, so two pointers can track the valid range in linear time.

Approach

  1. Build prefix sums, where prefix[k] is the sum of the first k elements.
  2. For each possible end of the left part, let its sum be left.
  3. Advance the lower pointer until the middle sum is at least left.
  4. Advance the upper pointer until the right sum is at least the middle sum.
  5. The distance between the pointers gives the number of valid middle-part ends; add it modulo \(10^9+7\).
class Solution:
    def waysToSplit(self, nums: list[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)

        prefix = [0] * (n + 1)
        for i, value in enumerate(nums):
            prefix[i + 1] = prefix[i] + value

        total = prefix[n]
        lower = upper = 2
        answer = 0

        # The left part ends at index i; prefix endpoint i + 1.
        for i in range(n - 2):
            left = prefix[i + 1]

            # The middle part must contain at least one element.
            lower = max(lower, i + 2)
            upper = max(upper, lower)

            # middle >= left
            while lower < n and prefix[lower] < 2 * left:
                lower += 1

            # right >= middle, equivalently:
            # prefix[upper] <= (total + left) // 2
            limit = (total + left) // 2
            while upper < n and prefix[upper] <= limit:
                upper += 1

            answer = (answer + upper - lower) % mod

        return answer

Complexity:

  • Time: O(n), because each pointer moves forward at most n times.
  • Space: O(n), for the prefix-sum array.

Common follow-ups

  • What if values can be negative? Prefix sums are no longer monotonic, so this two-pointer approach does not apply directly.
  • Can the prefix-sum storage be reduced? Yes; the total and running prefix can be maintained, though the pointer comparisons need access to prefix values.
  • How would you verify the boundaries? Check that the middle part is nonempty and the right part remains nonempty; the loop and pointer limit enforce both.
CodingMediumTekionSoftware Engineer

5. Shortest Subarray to be Removed to Make Array Sorted (LeetCode)

Model answer

The task

Find the shortest contiguous segment to delete so the remaining elements are in non-decreasing order. The remaining elements on either side of the deleted segment stay in their original order.

Key idea

A valid result can keep a sorted prefix and a sorted suffix, deleting everything between them. Scan the boundary between those parts, matching prefix values to suffix values while preserving sorted order.

Approach

  1. Find the end of the longest non-decreasing prefix.
  2. If it reaches the array’s end, no deletion is needed.
  3. Find the start of the longest non-decreasing suffix.
  4. Consider deleting only the prefix or only the suffix as initial candidates.
  5. For each prefix endpoint, advance through the suffix until its value can follow the prefix value; update the minimum deletion length.
class Solution:
    def findLengthOfShortestSubarray(self, arr: list[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        # Locate the longest non-decreasing prefix.
        left = 0
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1

        if left == n - 1:
            return 0

        # Locate the longest non-decreasing suffix.
        right = n - 1
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1

        # Delete everything before the suffix or after the prefix.
        shortest = min(right, n - left - 1)

        # Try joining each prefix endpoint to a compatible suffix value.
        suffix = right
        for prefix in range(left + 1):
            while suffix < n and arr[suffix] < arr[prefix]:
                suffix += 1

            # Remove the elements strictly between these two kept values.
            shortest = min(shortest, suffix - prefix - 1)

        return shortest

Complexity:

  • Time: O(n), since each pointer moves only forward.
  • Space: O(1), using a fixed number of indices.

Common follow-ups

  • What if the remaining array must be strictly increasing? Use strict comparisons when identifying sorted runs and when matching the two parts.
  • Can this be done with binary search? Yes; for each prefix endpoint, binary-search the suffix for the first compatible value, giving O(n log n) time.
  • What if the array is already sorted? The prefix scan reaches the end, so the answer is zero.
CodingMediumTekionSoftware Engineer

6. Letter Combinations of a Phone Number (LeetCode)

Model answer

The task

Given a string of digits from 2 through 9, return every string formed by choosing the corresponding phone-keypad letter for each digit. If the input is empty, return an empty list.

Key idea

Build each string one character at a time using backtracking. For each digit, try every letter mapped to it, then undo that choice before trying the next one.

Approach

  1. Define the digit-to-letters mapping.
  2. Return an empty list if there are no digits.
  3. Use a recursive helper to track the current digit position and partial string.
  4. When the partial string has one letter per digit, add it to the results.
  5. Otherwise, recurse once for each letter mapped to the current digit.
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        letters = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []
        current = []

        def backtrack(index: int) -> None:
            # A complete choice has one letter for every digit.
            if index == len(digits):
                result.append("".join(current))
                return

            # Try each possible letter for this digit.
            for letter in letters[digits[index]]:
                current.append(letter)
                backtrack(index + 1)
                current.pop()  # Undo the choice before trying another.

        backtrack(0)
        return result

Complexity:

  • Time: O(n · 4ⁿ), since there can be up to 4ⁿ combinations and building each takes O(n).
  • Space: O(n) auxiliary space for the recursion and current combination, excluding the output.

Common follow-ups

  • What if the input contains 0 or 1? Define their behavior explicitly, since they do not map to letters in the standard keypad mapping.
  • How would you avoid recursion? Build combinations iteratively, adding each digit’s letters to the partial results.
  • Can the results be generated lazily? Yield each completed combination from the recursive search instead of storing them all.
CodingMediumTekionSoftware Engineer

7. Largest Divisible Subset (LeetCode)

Model answer

The task

Given a list of distinct positive integers, return a largest subset in which every pair is divisible in one direction: one number divides the other.

Key idea

Sort the numbers. In sorted order, a valid subset forms a divisibility chain, so dynamic programming can track the longest chain ending at each number. Store predecessors to reconstruct one such chain.

Approach

  1. Sort the numbers in ascending order.
  2. For each number, initialize its chain length to 1 and its predecessor to none.
  3. Check each earlier number; if it divides the current number, use its chain when it produces a longer one.
  4. Track the endpoint of the longest chain.
  5. Follow predecessor links from that endpoint and reverse the collected values.
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        if not nums:
            return []

        nums.sort()
        n = len(nums)

        # Length of the longest divisible chain ending at each index.
        dp = [1] * n
        parent = [-1] * n

        best_end = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j

            if dp[i] > dp[best_end]:
                best_end = i

        # Reconstruct the chain by walking backward through its predecessors.
        result = []
        index = best_end
        while index != -1:
            result.append(nums[index])
            index = parent[index]

        return result[::-1]

Complexity:

  • Time: O(n²), from checking pairs after sorting.
  • Space: O(n), for chain lengths, predecessors, and the returned subset.

Common follow-ups

  • How would you return every maximum subset? Track all predecessors that tie for the best length, then enumerate the resulting chains.
  • What if the input contains duplicates? Decide whether duplicates are allowed in a subset; if so, the divisibility check naturally permits repeated equal values.
  • Can the quadratic approach be improved? The pairwise checks are generally the simple choice; alternatives depend on bounds and the structure of the input values.
CodingMediumTekionSoftware Engineer

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

9. Daily Temperatures (LeetCode)

Model answer

The task

For each day in a temperature list, find how many days later a warmer temperature first occurs. If no warmer day follows, its answer is zero.

Key idea

Keep a stack of indices whose temperatures are still waiting for a warmer day. Their temperatures are in non-increasing order; when a warmer day arrives, it resolves the waiting indices at the top.

Approach

  1. Create an answer array filled with zeros and an empty stack of indices.
  2. Scan the temperatures from left to right.
  3. While the current temperature is warmer than the temperature at the stack’s top index, pop that index.
  4. Set its answer to the difference between the current index and the popped index.
  5. Push the current index; unresolved indices remain zero.
from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        waiting: List[int] = []

        for day, temperature in enumerate(temperatures):
            # Resolve every earlier day for which today is the first
            # warmer day encountered.
            while waiting and temperatures[waiting[-1]] < temperature:
                earlier_day = waiting.pop()
                answer[earlier_day] = day - earlier_day

            # This day is now waiting for a warmer temperature.
            waiting.append(day)

        return answer

Complexity:

  • Time: O(n), since each index is pushed and popped at most once.
  • Space: O(n), for the answer array and the stack.

Common follow-ups

  • How would you handle temperatures arriving as a stream? Keep the unresolved indices and their temperatures in a stack, and emit answers when warmer values arrive; some earlier outputs may remain pending.
  • What changes if the question asks for the next colder day? Reverse the comparison so an index is resolved by a lower temperature.
  • Can the stack store temperatures instead of indices? Not for this output, because the index difference is needed to calculate the number of days.
  • What happens when temperatures are equal? Equal values do not resolve each other; only a strictly warmer temperature does.
CodingMediumTekionSoftware Engineer

10. Product of the Last K Numbers (LeetCode)

Model answer

The task

Design a data structure that accepts numbers from a stream and can return the product of its most recently added k numbers.

Key idea

Store cumulative products since the most recent zero. A zero resets the cumulative products, because any queried range that includes it has product zero. Otherwise, divide the latest cumulative product by the one just before the queried range.

Approach

  1. Initialize a list with 1, representing the product of an empty range.
  2. When adding a nonzero number, append its product with the latest cumulative product.
  3. When adding zero, reset the list to [1].
  4. To query, return zero if k exceeds the number of values since the last zero.
  5. Otherwise, divide the latest cumulative product by the cumulative product preceding the last k values.
class ProductOfNumbers:
    def __init__(self):
        # Cumulative products since the most recent zero.
        self.prefix_products = [1]

    def add(self, num: int) -> None:
        if num == 0:
            # Any product reaching across this zero is zero.
            self.prefix_products = [1]
        else:
            self.prefix_products.append(self.prefix_products[-1] * num)

    def getProduct(self, k: int) -> int:
        # A query containing a zero has product zero.
        if k >= len(self.prefix_products):
            return 0

        latest = self.prefix_products[-1]
        before_range = self.prefix_products[-k - 1]
        return latest // before_range

Complexity:

  • Time: O(1) per operation, using arithmetic operations on the stored products.
  • Space: O(n) for the numbers added since the most recent zero.

Common follow-ups

  • What if products can be negative? The prefix-division method still works, provided division is exact.
  • Can memory be bounded? If queries have a known maximum k, retain only enough recent prefix products to answer them.
  • What if division is unavailable? Store recent values and multiply the last k values per query, taking O(k) time.
  • How should very large products be handled? Use arbitrary-precision integers, or choose a suitable numeric representation if the requirements permit.
CodingMediumTekionSoftware Engineer

11. Numbers With Same Consecutive Differences (LeetCode)

Model answer

The task

Return all positive n-digit numbers whose neighboring digits differ by exactly k. A number cannot start with zero, except that the one-digit number 0 is valid when n == 1.

Key idea

Build numbers one digit at a time. From a number ending in digit d, the next digit can only be d + k or d - k, if that digit is between 0 and 9. Keep zero out of the starting digits so every longer number has the required length.

Approach

  1. If n == 1, return all digits from 0 through 9.
  2. Initialize the current layer with the one-digit numbers 1 through 9.
  3. For each remaining position, extend each number with each valid next digit.
  4. When k == 0, add the matching digit only once.
  5. Return the numbers from the final layer.
class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> list[int]:
        # Zero is valid only as a one-digit number.
        if n == 1:
            return list(range(10))

        numbers = list(range(1, 10))

        # Each iteration adds one digit to every current number.
        for _ in range(n - 1):
            extended = []

            for number in numbers:
                last_digit = number % 10

                higher = last_digit + k
                lower = last_digit - k

                if higher <= 9:
                    extended.append(number * 10 + higher)

                # Avoid adding the same extension twice when k is zero.
                if k != 0 and lower >= 0:
                    extended.append(number * 10 + lower)

            numbers = extended

        return numbers

Complexity:

  • Time: O(n · 2ⁿ), since each number can produce at most two extensions over n - 1 positions.
  • Space: O(2ⁿ) for the current and next layers of generated numbers.

Common follow-ups

  • How would you avoid storing every number? Generate and emit completed numbers with DFS instead.
  • What changes if leading zeros are allowed? Start from zero as well as digits 1 through 9.
  • What if the difference is a range of values? Try every allowed next digit and keep those satisfying the range condition.
CodingMediumTekionSoftware Engineer

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

13. Longest String Chain (LeetCode)

Model answer

The task

Given a list of distinct words, find the length of the longest sequence where each word is formed by inserting one letter anywhere into the previous word.

Key idea

For each word, try removing each character in turn. Any resulting word in the list can precede it in a chain. Dynamic programming stores the longest chain ending at each word.

Approach

  1. Sort the words by increasing length so shorter possible predecessors are processed first.
  2. For each word, initialize its best chain length to 1.
  3. Remove each character to generate possible predecessors.
  4. If a predecessor has already been processed, extend its chain by one.
  5. Track and return the maximum chain length.
from typing import List

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        # Process possible predecessors before their longer successors.
        words.sort(key=len)

        # dp[word] is the longest chain ending at word.
        dp = {}
        longest = 0

        for word in words:
            best = 1

            # Try removing each character to find a predecessor.
            for i in range(len(word)):
                predecessor = word[:i] + word[i + 1:]
                if predecessor in dp:
                    best = max(best, dp[predecessor] + 1)

            dp[word] = best
            longest = max(longest, best)

        return longest

Complexity:

  • Time: O(n log n + nL²), where sorting costs O(n log n) and generating and hashing each deletion costs O(L²) per word in the worst case.
  • Space: O(nL), for storing the words as keys in the dynamic-programming map.

Common follow-ups

  • What if words can repeat? Deduplicate them first; duplicates do not create a valid extra link.
  • How would you return an actual longest chain? Store the best predecessor alongside each word, then backtrack from the word with the largest DP value.
  • Can the approach handle an empty list? Yes; initialize the answer to zero and return it when no words are processed.
CodingMediumTekionSoftware Engineer

14. Rank Teams by Votes (LeetCode)

Model answer

The task

Given ballots that list the same teams in preference order, rank teams by how often they appear in each position. Break any remaining tie alphabetically.

Key idea

For each team, count its votes at every position. Compare teams by their count vectors from first position to last, in descending order, using alphabetical order as the final tie-breaker.

Approach

  1. Get the teams and number of positions from the first ballot.
  2. Create a count vector for each team.
  3. For every ballot, increment the count for each team at its position.
  4. Sort teams by their count vectors, highest counts first, then alphabetically.
  5. Return the sorted team names as a string.
class Solution:
    def rankTeams(self, votes: list[str]) -> str:
        teams = votes[0]
        positions = len(teams)

        # counts[team][position] stores votes for that team at that rank.
        counts = {team: [0] * positions for team in teams}

        for ballot in votes:
            for position, team in enumerate(ballot):
                counts[team][position] += 1

        # Negate counts so Python's ascending sort puts larger counts first.
        ranked = sorted(
            teams,
            key=lambda team: tuple(-count for count in counts[team]) + (team,),
        )

        return "".join(ranked)

Complexity:

  • Time: O(V · T + T² log T), where V is the number of ballots and T is the number of teams.
  • Space: O(T²) for the per-team position counts.

Common follow-ups

  • What if teams can have different numbers of positions? Define how missing positions should be counted, then normalize ballots before tallying.
  • How would you rank a very large number of ballots? Tally counts incrementally as ballots arrive; the final sort is still needed for the ranking.
  • What if alphabetical order is replaced by a custom priority? Use that priority as the final sort tie-breaker.
CodingMediumTekionSoftware Engineer

15. Subarray Product Less Than K (LeetCode)

Model answer

The task

Count the contiguous subarrays whose product is strictly less than k.

Key idea

With positive numbers, extending a window never decreases its product. Maintain the longest window whose product is below k; every suffix of that window ending at the current position also qualifies.

Approach

  1. If k <= 1, return 0, since positive-number products are at least 1.
  2. Expand the right edge, multiplying its value into the window product.
  3. While the product is at least k, move the left edge forward and divide out the values it passes.
  4. Add the window length to the count: each possible starting point in the current window gives one qualifying subarray ending at the right edge.
from typing import List

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

        left = 0
        product = 1
        count = 0

        for right, value in enumerate(nums):
            product *= value

            # Restore the condition that the window product is less than k.
            while product >= k:
                product //= nums[left]
                left += 1

            # Every nonempty suffix of this window is valid.
            count += right - left + 1

        return count

Complexity:

  • Time: O(n), since each element enters and leaves the window at most once.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if the array can contain zeros? Split at zeros, count positive-only ranges, and account for subarrays containing zero separately.
  • What if values can be negative? This sliding-window method no longer applies; products are not monotonic as the window grows.
  • Can the answer exceed a 32-bit integer? Yes; use an integer type large enough for the maximum subarray count.
CodingMediumTekionSoftware Engineer

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

17. Max Consecutive Ones III (LeetCode)

Model answer

The task

Given a binary array and a budget k, find the longest contiguous segment that can be made entirely ones by changing at most k zeros.

Key idea

Use a sliding window and track how many zeros it contains. Expand the right edge; whenever the window exceeds the budget, move the left edge until it is valid again.

Approach

  1. Initialize both window boundaries and a zero counter.
  2. Extend the window one element at a time from the right.
  3. Add to the counter when the new element is zero.
  4. If the counter exceeds k, advance the left edge, subtracting any zero it passes.
  5. Record the largest valid window length.
class Solution:
    def longestOnes(self, nums: list[int], k: int) -> int:
        left = 0
        zero_count = 0
        longest = 0

        for right, value in enumerate(nums):
            if value == 0:
                zero_count += 1

            # Restore the budget by shrinking from the left.
            while zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1

            longest = max(longest, right - left + 1)

        return longest

Complexity:

  • Time: O(n), since each index enters and leaves the window at most once.
  • Space: O(1), using only a few counters and indices.

Common follow-ups

  • Can this be solved with binary search? Yes: binary-search the window length and check whether any window of that size contains at most k zeros.
  • What if the array contains values other than zero and one? Define which values may be changed, then count those values in the window.
  • How would you return the segment’s boundaries too? Store the left and right indices whenever a new maximum length is found.
CodingMediumTekionSoftware Engineer

18. Meeting Rooms II (LeetCode)

Model answer

The task

Given meeting time intervals, find the minimum number of rooms needed so that no overlapping meetings share a room.

Key idea

Process meetings in start-time order. Track each occupied room by the time its meeting ends; a room is available when its meeting ends no later than the next meeting starts.

Approach

  1. Sort intervals by start time.
  2. Keep a min-heap of end times for meetings using rooms.
  3. For each meeting, remove the earliest end time if that room is available.
  4. Add the current meeting’s end time to the heap.
  5. The largest heap size reached is the minimum room count.
import heapq
from typing import List

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

        intervals.sort(key=lambda meeting: meeting[0])
        room_end_times = []

        for start, end in intervals:
            # Reuse the room whose meeting finishes first, if available.
            if room_end_times and room_end_times[0] <= start:
                heapq.heappop(room_end_times)

            heapq.heappush(room_end_times, end)

        return len(room_end_times)

Complexity:

  • Time: O(n log n), for sorting and heap operations across n meetings.
  • Space: O(n), for the heap in the worst case.

Common follow-ups

  • What if a meeting ending at time t overlaps one starting at t? Change the availability check from <= to <.
  • How can you return a room assignment for every meeting? Store (end_time, room_id) in the heap and reuse the freed room ID.
  • How would you handle meetings arriving online? Maintain the end-time heap as meetings arrive; each new meeting can reuse a room or add one.
CodingMediumTekionSoftware Engineer

19. Longest Substring Without Repeating Characters (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

        return best

Complexity:

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

Common follow-ups

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

20. Count the Number of Infection Sequences (LeetCode)

Model answer

The task

Count the possible orders in which all initially healthy positions become infected, given the positions that are infected at the start. A position can become infected only when it is next to an already infected position.

Key idea

Divide the healthy positions into gaps between initially infected positions and at the two ends. The gaps can be interleaved in any order, while an interior gap of length g has 2^(g-1) possible infection orders because its infection can advance from either end.

Approach

  1. Compute the length of each gap, including the two end gaps.
  2. Let h be the total number of healthy positions. Start with h! to order all infections.
  3. Divide by gap! for each gap to account for interleavings between gaps.
  4. For each interior gap, multiply by 2^(gap-1).
  5. Compute factorial inverses modulo 10^9 + 7 using Fermat’s little theorem.
from typing import List

class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        mod = 10**9 + 7
        healthy = n - len(sick)

        # Factorials and inverse factorials modulo mod.
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % mod

        inv_fact = [1] * (n + 1)
        inv_fact[n] = pow(fact[n], mod - 2, mod)
        for i in range(n, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % mod

        # Gaps before, between, and after the initially infected positions.
        gaps = [sick[0]]
        for i in range(1, len(sick)):
            gaps.append(sick[i] - sick[i - 1] - 1)
        gaps.append(n - 1 - sick[-1])

        answer = fact[healthy]

        # Remove the gap-internal orderings from the overall permutations.
        for gap in gaps:
            answer = answer * inv_fact[gap] % mod

        # Interior gaps can be infected from either end.
        for gap in gaps[1:-1]:
            if gap > 0:
                answer = answer * pow(2, gap - 1, mod) % mod

        return answer

Complexity:

  • Time: O(n), for factorial precomputation.
  • Space: O(n), for the factorial tables.

Common follow-ups

  • Why do end gaps lack the power-of-two factor? Infection can enter each end gap from only one direction.
  • What if the infected positions are unsorted? Sort them first; this adds O(k log k) time for k infected positions.
  • Can factorial tables be reused? Yes. For many queries, precompute factorials and inverse factorials once up to the largest n.

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