Структуры данных и алгоритмы для QA инженеров

От тестировщика до Software Engineer in Test

Почему современным QA инженерам нужно знать алгоритмы и как это поможет получить работу в Apple, Google и других топовых компаниях

Вы находитесь здесь

[✓] Статья 1: Основы QA
[✓] Статья 2: Практика QA  
[→] Статья 3: DSA для QA ← Сейчас читаете
[ ] Статья 4: Фреймворки автоматизации
[ ] Статья 5: CI/CD
[ ] Статья 6: Тестирование производительности
[ ] Статья 7: Как устроиться в Apple

Прогресс: 43% ✨

Вы изучили основы тестирования и написание тест-кейсов. Однако вакансии в Apple, Google или Amazon требуют “сильный технический бэкграунд” и “опыт разработки ПО”.

Что это значит? И почему знания Postman и Selenium недостаточно?

Прежде чем погружаться, давайте разберём разницу между тестировщиком и Software Engineer in Test. Посмотрим, почему освоение структур данных и алгоритмов (DSA) может превратить вас из тестировщика в Software Engineer in Test — роль, которую ценят топовые компании.

Вот что мы рассмотрим в этом руководстве:

🎯 QA Тестировщик vs Software Engineer in Test

Традиционный QA Тестировщик

Навыки:

  • ✓ Написание тест-кейсов
  • ✓ Ручное тестирование
  • ✓ Использование Postman
  • ✓ Базовая автоматизация

Зарплата: $50K - $80K Карьерный потолок: Senior QA Тестировщик

Software Engineer in Test (SDET)

Навыки:

  • ✓ Всё вышеперечисленное +
  • ✓ Структуры данных и алгоритмы
  • ✓ Проектирование тестовых фреймворков
  • ✓ Оптимизация производительности
  • ✓ Код ревью
  • ✓ Менторство разработчиков

Зарплата: $100K - $180K (FAANG: $150K - $250K+) Карьерный потолок: Staff Engineer, Engineering Manager

SDET решают задачи как разработчики, но фокусируются на качестве.

💡 Почему DSA критически важны для современного QA

Реальная история из моего опыта

На собеседовании в топовую tech-компанию мне дали такую задачу:

“У нас есть набор из 10,000 тест-кейсов. Некоторые тесты зависят от других (например, тест B требует успешного выполнения теста A). Напишите алгоритм для определения оптимального порядка выполнения тестов.”

Без знания DSA я бы застрял на brute force решении.

Благодаря знанию DSA я быстро понял, что это задача на граф и топологическую сортировку.

Решение: Алгоритм топологической сортировки

Что такое топологическая сортировка? Представьте, что вы одеваетесь. Нельзя надеть ботинки до носков! Топологическая сортировка определяет правильный порядок, когда некоторые задачи зависят от других.

/**
 * Определяет порядок выполнения тестов с учётом зависимостей.
 * 
 * Как это работает (Алгоритм Кана):
 * 1. Находим тесты БЕЗ зависимостей (они могут выполняться первыми)
 * 2. Выполняем эти тесты, затем удаляем их из графа
 * 3. Теперь другие тесты не имеют зависимостей - выполняем их
 * 4. Повторяем пока все тесты не упорядочены
 * 
 * Если не можем упорядочить все тесты = циклическая зависимость (A нужен B, B нужен A)
 * 
 * @param {Array} tests - список ID тест-кейсов
 * @param {Object} dependencies - {test_id: [тесты которые должны выполниться первыми]}
 * @returns {Array|null} - упорядоченный список или null при циклической зависимости
 */
