Tinkoff interview questions & answers

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

CodingEasyTinkoffSoftware Engineer

1. Roman to Integer (LeetCode)

Model answer

The task

Convert a string of Roman numeral symbols into its integer value. Roman numerals use a small set of symbols, with some smaller values placed before larger ones to indicate subtraction.

Key idea

Scan the string from left to right, comparing each symbol’s value with the next one. If the current value is smaller, subtract it; otherwise, add it. This handles subtractive pairs without needing to process them separately.

Approach

  1. Store the integer value for each Roman numeral symbol in a lookup table.
  2. Initialize a running total to zero.
  3. For each symbol, compare its value with the following symbol’s value, if one exists.
  4. Subtract the current value when it is smaller than the next value; otherwise, add it.
  5. Return the total. This assumes the input is a valid Roman numeral.
class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        total = 0

        for i, symbol in enumerate(s):
            current = values[symbol]

            # A smaller value before a larger value is subtracted.
            if i + 1 < len(s) and current < values[s[i + 1]]:
                total -= current
            else:
                total += current

        return total

Complexity: Time: O(n), where n is the string length, since each symbol is visited once.

Complexity: Space: O(1), because the lookup table has a fixed number of entries.

Common follow-ups

  • How would you handle invalid Roman numeral strings? Validate symbol order and repetition rules before or during conversion.
  • How would you convert an integer to a Roman numeral? Greedily subtract from a descending list of allowed values, including subtractive pairs.
  • Can the conversion be done scanning right to left? Yes; subtract a value if it is smaller than the largest value already seen to its right, otherwise add it.
CodingEasyTinkoffSoftware 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.
CodingEasyTinkoffSoftware Engineer

3. Find the Longest Balanced Substring of a Binary String (LeetCode)

Model answer

The task

Find the length of the longest contiguous substring made of an equal number of 0s followed by 1s. The substring must contain all its zeroes before its ones.

Key idea

A valid substring can only span a consecutive run of zeroes immediately followed by a consecutive run of ones. For each such pair of runs, the longest balanced substring uses the smaller run’s full length.

Approach

  1. Scan the string from left to right.
  2. Skip any leading 1s until reaching a run of zeroes.
  3. Count that run of zeroes, then count the immediately following run of ones.
  4. Update the answer to the maximum of its current value and twice the smaller run length.
  5. Continue scanning from the end of those runs.
class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        best = 0
        i = 0
        n = len(s)

        while i < n:
            # A run of ones cannot begin a balanced substring.
            if s[i] == "1":
                i += 1
                continue

            zero_count = 0
            while i < n and s[i] == "0":
                zero_count += 1
                i += 1

            one_count = 0
            while i < n and s[i] == "1":
                one_count += 1
                i += 1

            best = max(best, 2 * min(zero_count, one_count))

        return best

Complexity:

  • Time: O(n), because each character is scanned at most once.
  • Space: O(1), using only a few counters.

Common follow-ups

  • What if the substring may start with 1s? Then track both run orders and compare their lengths.
  • How would you return the substring itself? Store the start and end indices whenever the best length improves.
  • What if the string is streamed? Keep the previous run length and current run length, updating the best when a run changes.
CodingEasyTinkoffSoftware Engineer

4. Summary Ranges (LeetCode)

Model answer

The task

Given a sorted array of distinct integers, combine each maximal run of consecutive values into a compact string. A run of one value is written as that value; a longer run uses its first and last values separated by an arrow.

Key idea

Scan the array once, keeping track of the start of the current run. When the next number is not consecutive, emit the completed run and begin a new one.

Approach

  1. Start at the first array element.
  2. Advance while each next value is exactly one greater than the current value.
  3. Emit the run as a single number or as a start-to-end range.
  4. Continue from the next unprocessed element.
  5. Return the collected strings.
from typing import List

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ranges = []
        i = 0

        while i < len(nums):
            start = nums[i]

            # Find the end of this consecutive run.
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                i += 1

            end = nums[i]
            if start == end:
                ranges.append(str(start))
            else:
                ranges.append(f"{start}->{end}")

            i += 1

        return ranges

Complexity:

  • Time: O(n), since each element is visited once.
  • Space: O(1) auxiliary space, excluding the output list.

Common follow-ups

  • What if duplicates are allowed? Skip duplicates during the scan so they do not break a consecutive run.
  • What if the input is not sorted? Sort it first, then deduplicate if needed; sorting takes O(n log n).
  • Can the ranges be generated from a stream? Keep the current run’s start and end, and emit it whenever the next value is not consecutive.
