Профессия:
Задачи с собеседований на автоматизатора тестирования: автотест на pytest, тест формы регистрации, вход в систему, CSS-селекторы, SQL-запросы с JOIN и поиском дубликатов, алгоритмы на строках и массивах. К каждой задаче приложен разбор с кодом решения.
Решение: Алгоритм поиска подстроки без встроенных методов
Подход
Для поиска подстроки в строке без встроенных методов используются два основных алгоритма: наивный и эффективный (KMP). Здесь представлены обе реализации с объяснением.
1. Наивный алгоритм O(n*m)
Проверяем каждую позицию в основной строке и сравниваем посимвольно.
def strStr_naive(haystack: str, needle: str) -> int:
"""
Наивный поиск подстроки.
Time: O(n*m) где n=len(haystack), m=len(needle)
Space: O(1)
"""
if not needle:
return 0
if len(needle) > len(haystack):
return -1
for i in range(len(haystack) - len(needle) + 1):
# Проверяем совпадение на позиции i
match = True
for j in range(len(needle)):
if haystack[i + j] != needle[j]:
match = False
break
if match:
return i
return -1
2. KMP алгоритм O(n+m)
Решение
Понимание задачи
Найти медиану двух отсортированных массивов. Медиана — среднее значение в объединённом отсортированном массиве.
Простое решение: Объединение и сортировка
def find_median(nums1, nums2):
merged = sorted(nums1 + nums2)
n = len(merged)
if n % 2 == 1:
return float(merged[n // 2])
else:
return (merged[n // 2 - 1] + merged[n // 2]) / 2.0
Примеры:
Сложность
Оптимальное решение: Двухуказатель
Решение: Сложение двух связных списков
Эта задача требует работы со связными списками. Ключевой момент — цифры хранятся в обратном порядке, что упрощает сложение (начинаем с младших разрядов).
Алгоритм решения
Структура узла списка
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Реализация решения
Решение
Понимание задачи
Преобразовать целое число (1-3999) в римскую запись. Используется принцип вычитания: V (5) перед X (10) означает 4, а не 15.
Оптимальный алгоритм: Greedy с таблицей значений
def int_to_roman(num):
"""
Преобразует число в римскую запись.
"""
# Таблица (значение, символ) отсортирована по убыванию
values = [
(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
]
result = ''
for value, symbol in values:
count = num // value
if count:
result += symbol * count
num -= value * count
return result
Как это работает
Пример: 1994
Шаг 1: 1994 / 1000 = 1 -> 'M', остаток 994 Шаг 2: 994 / 900 = 1 -> 'CM', остаток 94 Шаг 3: 94 / 90 = 1 -> 'XC', остаток 4 Шаг 4: 4 / 4 = 1 -> 'IV', остаток 0
Результат: 'MCMXCIV'
Сложность
Решение задачи "Частота символов в строке"
Для подсчёта частоты символов в строке я реализую функцию, которая принимает строку в качестве входного параметра и возвращает словарь (или аналогичную структуру данных), где ключами являются символы, а значениями — количество их вхождений в строке. Рассмотрю несколько подходов к решению, их плюсы и минусы, а также приведу реализацию на Python.
Основные подходы к решению
Реализация на Python
Этот подход универсален и подходит для любых символов, включая Unicode.
Решение
Понимание задачи
Нужно найти сумму всех элементов массива без использования встроенной функции sum(). Это базовая операция, но важная для тестирования и разработки.
Основное решение: Итерация с циклом
def array_sum(arr):
"""
Находит сумму всех элементов массива без sum().
"""
total = 0
for num in arr:
total += num
return total
# Использование
result = array_sum([1, 2, 3, 4, 5])
print(result) # 15
Как это работает
Пошаговое выполнение:
Шаг 0: total = 0
Шаг 1: total = 0 + 1 = 1
Шаг 2: total = 1 + 2 = 3
Шаг 3: total = 3 + 3 = 6
Шаг 4: total = 6 + 4 = 10
Шаг 5: total = 10 + 5 = 15
Результат: 15
Анализ сложности
Временная сложность: O(n)
Пространственная сложность: O(1)
Решение: Определение цикла в связном списке
Описание проблемы
Нужно определить, содержит ли односвязный список цикл (loop). Цикл — это когда некоторый узел указывает на один из предыдущих узлов, создавая бесконечный путь.
Требуемые метрики:
Подход 1: Алгоритм Флойда (Черепаха и Заяц) — Оптимальный
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Решение: Автотест логина с Page Object Model
Структура проекта
tests/
pages/
login_page.py
home_page.py
base_page.py
test_login.py
conftest.py
1. Base Page (Базовый класс)
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
class BasePage:
def __init__(self, driver, timeout=10):
self.driver = driver
self.wait = WebDriverWait(driver, timeout)
def wait_for_element(self, by, locator):
return self.wait.until(EC.presence_of_element_located((by, locator)))
def wait_for_clickable(self, by, locator):
return self.wait.until(EC.element_to_be_clickable((by, locator)))
def wait_for_url(self, url):
return self.wait.until(EC.url_contains(url))
2. Login Page
from selenium.webdriver.common.by import By
from pages.base_page import BasePage
Решение
CSS селекторы — это фундаментальный навык QA-автоматизатора при работе с Selenium, Playwright и другими фреймворками. Правильно написанный селектор — залог надёжности и поддерживаемости тестов.
1. Все строки таблицы (кроме заголовка)
#users-table tr.row
Объяснение: Селектор #users-table выбирает таблицу по ID, затем спускаемся к элементам tr с классом row. Это исключает заголовок, так как у него класс header, а не row.
Альтернативные варианты:
#users-table tr:not(.header) — все строки таблицы, кроме заголовкаtable#users-table tr.row — более специфичный селектор2. Активная строка
#users-table tr.row.active
Объяснение: Селектор ищет элемент tr, у которого одновременно присутствуют классы row и active. В нашем HTML это вторая строка данных с Jane.
Решение
Описание задачи
Классическая логическая задача, которая проверяет творческое мышление и умение выбирать оптимальную стратегию при ограниченных ресурсах. Нужно использовать весы только один раз, чтобы найти одну тяжелую банку среди 20.
Ключевая идея
Вместо поиска отдельной банки используем кодирование информации через количество таблеток с каждой банки. Таким образом, одно взвешивание даст нам информацию о всех банках сразу.
Алгоритм решения
Шаг 1: Подготовка
Шаг 2: Взятие таблеток
Всего возьмём: 1 + 2 + 3 + ... + 20 = 20 × 21 / 2 = 210 таблеток
Шаг 3: Взвешивание
Шаг 4: Вычисление ответа
Если бы все таблетки весили 1 грамм, общий вес был бы 210 граммов.
Решение: Проверка палиндрома
Описание задачи
Требуется реализовать функцию для определения, является ли строка палиндромом (palindrome). Палиндром — это строка, которая читается одинаково в обе стороны: как слева направо, так и справа налево. Проверка палиндромов — частая задача в алгоритмическом тестировании и валидации данных, особенно при работе с пользовательским вводом и обработкой текста.
Решение на Python
def is_palindrome(s):
"""
Проверяет, является ли строка палиндромом.
Args:
s: проверяемая строка
Returns:
True, если строка палиндром, False иначе
"""
# Очищаем строку: удаляем пробелы и приводим к нижнему регистру
cleaned = s.replace(' ', '').lower()
return cleaned == cleaned[::-1]
Альтернативные подходы
Решение
Анализ задачи
Необходимо преобразовать строку из camelCase в snake_case. Это часто встречается при работе с API, где названия полей приходят в camelCase (JavaScript/JSON), а нужно преобразовать их в snake_case (Python). Критично при автоматизации тестирования REST API.
Решение
import re
def camel_to_snake(camel_case_str: str) -> str:
"""Преобразует camelCase в snake_case."""
if not isinstance(camel_case_str, str):
raise TypeError("Входное значение должно быть строкой")
if not camel_case_str:
return ""
snake_case = re.sub(r"([a-z])([A-Z])", r"\1_\2", camel_case_str)
return snake_case.lower()
Решение
Понимание задачи
Все числа в массиве встречаются ровно два раза, кроме одного числа, которое встречается один раз. Нужно найти это единственное число.
Оптимальный подход: XOR
Используем свойство XOR:
Проходим по массиву и XOR-им все числа. Парные числа дадут 0, а единственное число останется.
Реализация
def single_number_xor(nums: list[int]) -> int:
"""Найти единственное число, используя XOR"""
result = 0
for num in nums:
result ^= num
return result
def single_number_hash(nums: list[int]) -> int:
"""Найти единственное число, используя хеш-таблицу"""
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
for num, cnt in count.items():
if cnt == 1:
return num
return 0
Решение
Понимание задачи
Проверить, что все скобки в выражении расставлены корректно. Для этого нужно:
Оптимальный алгоритм: Stack
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping:
# Закрывающая скобка
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
elif char in mapping.values():
# Открывающая скобка
stack.append(char)
# Stack должен быть пустой
return len(stack) == 0
Как это работает
Пример 1: (1 + 2) * (3 + 4)
Решение: Нахождение максимального элемента в массиве
Описание проблемы
Нужно найти наибольший элемент в массиве, не использоваихая встроенные функции типа max(). Это фундаментальная задача, проверяющая понимание итерации, сравнения и логики управления состоянием. Рассмотрю несколько подходов с разными уровнями оптимизации.
Подход 1: Простой линейный поиск
def find_maximum(arr):
"""
Находит максимум простой итерацией по всем элементам.
Args:
arr: List[int] - массив целых чисел
Returns:
int - максимальный элемент
Raises:
ValueError - если массив пуст
"""
if not arr: # Обработка пустого массива
raise ValueError("Массив не может быть пустым")
max_value = arr[0] # Инициализируем первым элементом
for i in range(1, len(arr)): # Начинаем со второго элемента
if arr[i] > max_value:
max_value = arr[i]
return max_value
Решение
Задача требует найти K-й элемент с конца в односвязном списке. Это классическая задача, которая демонстрирует работу с указателями и требует выбора между пространством и временем.
Определение структуры узла
class ListNode:
"""Класс для представления узла односвязного списка."""
def __init__(self, value: int):
self.value = value
self.next = None
Решение 1: Двухпроходный алгоритм (Оптимально)
Первый проход определяет длину списка, второй проход находит нужный элемент.
Решение: Проверка на простое число
Описание задачи
Требуется реализовать функцию для определения, является ли число простым (prime number). Простое число — это натуральное число, которое делится только на 1 и на само себя. Проверка простоты чисел — фундаментальная задача в программировании и криптографии, часто встречается в QA автоматизации при тестировании математических алгоритмов и валидации числовых данных.
Решение на Python
Решение
Анализ задачи
Необходимо извлечь каждый N-й элемент из массива. Это типичная задача на работу с индексами и срезами данных, которая часто используется в автоматизации тестирования при выборке данных из логов, ответов API или выборке тестовых случаев из больших наборов.
Решение
Создам несколько вариантов решения:
def get_every_nth_element(arr: list, n: int) -> list:
"""Возвращает каждый N-й элемент из массива."""
if n <= 0:
raise ValueError("N должно быть положительным числом")
if not arr:
return []
return arr[n - 1::n]
Решение: Спиральный обход матрицы
Это задача требует обхода матрицы по спирали: слева направо, сверху вниз, справа налево, снизу вверх, и повторения этого процесса для внутренних слоёв матрицы. Используем подход с четырьмя указателями границ.
Алгоритм решения
Визуализация
Матрица 3x3:
1 2 3
4 5 6
7 8 9
Шаг 1 - Слева направо по top: 1, 2, 3 (top--)
Шаг 2 - Сверху вниз по right: 6, 9 (right--)
Шаг 3 - Справа налево по bottom: 8, 7 (bottom--)
Шаг 4 - Снизу вверх по left: 4, 5 (left++)
Результат: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Решение: Поиск пиковых элементов
Пиковый элемент — это элемент, который больше всех своих соседей. На краях массива элементы имеют только одного соседа. Решение требует правильной обработки граничных случаев.
Определение пикового элемента
Алгоритм решения (наивный)
Реализация (простой подход)
Решение: Преобразование римского числа в целое число
Римская система счисления использует буквы для обозначения чисел. Ключевой момент — правило вычитания: когда меньшее значение стоит перед большим, оно вычитается.
Таблица значений
| Буква | Значение |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Алгоритм решения
Реализация на Python
Основные подходы к поиску дубликатов в массиве целых чисел
Задача поиска дубликатов в массиве – классическая и часто встречается на собеседованиях. Существует несколько подходов, каждый с разной эффективностью и требованиями к памяти. Основное внимание уделяется выбору алгоритма в зависимости от ограничений: можно ли использовать дополнительные структуры данных, допустима ли сортировка исходного массива, важна ли сложность по времени или памяти.
1. Использование HashSet (или словаря) – наиболее эффективный по времени подход
Этот метод использует дополнительную память для отслеживания уже встреченных элементов. Он работает за линейное время O(n) и требует O(n) дополнительной памяти (в худшем случае).
Алгоритм:
HashSet (seen).duplicates).seen.Решение
Описание задачи
Необходимо развернуть порядок слов в строке без использования встроенных коллекций (List, Array, Vector и т.д.). Это требует творческого подхода к манипулированию строками с использованием стека вызовов или встроенных строковых операций.
Подход 1: Манипулирование символами
Реализуем логику вручную, проходя по строке и выделяя слова:
def reverse_words_manual(s: str) -> str:
result = ""
current_word = ""
for i in range(len(s) - 1, -1, -1):
char = s[i]
if char == " ":
if current_word:
result += current_word[::-1] + " "
current_word = ""
else:
current_word += char
if current_word:
result += current_word[::-1]
return result.strip()
Подход 2: Двойной реверс (для Python)
def reverse_words(s: str) -> str:
return " ".join(word for word in s.split()[::-1])
Подход 3: На JavaScript
Решение
Задача требует найти все пары чисел в массиве, чья сумма равна целевому значению. Это фундаментальная задача, которая требует выбора оптимального подхода в зависимости от требований.
Решение 1: Хеш-таблица (Оптимальное для больших данных)
Используем HashSet для отслеживания уже посещённых элементов. Это позволяет находить все пары за один проход.
def find_pairs_hashmap(arr: list[int], target_sum: int) -> list[tuple[int, int]]:
"""
Находит все пары чисел с заданной суммой используя хеш-таблицу.
Args:
arr: Массив целых чисел
target_sum: Целевая сумма
Returns:
Список всех пар чисел, сумма которых равна target_sum
Time Complexity: O(n)
Space Complexity: O(n)
"""
pairs = []
seen = set()
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
Решение
Понимание задачи
Найти индексы двух чисел в массиве, сумма которых равна целевому значению. Каждый элемент используется только один раз, индексы должны отличаться.
Два подхода
1. Хеш-таблица (оптимальный)
2. Два указателя (для отсортированного массива)
Реализация
def two_sum_hash(nums: list[int], target: int) -> list[int]:
"""Найти индексы двух чисел, сумма которых равна target"""
seen = {} # {число: индекс}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return [] # Не найдено
Решение
Структура тестирования с pytest
pytest — современный фреймворк для автоматизации тестирования на Python с поддержкой fixtures и параметризации.
Реализация калькулятора
# calculator.py
class Calculator:
"""Класс калькулятора с базовыми операциями"""
def add(self, a, b):
return a + b
def subtract(self, a, b):
return a - b
def multiply(self, a, b):
return a * b
def divide(self, a, b):
if b == 0:
raise ValueError("Деление на ноль невозможно")
return a / b
Тесты на pytest
# test_calculator.py
import pytest
from calculator import Calculator
@pytest.fixture
def calculator():
"""Fixture для инициализации калькулятора"""
return Calculator()
Развернутый ответ на задачу о подсчете вхождений слов
В качестве QA Automation инженера с 10+ лет опыта, я подхожу к этой задаче не только с точки зрения написания рабочего кода, но и с учетом тестируемости, производительности, читаемости и потенциальных крайних случаев. Задача кажется простой, но в реальных проектах она часто усложняется требованиями к обработке разных языков, пунктуации, регистра и производительности на больших объемах данных.
Ключевые аспекты реализации
Базовая реализация на Python
Решение задачи на транспонирование матрицы
В контексте QA Automation, задача по транспонированию матрицы является отличным примером для проверки понимания основ программирования, работы с многомерными массивами и алгоритмического мышления. Это задание часто используется на собеседованиях для оценки способности кандидата писать чистый, эффективный и корректно работающий код.
Алгоритмический подход
Для транспонирования матрицы необходимо преобразовать строки исходной матрицы в столбцы результирующей матрицы. Если исходная матрица имеет размерность m x n (m строк, n столбцов), то транспонированная матрица будет иметь размерность n x m.
Ключевые шаги алгоритма:
result[j][i] = matrix[i][j]Реализация на Python
Решение: Первый неповторяющийся символ
Эта задача требует поиска первого символа, который встречается только один раз в строке. Решается за два прохода по строке: первый для подсчёта частоты символов, второй для поиска первого неповторяющегося.
Алгоритм решения
Реализация решения
Решение
Анализ задачи
Нужно вычислить среднее арифметическое элементов массива. Формула:
Average = (сумма всех элементов) / (количество элементов)
Задача проста на первый взгляд, но требует учитывать граничные случаи.
Решение 1: Простое вычисление
def average(arr):
if not arr:
return 0 # Или raise ValueError
total = 0
for num in arr:
total += num
return total / len(arr)
Пояснение:
Пример:
[10, 20, 30, 40, 50]
сумма = 150
количество = 5
среднее = 150 / 5 = 30.0
Решение 2: С использованием встроенных функций
def average(arr):
if not arr:
return 0
return sum(arr) / len(arr)
Более читаемо и эффективно в Python.
Решение 3: С обработкой ошибок
Решение: Selection Sort (Сортировка выбором)
Понимание алгоритма
Selection Sort работает в два этапа:
Решение 1: Классическая реализация
def selection_sort(arr: list[int]) -> list[int]:
arr_copy = arr.copy()
for i in range(len(arr_copy)):
# Найти минимальный элемент в оставшейся части
min_idx = i
for j in range(i + 1, len(arr_copy)):
if arr_copy[j] < arr_copy[min_idx]:
min_idx = j
# Поменять элементы местами
arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
return arr_copy
Time Complexity: O(n^2) Space Complexity: O(1) если сортировать in-place
Решение 2: In-place сортировка (оптимально)
Решение
Анализ требований
Форма регистрации содержит 4 основных элемента:
1. Тест-кейсы на граничные значения
Решение
Описание проблемы
Генерация всех правильных скобочных последовательностей (valid parentheses combinations) — это фундаментальная задача на использование рекурсии и backtracking. Правильная последовательность должна удовлетворять условиям:
Подход решения
Используем рекурсивный backtracking алгоритм:
Реализация на Python
Решение
Задача требует объединения двух отсортированных списков в один отсортированный результат. Это классическая задача, которая часто встречается на собеседованиях и тесно связана с алгоритмом merge из сортировки MergeSort.
Подход с двумя указателями (Two-Pointer Technique)
Оптимальное решение использует технику двух указателей с временной сложностью O(n + m), где n и m — длины списков. Идея проста: проходим оба списка одновременно, сравниваем элементы и добавляем меньший в результат.
Решение: Сортировка пузырьком
Описание задачи
Требуется реализовать алгоритм сортировки пузырьком (bubble sort) для массива целых чисел без использования встроенных методов сортировки. Сортировка пузырьком — это классический алгоритм сортировки, который многократно проходит по массиву, сравнивает соседние элементы и обменивает их местами, если они находятся в неправильном порядке. Хотя в реальной практике этот алгоритм считается неэффективным (O(n²)), он является отличным инструментом обучения и часто встречается в тестировании алгоритмов, обучении программированию и интервью.
Решение на Python
Решение: Разворот массива
Описание задачи
Требуется реализовать метод, который принимает массив целых чисел и возвращает его в полностью обратном порядке. Первый элемент становится последним, второй — предпоследним, и так далее. Данная операция часто называется разворотом массива (array reversal) и является фундаментальным алгоритмом в программировании.
Решение на Python
def reverse_array(arr):
"""
Разворачивает массив целых чисел в обратном порядке.
Args:
arr: список целых чисел
Returns:
список целых чисел в обратном порядке
"""
return arr[::-1]
Альтернативные подходы
def reverse_array(arr):
# Изменяет массив на месте и возвращает None,
# поэтому нужно вернуть копию
arr_copy = arr.copy()
arr_copy.reverse()
return arr_copy
Решение: Проверка на подпоследовательность
Подпоследовательность — это последовательность, которая может быть получена из другой последовательности путём удаления некоторых элементов без изменения порядка оставшихся элементов. Решается через двухточечный проход по строкам.
Определение подпоследовательности
Примеры:
Алгоритм (двухточечный подход)
Анализ задачи и подход к решению
Задача на валидацию строки как числа (целого или с плавающей точкой) классическая и часто встречается на собеседованиях. Она проверяет понимание конечных автоматов (Finite State Machine, FSM), умение работать с граничными случаями и писать чистый, тестируемый код.
Основная сложность — корректно обработать все возможные форматы числа без использования регулярных выражений (если это явно не разрешено) и встроенных функций преобразования строк в числа (например, parseInt, parseFloat, Number()), так как они могут некорректно обрабатывать некоторые случаи (например, parseInt("12.5") вернет 12, игнорируя .5).
Ключевые аспекты валидации
Развернутый ответ на вопрос о реализации функции для поиска НОД
Наибольший общий делитель (НОД) двух целых чисел — это наибольшее положительное целое число, которое делит оба исходных числа без остатка. Алгоритм поиска НОД является классической задачей, часто используемой в программировании для проверки понимания базовых алгоритмов и математических концепций.
Основные алгоритмы для вычисления НОД
Существует несколько эффективных алгоритмов для решения этой задачи:
Простейший способ — проверка всех чисел от меньшего из двух чисел до 1, но это крайне неэффективно для больших значений.
def gcd_naive(a: int, b: int) -> int:
smaller = min(a, b)
for divisor in range(smaller, 0, -1):
if a % divisor == 0 and b % divisor == 0:
return divisor
return 1
Решение
Понимание задачи
Необходимо связать три таблицы через JOIN для получения информации о пользователях, их заказах и продуктах в одном результирующем наборе данных.
SQL Запрос
SELECT
u.name AS user_name,
p.name AS product_name,
o.amount
FROM orders o
JOIN users u ON o.user_id = u.id
JOIN products p ON o.product_id = p.id
ORDER BY u.name, p.name;
Разбор запроса
Структура JOIN:
o.user_id = u.ido.product_id = p.idВыбор INNER JOIN:
Решение
Поиск дубликатов в базе данных — частая задача при тестировании, валидации данных и подготовке тест-кейсов. Правильно написанный SQL запрос позволяет быстро выявить проблемы с уникальностью данных.
Основной запрос
SELECT email, COUNT(*) as count
FROM employees
GROUP BY email
HAVING COUNT(*) > 1
ORDER BY count DESC;
Объяснение:
SELECT email, COUNT(*) — выбираем email и считаем количество повторенийFROM employees — из таблицы employeesGROUP BY email — группируем по email адресуHAVING COUNT(*) > 1 — фильтруем группы с дубликатамиORDER BY count DESC — сортируем по количеству повторенийРасширенный запрос
SELECT e.*
FROM employees e
WHERE e.email IN (
SELECT email
FROM employees
GROUP BY email
HAVING COUNT(*) > 1
)
ORDER BY e.email;
Показывает все записи с дублирующимися email адресами.
С оконной функцией
Решение
Анализ проблемы
Это классическая задача интервью на понимание ограничений памяти и оптимизации:
Дано:
Решение 1: Побитовое XOR
def findMissing(filename):
result = 0
# XOR всех чисел 0..2^32-1
for i in range(2**32):
result ^= i
# XOR с числами в файле
with open(filename, 'rb') as f:
while True:
chunk = f.read(4)
if not chunk:
break
num = int.from_bytes(chunk, byteorder='little')
result ^= num
return result
Почему работает: a ^ a = 0, поэтому парные элементы исчезают, остаётся непарный.
Решение 2: Математическая сумма
Решение факториала
Рекурсивный подход
def factorial_recursive(n: int) -> int: if n < 0: raise ValueError("Факториал только для неотрицательных чисел") if n == 0 or n == 1: return 1 return n * factorial_recursive(n - 1)
Итеративный подход
def factorial_iterative(n: int) -> int: if n < 0: raise ValueError("Факториал только для неотрицательных чисел") result = 1 for i in range(2, n + 1): result *= i return result
Встроенная функция
import math result = math.factorial(5) # 120
Примеры
Анализ сложности
| Подход | Время | Память | Применение |
|---|---|---|---|
| Рекурсивный | O(n) | O(n) | Элегантно, ограничен |
| Итеративный | O(n) | O(1) | Производство, надежно |
| Встроенная | O(n) | O(1) | Оптимально |
Решение
Задача требует сложить два числа без использования оператора + или арифметических операторов. Это задача, которая демонстрирует понимание битовых операций и принципов работы с числами на низком уровне.
Решение 1: Битовые операции (XOR + AND)
Основной подход — использовать XOR для суммирования битов и AND с левым сдвигом для переноса.
Решение
Задача требует найти вторую по величине зарплату из таблицы Employees. Это классическая SQL задача с несколькими подходами разной сложности и эффективности.
Решение 1: DISTINCT + ORDER BY + LIMIT (Рекомендуемое)
Простое и понятное решение, которое работает в подавляющем большинстве случаев.
SELECT MAX(salary) AS second_largest
FROM Employees
WHERE salary < (SELECT MAX(salary) FROM Employees);
Решение 2: DISTINCT с OFFSET (Альтернативное)
Использует DISTINCT для удаления дубликатов зарплат, затем сортирует и берёт вторую.
SELECT DISTINCT salary
FROM Employees
ORDER BY salary DESC
LIMIT 1 OFFSET 1;
Решение 3: Подзапрос с MAX (Оптимальное)
Находит максимальную зарплату среди всех, которые меньше чем глобальный максимум.
SELECT MAX(salary) AS second_largest_salary
FROM Employees
WHERE salary < (SELECT MAX(salary) FROM Employees);
Решение 4: Window Functions (Модерный подход)
Решение: Общие элементы двух массивов
Описание задачи
Требуется реализовать метод для поиска пересечения двух массивов (intersection of arrays). Необходимо найти все элементы, которые присутствуют в обоих массивах одновременно, и вернуть их. Эта задача часто встречается в тестировании обработки коллекций данных, сравнении наборов данных, анализе пересечений и работе с множествами. Решение требует выбора оптимального алгоритма в зависимости от размера массивов и наличия дубликатов.
Решение на Python
Решение: Проверка анаграмм
Описание задачи
Требуется реализовать функцию для определения, являются ли две строки анаграммами (anagrams) друг друга. Анаграмма — это слово или фраза, составленная из тех же букв, что и исходное слово, но в другом порядке. При проверке необходимо игнорировать регистр букв, пробелы и знаки препинания. Эта задача часто встречается в тестировании обработки текстовых данных, валидации пользовательского ввода и работе со строками в автоматизированном тестировании.
Решение на Python
Решение: Валидация email адреса
Решение 1: Регулярное выражение (Практичное)
import re
def is_valid_email_regex(email: str) -> bool:
pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
return re.match(pattern, email) is not None
Плюсы:
Минусы:
Решение 2: RFC 5322 (Более строгое)
import re
Решение
Описание структуры данных
Стек (Stack) — это абстрактный тип данных, реализующий принцип LIFO (Last In, First Out). Последний добавленный элемент — первый удаляемый.
Подход 1: Реализация на Python с использованием списка
Решение
Задача требует определить, являются ли все символы в строке уникальными, БЕЗ использования дополнительных структур данных. Это требует творческого подхода к решению задачи в условиях строгих ограничений.
Решение 1: Без дополнительных структур — Сортировка
Если буквально не использовать дополнительные структуры, можно отсортировать символы и проверить соседние элементы. Это использует встроенные функции, но не создаёт новые структуры данных явно.