Yandex interview questions & answers

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

CodingEasyYandexSoftware Engineer

1. Find the Index of the First Occurrence in a String (LeetCode)

Model answer

The task

Given a text string and a pattern string, return the starting index of the pattern’s first occurrence in the text. Return -1 if it does not occur; an empty pattern matches at index 0.

Key idea

Use Knuth–Morris–Pratt (KMP). Its prefix table lets the search reuse information about matched characters instead of restarting from scratch after a mismatch.

Approach

  1. Build a prefix table for the pattern. At each position, it records the length of the longest proper prefix that is also a suffix.
  2. Scan the text while tracking how many pattern characters currently match.
  3. On a mismatch, use the prefix table to find the next viable match length.
  4. Return the match’s starting index when the entire pattern matches; otherwise return -1.
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        # Build the longest-prefix-suffix table for needle.
        lps = [0] * len(needle)
        prefix_len = 0
        i = 1

        while i < len(needle):
            if needle[i] == needle[prefix_len]:
                prefix_len += 1
                lps[i] = prefix_len
                i += 1
            elif prefix_len > 0:
                prefix_len = lps[prefix_len - 1]
            else:
                i += 1

        # Search haystack without rechecking matched characters.
        text_i = 0
        pattern_i = 0

        while text_i < len(haystack):
            if haystack[text_i] == needle[pattern_i]:
                text_i += 1
                pattern_i += 1

                if pattern_i == len(needle):
                    return text_i - pattern_i
            elif pattern_i > 0:
                pattern_i = lps[pattern_i - 1]
            else:
                text_i += 1

        return -1

Complexity:

  • Time: O(n + m), where n and m are the text and pattern lengths.
  • Space: O(m), for the prefix table.

Common follow-ups

  • How would you handle many pattern searches in the same text? Build an index or use a multi-pattern algorithm such as Aho–Corasick.
  • What if the text arrives as a stream? Keep the KMP match state and prefix table between chunks.
  • How would you find all occurrences? After each full match, record its start and reset the pattern index using the final prefix-table value.
CodingEasyYandexSoftware Engineer

2. Merge Sorted Array (LeetCode)

Model answer

The task

Combine two already sorted arrays into one sorted array, placing the result in the first array. The first array has enough spare capacity to hold all elements from both arrays.

Key idea

Fill the first array from right to left. Comparing the largest remaining elements avoids overwriting values in the first array that have not yet been processed.

Approach

  1. Set pointers to the last valid elements of both arrays.
  2. Set a write pointer to the last slot in the first array.
  3. While the second array still has elements, compare the values at the two read pointers.
  4. Write the larger value at the write pointer, then move the corresponding read pointer and the write pointer left.
  5. Any remaining elements from the second array are copied into the first. Remaining elements from the first are already in place.
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        """Merge nums2 into nums1 in-place, keeping nums1 sorted."""
        i = m - 1          # Last initialized element in nums1
        j = n - 1          # Last element in nums2
        write = m + n - 1  # Last available position in nums1

        # Fill from the back so unread nums1 elements are not overwritten.
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write] = nums1[i]
                i -= 1
            else:
                nums1[write] = nums2[j]
                j -= 1
            write -= 1

Complexity:

  • Time: O(m + n), since each element is considered at most once.
  • Space: O(1), because the merge modifies the first array directly.

Common follow-ups

  • What if the arrays are sorted in descending order? Reverse the comparison or adapt the traversal direction.
  • What if the result must go into a separate array? Use two forward pointers and allocate O(m + n) extra space.
  • What if either array is empty? The loop naturally handles it; if the second is empty, the first is already complete.
  • Why merge from the end? Writing from the front could overwrite unprocessed elements in the first array.
CodingEasyYandexSoftware Engineer

3. Valid Palindrome II (LeetCode)

Model answer

The task

Determine whether a string can become a palindrome after removing at most one character.

Key idea