CodingEasyTinkoffSoftware Engineer

5. Is Subsequence (LeetCode)

Model answer

The task

Determine whether all characters of one string appear in another string in the same order. The characters do not need to be adjacent.

Key idea

Scan the larger string from left to right, matching the next needed character from the smaller string. If every character is matched, the smaller string is a subsequence.

Approach

  1. Keep a pointer to the next character to match in s.
  2. Iterate through each character in t.
  3. Advance the pointer whenever the current character matches.
  4. Return True once all characters in s have been matched.
  5. If the scan ends first, return False. An empty s is automatically a subsequence.
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        matched = 0

        for char in t:
            if matched < len(s) and char == s[matched]:
                matched += 1

                if matched == len(s):
                    return True

        return matched == len(s)

Complexity:

  • Time: O(len(t)) — each character in t is scanned at most once.
  • Space: O(1) — only a pointer is used.

Common follow-ups

  • What if there are many queries against the same t? Precompute each character’s positions in t, then use binary search to find the next valid position for each query character.
  • What if the strings are streamed? Keep the pointer into s and process each incoming character of t; stop once all characters match.
  • How should repeated characters be handled? Match them in order, advancing the pointer after every match; each occurrence requires a distinct position in t.
CodingEasyTinkoffSoftware Engineer

6. Minimum Difference Between Highest and Lowest of K Scores (LeetCode)

Model answer

The task

Choose exactly k scores and make the difference between the highest and lowest as small as possible. Return that smallest possible difference.

Key idea

Sort the scores. In sorted order, the best group of k scores is a consecutive window: any scores between the group's minimum and maximum can only narrow that range.

Approach

  1. Sort the scores in ascending order.
  2. For each window of k consecutive scores, compute the last score minus the first.
  3. Return the smallest difference found.
class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        # Sorting makes each consecutive window a candidate group
        # with its smallest and largest scores at the ends.
        nums.sort()

        smallest_difference = float("inf")

        for start in range(len(nums) - k + 1):
            difference = nums[start + k - 1] - nums[start]
            smallest_difference = min(smallest_difference, difference)

        return smallest_difference

Complexity:

  • Time: O(n log n), dominated by sorting; scanning windows takes O(n).
  • Space: O(n) in the worst case for Python's sorting implementation.

Common follow-ups

  • What if k is 1? Every group contains one score, so the answer is 0.
  • Can the input order be preserved? Sort a copy of the scores rather than modifying the original list.
  • What if the scores arrive as a stream? Without storing or indexing scores, finding the exact minimum generally requires retaining enough data to sort or otherwise examine candidate groups.
CodingMediumTinkoffSoftware Engineer

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

8. Event Emitter (LeetCode)

Model answer

The task

Build an event emitter that lets callers register callbacks for named events, trigger those callbacks with arguments, and unsubscribe individual registrations. Triggering an event returns the callbacks’ results in registration order.

Key idea

Store a list of subscription records for each event. Give each registration its own record so that unsubscribing one subscription does not accidentally remove another registration of the same callback.

Approach

  1. Keep a mapping from event names to lists of subscription records.
  2. On subscription, create a record and append it to that event’s list.
  3. Return the record as a handle with an unsubscribe method.
  4. On emission, iterate over a snapshot of the list and call each still-active callback.
  5. Return the results in the order callbacks ran.
from typing import Any, Callable

class Subscription:
    """A handle for one particular callback registration."""

    def __init__(
        self,
        emitter: "EventEmitter",
        event: str,
        callback: Callable[..., Any],
    ) -> None:
        self._emitter = emitter
        self._event = event
        self._callback = callback
        self._active = True

    def unsubscribe(self) -> None:
        """Remove this registration; repeated calls have no effect."""
        if not self._active:
            return

        self._active = False
        subscriptions = self._emitter._subscriptions[self._event]
        subscriptions.remove(self)

        if not subscriptions:
            del self._emitter._subscriptions[self._event]

