Turing interview questions & answers

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

CodingEasyTuringSoftware Engineer

1. Degree of an Array (LeetCode)

Model answer

The task

Given an integer array, find the length of its shortest contiguous subarray whose elements have the same degree as the full array. The degree is the highest frequency of any value in the array.

Key idea

For each value, record its frequency and the indices of its first and last occurrences. A value’s shortest covering subarray spans those two indices; among values with maximum frequency, return the smallest such span.

Approach

  1. Scan the array once, recording each value’s count, first index, and last index.
  2. Track the largest count seen, which is the array’s degree.
  3. For every value with that count, calculate last - first + 1.
  4. Return the minimum calculated length.
from typing import List

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        counts = {}
        first = {}
        last = {}

        for i, value in enumerate(nums):
            if value not in counts:
                counts[value] = 0
                first[value] = i

            counts[value] += 1
            last[value] = i

        degree = max(counts.values())
        shortest = len(nums)

        for value, count in counts.items():
            if count == degree:
                span = last[value] - first[value] + 1
                shortest = min(shortest, span)

        return shortest

Complexity:

  • Time: O(n), for scanning the array and checking the distinct values.
  • Space: O(k), where k is the number of distinct values stored in the dictionaries.

Common follow-ups

  • How would you return the actual subarray as well as its length? Keep the start and end indices of the best span.
  • What if the array is empty? Define the expected behavior, such as returning 0, and handle it before calling max.
  • Can the result be found in one pass? Yes; update each value’s span and count while tracking the best span for the current degree.
CodingEasyTuringSoftware Engineer

2. 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.
CodingEasyTuringSoftware Engineer

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

4. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingEasyTuringSoftware Engineer

5. Count Square Sum Triples (LeetCode)

Model answer

The task

Count the ordered positive-integer triples (a, b, c) with each value at most n that satisfy the Pythagorean equation. Swapping a and b counts as a separate triple.

Key idea

Enumerate the two leg values and test whether their squared sum is a perfect square. Use integer square root so the check avoids floating-point precision issues.

Approach

  1. Iterate over every possible a and b from 1 through n.
  2. Compute s = a² + b².
  3. Find c = isqrt(s).
  4. Count the pair if c is within the allowed range and c² == s.
  5. Return the count.
from math import isqrt

class Solution:
    def countTriples(self, n: int) -> int:
        count = 0

        for a in range(1, n + 1):
            for b in range(1, n + 1):
                squared_sum = a * a + b * b
                c = isqrt(squared_sum)

                if c <= n and c * c == squared_sum:
                    count += 1

        return count

Complexity:

  • Time: O(n²), from checking every ordered pair of legs.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if swapping a and b should count only once? Iterate only over pairs with a <= b.
  • Can the search be reduced? Precompute the squares up to n² and check membership, though the pair enumeration remains O(n²).
  • How do you handle larger bounds safely? Keep integer arithmetic and use isqrt rather than floating-point square roots.
CodingMediumTuringSoftware Engineer