Compare characters from both ends, moving inward while they match. At the first mismatch, the one allowed removal must skip either the left character or the right character; check whether either remaining range is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. While the pointed-to characters match, move both pointers inward.
  3. If the pointers meet, the string is already a palindrome.
  4. Otherwise, check the two ranges formed by skipping either mismatched character.
  5. Return true if at least one range is a palindrome.
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left: int, right: int) -> bool:
            # Check whether this inclusive range reads the same both ways.
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        left, right = 0, len(s) - 1

        while left < right:
            if s[left] != s[right]:
                # Use the one allowed deletion on either mismatched end.
                return (
                    is_palindrome(left + 1, right)
                    or is_palindrome(left, right - 1)
                )
            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), since at most two linear range checks are performed.
  • Space: O(1), excluding the input string; the checks use only pointers.

Common follow-ups

  • What if up to k characters may be removed? Use recursion or dynamic programming to track the remaining deletion budget; the simple one-mismatch check no longer suffices.
  • What if the input is a linked list? Use a stack or find the midpoint and reverse part of the list, depending on whether extra space is allowed.
  • Should comparison ignore capitalization or punctuation? Normalize or skip irrelevant characters while moving the two pointers inward.
CodingEasyYandexSoftware Engineer

4. 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.
CodingEasyYandexSoftware Engineer

5. Merge Two 2D Arrays by Summing Values (LeetCode)

Model answer

The task

Combine two arrays of [id, value] pairs. Return one pair per distinct ID, with values added when an ID appears in both arrays, and IDs in ascending order.

Key idea

Both arrays are already sorted by ID, so use two pointers to merge them. This avoids building a hash table and keeps the result ordered.

Approach

  1. Start pointers at the beginning of each array.
  2. If one current ID is smaller, append its pair and advance that pointer.
  3. If the IDs match, append their ID with the sum of their values and advance both pointers.
  4. Append any remaining pairs from either array.
from typing import List

class Solution:
    def mergeArrays(
        self, nums1: List[List[int]], nums2: List[List[int]]
    ) -> List[List[int]]:
        result = []
        i = j = 0

        while i < len(nums1) and j < len(nums2):
            id1, value1 = nums1[i]
            id2, value2 = nums2[j]

            if id1 < id2:
                result.append([id1, value1])
                i += 1
            elif id2 < id1:
                result.append([id2, value2])
                j += 1
            else:
                result.append([id1, value1 + value2])
                i += 1
                j += 1

        # Only one array can have unprocessed pairs remaining.
        while i < len(nums1):
            result.append(nums1[i])
            i += 1

        while j < len(nums2):
            result.append(nums2[j])
            j += 1

        return result

Complexity:

  • Time: O(m + n), where each pair is processed once.
  • Space: O(m + n) for the returned result; O(1) extra space excluding it.

Common follow-ups

  • What if the inputs are not sorted? Sort them by ID first, or aggregate with a hash table and sort the result.
  • What if there are many arrays to merge? Merge them incrementally or use a min-heap keyed by ID.
  • Can this be done in place? Only if the input storage allows extending and modifying one array; otherwise, a separate result is needed.
CodingEasyYandexSoftware Engineer

6. Implement Queue using Stacks (LeetCode)

Model answer

The task

Build a queue that supports adding to the back, removing or inspecting the front, and checking whether it is empty, using only stacks.

Key idea

Use one stack to collect newly added items and another to serve items in queue order. When the serving stack is empty, move all items from the collection stack into it; this reverses their order so the oldest item is on top.

Approach

  1. Initialize an input stack and an output stack.
  2. For push, append the new item to the input stack.
  3. Before pop or peek, transfer items from input to output if output is empty.
  4. For pop, remove and return the top of output; for peek, return it without removing.
  5. For empty, report whether both stacks are empty.
class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, x: int) -> None:
        # New items are collected here.
        self.input_stack.append(x)

    def _prepare_output(self) -> None:
        # Reverse the input stack only when needed.
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

    def pop(self) -> int:
        self._prepare_output()
        return self.output_stack.pop()

    def peek(self) -> int:
        self._prepare_output()
        return self.output_stack[-1]

    def empty(self) -> bool:
        return not self.input_stack and not self.output_stack