class EventEmitter:
    def __init__(self) -> None:
        self._subscriptions: dict[str, list[Subscription]] = {}

    def subscribe(
        self, event: str, callback: Callable[..., Any]
    ) -> Subscription:
        subscription = Subscription(self, event, callback)
        self._subscriptions.setdefault(event, []).append(subscription)
        return subscription

    def emit(self, event: str, args: list[Any] | None = None) -> list[Any]:
        results = []
        # Snapshot the list so changes during a callback do not alter iteration.
        for subscription in list(self._subscriptions.get(event, [])):
            if subscription._active:
                results.append(subscription._callback(*(args or [])))
        return results

Complexity:

  • Time: subscribe is O(1); emit is O(k), where k is the number of subscriptions for the event.
  • Space: O(s), where s is the total number of active subscriptions.

Common follow-ups

  • How can unsubscribe be O(1)? Store linked-list nodes or use indexed subscription records.
  • What if the same callback is subscribed twice? Keep separate records so each handle removes only its own registration.
  • Should callbacks added during an emission run immediately? Define the behavior; this implementation uses a snapshot, so they run on the next emission.
CodingMediumTinkoffSoftware Engineer

9. String Compression (LeetCode)

Model answer

The task

Compress consecutive runs of identical characters in a character array, modifying it in place. Keep one character per run and append the run’s count as decimal digits when it is greater than one; return the length of the compressed prefix.

Key idea

Use one pointer to scan each run and another to write the compressed result. Since the write pointer never moves ahead of the read pointer, writing the result cannot overwrite characters that are still needed.

Approach

  1. Start read and write pointers at the beginning of the array.
  2. For each run, remember its character and count its length.
  3. Write the character at the next output position.
  4. If the run has multiple characters, write its count one digit at a time.
  5. Return the final write position.