6. Number of Islands (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

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

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

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

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

        return islands

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

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

Common follow-ups

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

7. Validate IP Address (LeetCode)

Model answer

The task

Classify a string as an IPv4 address, an IPv6 address, or neither. Each format has its own rules for the number and shape of its components.

Key idea

Check the two formats independently. Splitting on the appropriate separator makes it straightforward to validate both the component count and each component’s characters and numeric or length limits.

Approach

  1. Split on . and check for four IPv4 components.
  2. Require each component to contain only ASCII digits, have no unnecessary leading zero, and represent a value from 0 to 255.
  3. Otherwise, split on : and check for eight IPv6 components.
  4. Require each IPv6 component to contain one to four ASCII hexadecimal characters.
  5. Return the matching classification, or "Neither" if neither check succeeds.
class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        parts = queryIP.split(".")

        if len(parts) == 4:
            valid_ipv4 = True

            for part in parts:
                # IPv4 components must be nonempty ASCII decimal strings.
                if not part or any(ch not in "0123456789" for ch in part):
                    valid_ipv4 = False
                    break

                # Multi-digit components cannot begin with zero.
                if len(part) > 1 and part[0] == "0":
                    valid_ipv4 = False
                    break

                if int(part) > 255:
                    valid_ipv4 = False
                    break

            if valid_ipv4:
                return "IPv4"

        parts = queryIP.split(":")

        if len(parts) == 8:
            hex_digits = "0123456789abcdefABCDEF"

            for part in parts:
                if not 1 <= len(part) <= 4:
                    break
                if any(ch not in hex_digits for ch in part):
                    break
            else:
                return "IPv6"

        return "Neither"

Complexity:

  • Time: O(n), where n is the string length; each character is checked a constant number of times.
  • Space: O(n) for the component lists created by splitting the string.

Common follow-ups

  • How would you support IPv6 :: compression? Allow one compression marker and verify it replaces at least one omitted group.
  • How would you handle IPv4-embedded IPv6 addresses? Parse the final dotted component as IPv4 and count it as two IPv6 groups.
  • What happens with leading zeros in IPv4 components? Reject them unless the component is exactly "0".
CodingMediumTuringSoftware Engineer

8. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumTuringSoftware Engineer

9. Longest Palindromic Substring (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

        return s[best_start:best_start + best_length]

Complexity:

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

Common follow-ups

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

10. Find First and Last Position of Element in Sorted Array (LeetCode)

Model answer

The task

Given a sorted array and a target value, return the indices of its first and last occurrences. If the target is absent, return [-1, -1].

Key idea

Use binary search twice: once to find the first index whose value is at least the target, and once to find the first index whose value is greater than the target. The second boundary, minus one, is the target’s last index.

Approach

  1. Write a binary search that finds the first index meeting a chosen comparison.
  2. Find the first index with a value at least the target.
  3. If that index is past the array or does not contain the target, return [-1, -1].
  4. Find the first index with a value greater than the target.
  5. Return the first index and the second boundary minus one.
from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def first_index(strictly_greater: bool) -> int:
            """Return the first index with value > target, or >= target."""
            left, right = 0, len(nums)

            while left < right:
                mid = (left + right) // 2
                qualifies = (
                    nums[mid] > target
                    if strictly_greater
                    else nums[mid] >= target
                )

                if qualifies:
                    right = mid
                else:
                    left = mid + 1

            return left

        first = first_index(strictly_greater=False)

        if first == len(nums) or nums[first] != target:
            return [-1, -1]

        after_last = first_index(strictly_greater=True)
        return [first, after_last - 1]

Complexity:

  • Time: O(log n), from two binary searches.
  • Space: O(1), excluding the returned list.

Common follow-ups

  • Can the search be done with one binary search? A single search finds only one occurrence; additional work is needed to locate both boundaries.
  • What if the array is empty? The first boundary is zero, so the method returns [-1, -1].
  • How would you count occurrences instead? Subtract the first index from the first index greater than the target.
CodingMediumTuringSoftware Engineer

11. Minimum Cost For Tickets (LeetCode)

Model answer

The task

Given the days you need to travel and the prices of one-day, seven-day, and thirty-day passes, find the lowest total cost that covers every travel day.

Key idea

Process travel days from earliest to latest. For each day, consider buying each pass and jump to the first travel day it does not cover; dynamic programming records the cheapest cost of reaching each such position.

Approach

  1. Store dp[i] as the minimum cost to cover all travel days before index i.
  2. Initialize dp[0] to zero; all other positions start unreachable.
  3. For each reachable index, try each pass duration and its matching price.
  4. Use binary search to find the first travel day at or after the pass’s expiration.
  5. Update the cost at that position and return the cost for all days.
from bisect import bisect_left
from typing import List

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        durations = (1, 7, 30)

        # dp[i] is the minimum cost to cover days before index i.
        dp = [float("inf")] * (n + 1)
        dp[0] = 0

        for i in range(n):
            if dp[i] == float("inf"):
                continue

            for duration, price in zip(durations, costs):
                # A pass bought on days[i] covers through days[i] + duration - 1.
                next_index = bisect_left(days, days[i] + duration)
                dp[next_index] = min(dp[next_index], dp[i] + price)

        return dp[n]

Complexity:

  • Time: O(n log n), for up to three binary searches per travel day.
  • Space: O(n), for the dynamic programming array.

Common follow-ups

  • Can the time be reduced to O(n)? Yes; maintain a moving pointer for each pass duration as the travel days are processed.
  • What if the pass durations differ? Replace the duration list with the available pass lengths and apply the same transitions.
  • What if travel days are not sorted? Sort them first, removing duplicates if needed.
  • What if the calendar is small and fixed? Use day-by-day dynamic programming, carrying the best cost forward on non-travel days.
CodingMediumTuringSoftware Engineer

12. Minimum Number of Operations to Satisfy Conditions (LeetCode)

Model answer

The task

Change as few grid cells as possible so every column contains one repeated digit, and neighboring columns use different digits.

Key idea

For each column, count how many cells already hold each digit; this gives the cost of choosing any digit for that column. Dynamic programming then finds the least total cost while enforcing that consecutive columns choose different digits.

Approach

  1. Keep dp[d] as the minimum operations for the columns processed so far when the latest column uses digit d.
  2. For each column, count its digits.
  3. The cost of choosing d is the column height minus the count of d.
  4. For each possible d, add that cost to the best previous state whose digit is not d.
  5. Return the minimum final state.
class Solution:
    def minimumOperations(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        # Initially, there are no processed columns.
        dp = [0] * 10

        for col in range(cols):
            counts = [0] * 10
            for row in range(rows):
                counts[grid[row][col]] += 1

            next_dp = [0] * 10
            for digit in range(10):
                change_cost = rows - counts[digit]
                # Adjacent columns must use different digits.
                best_previous = min(
                    dp[other] for other in range(10) if other != digit
                )
                next_dp[digit] = best_previous + change_cost

            dp = next_dp

        return min(dp)

Complexity:

  • Time: O(mn + 100n), where m and n are the grid dimensions.
  • Space: O(10), for the digit counts and DP states.

Common follow-ups

  • What if the allowed values are not digits 0–9? Use the size of the allowed-value set as the DP state count.
  • Can the transition be faster for many allowed values? Track the smallest and second-smallest previous DP values, so each state finds its best different predecessor in O(1).
  • What if columns may also match their neighbors? Remove the different-digit restriction and choose the minimum previous state.
CodingMediumTuringSoftware Engineer

13. K Divisible Elements Subarrays (LeetCode)

Model answer

The task

Count the different contiguous subarrays that contain at most k values divisible by p. Subarrays with identical values count only once.

Key idea

Insert each allowed subarray into a trie, starting from every array index. Each newly created trie node represents a distinct value sequence, so the number of new nodes is the answer.

Approach

  1. Initialize a trie root and a distinct-subarray counter.
  2. For each starting index, walk forward through the array.
  3. Track how many encountered values are divisible by p; stop once the count exceeds k.
  4. At each trie node, create a child for the next value if one does not exist, and increment the counter.
  5. Return the counter.
class Solution:
    def countDistinct(self, nums: list[int], k: int, p: int) -> int:
        root = {}
        distinct = 0

        for start in range(len(nums)):
            node = root
            divisible_count = 0

            for end in range(start, len(nums)):
                value = nums[end]

                if value % p == 0:
                    divisible_count += 1
                    if divisible_count > k:
                        break

                # A new trie edge represents a previously unseen sequence.
                if value not in node:
                    node[value] = {}
                    distinct += 1

                node = node[value]

        return distinct

Complexity:

  • Time: O(n²), for extending subarrays from every starting index.
  • Space: O(n²), for trie nodes in the worst case.

Common follow-ups

  • What if p can be zero? The divisibility condition needs a defined alternative, since modulo by zero is undefined.
  • Can rolling hashes reduce trie overhead? Yes; hash each subarray incrementally and store hashes, while accounting for possible collisions.
  • What if the input is too large to keep all trie nodes in memory? Use hashing or external storage, depending on the acceptable collision and storage tradeoffs.
CodingMediumTuringSoftware Engineer

14. Ugly Number II (LeetCode)

Model answer

The task

Return the nth positive integer whose prime factors are limited to 2, 3, and 5.

Key idea

Every such number is formed by multiplying a smaller such number by 2, 3, or 5. Build the sequence in increasing order, keeping a pointer for each multiplier; choosing the smallest next candidate avoids duplicates and ensures the sequence stays sorted.

Approach

  1. Store the sequence so far, starting with 1.
  2. Keep three indices pointing to values whose multiples by 2, 3, and 5 are candidates for the next number.
  3. Append the smallest of those three candidates.
  4. Advance every pointer whose candidate equals the appended number, so duplicates such as 6 are skipped.
  5. Return the final value in the sequence.
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # The first ugly number is 1.
        ugly = [1]

        i2 = i3 = i5 = 0

        while len(ugly) < n:
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5

            next_value = min(next2, next3, next5)
            ugly.append(next_value)

            # Advance all matching pointers to avoid duplicates.
            if next_value == next2:
                i2 += 1
            if next_value == next3:
                i3 += 1
            if next_value == next5:
                i5 += 1

        return ugly[-1]

Complexity:

  • Time: O(n) — each sequence value is generated once.
  • Space: O(n) — stores the sequence up to the requested position.

Common follow-ups

  • How could a min-heap solve it? Repeatedly pop the smallest candidate and push its multiples by 2, 3, and 5, using a set to prevent duplicates.
  • How would you handle other allowed prime factors? Maintain one pointer per factor and choose the minimum next candidate across them.
  • Can the sequence be generated as a stream? Yes; keep the generated values and pointers, producing each next value on demand.
CodingMediumTuringSoftware Engineer

15. Koko Eating Bananas (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

        return left

Complexity:

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

Common follow-ups

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

16. Merge Intervals (LeetCode)

Model answer

The task

Given a collection of intervals, combine every pair that overlaps and return the resulting non-overlapping intervals. The result should be ordered by starting point.

Key idea

Sort intervals by their start. Then scan once, keeping the most recently merged interval; each next interval either extends it or starts a new one.

Approach

  1. Sort the intervals by their start value.
  2. Initialize the result with the first interval, if any.
  3. For each remaining interval, compare its start with the end of the last result interval.
  4. If they overlap, update that end to the larger of the two ends.
  5. Otherwise, append the interval as a new result.
from typing import List

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

        intervals.sort(key=lambda interval: interval[0])
        merged = [intervals[0]]

        for start, end in intervals[1:]:
            # The intervals overlap, so extend the last merged interval.
            if start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                # No overlap: this interval begins a new merged range.
                merged.append([start, end])

        return merged

Complexity: Time: O(n log n), dominated by sorting n intervals.

Complexity: Space: O(n) for the merged result; sorting may also use up to O(n) space.

Common follow-ups

  • What if intervals that only touch at an endpoint should remain separate? Use start < merged[-1][1] as the overlap test.
  • How would you merge intervals as they arrive in sorted order? Skip sorting and apply the same scan, processing each interval once.
  • What if intervals are inserted one at a time into an already merged collection? Use binary search to find the insertion point, then merge neighboring overlaps.
CodingMediumTuringSoftware Engineer

17. Longest Arithmetic Subsequence (LeetCode)

Model answer

The task

Given an integer array, find the length of its longest subsequence whose consecutive values have a constant difference. The selected elements must keep their original order, but need not be adjacent.

Key idea

For each ending index, track the best subsequence length for every possible difference. Extending a subsequence ending earlier with the same difference gives a candidate one element longer.

Approach

  1. Create a hash map for each array index, keyed by the common difference.
  2. Visit every pair of indices j < i; their values define the difference nums[i] - nums[j].
  3. Extend the best matching subsequence ending at j, or start a new pair of length two.
  4. Store the result for index i and update the overall maximum.
class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        # dp[i][diff] is the longest arithmetic subsequence
        # ending at index i with common difference diff.
        dp = [{} for _ in range(n)]
        longest = 2

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                length = dp[j].get(diff, 1) + 1
                dp[i][diff] = length
                longest = max(longest, length)

        return longest

Complexity:

  • Time: O(n²), for checking every pair of indices.
  • Space: O(n²), for storing difference states across indices.

Common follow-ups

  • How would you return one longest subsequence, not just its length? Store predecessor indices alongside the DP states, then backtrack from the best state.
  • How does this handle duplicate values? A difference of zero is stored like any other difference.
  • Can the space be reduced? In general, many distinct differences may occur per index, so the pair-based DP can require O(n²) space.
CodingMediumTuringSoftware Engineer

18. Non-decreasing Array (LeetCode)

Model answer

The task

Determine whether an integer array can be made non-decreasing by changing at most one element.

Key idea

Scan from left to right and handle the first descending pair. Either lower the earlier value or raise the later one; the value two positions back tells us which choice keeps the sequence valid. A second descending pair means one change is not enough.

Approach

  1. Track whether a change has already been used.
  2. For each adjacent pair, continue if it is already non-decreasing.
  3. On a descent, return False if a change was already used.
  4. Otherwise, lower the earlier value when that preserves the order with the value before it; if not, raise the later value.
  5. Return True if the scan completes.
class Solution:
    def checkPossibility(self, nums: list[int]) -> bool:
        changed = False

        for i in range(1, len(nums)):
            if nums[i - 1] <= nums[i]:
                continue

            if changed:
                return False

            changed = True

            # Lower nums[i - 1] if that won't violate the earlier pair.
            if i == 1 or nums[i - 2] <= nums[i]:
                nums[i - 1] = nums[i]
            else:
                # Otherwise, raise nums[i] to preserve the earlier pair.
                nums[i] = nums[i - 1]

        return True

Complexity:

  • Time: O(n), where n is the array length.
  • Space: O(1), using only a few variables. The input array is modified.

Common follow-ups

  • What if the input must not be modified? Make a copy first, using O(n) extra space.
  • What if up to k changes are allowed? Track the number of descents and reason about which adjustment each one requires.
  • What if the array must be strictly increasing? Change the pair checks to require < rather than <=, and adjust the chosen replacement values accordingly.
CodingMediumTuringSoftware Engineer

19. Minimum Length of Anagram Concatenation (LeetCode)

Model answer

The task

Find the shortest block length such that the string can be split into equal-sized blocks, and every block has the same character frequencies.

Key idea

A valid block length must divide the string length. For each possible divisor, compare every block’s character counts with the first block’s; the first length that passes is the minimum.

Approach

  1. Try block lengths in increasing order.
  2. Skip lengths that do not divide the string length.
  3. Count the characters in the first block.
  4. Compare each remaining block’s character counts with that count.
  5. Return the first valid length.
from collections import Counter

class Solution:
    def minAnagramLength(self, s: str) -> int:
        n = len(s)

        # Increasing order ensures the first valid length is minimal.
        for length in range(1, n + 1):
            if n % length != 0:
                continue

            target_counts = Counter(s[:length])
            valid = True

            for start in range(length, n, length):
                if Counter(s[start:start + length]) != target_counts:
                    valid = False
                    break

            if valid:
                return length

        # The full string is always a valid single block.
        return n

Complexity:

  • Time: O(n · τ(n)), where τ(n) is the number of divisors of n; each candidate checks all characters.
  • Space: O(n) for temporary block slices and character counts.

Common follow-ups

  • How could this be faster for a fixed alphabet? Use a fixed-size frequency array instead of Counter.
  • Can non-divisor lengths be valid? No; equal-sized blocks must divide the total string length.
  • Can the method return a shortest representative block too? Yes; return the first block along with its length when a candidate passes.
CodingMediumTuringSoftware Engineer

20. Sum of Digit Differences of All Pairs (LeetCode)

Model answer

The task

Given integers with the same number of digits, add up how many digit positions differ for every pair of distinct numbers.

Key idea

Count digit frequencies separately at each position. At a position, the number of pairs that differ is the total number of pairs minus the pairs whose digits match.

Approach

  1. Find the number of digit positions.
  2. For each position, count how many numbers have each digit.
  3. Subtract matching-digit pairs from all pairs.
  4. Sum the differing pairs across positions.
from typing import List

class Solution:
    def sumOfDigitDifferences(self, nums: List[int]) -> int:
        n = len(nums)
        positions = len(str(max(nums)))
        total_pairs = n * (n - 1) // 2
        answer = 0

        # Count digits independently at each place value.
        for _ in range(positions):
            frequencies = [0] * 10

            for value in nums:
                frequencies[value % 10] += 1

            matching_pairs = sum(
                count * (count - 1) // 2
                for count in frequencies
            )
            answer += total_pairs - matching_pairs

            # Move every number to its next digit.
            nums = [value // 10 for value in nums]

        return answer

Complexity:

  • Time: O(n · d), where d is the number of digits.
  • Space: O(n), for the shifted list of values.

Common follow-ups

  • How can this be computed as numbers arrive in a stream? For each new digit, add the number of earlier digits that differ from it, then update its frequency.
  • What if numbers have different digit lengths? Treat missing leading digits as zero, if that matches the intended definition.
  • What if each digit position has a different weight? Multiply that position’s differing-pair count by its weight before adding it.

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