Complexity:

  • Time: O(1) amortized per operation; each item moves between stacks at most once.
  • Space: O(n), for the items stored across both stacks.

Common follow-ups

  • What is the worst-case time for one pop? O(n), if it triggers a transfer of all queued items.
  • Can you use a single stack? Yes, but preserving queue order generally requires recursion or another storage mechanism.
  • What happens if pop or peek is called on an empty queue? Define an error or sentinel behavior, depending on the API contract.
CodingEasyYandexSoftware Engineer

7. Longest Continuous Increasing Subsequence (LeetCode)

Model answer

The task

Given an array of integers, return the length of its longest contiguous segment whose values are strictly increasing. A segment of one element is increasing.

Key idea

Scan from left to right, tracking the length of the increasing run ending at the current element. If the current value is greater than the previous one, extend the run; otherwise, start a new run.

Approach

  1. Return 0 if the array is empty.
  2. Initialize the current run length and best length to 1.
  3. For each element after the first, compare it with its predecessor.
  4. Extend the current run when it is strictly greater; otherwise, reset the run length to 1.
  5. Update and return the best length after each comparison.
class Solution:
    def findLengthOfLCIS(self, nums: list[int]) -> int:
        # An empty array has no increasing segment.
        if not nums:
            return 0

        current_length = 1
        best_length = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current_length += 1
            else:
                # A tie or decrease breaks a strictly increasing run.
                current_length = 1

            best_length = max(best_length, current_length)

        return best_length

Complexity:

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

Common follow-ups

  • How would you return the segment itself, not just its length? Track the start index of each run and save the best run’s start and end when its length improves.
  • What changes if the sequence need not be contiguous? Use a longest-increasing-subsequence algorithm, such as patience sorting, which runs in O(n log n).
  • How should equal adjacent values be handled? They break the run because the increase must be strict.
  • Can this be processed as a stream? Yes; keep only the previous value, current run length, and best length.
CodingEasyYandexSoftware Engineer

8. Symmetric Tree (LeetCode)

Model answer

The task

Determine whether a binary tree is symmetric around its center: its left and right subtrees must be mirror images.

Key idea

Compare nodes in mirrored pairs. For each pair, their values must match, and their outer children and inner children must also match as mirrored pairs.

Approach

  1. Put the root’s left and right children into a queue as a pair.
  2. Remove a pair; if both nodes are absent, continue. If only one is absent or their values differ, return False.
  3. Add the outer pair of children and the inner pair of children to the queue.
  4. If every pair matches, return True.
from collections import deque
from typing import Optional

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        queue = deque([(root.left, root.right)])

        while queue:
            left, right = queue.popleft()

            # Missing nodes must occur in matching positions.
            if left is None or right is None:
                if left is not right:
                    return False
                continue

            if left.val != right.val:
                return False

            # Compare mirrored child positions.
            queue.append((left.left, right.right))
            queue.append((left.right, right.left))

        return True

Complexity:

  • Time: O(n), where n is the number of nodes; each node is checked at most once.
  • Space: O(n) in the worst case for the queue.

Common follow-ups

  • Can this be solved recursively? Yes; define a helper that checks a pair of mirrored nodes and recursively compares their outer and inner children.
  • What if node values are not unique? The method still works because it checks both values and structure.
  • What if the tree is very deep? The iterative queue avoids recursion-depth limits; its memory use depends on the tree’s maximum width.
CodingEasyYandexSoftware Engineer

9. Can Place Flowers (LeetCode)

Model answer

The task

Given a row of plots where 1 marks an occupied plot and 0 an empty one, decide whether at least n flowers can be added without placing flowers in neighboring plots.

Key idea

Scan from left to right, planting in an empty plot whenever both neighboring plots are empty or outside the row. Greedily planting at the earliest available plot cannot reduce the number of later planting opportunities.

Approach

  1. Return True immediately if n is zero.
  2. Visit each plot from left to right.
  3. For an empty plot, check its left and right neighbors, treating the row boundaries as empty.
  4. If both are empty, plant there and decrement n.
  5. Return True once n reaches zero; otherwise return whether it reached zero by the end.