from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        read = 0
        write = 0
        n = len(chars)

        while read < n:
            char = chars[read]
            run_start = read

            while read < n and chars[read] == char:
                read += 1

            count = read - run_start
            chars[write] = char
            write += 1

            if count > 1:
                # Find the highest power of ten in the count.
                divisor = 1
                while divisor <= count // 10:
                    divisor *= 10

                # Write the count's digits from most to least significant.
                while divisor > 0:
                    digit = (count // divisor) % 10
                    chars[write] = str(digit)
                    write += 1
                    divisor //= 10

        return write

Complexity:

  • Time: O(n), since each character is scanned once and the output has at most O(n) digits.
  • Space: O(1) auxiliary space; the array is modified in place.

Common follow-ups

  • What if counts use a different base? Find the digits in that base and write them from most significant to least.
  • What if the input cannot be modified? Build and return a separate output sequence.
  • What if runs are streamed and the input is unbounded? Retain the current character and count, emitting each run when it ends.
CodingMediumTinkoffSoftware Engineer

10. Decode String (LeetCode)

Model answer

The task

Decode a string where a number before brackets indicates how many times to repeat the bracketed section. Sections may be nested.

Key idea

Parse the input into a compact tree of literal fragments and repeat nodes instead of expanding nested sections immediately. Then traverse that tree to produce the decoded string, avoiding repeated copying of large intermediate strings.

Approach

  1. Scan the input, accumulating each repetition count.
  2. On an opening bracket, save the current fragment list and count, then start a new list.
  3. On a closing bracket, wrap the current list in a repeat node and add it to its parent.
  4. Traverse the resulting structure with an explicit stack, yielding literal fragments as they are needed.
  5. Join the yielded fragments into the result.
class Solution:
    def decodeString(self, s: str) -> str:
        # Each repeat node is a (count, fragments) tuple.
        current = []
        stack = []
        count = 0

        for char in s:
            if "0" <= char <= "9":
                count = count * 10 + int(char)
            elif char == "[":
                stack.append((current, count))
                current = []
                count = 0
            elif char == "]":
                parent, repeat = stack.pop()
                # Omit zero repetitions so traversal skips empty sections.
                if repeat:
                    parent.append((repeat, current))
                current = parent
            else:
                current.append(char)

        def fragments():
            # Frames contain a fragment list, its next index, and
            # how many times to traverse that list.
            frames = [[current, 0, 1]]

            while frames:
                parts, index, remaining = frames[-1]

                if index == len(parts):
                    remaining -= 1
                    if remaining == 0:
                        frames.pop()
                    else:
                        frames[-1][1] = 0
                        frames[-1][2] = remaining
                    continue

                node = parts[index]
                frames[-1][1] += 1

                if isinstance(node, str):
                    yield node
                else:
                    repeat, nested = node
                    frames.append([nested, 0, repeat])

        return "".join(fragments())

Complexity:

  • Time: O(n + m), where n is the encoded length and m is the decoded length.
  • Space: O(n + m) for the parsed structure and returned string.

Common follow-ups

  • How would you handle malformed input? Validate bracket balance and ensure each opening bracket has a preceding count.
  • How could this support streaming output? Yield decoded fragments to a consumer instead of joining them into one string.
  • What if the grammar adds escaping or other operators? Extend the parser with explicit rules and represent each operation as a distinct node.
CodingMediumTinkoffSoftware Engineer

11. 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.
CodingMediumTinkoffSoftware Engineer

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

13. Search in Rotated Sorted Array (LeetCode)

Model answer

The task

Given an ascending array that has been rotated at an unknown position, find the index of a target value, or return -1 if it is absent. The values are distinct.

Key idea

At each binary-search step, at least one half of the current range is still sorted. Check whether the target falls within that half; if so, keep it, otherwise search the other half.

Approach

  1. Initialize two pointers at the ends of the array.
  2. While the pointers have not crossed, inspect the middle value.
  3. If it matches the target, return its index.
  4. If the left half is sorted, check whether the target lies within its bounds and discard the other half if it does.
  5. Otherwise, use the sorted right half in the same way.
  6. Return -1 if the range becomes empty.
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

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

            if nums[mid] == target:
                return mid

            # The left half is sorted.
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Otherwise, the right half is sorted.
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Complexity:

  • Time: O(log n), because each step discards about half the remaining range.
  • Space: O(1), since the search uses only a fixed number of variables.

Common follow-ups

  • What changes if duplicates are allowed? If the endpoints and midpoint are equal, discard one endpoint; worst-case time can become O(n).
  • How would you find the rotation pivot? Binary-search for the minimum element, then search the appropriate sorted portion.
  • How would you return all matching indices with duplicates? First locate a match, then scan outward across adjacent equal values.
CodingMediumTinkoffSoftware Engineer

14. Line Reflection (LeetCode)

Model answer

The task

Given a collection of 2D points, decide whether reflecting the collection across some vertical line leaves the set of points unchanged.

Key idea

The leftmost and rightmost points determine the only possible vertical axis: its x-coordinate is their average. Let axis_sum be twice that coordinate. A point (x, y) must have its reflected partner (axis_sum - x, y) in the collection.

Approach

  1. Return True for an empty collection.
  2. Find the minimum and maximum x-coordinates, and add them to get axis_sum.
  3. Store all points as coordinate tuples in a set for fast membership checks.
  4. For each point, check that its reflection across the candidate axis is in the set.
  5. Return False if any reflected point is missing; otherwise return True.
from typing import List

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        if not points:
            return True

        min_x = min(x for x, _ in points)
        max_x = max(x for x, _ in points)
        axis_sum = min_x + max_x

        point_set = {(x, y) for x, y in points}

        for x, y in points:
            reflected = (axis_sum - x, y)
            if reflected not in point_set:
                return False

        return True

Complexity:

  • Time: O(n), using expected O(1) set lookups.
  • Space: O(n) for the set of points.

Common follow-ups

  • What if the points arrive as a stream? Keep track of the current horizontal bounds and stored points; verify pairs once the candidate axis is known.
  • What if coordinates are floating-point values? Use a suitable tolerance or exact rational representation for comparisons.
  • How would you handle reflection across an arbitrary line? The candidate line is no longer determined by x-extremes; derive and test a line from the point set’s symmetry.
CodingMediumTinkoffSoftware Engineer

15. Min Stack (LeetCode)

Model answer

The task

Design a stack that supports pushing and removing values, inspecting the top value, and retrieving the minimum value currently stored. Each operation should take constant time.

Key idea

Alongside each value, store the minimum seen at that point in the stack. The top entry then contains enough information to answer a minimum query without scanning the stack.

Approach

  1. Keep a list of (value, minimum_so_far) pairs.
  2. On push, compare the new value with the current minimum and store the smaller one.
  3. On pop, remove the top pair.
  4. Return the value or minimum from the top pair for top and getMin.
class MinStack:
    def __init__(self):
        # Each entry is (value, minimum among entries up to this one).
        self.stack = []

    def push(self, val: int) -> None:
        current_min = val
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity:

  • Time: O(1) per operation; each method accesses or updates only the top entry.
  • Space: O(n); each stack entry stores its value and the minimum so far.

Common follow-ups

  • Can you reduce the extra space? Store only values and keep a second stack of minimums, pushing a minimum when it is no greater than the current one.
  • How should duplicate minimums be handled? Track duplicates in the minimum stack too, so popping one leaves the other available.
  • What if the stack can be empty when queried? Define the API’s empty-stack behavior, such as raising an exception or returning a sentinel.
CodingMediumTinkoffSoftware Engineer

16. Battleships in a Board (LeetCode)

Model answer

The task

Count the straight horizontal or vertical ships marked on a character grid, without changing the grid.

Key idea

Each ship has one topmost cell and one leftmost cell. Count an X only when the cell above and the cell to its left are not X; this identifies each ship exactly once.

Approach

  1. Get the board dimensions, handling an empty board.
  2. Scan every cell.
  3. For each X, check its upper and left neighbors, treating off-board positions as water.
  4. Increment the count only if neither neighbor is X.
from typing import List

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

        rows, cols = len(board), len(board[0])
        ships = 0

        for r in range(rows):
            for c in range(cols):
                if board[r][c] != "X":
                    continue

                has_ship_above = r > 0 and board[r - 1][c] == "X"
                has_ship_left = c > 0 and board[r][c - 1] == "X"

                if not has_ship_above and not has_ship_left:
                    ships += 1

        return ships

Complexity:

  • Time: O(mn), where m and n are the board dimensions; every cell is checked once.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if the board may be modified? Mark visited cells during a traversal, though it is unnecessary here.
  • What if ships can bend? Use DFS or BFS to find each connected component, then validate its shape if required.
  • What if ships can touch? The simple scan may merge touching ships; use extra information or a different representation to distinguish them.
CodingMediumTinkoffSoftware Engineer

17. Simplify Path (LeetCode)

Model answer

The task

Given an absolute Unix-style path, return its canonical form by removing redundant separators and current-directory components, and resolving parent-directory components.

Key idea

Process the path one component at a time with a stack. Keep ordinary directory names, ignore . and empty components, and pop a directory for .. when possible.

Approach

  1. Split the path on /.
  2. Ignore empty components and ..
  3. For .., pop the most recent directory if the stack is not empty.
  4. Push all other components.
  5. Join the stack with / and add the leading slash. An empty stack represents the root.
class Solution:
    def simplifyPath(self, path: str) -> str:
        directories = []

        for component in path.split("/"):
            if component == "" or component == ".":
                continue

            if component == "..":
                if directories:
                    directories.pop()
            else:
                directories.append(component)

        return "/" + "/".join(directories)

Complexity:

  • Time: O(n), where n is the length of the path; each character is processed a constant number of times.
  • Space: O(n), for the components stored in the stack.

Common follow-ups

  • How would you handle relative paths? Preserve leading .. components that cannot be resolved.
  • What if directory names can contain escaped slashes? Tokenize according to the specified escaping rules before applying the stack logic.
  • Can the result be built without storing all components? Not generally with a single forward pass, since parent components may remove earlier names.
CodingMediumTinkoffSoftware Engineer

18. Remove Nth Node From End of List (LeetCode)

Model answer

The task

Given the head of a singly linked list and an integer n, remove the node that is n positions from the end, then return the updated head.

Key idea

Keep two pointers a fixed distance apart. Once the lead pointer reaches the end, the trailing pointer is just before the node to remove. A dummy node handles removing the head uniformly.

Approach

  1. Create a dummy node pointing to the head.
  2. Set both pointers to the dummy.
  3. Advance the lead pointer n + 1 steps to establish the gap.
  4. Move both pointers until the lead reaches the end.
  5. Bypass the target node and return dummy.next.
# LeetCode provides the ListNode definition.
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        lead = dummy
        trail = dummy

        # Leave trail immediately before the node to remove.
        for _ in range(n + 1):
            lead = lead.next

        while lead is not None:
            lead = lead.next
            trail = trail.next

        # Remove the target node.
        trail.next = trail.next.next
        return dummy.next

Complexity:

  • Time: O(L), where L is the list length; the pointers traverse the list once.
  • Space: O(1), using only a fixed number of pointers.

Common follow-ups

  • What if the list has one node? The dummy node lets the same removal logic return None.
  • Can this be done in two passes? Yes: count the nodes, then traverse to the node before the target.
  • What if n is invalid? Validate it or define the desired behavior before advancing the lead pointer.
CodingMediumTinkoffSoftware 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.

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