function getTestExecutionOrder(tests, dependencies) {
    // Граф: отображает тест -> тесты которые от него зависят
    const graph = new Map();
    // InDegree: считает сколько зависимостей у каждого теста
    const inDegree = new Map();
    
    // Инициализация: каждый тест начинает с 0 зависимостей
    tests.forEach(test => {
        graph.set(test, []);
        inDegree.set(test, 0);
    });
    
    // Строим граф: для каждой зависимости добавляем ребро и увеличиваем inDegree
    for (const [test, prereqs] of Object.entries(dependencies)) {
        for (const prereq of prereqs) {
            if (!graph.has(prereq)) graph.set(prereq, []);
            graph.get(prereq).push(test);  // prereq -> test (ребро)
            inDegree.set(test, inDegree.get(test) + 1);  // у теста ещё одна зависимость
        }
    }
    
    // Начинаем с тестов БЕЗ зависимостей (inDegree = 0)
    const queue = tests.filter(test => inDegree.get(test) === 0);
    const executionOrder = [];
    
    while (queue.length > 0) {
        // Берём тест без оставшихся зависимостей
        const current = queue.shift();
        executionOrder.push(current);
        
        // Этот тест выполнен - уменьшаем зависимости для тестов которые его ждали
        const neighbors = graph.get(current) || [];
        for (const neighbor of neighbors) {
            inDegree.set(neighbor, inDegree.get(neighbor) - 1);
            // Если у соседа теперь нет зависимостей, он может выполняться
            if (inDegree.get(neighbor) === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    // Если не упорядочили все тесты, есть цикл!
    if (executionOrder.length !== tests.length) {
        return null; // Обнаружена циклическая зависимость!
    }
    
    return executionOrder;
}

// Пример: Зависимости тестов
const tests = ['TC001', 'TC002', 'TC003', 'TC004', 'TC005'];
const dependencies = {
    'TC002': ['TC001'],          // TC002 зависит от TC001
    'TC003': ['TC001'],          // TC003 зависит от TC001
    'TC004': ['TC002', 'TC003'], // TC004 зависит от TC002 И TC003
    'TC005': ['TC004']           // TC005 зависит от TC004
};

const order = getTestExecutionOrder(tests, dependencies);
console.log(`Порядок выполнения: ${order}`);
// Вывод: ['TC001', 'TC002', 'TC003', 'TC004', 'TC005']

Это привело к офферу с зарплатой на 40% выше ожидаемой.

Где DSA реально используется в QA

1. Оптимизация покрытия тестами

Проблема: У нас 1,000 тест-кейсов, но можем запустить только 100. Как выбрать лучший набор?

Решение: Жадный алгоритм + Задача о покрытии множества

“Жадный” алгоритм делает лучший выбор на каждом шаге. Как выбирать самое спелое яблоко каждый раз!

/**
 * Выбирает минимальный набор тестов для максимального покрытия функций.
 * 
 * Жадный подход: На каждом шаге выбираем тест, который покрывает
 * больше всего НОВЫХ функций, которые мы ещё не покрыли.
 * 
 * @param {Array} testCases - список ID тест-кейсов
 * @param {number} maxTests - максимальное количество тестов для запуска
 * @param {Object} featureCoverage - {test_id: Set(покрытые_функции)}
 */
function optimizeTestCoverage(testCases, maxTests, featureCoverage) {
    const selectedTests = [];          // Выбранные тесты
    const coveredFeatures = new Set(); // Уже покрытые функции
    const remainingTests = [...testCases]; // Ещё не выбранные тесты
    
    while (selectedTests.length < maxTests && remainingTests.length > 0) {
        // Жадный выбор: Находим тест покрывающий больше всего НОВЫХ функций
        let bestTest = null;
        let bestNewCoverage = 0;
        
        // Проверяем каждый оставшийся тест
        for (const test of remainingTests) {
            const testFeatures = featureCoverage[test];
            // Считаем функции которые этот тест покрывает и которых у нас ЕЩЁ нет
            const newFeatures = [...testFeatures].filter(f => !coveredFeatures.has(f));
            const newCoverage = newFeatures.length;
            
            // Этот тест лучше нашего текущего лучшего?
            if (newCoverage > bestNewCoverage) {
                bestNewCoverage = newCoverage;
                bestTest = test;
            }
        }
        
        // Если ни один тест не добавляет покрытия, останавливаемся
        if (bestNewCoverage === 0) break;
        
        // Добавляем лучший тест в нашу выборку
        selectedTests.push(bestTest);
        // Отмечаем его функции как покрытые
        featureCoverage[bestTest].forEach(f => coveredFeatures.add(f));
        // Удаляем из оставшихся тестов
        remainingTests.splice(remainingTests.indexOf(bestTest), 1);
    }
    
    return { selectedTests, coveredFeatures };
}

// Пример: 5 тестов, но можем запустить только 3
const testCases = ['TC001', 'TC002', 'TC003', 'TC004', 'TC005'];
const featureCoverage = {
    'TC001': new Set(['login', 'auth', 'session']),     // 3 функции
    'TC002': new Set(['login', 'logout']),              // 2 функции (1 пересечение)
    'TC003': new Set(['profile', 'edit']),              // 2 новые функции
    'TC004': new Set(['payment', 'checkout', 'auth']),  // 3 функции (1 пересечение)
    'TC005': new Set(['payment', 'refund'])             // 2 функции (1 пересечение)
};

const result = optimizeTestCoverage(testCases, 3, featureCoverage);
console.log(`Выбранные тесты: ${result.selectedTests}`);
console.log(`Покрытие: ${[...result.coveredFeatures]}`);
// Результат: С только 3 тестами покрываем 8 из 9 функций!

Это сократило время регрессионного тестирования на 90% при сохранении 89% покрытия.

2. Поиск дубликатов тест-кейсов

Проблема: У нас 5000 тест-кейсов. Как найти дубликаты?

Базовое решение O(n²), сравнивающее каждый тест со всеми другими — процесс занимающий часы.

Хеш-таблица сокращает это до O(n), занимая секунды!

Почему O(n²) медленно?

  • 5000 тестов × 5000 сравнений = 25,000,000 операций!

Почему O(n) быстро?

  • 5000 тестов × 1 поиск в хеше = 5,000 операций!
const crypto = require('crypto');

class TestCase {
    constructor(id, steps, expectedResult, testData) {
        this.id = id;
        this.steps = steps;
        this.expectedResult = expectedResult;
        this.testData = testData;
    }
}

/**
 * Находит дубликаты тест-кейсов за O(n) время.
 * @param {Array<TestCase>} testSuite - массив тест-кейсов
 * @returns {Object} - объект с дубликатами
 */
function findDuplicateTests(testSuite) {
    const testSignatures = new Map();
    
    for (const test of testSuite) {
        // Создаём уникальную сигнатуру для теста
        const signatureData = `${test.steps}|${test.expectedResult}|${test.testData}`;
        const signature = crypto.createHash('md5').update(signatureData).digest('hex');
        
        if (!testSignatures.has(signature)) {
            testSignatures.set(signature, []);
        }
        testSignatures.get(signature).push(test.id);
    }
    
    // Находим дубликаты
    const duplicates = {};
    for (const [signature, ids] of testSignatures.entries()) {
        if (ids.length > 1) {
            duplicates[signature] = ids;
        }
    }
    
    return duplicates;
}

// Пример
const testSuite = [
    new TestCase("TC001", "Логин с валидными данными", "Успех", "user@test.com"),
    new TestCase("TC002", "Логин с валидными данными", "Успех", "user@test.com"), // Дубликат!
    new TestCase("TC003", "Логин с невалидными данными", "Ошибка", "wrong@test.com"),
];

const duplicates = findDuplicateTests(testSuite);
for (const [sig, ids] of Object.entries(duplicates)) {
    console.log(`Найдены дубликаты: ${ids}`);
}
// Вывод: Найдены дубликаты: TC001,TC002

3. Тестирование UI навигации (BFS)

Задача: Проверить, что все страницы доступны за 3 клика с главной страницы.

Решение: Поиск в ширину (BFS)

/**
 * Проверяет доступность всех страниц за maxClicks кликов.
 * @param {string} startPage - начальная страница
 * @param {number} maxClicks - максимальное количество кликов
 * @returns {Object} - результаты с доступными и недоступными страницами
 */
function testNavigationDepth(startPage, maxClicks = 3) {
    const visited = new Map([[startPage, 0]]);
    const queue = [[startPage, 0]];
    
    while (queue.length > 0) {
        const [currentPage, depth] = queue.shift();
        
        if (depth >= maxClicks) continue;
        
        // Получаем все ссылки на текущей странице
        const links = getLinksOnPage(currentPage);
        
        for (const link of links) {
            if (!visited.has(link)) {
                visited.set(link, depth + 1);
                queue.push([link, depth + 1]);
            }
        }
    }
    
    // Находим недоступные страницы
    const allPages = getAllSitePages();
    const unreachable = allPages.filter(page => !visited.has(page));
    const maxDepth = Math.max(...visited.values());
    
    return {
        reachable: Object.fromEntries(visited),
        unreachable,
        maxDepth
    };
}

// Мок-функции для примера
function getLinksOnPage(page) {
    const links = {
        '/home': ['/products', '/about', '/contact'],
        '/products': ['/product/1', '/product/2'],
        '/about': ['/team', '/history'],
        '/contact': []
    };
    return links[page] || [];
}

function getAllSitePages() {
    return ['/home', '/products', '/about', '/contact', 
            '/product/1', '/product/2', '/team', '/history'];
}

// Результат теста
const result = testNavigationDepth('/home');
if (result.unreachable.length > 0) {
    console.log(`❌ FAIL: Страницы недоступны за 3 клика: ${result.unreachable}`);
} else {
    console.log(`✅ PASS: Все страницы доступны. Макс. глубина: ${result.maxDepth}`);
}

Основные структуры данных для QA

1. Массивы и списки

Когда использовать:

  • Хранение списка тест-кейсов
  • Результаты тестов
  • Наборы тестовых данных
class TestSuite {
    constructor() {
        this.tests = [];  // Массив
        this.results = [];
    }
    
    /**
     * O(1) - добавление в конец
     */
    addTest(test) {
        this.tests.push(test);
    }
    
    /**
     * O(n) - итерация по всем тестам
     */
    runAllTests() {
        for (const test of this.tests) {
            const result = test.execute();
            this.results.push(result);
        }
    }
    
    /**
     * O(n) - фильтрация
     */
    getFailedTests() {
        return this.results.filter(r => r.status === 'FAILED');
    }
    
    /**
     * O(1) - доступ по индексу
     */
    getTestByIndex(index) {
        return this.tests[index];
    }
    
    /**
     * O(n) - поиск по ID
     */
    findTestById(id) {
        return this.tests.find(test => test.id === id);
    }
}

// Ключевые операции:
// - Поиск: O(n)
// - Доступ: O(1)
// - Вставка в конец: O(1)
// - Удаление: O(n)

Задачи LeetCode для практики:

  • Easy: Two Sum, Best Time to Buy and Sell Stock
  • Medium: Product of Array Except Self, Container With Most Water

2. Хеш-таблицы (Map/Object)

Когда использовать:

  • Быстрый поиск теста по ID
  • Кэширование результатов
  • Подсчёт частоты багов
class TestRegistry {
    constructor() {
        this.tests = new Map();  // Хеш-таблица
        this.executionCount = new Map();
        this.bugFrequency = new Map();
    }
    
    /**
     * O(1) - добавление
     */
    registerTest(testId, test) {
        this.tests.set(testId, test);
    }
    
    /**
     * O(1) - поиск
     */
    getTest(testId) {
        return this.tests.get(testId);
    }
    
    /**
     * Отслеживание частоты багов по модулю - O(1)
     */
    trackBug(module) {
        const current = this.bugFrequency.get(module) || 0;
        this.bugFrequency.set(module, current + 1);
    }
    
    /**
     * Поиск модулей с высоким количеством багов - O(n)
     */
    getProblematicModules(threshold = 5) {
        const problematic = {};
        for (const [module, count] of this.bugFrequency.entries()) {
            if (count >= threshold) {
                problematic[module] = count;
            }
        }
        return problematic;
    }
}

// Пример использования
const registry = new TestRegistry();
registry.registerTest("TC001", new LoginTest());
registry.registerTest("TC002", new PaymentTest());

// Быстрый поиск - O(1)!
const test = registry.getTest("TC001");

// Отслеживание багов
registry.trackBug("payment");
registry.trackBug("payment");
registry.trackBug("payment");
registry.trackBug("login");

const problematic = registry.getProblematicModules(2);
console.log(`Проблемные модули:`, problematic);
// Вывод: { payment: 3 }

Почему хеш-таблицы важны для QA:

  • Поиск теста среди 10,000 теперь занимает микросекунды вместо секунд.
  • Для анализа багов можно мгновенно определить какие модули имеют больше проблем.

Задачи LeetCode:

  • Easy: Two Sum (классика!), Valid Anagram
  • Medium: Group Anagrams, Top K Frequent Elements

3. Стеки и очереди

Стек (Last In, First Out) полезен для тестирования кнопки “Назад” в браузере.

Думайте о стеке как о стопке тарелок - можно взять только верхнюю тарелку первой!

class BrowserHistory {
    /**
     * Тестирование функциональности "Назад" в браузере
     * 
     * Как работает стек:
     * - Вы посещаете страницу A, затем B, затем C
     * - Стек теперь: [A, B, C] (C наверху)
     * - Нажимаете "Назад": C удаляется, видите B
     * - Стек теперь: [A, B]
     */
    constructor() {
        this.history = [];      // Стек - хранит посещённые страницы
        this.forwardStack = []; // Стек - хранит страницы для "Вперёд"
    }
    
    /**
     * Посещение новой страницы - добавляет наверх стека
     */
    visit(url) {
        this.history.push(url);         // Добавляем наверх стека
        this.forwardStack = [];         // Очищаем вперёд (как настоящий браузер)
    }
    
    /**
     * Кнопка "Назад" - удаляет текущую страницу, показывает предыдущую
     */
    back() {
        if (this.history.length > 1) {
            const current = this.history.pop();     // Удаляем верхнюю страницу
            this.forwardStack.push(current);        // Сохраняем для Вперёд
            return this.history[this.history.length - 1]; // Возвращаем новую верхнюю
        }
        return null;  // Нельзя вернуться с первой страницы
    }
    
    /**
     * Кнопка "Вперёд" - возвращаемся на страницу которую покинули
     */
    forward() {
        if (this.forwardStack.length > 0) {
            const url = this.forwardStack.pop();    // Берём страницу из стека Вперёд
            this.history.push(url);                 // Возвращаем в историю
            return url;
        }
        return null;  // Некуда идти вперёд
    }
}

// Тестируем историю браузера
const browser = new BrowserHistory();
browser.visit("google.com");    // history: [google]
browser.visit("youtube.com");   // history: [google, youtube]
browser.visit("github.com");    // history: [google, youtube, github]

console.assert(browser.back() === "youtube.com");   // назад к youtube
console.assert(browser.back() === "google.com");    // назад к google
console.assert(browser.forward() === "youtube.com"); // вперёд к youtube
console.log("✅ История браузера работает!");

Очередь - First In, First Out

Очередь как очередь в магазине - первый пришёл, первый обслужен!

class TestExecutionQueue {
    /**
     * FIFO (First In, First Out) очередь для выполнения тестов
     * 
     * Как работает очередь:
     * - Тесты добавляются в конец очереди
     * - Тесты берутся с начала очереди
     * - Первый добавленный тест = первый выполняемый
     */
    constructor() {
        this.queue = [];          // Обычные тесты ждут здесь
        this.priorityQueue = [];  // Критические тесты имеют приоритет
    }
    
    /**
     * Добавить тест в очередь
     * @param {Object} test - тест для добавления
     * @param {boolean} priority - true = выполнить перед обычными тестами
     */
    addTest(test, priority = false) {
        if (priority) {
            this.priorityQueue.push(test);  // Добавляем в приоритетную очередь
        } else {
            this.queue.push(test);          // Добавляем в обычную очередь
        }
    }
    
    /**
     * Получить следующий тест для выполнения
     * Приоритетные тесты идут первыми, затем обычные
     */
    getNextTest() {
        // Всегда сначала проверяем приоритетную очередь
        if (this.priorityQueue.length > 0) {
            return this.priorityQueue.shift();  // Удаляем с начала (FIFO)
        } else if (this.queue.length > 0) {
            return this.queue.shift();          // Удаляем с начала (FIFO)
        }
        return null;  // Тестов не осталось
    }
    
    /**
     * Сколько тестов ожидает?
     */
    size() {
        return this.priorityQueue.length + this.queue.length;
    }
}

// Пример использования
const executor = new TestExecutionQueue();
executor.addTest(new SmokeTest());            // Добавлен первым, выполняется вторым
executor.addTest(new RegressionTest());       // Добавлен вторым, выполняется третьим
executor.addTest(new CriticalBugTest(), true); // Приоритет! Выполняется первым!

// Порядок выполнения: CriticalBugTest → SmokeTest → RegressionTest
while (executor.size() > 0) {
    const test = executor.getNextTest();
    test.run();
}

Задачи LeetCode:

  • Easy: Valid Parentheses (Стек), Implement a Queue using Stacks
  • Medium: Min Stack, Design Circular Queue

4. Деревья и графы

Структура дерева - DOM и файловые системы

Дерево как генеалогическое древо - один родитель, много детей. Каждый узел может иметь дочерние узлы.

Используется для: HTML DOM, файловых систем, организационных схем.

class DOMNode {
    /**
     * Представление элемента DOM (HTML тег)
     * 
     * Что такое дерево?
     * - Дерево имеет "корневой" узел наверху
     * - Каждый узел может иметь дочерние узлы
     * - Дети могут иметь своих детей
     * 
     * Пример: HTML структура
     *          <html>
     *         /      \
     *     <body>    <head>
     *       |
     *     <div>
     *    /    \
     * <p>    <button>
     */
    constructor(tag, id = null, text = null) {
        this.tag = tag;         // например, "div", "button"
        this.id = id;
        this.text = text;
        this.children = [];
    }
    
    addChild(child) {
        this.children.push(child);
    }
    
    /**
     * DFS поиск элемента по ID
     * Поиск в глубину: Начинаем с корня, идём вглубь первой ветки
     */
    findById(targetId) {
        // Проверяем совпадает ли текущий узел
        if (this.id === targetId) {
            return this;
        }
        
        // Ищем во всех детях рекурсивно
        for (const child of this.children) {
            const result = child.findById(targetId);
            if (result) return result;  // Нашли!
        }
        
        // Не найдено в этой ветке
        return null;
    }
    
    /**
     * Собрать весь текст из дерева
     * Рекурсивно собираем текст из всех узлов
     */
    getAllText() {
        // Начинаем с текста текущего узла (если есть)
        const texts = this.text ? [this.text] : [];
        
        // Добавляем текст из всех детей рекурсивно
        for (const child of this.children) {
            texts.push(...child.getAllText());
        }
        
        return texts;
    }
    
    /**
     * Валидация структуры DOM
     * Проверка частых ошибок в DOM
     */
    validateStructure() {
        const errors = [];
        
        // Правило 1: Кнопки должны иметь текст
        if (this.tag === 'button' && !this.text) {
            errors.push(`Кнопка без текста: id=${this.id}`);
        }
        
        // Правило 2: Нельзя вкладывать кнопки в кнопки
        if (this.tag === 'button') {
            for (const child of this.children) {
                if (child.tag === 'button') {
                    errors.push(`Кнопка внутри кнопки: id=${this.id}`);
                }
            }
        }
        
        // Рекурсивно проверяем всех детей
        for (const child of this.children) {
            errors.push(...child.validateStructure());
        }
        
        return errors;
    }
}

// Создаём DOM
const html = new DOMNode('html');
const body = new DOMNode('body');
const div = new DOMNode('div', 'container');
const button = new DOMNode('button', 'submit-btn', 'Отправить');

html.addChild(body);
body.addChild(div);
div.addChild(button);

// Тестирование
const found = html.findById('submit-btn');
console.assert(found !== null);
console.assert(found.text === 'Отправить');

const errors = html.validateStructure();
if (errors.length > 0) {
    console.log(`❌ Валидация DOM не пройдена: ${errors}`);
} else {
    console.log("✅ Структура DOM валидна");
}

Структура графа - Зависимости модулей

Граф полезен для моделирования зависимостей модулей.

class ModuleDependencyGraph {
    /**
     * Граф зависимостей модулей для интеграционного тестирования
     */
    constructor() {
        this.graph = new Map();
    }
    
    /**
     * Модуль зависит от другого модуля
     */
    addDependency(module, dependsOn) {
        if (!this.graph.has(module)) {
            this.graph.set(module, []);
        }
        this.graph.get(module).push(dependsOn);
    }
    
    /**
     * Проверка циклических зависимостей (DFS)
     * Циклическая зависимость означает: A зависит от B, B зависит от C, C зависит от A
     * Это плохо - код даже не загрузится!
     */
    hasCircularDependency() {
        const visited = new Set();      // Уже проверенные узлы
        const recStack = new Set();     // Узлы в текущем пути
        
        // Вспомогательная функция для DFS
        const dfs = (node) => {
            visited.add(node);          // Отмечаем как обрабатываемый
            recStack.add(node);         // Добавляем в текущий путь
            
            // Проверяем все зависимости этого узла
            const neighbors = this.graph.get(node) || [];
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    // Ещё не посещён, исследуем
                    if (dfs(neighbor)) return true;  // Найден цикл!
                } else if (recStack.has(neighbor)) {
                    // Нашли узел в текущем пути = ЦИКЛ!
                    return true;
                }
            }
            
            // Закончили с этим путём
            recStack.delete(node);
            return false;
        };
        
        // Пробуем DFS от каждого узла
        for (const node of this.graph.keys()) {
            if (!visited.has(node)) {
                if (dfs(node)) return true;  // Найден цикл
            }
        }
        
        return false;  // Циклов нет - всё хорошо!
    }
}

// Пример использования
const deps = new ModuleDependencyGraph();
deps.addDependency('PaymentModule', 'AuthModule');
deps.addDependency('CheckoutModule', 'PaymentModule');
deps.addDependency('CheckoutModule', 'CartModule');

if (deps.hasCircularDependency()) {
    console.log("❌ ОШИБКА: Обнаружена циклическая зависимость!");
} else {
    console.log("✅ Циклических зависимостей нет");
}

Задачи LeetCode:

  • Easy: Maximum Depth of Binary Tree, Same Tree
  • Medium: Binary Tree Level Order Traversal, Course Schedule (Граф!)

Алгоритмы которые должен знать каждый SDET

1. Сортировка и поиск

/**
 * Сортировка тестов по частоте падений (по убыванию).
 * Тесты падающие чаще = выше приоритет исправления
 */
function prioritizeTestsByFailureRate(tests, history) {
    const getFailureRate = (test) => {
        const { total_runs, failures } = history[test.id];
        // Вычисляем: падения / всего_запусков = частота падений
        return total_runs > 0 ? failures / total_runs : 0;
    };
    
    // Сортируем по частоте падений (сначала наибольшие)
    // Временная сложность O(n log n)
    return tests.sort((a, b) => getFailureRate(b) - getFailureRate(a));
}

/**
 * Бинарный поиск записи в отсортированных логах
 * Намного быстрее чем проверка каждой записи: O(log n) вместо O(n)!
 */
function binarySearchLogEntry(logs, timestamp) {
    let left = 0;                      // Начало диапазона поиска
    let right = logs.length - 1;       // Конец диапазона поиска
    
    while (left <= right) {
        // Выбираем середину
        const mid = Math.floor((left + right) / 2);
        
        if (logs[mid].timestamp === timestamp) {
            return logs[mid];          // Нашли!
        } else if (logs[mid].timestamp < timestamp) {
            left = mid + 1;            // Ищем в правой половине
        } else {
            right = mid - 1;           // Ищем в левой половине
        }
    }
    
    return null;  // Не найдено
}

// Пример
const logs = [
    { timestamp: 100, message: "Тест начался" },
    { timestamp: 150, message: "Вызов API" },
    { timestamp: 200, message: "Произошла ошибка" },
    { timestamp: 300, message: "Тест завершён" },
];

const errorLog = binarySearchLogEntry(logs, 200);
console.log(errorLog);  // Найдено за O(log n)!

2. Техника двух указателей

Основная идея: Используем два указателя для эффективного обхода данных вместо вложенных циклов.

/**
 * Сравнение двух отсортированных списков результатов тестов
 * Находим: пропущенные тесты, лишние тесты, за O(n+m) время
 * 
 * ПОЧЕМУ два указателя?
 * - Наивный способ: Проверять каждый ожидаемый со всеми фактическими = O(n*m) вложенные циклы (МЕДЛЕННО!)
 * - Два указателя: Каждый элемент посещается один раз = O(n+m) один проход (БЫСТРО!)
 * 
 * КАК это работает:
 * - Оба списка отсортированы
 * - Указатель i в ожидаемых, указатель j в фактических
 * - Двигаем указатели вперёд вместе умно
 * - Никогда не возвращаемся! (Это делает O(n+m) а не O(n²))
 * 
 * @param {Array} expected - отсортированные ID тестов которые должны выполниться
 * @param {Array} actual - отсортированные ID тестов которые реально выполнились
 */
function compareTestResults(expected, actual) {
    let i = 0, j = 0;     // Указатель i для ожидаемых, указатель j для фактических
    const differences = [];
    
    // Основной цикл: Сравниваем элементы на текущих указателях
    while (i < expected.length && j < actual.length) {
        if (expected[i] === actual[j]) {
            // Одинаковый тест в обоих - двигаем ОБА указателя
            // Ни в одном списке нет разницы здесь
            i++;
            j++;
        } else if (expected[i] < actual[j]) {
            // ожидаемый имеет меньшее значение
            // Этот тест ПРОПУЩЕН в фактических результатах
            // Двигаем i чтобы проверить следующий ожидаемый тест
            differences.push(`Пропущен в фактических: ${expected[i]}`);
            i++;
        } else {
            // фактический имеет меньшее значение
            // Этот тест ЛИШНИЙ в фактических результатах (неожиданный)
            // Двигаем j чтобы проверить следующий фактический тест
            differences.push(`Лишний в фактических: ${actual[j]}`);
            j++;
        }
    }
    
    // Обрабатываем оставшиеся элементы (один список исчерпан, другой нет)
    // Всё что осталось в ожидаемых = пропущено в фактических
    while (i < expected.length) {
        differences.push(`Пропущен в фактических: ${expected[i]}`);
        i++;
    }
    
    // Всё что осталось в фактических = лишнее (неожиданное)
    while (j < actual.length) {
        differences.push(`Лишний в фактических: ${actual[j]}`);
        j++;
    }
    
    return differences;
}

// Пример: Два отсортированных списка результатов тестов
const expected = [1, 2, 3, 5, 6];    // Что ДОЛЖНО было выполниться
const actual = [1, 2, 4, 5];         // Что РЕАЛЬНО выполнилось
const diffs = compareTestResults(expected, actual);

diffs.forEach(diff => console.log(diff));
// Вывод:
// Пропущен в фактических: 3
// Лишний в фактических: 4
// Пропущен в фактических: 6

// Анализ:
// - Тест 3 был пропущен (должен был выполниться но не выполнился)
// - Тест 4 выполнился неожиданно (не должен был выполняться)
// - Тест 6 был пропущен
// Почему O(n+m) быстро: каждое число посещается ровно один раз

3. Скользящее окно

Основная идея: “Окно” - это диапазон фиксированного размера. Мы скользим им по данным как движущимся фильтром для поиска паттернов.

/**
 * Анализ времени ответа в скользящем окне
 * 
 * Представьте так:
 * - У вас есть 1 час логов API запросов
 * - Каждые 5 секунд проверяете: "Были ли запросы медленными за последние 60 секунд?"
 * - Вы СКОЛЬЗИТЕ этим 60-секундным окном вперёд, проверяя каждую позицию
 * 
 * Почему скользящее окно?
 * - Один проход по данным = O(n) время (очень быстро!)
 * - Без него, проверка каждого возможного 60-сек диапазона = O(n²) (очень медленно!)
 * 
 * @param {Array} responseTimes - [{timestamp: мс, duration: мс}, ...]
 * @param {number} windowSizeSeconds - ширина окна (например, 60 секунд)
 */
function analyzeResponseTimes(responseTimes, windowSizeSeconds = 60) {
    const issues = [];
    let windowStart = 0;  // Указатель ЛЕВОГО края окна
    
    // Указатель windowEnd: двигается ВПРАВО
    for (let windowEnd = 0; windowEnd < responseTimes.length; windowEnd++) {
        // Держим размер окна фиксированным:
        // Если окно слишком широкое (новое время - старое время > 60 секунд)
        // сжимаем слева двигая windowStart вправо
        while (responseTimes[windowEnd].timestamp - 
               responseTimes[windowStart].timestamp > windowSizeSeconds) {
            windowStart++;  // Отбрасываем старейший элемент, держим окно свежим
        }
        
        // Теперь у нас валидное окно: responseTimes[windowStart ... windowEnd]
        const windowTimes = responseTimes
            .slice(windowStart, windowEnd + 1)
            .map(rt => rt.duration);
        
        // Вычисляем среднее: сумма всех / количество = среднее
        const avgTime = windowTimes.reduce((a, b) => a + b, 0) / windowTimes.length;
        
        // Среднее > 2 секунд? Это медленно! Записываем этот проблемный период
        if (avgTime > 2000) {  
            issues.push({
                timeRange: [
                    responseTimes[windowStart].timestamp,
                    responseTimes[windowEnd].timestamp
                ],
                avgResponseTime: avgTime,
                requestsCount: windowTimes.length
            });
        }
    }
    
    return issues;
}

// Временная сложность: O(n) - каждый элемент посещается максимум 2 раза
// Пространственная сложность: O(k) - k = количество найденных проблемных периодов

4. Динамическое программирование

Основная идея: Разбиваем большую задачу на меньшие части. Решаем каждую часть один раз. Комбинируем части в финальный ответ.

Задача: У вас 15 минут на запуск тестов. Каждый тест занимает время и имеет оценку важности. Выберите тесты чтобы максимизировать важность.

/**
 * Задача о рюкзаке 0/1 с использованием динамического программирования
 * 
 * Большая идея:
 * - Это как задача о рюкзаке
 * - Вместимость рюкзака = временной бюджет (15 минут)
 * - Каждый тест = предмет с весом (время выполнения) + ценностью (важность)
 * - Цель = максимизировать ценность не превышая вместимость
 * 
 * Почему динамическое программирование?
 * - Полный перебор: Попробовать все 2^n комбинаций (n=10 тестов = 1024 попытки = МЕДЛЕННО)
 * - DP: Строим таблицу оптимальных выборов, переиспользуем результаты (10 тестов = 150 ячеек = БЫСТРО)
 * 
 * КЛЮЧЕВОЕ ПОНИМАНИЕ - DP Таблица dp[i][t]:
 * - i = "рассматривая первые i тестов"
 * - t = "с t минутами доступными"
 * - dp[i][t] = максимальная достижимая важность
 * 
 * Пример: dp[3][15] означает:
 * "Если я смотрю только на первые 3 теста и имею 15 минут,
 *  какой лучший счёт важности я могу получить?"
 * 
 * @param {Array} tests - [[имяТеста, времяВыполнения, важность], ...]
 * @param {number} timeBudget - всего доступных минут
 */
function selectTestsWithBudget(tests, timeBudget) {
    const n = tests.length;
    
    // Создаём DP таблицу: (n+1) строк × (timeBudget+1) столбцов
    // Все ячейки начинаются с 0 (нет выбранных тестов = 0 важности)
    const dp = Array(n + 1).fill(null)
        .map(() => Array(timeBudget + 1).fill(0));
    
    // Заполняем таблицу строка за строкой (каждая строка = ещё один тест для рассмотрения)
    for (let i = 1; i <= n; i++) {
        const [testName, time, importance] = tests[i - 1];
        
        // Для каждого возможного временного бюджета (от 0 до timeBudget)
        for (let t = 0; t <= timeBudget; t++) {
            // Решение 1: Не включаем этот тест
            // Используем лучшую важность от предыдущих тестов с тем же временным бюджетом
            dp[i][t] = dp[i - 1][t];
            
            // Решение 2: Включаем этот тест (если время позволяет)
            // Этот тест использует 'time' минут, оставляя (t - time) минут
            // Лучшая важность с оставшимся временем = dp[i-1][t-time]
            // Плюс важность этого теста
            if (time <= t) {
                const importanceIfIncluded = dp[i - 1][t - time] + importance;
                // Выбираем что лучше: включить или не включить
                dp[i][t] = Math.max(dp[i][t], importanceIfIncluded);
            }
        }
    }
    
    // РЕКОНСТРУКЦИЯ: Отслеживаем назад чтобы найти какие тесты были реально выбраны
    // Начинаем с dp[n][timeBudget] (ответ на полную задачу)
    // Идём назад чтобы понять какие выборы привели сюда
    const selected = [];
    let t = timeBudget;
    
    for (let i = n; i > 0; i--) {
        // Включили ли мы тест[i]?
        // Если dp[i][t] !== dp[i-1][t], то значение ИЗМЕНИЛОСЬ
        // Значение меняется только если мы включили этот тест!
        if (dp[i][t] !== dp[i - 1][t]) {
            // Да! Этот тест был включён в оптимальное решение
            selected.push(tests[i - 1]);
            // Используем время этого теста: t -= времяТеста
            t -= tests[i - 1][1];
        }
        // Если равны, этот тест НЕ был включён, продолжаем назад
    }
    
    return { 
        selected, 
        totalImportance: dp[n][timeBudget],
        timeUsed: timeBudget - t
    };
}

// ПРИМЕР:
const tests = [
    ['LoginTest',    5, 10],      // 5 мин выполнения, важность 10
    ['PaymentTest', 10, 20],      // 10 мин выполнения, важность 20
    ['CheckoutTest', 8, 15],      // 8 мин выполнения, важность 15
    ['SearchTest',   3,  8],      // 3 мин выполнения, важность 8
];

const result = selectTestsWithBudget(tests, 15);
console.log('Выбранные тесты:', result.selected);
console.log('Общая важность:', result.totalImportance);
console.log('Использовано времени:', result.timeUsed, 'минут');

LeetCode для QA: Практический план

Почему QA должен решать LeetCode?

  1. Технические собеседования в Apple, Google и Amazon включают вопросы по DSA.
  2. Это развивает алгоритмическое мышление, что делает вас лучшим тестировщиком.
  3. Вы сможете замечать неэффективный код на код ревью.

Топ-20 задач для QA инженеров

Easy уровень (начните здесь):

  1. Two Sum - Основы хеш-таблиц
  2. Valid Parentheses - Применение стека
  3. Merge Two Sorted Lists - Техника указателей
  4. Maximum Depth of Binary Tree - Обход дерева
  5. Best Time to Buy and Sell Stock - Итерация массива
  6. Valid Anagram - Хеш-таблица для сравнения
  7. Palindrome Linked List - Два указателя
  8. Contains Duplicate - Использование Set
  9. Reverse Linked List - Манипуляция указателями
  10. Climbing Stairs - Базовое DP

Medium уровень (когда освоите Easy):

  1. Group Anagrams - Продвинутая хеш-таблица
  2. Top K Frequent Elements - Куча/Очередь с приоритетом
  3. Course Schedule - Граф + Топологическая сортировка (важно!)
  4. Product of Array Except Self - Манипуляция массивом
  5. Longest Substring Without Repeating Characters - Скользящее окно
  6. 3Sum - Два указателя
  7. Binary Tree Level Order Traversal - BFS
  8. Implement Trie - Структура дерева
  9. Word Search - Backtracking
  10. LRU Cache - Хеш-таблица + Двусвязный список

8-недельный план практики

Недели 1-2: Массивы и хеш-таблицы

  • Дни 1-3: Изучение концепций
  • Дни 4-7: Easy задачи (2-3 в день)
  • Дни 8-14: Medium задачи (1 в день)

Недели 3-4: Связные списки, стеки и очереди

  • Понедельник-Среда: Теория
  • Четверг-Воскресенье: Практика

Недели 5-6: Деревья и графы

  • Самый важный раздел для QA!
  • Уделите больше времени

Недели 7-8: Динамическое программирование и алгоритмы

  • Сортировка, поиск
  • Два указателя, скользящее окно
  • Базовое DP

Как эффективно решать задачи

Методология:

  1. Прочитайте задачу дважды
  2. Нарисуйте пример на бумаге
  3. Подумайте о подходе (5-10 минут)
  4. Начните с brute force решения
  5. Оптимизируйте
  6. Напишите код
  7. Протестируйте на граничных случаях

Шаблон решения:

/**
 * ШАБЛОН для решения задач LeetCode
 * Используйте эту структуру для каждой решаемой задачи
 * 
 * Это помогает:
 * - Ясно думать о подходе
 * - Документировать решение
 * - Систематически тестировать граничные случаи
 */
function solveProblem(inputData) {
    /**
     * Задача: [Описание задачи]
     * 
     * Подход: [Ваш подход]
     * Временная сложность: O(?)
     * Пространственная сложность: O(?)
     * 
     * Примеры:
     * Вход: [...]
     * Выход: [...]
     */
    
    // Граничные случаи: Обработка пустого, null, одного элемента
    if (!inputData) {
        return null;
    }
    
    // Основная логика здесь
    // ...
    
    return result;
}

// Тест-кейсы: Всегда проверяйте что решение работает!
console.assert(solveProblem([1,2,3]) === expectedOutput, "Тест 1 не пройден");
console.assert(solveProblem([]) === null, "Тест пустого массива не пройден");
console.assert(solveProblem([1]) === expectedOutput, "Тест одного элемента не пройден");

Ресурсы для обучения

📺 YouTube каналы (БЕСПЛАТНО!)

На русском:

  1. Тимофей Хирьянов - Алгоритмы и структуры данных

    • Лекции МФТИ
    • Очень подробно с примерами
    • YouTube плейлист

  2. CS Center - Алгоритмы

    • Академический подход

На английском:

  1. NeetCode ⭐⭐⭐⭐⭐

    • Лучший канал для LeetCode!
    • Понятные объяснения
    • Визуализация алгоритмов
    • NeetCode.io

  2. FreeCodeCamp - Data Structures Full Course

    • 8+ часов бесплатного контента
    • От новичка до профи

  3. Fireship - короткие, лаконичные видео

💻 Платформы для практики

  1. LeetCode

    • 🌟 Основная платформа
    • Бесплатный план: 50+ бесплатных задач
    • Premium ($35/месяц): Вопросы по компаниям, видео решения

  2. HackerRank

    • Хорошо для начинающих
    • БЕСПЛАТНО!

  3. CodeSignal

    • Реальные задачи с собеседований

📚 Книги

  1. “Grokking Algorithms” - Aditya Bhargava

    • ⭐⭐⭐⭐⭐ Лучшая для начинающих!
    • Визуальный подход
    • Простой язык

  2. “Cracking the Coding Interview” - Gayle McDowell

    • Библия подготовки к собеседованиям
    • 189 задач с решениями
    • Советы от бывшего инженера Google

  3. “JavaScript Algorithms” - Oleksii Trekhleb

    • Специально для JS разработчиков
    • GitHub (БЕСПЛАТНО)

✅ Ключевые выводы

  1. DSA не только для разработчиков - QA использует это каждый день
  2. JavaScript + DSA = мощная комбинация для роли SDET
  3. Начните с практических примеров - не с теории
  4. Постоянство важнее интенсивности - 30 минут каждый день
  5. LeetCode не про заучивание - фокусируйтесь на понимании паттернов
  6. Знание DSA может существенно изменить зарплату — иногда на $50K - $100K

📍 Что дальше?

В следующей статье мы погрузимся в продвинутые фреймворки автоматизации тестирования:

  • Глубокое изучение Playwright (требование Apple!)
  • Продвинутые паттерны Selenium
  • Karate для API
  • Построение масштабируемых фреймворков
  • Интеграция CI/CD

Следующая статья: Статья 4: Фреймворки автоматизации

Бонус: Быстрая справка по JavaScript

Примеры временной сложности

Понимание временной сложности помогает писать более быстрые тесты и замечать медленный код на код ревью.

// O(1) - Константное время: Одинаковая скорость независимо от размера входных данных
// Как посмотреть на первый элемент списка - мгновенно!
const getFirst = (arr) => arr[0];  // ✅ Всегда быстро

// O(log n) - Логарифмическое: Уменьшаем область поиска вдвое каждый раз
// Как найти слово в словаре - очень эффективно!
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // ✅ Очень быстро даже с миллионами элементов
}

// O(n) - Линейное: Смотрим на каждый элемент один раз
// Как подсчёт предметов в сумке - масштабируется с размером
const findMax = (arr) => Math.max(...arr);  // ✅ Хорошо

// O(n log n) - Линеарифмическое: Хорошие алгоритмы сортировки
// Как эффективная организация карт
const sorted = arr.sort((a, b) => a - b);  // ✅ Приемлемо

// O(n²) - Квадратичное: Вложенные циклы = МЕДЛЕННО!
// Как сравнение каждого студента с каждым другим студентом
function bubbleSort(arr) {
    // Два вложенных цикла = O(n²)
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;  // ❌ Избегайте для больших наборов данных
}

// Пространственная сложность - Сколько памяти мы используем?
// O(1) пространство - Не создаём новые структуры (лучше всего)
// O(n) пространство - Создаём массив размера n (приемлемо)
// O(n²) пространство - Создаём 2D массив (будьте осторожны!)

Была ли эта статья полезной? 👏

Вопросы? Оставьте комментарий!