from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True

        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                left_empty = i == 0 or flowerbed[i - 1] == 0
                right_empty = (
                    i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
                )

                if left_empty and right_empty:
                    flowerbed[i] = 1
                    n -= 1

                    if n == 0:
                        return True

        return False

Complexity:

  • Time: O(m), where m is the number of plots; each plot is checked at most once.
  • Space: O(1), using only a fixed amount of extra space.

Common follow-ups

  • What if the input must not be modified? Track the previous plot’s occupancy instead of planting in the array.
  • How would you return the planting positions? Record each plot index when the greedy rule permits planting.
  • What if plots wrap around in a circle? Handle the first and last plots as neighbors, with special care for rows of length one or two.
CodingEasyYandexSoftware Engineer

10. Longest Strictly Increasing or Strictly Decreasing Subarray (LeetCode)

Model answer

The task

Find the length of the longest contiguous portion of an array that is strictly increasing or strictly decreasing. Equal neighboring values break either kind of run.

Key idea

At each position, track the lengths of the increasing and decreasing runs that end there. Extend the appropriate run based on the comparison with the previous value, and keep the largest length seen.

Approach

  1. Return 0 for an empty array.
  2. Initialize both run lengths and the best length to 1.
  3. Scan adjacent values from left to right.
  4. Extend the increasing run if the current value is larger; extend the decreasing run if it is smaller.
  5. If the values are equal, reset both runs to 1. Update the best length after each comparison.
class Solution:
    def longestMonotonicSubarray(self, nums: list[int]) -> int:
        if not nums:
            return 0

        increasing = 1
        decreasing = 1
        best = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                increasing += 1
                decreasing = 1
            elif nums[i] < nums[i - 1]:
                decreasing += 1
                increasing = 1
            else:
                # Equal values cannot extend a strict run.
                increasing = 1
                decreasing = 1

            best = max(best, increasing, decreasing)

        return best

Complexity:

  • Time: O(n), because each value is processed once.
  • Space: O(1), using only a fixed number of counters.

Common follow-ups

  • What if the subarray must be strictly increasing only? Track just the increasing run and its maximum.
  • What if the subarray may be non-decreasing or non-increasing? Allow equal neighbors to extend the corresponding run.
  • Can the actual subarray be returned too? Record the start index whenever a longer run is found, along with its length and direction.
CodingEasyYandexSoftware Engineer

11. Palindrome Number (LeetCode)

Model answer

The task

Determine whether an integer reads the same from left to right and right to left. Negative values are not palindromes.

Key idea

Reverse only the last half of the digits, then compare it with the remaining first half. This avoids converting to a string and keeps the extra space constant.

Approach

  1. Return False for negative integers.
  2. Return False for positive integers ending in zero; zero itself is a palindrome.
  3. Repeatedly move the last digit from the number to a reversed-half accumulator.
  4. Stop when the accumulator has at least as many digits as the remaining number.
  5. Compare the halves directly for even digit counts, or discard the middle digit for odd counts.
class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Negative numbers have a leading minus sign, so they cannot be palindromes.
        if x < 0:
            return False

        # A positive number ending in zero would need a leading zero to be palindromic.
        if x != 0 and x % 10 == 0:
            return False

        reversed_half = 0

        # Move digits until the reversed half is at least as long as the remaining half.
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10

        # For an odd number of digits, ignore the middle digit.
        return x == reversed_half or x == reversed_half // 10

Complexity:

  • Time: O(log₁₀ n), for processing the digits of the number.
  • Space: O(1), using only a few integer variables.

Common follow-ups

  • How would you check a palindrome by converting to a string? Compare symmetric characters, using O(log n) extra space.
  • How would you avoid integer overflow in a fixed-width language? Reversing only half the digits keeps the accumulator bounded.
  • What about zero and numbers ending in zero? Zero is palindromic; other numbers ending in zero are not.
CodingEasyYandexSoftware Engineer

12. Design an Ordered Stream (LeetCode)

Model answer

The task

Build a stream that accepts values paired with sequential integer keys. After each insertion, return the longest newly available run of values starting at the next key that has not yet been returned.

