Python. Задачи с собесов (draft)

В заметке приведено несколько задач с собесов, которые нужно было решать онлайн. Со временем возможно будут дополнения.

Задача: Написать функцию, которая считает сумму произведений всех элементов массива, исключая одно на каждом шаге. В массиве только положительные целые числа.

# multsum([1,5,6]) = 5*6 + 1*6 + 1*5 = 41

# multsum([1,5,6,7]) = 5*6*7 + 1*6*7 + 1*5*7+ 1*5*6 = 317

import math

def multsum(arr: list):
    total_product = math.prod(arr) # Вычисляем общее произведение всех чисел
    sum_of_excluded_products = 0
    
    for num in arr:
        sum_of_excluded_products += total_product // num
            
    return sum_of_excluded_products

Задача: Есть массив целых чисел и число K. Найти два таких (не обязательно различных) числа в массиве, сумма которых равна K, либо вывести, что таких чисел нет.

def find_two_sum(nums, K: int):
    """
    Находит два числа в массиве, сумма которых равна K.
    
    Args:
        nums: Список целых чисел.
        K: Целевая сумма.
        
    Returns:
        Кортеж из двух чисел, если пара найдена, или строка "null", если не найдена.
    """
    
    # Словарь для хранения чисел, которые мы уже встречали
    seen_numbers = {} 
    
    for num in nums:
        # Вычисляем число, которое дополнит текущее `num` до `K`
        complement = K - num
        
        # Если `complement` уже есть в нашем словаре `seen_numbers`,
        # значит, мы нашли нужную пару.
        if complement in seen_numbers:
            return (complement, num)
        
        # Если `complement` не найден, добавляем текущее `num` в словарь,
        # чтобы его могли найти на следующих шагах.
        # Значение в словаре (например, True или индекс) не имеет значения для этой конкретной задачи,
        # главное, чтобы ключ был добавлен.
        seen_numbers[num] = True 
        
    # Если цикл завершился, и мы не нашли пару, возвращаем "null"
    return "null"

Задача: Дана строка из латинских заглавных букв. Необходимо заменить все повторы одинаковых подряд идущих букв на букву + цифру. Одиночные буквы заменять не надо.

def compress_rle(s: str) -> str:
    """
    Сжимает строку: для подряд идущих одинаковых символов длины >= 2
    заменяет их на 'символ' + 'число'. Одиночные символы не меняет.
    Пример: "AAAABBB CAAA" -> "A4B3C A3" (пробелы сохраняются)
    """
    if not s:
        return ""
    
    res = []
    prev = s[0]
    count = 1
    
    for ch in s[1:]:
        if ch == prev:
            count += 1
        else:
            # Завершили блок
            if count == 1:
                res.append(prev)
            else:
                res.append(f"{prev}{count}")
            prev = ch
            count = 1
    
    # Добавляем последний блок
    if count == 1:
        res.append(prev)
    else:
        res.append(f"{prev}{count}")
    
    return "".join(res)

Задача о «Правильной скобочной последовательности» (Valid Parentheses)

Дана строка, состоящая только из символов скобок: '(', ')', '{', '}', '[' и ']'.
Определите, является ли входная строка валидной.
Строка считается валидной, если:

1. Открытые скобки должны быть закрыты скобками того же типа.

2. Открытые скобки должны быть закрыты в правильном порядке.

3. Каждая закрывающая скобка должна иметь соответствующую ей открывающую скобку того же типа.
Примеры:

• Вход: s = "()" — Вывод: True
• Вход: s = "()[]{}" — Вывод: True
• Вход: s = "(]" — Вывод: False
• Вход: s = "([)]" — Вывод: False
• Вход: s = "{[]}" — Вывод: True

def is_valid(s: str) -> bool:
    # Словарь соответствия закрывающей скобки открывающей
    bracket_map = {
        ")": "(",
        "}": "{",
        "]": "["
    }
    
    # Стек для хранения открывающих скобок
    stack = []
    
    for char in s:
        # Если символ — это закрывающая скобка
        if char in bracket_map:
            # Извлекаем верхний элемент из стека, если он не пуст,
            # иначе присваиваем заглушку (например, '#')
            top_element = stack.pop() if stack else '#'
            
            # Если открывающая скобка из стека не совпадает с нужной для этого типа
            if bracket_map[char] != top_element:
                return False
        else:
            # Если символ — открывающая скобка, кладем её в стек
            stack.append(char)
            
    # Если в конце стек пуст — все скобки закрыты корректно
    return not stack