Key idea

Store each value at its key’s position in an array, and keep a pointer to the next key to emit. After an insertion, advance the pointer while its position contains a value.

Approach

  1. Initialize an array with one empty slot per key and set the pointer to the first slot.
  2. On insertion, store the value at the corresponding slot.
  3. Starting at the pointer, collect consecutive filled slots.
  4. Move the pointer past the collected values and return them.
class OrderedStream:
    def __init__(self, n: int):
        # Keys range from 1 to n; use zero-based array indices.
        self.values = [None] * n
        self.pointer = 0

    def insert(self, idKey: int, value: str) -> list[str]:
        # Store the value in its key's position.
        self.values[idKey - 1] = value

        # Emit the newly available contiguous portion of the stream.
        chunk = []
        while (
            self.pointer < len(self.values)
            and self.values[self.pointer] is not None
        ):
            chunk.append(self.values[self.pointer])
            self.pointer += 1

        return chunk

Complexity:

  • Time: O(n) worst case for one insertion; across all insertions, O(n) total work because the pointer only advances.
  • Space: O(n) for the stored values.

Common follow-ups

  • What if a key is inserted more than once? Define whether duplicates are rejected or replace the previous value.
  • How would you handle keys from a very large range? Use a hash map to avoid allocating an array for every possible key.
  • Can emitted values be discarded? Yes; clear consumed slots if later operations never need previously emitted values.
CodingEasyYandexSoftware Engineer

13. 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.
CodingEasyYandexSoftware Engineer

14. Valid Palindrome (LeetCode)

Model answer

The task

Determine whether a string reads the same forward and backward after disregarding characters that are not letters or digits and treating uppercase and lowercase as equivalent.

Key idea

Compare characters from both ends, skipping anything that should be ignored. If every remaining pair matches, the string is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. Move the left pointer past non-alphanumeric characters.
  3. Move the right pointer past non-alphanumeric characters.
  4. Compare the lowercase forms of the characters at the pointers; return False if they differ.
  5. Move both pointers inward and continue. If they meet or cross, return True.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Ignore characters that are not letters or digits.
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare without regard to letter case.
            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), where n is the string length; each pointer moves only inward.
  • Space: O(1), since the comparisons use no additional data structure.

Common follow-ups

  • What if the input contains no letters or digits? It is considered a palindrome, since there are no mismatching characters.
  • Can you avoid creating a normalized copy of the string? Yes; the two-pointer scan uses constant extra space.
  • How would you handle Unicode normalization? Normalize the string first if canonically equivalent characters should compare as equal; that may require additional space.
CodingEasyYandexSoftware Engineer

15. Isomorphic Strings (LeetCode)

Model answer

The task

Determine whether two strings have the same length and whether their characters can be matched one-to-one so that each position in one string corresponds to the same position in the other.

Key idea

Maintain mappings in both directions. A character in the first string must always map to the same character in the second, and two different characters cannot map to the same character.

Approach

  1. Return False if the strings have different lengths.
  2. Create a mapping from the first string to the second.
  3. Create a reverse mapping from the second string to the first.
  4. Scan corresponding characters together.
  5. If either mapping conflicts with the current pair, return False; otherwise, record the pair.
  6. If every pair is consistent, return True.
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        forward = {}
        reverse = {}

        for left, right in zip(s, t):
            if left in forward and forward[left] != right:
                return False
            if right in reverse and reverse[right] != left:
                return False

            forward[left] = right
            reverse[right] = left

        return True

Complexity:

  • Time: O(n), where n is the string length; each position is checked once.
  • Space: O(k), where k is the number of distinct characters stored in the mappings.

Common follow-ups

  • What if the mapping only needs to preserve characters in one direction? Use just one mapping; this does not enforce a one-to-one correspondence.
  • What if the strings are streamed? Process corresponding characters as they arrive, retaining the two mappings.
  • Can the extra space be bounded for a fixed alphabet? Yes; use arrays instead of dictionaries when the character set has a known, small range.
CodingEasyYandexSoftware Engineer

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

17. Allow One Function Call (LeetCode)

Model answer

The task

Create a wrapper around a function that allows it to run at most once. The first call forwards its arguments and returns the function’s result; later calls return None (the Python equivalent of JavaScript’s undefined).

Key idea

Keep a flag in the wrapper’s closure to remember whether the function has been called. Set it before invoking the original function so even a failed or reentrant call cannot trigger another invocation.

Approach

  1. Initialize a called flag to False inside once.
  2. Define a wrapper that can accept positional and keyword arguments.
  3. If the flag is already set, return None.
  4. Otherwise, set the flag and call the original function with the supplied arguments.
  5. Return the original function’s result.
from functools import wraps
from typing import Any, Callable

def once(fn: Callable[..., Any]) -> Callable[..., Any]:
    """Return a wrapper that invokes fn at most once."""
    called = False

    @wraps(fn)
    def wrapper(*args: Any, **kwargs: Any) -> Any:
        nonlocal called

        if called:
            return None

        # Mark it as called before invoking fn, including if fn raises.
        called = True
        return fn(*args, **kwargs)

    return wrapper

Complexity:

  • Time: O(1) wrapper overhead per call, excluding the original function’s work.
  • Space: O(1) extra space for the closure state.

Common follow-ups

  • What if the first invocation raises an exception? This implementation still counts it as the one allowed invocation.
  • How would you make it safe for concurrent calls? Protect the check-and-set operation with a lock.
  • Should later calls return the first result instead? Store the result on the first call and return that cached value afterward.
CodingEasyYandexSoftware Engineer

18. Add Strings (LeetCode)

Model answer

The task

Given two strings representing nonnegative integers, return their sum as a string. The solution should perform the addition directly on the digits rather than converting either entire string to an integer.

Key idea

Add digits from right to left, keeping a carry just as in manual addition. Since the strings can have different lengths, treat missing digits as zero.

Approach

  1. Start at the final digit of each string with a carry of zero.
  2. While either string has digits left or a carry remains, read the next digits (using zero if a string is exhausted).
  3. Add the digits and carry; append the result’s ones digit and update the carry.
  4. Reverse the collected digits to form the answer.
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            digit1 = ord(num1[i]) - ord("0") if i >= 0 else 0
            digit2 = ord(num2[j]) - ord("0") if j >= 0 else 0

            total = digit1 + digit2 + carry
            result.append(str(total % 10))
            carry = total // 10

            i -= 1
            j -= 1

        return "".join(reversed(result))

Complexity:

  • Time: O(max(n, m)), where n and m are the input lengths.
  • Space: O(max(n, m)) for the output digits.

Common follow-ups

  • How would you subtract two nonnegative number strings? Compare magnitudes first, then subtract digits with borrowing.
  • How would you handle negative values? Parse and track each sign, then add or subtract magnitudes as appropriate.
  • How would you add many number strings? Accumulate them with this routine, or use a digit-wise accumulator for a single pass over all inputs.
CodingEasyYandexSoftware Engineer

19. 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.
CodingEasyYandexSoftware Engineer

20. Search Insert Position (LeetCode)

Model answer

The task

Given a sorted array of distinct integers and a target, return its index if present. Otherwise, return the index where it should be inserted to keep the array sorted.

Key idea

Use binary search to find the first position whose value is at least the target. That position is both the target’s index when it exists and its insertion point otherwise.

Approach

  1. Set left to the start of the array and right to its length, treating right as an exclusive bound.
  2. While the search interval is nonempty, inspect its midpoint.
  3. If the midpoint value is less than the target, search to its right.
  4. Otherwise, search the portion including the midpoint and to its left.
  5. When the interval is empty, left is the answer. It can equal the array length if the target belongs at the end.
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        # Find the first index whose value is at least target.
        left, right = 0, len(nums)

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

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left

Complexity:

  • Time: O(log n), since each step halves the search interval.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if the array is empty? The result is 0, which is the correct insertion position.
  • What if duplicates are allowed? This algorithm returns the first position containing the target, or where it should first be inserted.
  • How would you find the last position of a target? Use a binary search for the first value greater than the target, then subtract one.

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