Data Structures & Algorithms for QA Engineers

From Tester to Software Engineer in Test

Why modern QA engineers need to know algorithms and how this will help you land a job at Apple, Google, and other top companies

QA Interview

/**
 * Determines test execution order considering dependencies.
 * 
 * How it works (Kahn's Algorithm):
 * 1. Find tests with NO dependencies (they can run first)
 * 2. Run those tests, then remove them from the graph
 * 3. Now some other tests have no dependencies - run those
 * 4. Repeat until all tests are ordered
 * 
 * If we can't order all tests = circular dependency (A needs B, B needs A)
 * 
 * @param {Array} tests - list of test case IDs
 * @param {Object} dependencies - {test_id: [tests that must run first]}
 * @returns {Array|null} - ordered list or null if circular dependency
 */
function getTestExecutionOrder(tests, dependencies) {
    // Graph: maps test -> tests that depend on it
    const graph = new Map();
    // InDegree: counts how many dependencies each test has
    const inDegree = new Map();
    
    // Initialize: every test starts with 0 dependencies
    tests.forEach(test => {
        graph.set(test, []);
        inDegree.set(test, 0);
    });
    
    // Build graph: for each dependency, add edge and increase 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 (edge)
            inDegree.set(test, inDegree.get(test) + 1);  // test has one more dependency
        }
    }
    
    // Start with tests that have NO dependencies (inDegree = 0)
    const queue = tests.filter(test => inDegree.get(test) === 0);
    const executionOrder = [];
    
    while (queue.length > 0) {
        // Take a test with no remaining dependencies
        const current = queue.shift();
        executionOrder.push(current);
        
        // This test is done - decrease dependencies for tests waiting on it
        const neighbors = graph.get(current) || [];
        for (const neighbor of neighbors) {
            inDegree.set(neighbor, inDegree.get(neighbor) - 1);
            // If neighbor now has no dependencies, it can run
            if (inDegree.get(neighbor) === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    // If we didn't order all tests, there's a cycle!
    if (executionOrder.length !== tests.length) {
        return null; // Circular dependency detected!
    }
    
    return executionOrder;
}

// Example: Test dependencies
const tests = ['TC001', 'TC002', 'TC003', 'TC004', 'TC005'];
const dependencies = {
    'TC002': ['TC001'],          // TC002 depends on TC001
    'TC003': ['TC001'],          // TC003 depends on TC001
    'TC004': ['TC002', 'TC003'], // TC004 depends on TC002 AND TC003
    'TC005': ['TC004']           // TC005 depends on TC004
};

const order = getTestExecutionOrder(tests, dependencies);
console.log(`Execution order: ${order}`);
// Output: ['TC001', 'TC002', 'TC003', 'TC004', 'TC005']

This led to a job offer with a salary 40% higher than expected.

Where DSA is Actually Used in QA

1. Optimizing Test Coverage

Problem: We have 1,000 test cases, but can only run 100 of them. How do we pick the best set?

Solution: Greedy Algorithm + Set Cover Problem

A “greedy” algorithm makes the best choice at each step. Like picking the ripest apple each time!

/**
 * Selects minimal set of tests for maximum feature coverage.
 * 
 * Greedy approach: At each step, pick the test that covers
 * the most NEW features we haven't covered yet.
 * 
 * @param {Array} testCases - list of test case IDs
 * @param {number} maxTests - maximum number of tests we can run
 * @param {Object} featureCoverage - {test_id: Set(covered_features)}
 */
function optimizeTestCoverage(testCases, maxTests, featureCoverage) {
    const selectedTests = [];          // Tests we've chosen
    const coveredFeatures = new Set(); // Features we've already covered
    const remainingTests = [...testCases]; // Tests not yet selected
    
    while (selectedTests.length < maxTests && remainingTests.length > 0) {
        // Greedy choice: Find test covering most NEW features
        let bestTest = null;
        let bestNewCoverage = 0;
        
        // Check each remaining test
        for (const test of remainingTests) {
            const testFeatures = featureCoverage[test];
            // Count features this test covers that we DON'T have yet
            const newFeatures = [...testFeatures].filter(f => !coveredFeatures.has(f));
            const newCoverage = newFeatures.length;
            
            // Is this test better than our current best?
            if (newCoverage > bestNewCoverage) {
                bestNewCoverage = newCoverage;
                bestTest = test;
            }
        }
        
        // If no test adds new coverage, stop
        if (bestNewCoverage === 0) break;
        
        // Add best test to our selection
        selectedTests.push(bestTest);
        // Mark its features as covered
        featureCoverage[bestTest].forEach(f => coveredFeatures.add(f));
        // Remove from remaining tests
        remainingTests.splice(remainingTests.indexOf(bestTest), 1);
    }
    
    return { selectedTests, coveredFeatures };
}

// Example: 5 tests, but we can only run 3
const testCases = ['TC001', 'TC002', 'TC003', 'TC004', 'TC005'];
const featureCoverage = {
    'TC001': new Set(['login', 'auth', 'session']),     // 3 features
    'TC002': new Set(['login', 'logout']),              // 2 features (1 overlap)
    'TC003': new Set(['profile', 'edit']),              // 2 new features
    'TC004': new Set(['payment', 'checkout', 'auth']),  // 3 features (1 overlap)
    'TC005': new Set(['payment', 'refund'])             // 2 features (1 overlap)
};

const result = optimizeTestCoverage(testCases, 3, featureCoverage);
console.log(`Selected tests: ${result.selectedTests}`);
console.log(`Coverage: ${[...result.coveredFeatures]}`);
// Result: With only 3 tests, we cover 8 out of 9 features!

This cut regression testing time by 90% while retaining 89% coverage.

2. Finding Duplicate Test Cases

Problem: We have 5000 test cases. How do we find duplicates?

A basic solution is O(n?), comparing each test to all others�a process that takes hours.

A hash table reduces this to O(n), taking only seconds!

Why is O(n?) slow?

5000 tests ? 5000 comparisons = 25,000,000 operations!

Why is O(n) fast?

5000 tests ? 1 hash lookup = 5,000 operations!

const crypto = require('crypto');

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

/**
 * Finds duplicate test cases in O(n) time.
 * @param {Array<TestCase>} testSuite - array of test cases
 * @returns {Object} - object with duplicates
 */
function findDuplicateTests(testSuite) {
    const testSignatures = new Map();
    
    for (const test of testSuite) {
        // Create a unique signature for the test
        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);
    }
    
    // Find duplicates
    const duplicates = {};
    for (const [signature, ids] of testSignatures.entries()) {
        if (ids.length > 1) {
            duplicates[signature] = ids;
        }
    }
    
    return duplicates;
}

// Example
const testSuite = [
    new TestCase("TC001", "Login with valid creds", "Success", "user@test.com"),
    new TestCase("TC002", "Login with valid creds", "Success", "user@test.com"), // Duplicate!
    new TestCase("TC003", "Login with invalid creds", "Error", "wrong@test.com"),
];

const duplicates = findDuplicateTests(testSuite);
for (const [sig, ids] of Object.entries(duplicates)) {
    console.log(`Found duplicates: ${ids}`);
}
// Output: Found duplicates: TC001,TC002

Task: Verify all pages are accessible within 3 clicks from the homepage.

Solution: Breadth-First Search (BFS)

/**
 * Checks if all pages are accessible within maxClicks clicks.
 * @param {string} startPage - starting page
 * @param {number} maxClicks - maximum number of clicks
 * @returns {Object} - results with reachable and unreachable pages
 */
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;
        
        // Get all links on the current page
        const links = getLinksOnPage(currentPage);
        
        for (const link of links) {
            if (!visited.has(link)) {
                visited.set(link, depth + 1);
                queue.push([link, depth + 1]);
            }
        }
    }
    
    // Find unreachable pages
    const allPages = getAllSitePages();
    const unreachable = allPages.filter(page => !visited.has(page));
    const maxDepth = Math.max(...visited.values());
    
    return {
        reachable: Object.fromEntries(visited),
        unreachable,
        maxDepth
    };
}

// Mock functions for example
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'];
}

// Test result
const result = testNavigationDepth('/home');
if (result.unreachable.length > 0) {
    console.log(`? FAIL: Pages not accessible within 3 clicks: ${result.unreachable}`);
} else {
    console.log(`? PASS: All pages accessible. Max depth: ${result.maxDepth}`);
}

Essential Data Structures for QA

1. Arrays & Lists

When to Use:

Storing a list of test cases
Test results
Test data sets

class TestSuite {
    constructor() {
        this.tests = [];  // Array
        this.results = [];
    }
    
    /**
     * O(1) - add to end
     */
    addTest(test) {
        this.tests.push(test);
    }
    
    /**
     * O(n) - iterate all tests
     */
    runAllTests() {
        for (const test of this.tests) {
            const result = test.execute();
            this.results.push(result);
        }
    }
    
    /**
     * O(n) - filtering
     */
    getFailedTests() {
        return this.results.filter(r => r.status === 'FAILED');
    }
    
    /**
     * O(1) - access by index
     */
    getTestByIndex(index) {
        return this.tests[index];
    }
    
    /**
     * O(n) - search by ID
     */
    findTestById(id) {
        return this.tests.find(test => test.id === id);
    }
}

// Key operations:
// - Search: O(n)
// - Access: O(1)
// - Insert at end: O(1)
// - Delete: O(n)

LeetCode Practice Problems:

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

2. Hash Tables (Map/Object)

When to Use:

Fast test lookup by ID
Caching results
Counting bug frequency

class TestRegistry {
    constructor() {
        this.tests = new Map();  // Hash Table
        this.executionCount = new Map();
        this.bugFrequency = new Map();
    }
    
    /**
     * O(1) - add
     */
    registerTest(testId, test) {
        this.tests.set(testId, test);
    }
    
    /**
     * O(1) - lookup
     */
    getTest(testId) {
        return this.tests.get(testId);
    }
    
    /**
     * Track bug frequency by module - O(1)
     */
    trackBug(module) {
        const current = this.bugFrequency.get(module) || 0;
        this.bugFrequency.set(module, current + 1);
    }
    
    /**
     * Find modules with high bug count - O(n)
     */
    getProblematicModules(threshold = 5) {
        const problematic = {};
        for (const [module, count] of this.bugFrequency.entries()) {
            if (count >= threshold) {
                problematic[module] = count;
            }
        }
        return problematic;
    }
}

// Example usage
const registry = new TestRegistry();
registry.registerTest("TC001", new LoginTest());
registry.registerTest("TC002", new PaymentTest());

// Fast lookup - O(1)!
const test = registry.getTest("TC001");

// Track bugs
registry.trackBug("payment");
registry.trackBug("payment");
registry.trackBug("payment");
registry.trackBug("login");

const problematic = registry.getProblematicModules(2);
console.log(`Problematic modules:`, problematic);
// Output: { payment: 3 }

Why Hash Tables Matter for QA:

Searching for a test among 10,000 now takes microseconds instead of seconds.
For bug analysis, you can instantly spot which modules have the most issues.

LeetCode Problems:

Easy: Two Sum (classic!), Valid Anagram
Medium: Group Anagrams, Top K Frequent Elements

3. Stacks & Queues

Stack (Last In, First Out) is useful for testing the browser’s “Back” button.

Think of a stack like a pile of plates - you can only take the top plate off first!

class BrowserHistory {
    /**
     * Testing browser "Back" functionality
     * 
     * How a stack works:
     * - You visit page A, then B, then C
     * - Stack is now: [A, B, C] (C is on top)
     * - Press "Back": C is removed, you see B
     * - Stack is now: [A, B]
     */
    constructor() {
        this.history = [];      // Stack - stores pages you visited
        this.forwardStack = []; // Stack - stores pages for "Forward"
    }
    
    /**
     * Visit new page - adds to top of stack
     */
    visit(url) {
        this.history.push(url);         // Add to top of stack
        this.forwardStack = [];         // Clear forward (like real browser)
    }
    
    /**
     * "Back" button - removes current page, shows previous
     */
    back() {
        if (this.history.length > 1) {
            const current = this.history.pop();     // Remove top page
            this.forwardStack.push(current);        // Save for Forward
            return this.history[this.history.length - 1]; // Return new top
        }
        return null;  // Can't go back from first page
    }
    
    /**
     * "Forward" button - go back to page we left
     */
    forward() {
        if (this.forwardStack.length > 0) {
            const url = this.forwardStack.pop();    // Get page from Forward stack
            this.history.push(url);                 // Put it back in history
            return url;
        }
        return null;  // Nothing to go forward to
    }
}

// Test the browser history
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");   // back to youtube
console.assert(browser.back() === "google.com");    // back to google
console.assert(browser.forward() === "youtube.com"); // forward to youtube
console.log("? Browser history works!");

Queue - First In, First Out

A queue is like a line at a store - first person in line gets served first!

class TestExecutionQueue {
    /**
     * FIFO (First In, First Out) queue for test execution
     * 
     * How a queue works:
     * - Tests are added to the end of the line
     * - Tests are taken from the front of the line
     * - First test added = first test to run
     */
    constructor() {
        this.queue = [];          // Regular tests wait here
        this.priorityQueue = [];  // Critical tests get priority
    }
    
    /**
     * Add test to queue
     * @param {Object} test - the test to add
     * @param {boolean} priority - true = run before regular tests
     */
    addTest(test, priority = false) {
        if (priority) {
            this.priorityQueue.push(test);  // Add to priority line
        } else {
            this.queue.push(test);          // Add to regular line
        }
    }
    
    /**
     * Get next test to execute
     * Priority tests go first, then regular tests
     */
    getNextTest() {
        // Always check priority queue first
        if (this.priorityQueue.length > 0) {
            return this.priorityQueue.shift();  // Remove from front (FIFO)
        } else if (this.queue.length > 0) {
            return this.queue.shift();          // Remove from front (FIFO)
        }
        return null;  // No tests left
    }
    
    /**
     * How many tests are waiting?
     */
    size() {
        return this.priorityQueue.length + this.queue.length;
    }
}

// Example usage
const executor = new TestExecutionQueue();
executor.addTest(new SmokeTest());            // Added first, runs second
executor.addTest(new RegressionTest());       // Added second, runs third
executor.addTest(new CriticalBugTest(), true); // Priority! Runs first!

// Order of execution: CriticalBugTest > SmokeTest > RegressionTest
while (executor.size() > 0) {
    const test = executor.getNextTest();
    test.run();
}

LeetCode Problems:

Easy: Valid Parentheses (Stack), Implement a Queue using Stacks.
Medium: Min Stack, Design Circular Queue

4. Trees & Graphs

Tree Structure - DOM and File Systems

A tree is like a family tree - one parent, many children. Each node can have child nodes.

Used for: HTML DOM, file systems, organization charts.

class DOMNode {
    /**
     * Representation of a DOM element (HTML tag)
     * 
     * What is a tree?
     * - A tree has a "root" node at the top
     * - Each node can have child nodes
     * - Children can have their own children
     * 
     * Example: HTML structure
     *          <html>
     *         /      \
     *     <body>    <head>
     *       |
     *     <div>
     *    /    \
     * <p>    <button>
     */
    constructor(tag, id = null, text = null) {
        this.tag = tag;         // e.g., "div", "button"
        this.id = id;
        this.text = text;
        this.children = [];
    }
    
    addChild(child) {
        this.children.push(child);
    }
    
    /**
     * DFS search for element by ID
     * Depth-First Search: Start from root, go deep into first branch
     */
    findById(targetId) {
        // Check if current node matches
        if (this.id === targetId) {
            return this;
        }
        
        // Search in all children recursively
        for (const child of this.children) {
            const result = child.findById(targetId);
            if (result) return result;  // Found it!
        }
        
        // Not found in this branch
        return null;
    }
    
    /**
     * Collect all text from this tree
     * Recursively gather text from all nodes
     */
    getAllText() {
        // Start with current node's text (if any)
        const texts = this.text ? [this.text] : [];
        
        // Add text from all children recursively
        for (const child of this.children) {
            texts.push(...child.getAllText());
        }
        
        return texts;
    }
    
    /**
     * Validate DOM structure
     * Check for common mistakes in DOM
     */
    validateStructure() {
        const errors = [];
        
        // Rule 1: Buttons must have text content
        if (this.tag === 'button' && !this.text) {
            errors.push(`Button without text: id=${this.id}`);
        }
        
        // Rule 2: Cannot nest buttons inside buttons
        if (this.tag === 'button') {
            for (const child of this.children) {
                if (child.tag === 'button') {
                    errors.push(`Button inside button: id=${this.id}`);
                }
            }
        }
        
        // Recursively check all children
        for (const child of this.children) {
            errors.push(...child.validateStructure());
        }
        
        return errors;
    }
}

// Create DOM
const html = new DOMNode('html');
const body = new DOMNode('body');
const div = new DOMNode('div', 'container');
const button = new DOMNode('button', 'submit-btn', 'Submit');

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

// Testing
const found = html.findById('submit-btn');
console.assert(found !== null);
console.assert(found.text === 'Submit');

const errors = html.validateStructure();
if (errors.length > 0) {
    console.log(`? DOM validation failed: ${errors}`);
} else {
    console.log("? DOM structure is valid");
}

Graph Structure - Module Dependencies

A graph is helpful for modeling module dependencies.

class ModuleDependencyGraph {
    /**
     * Module dependency graph for integration testing
     */
    constructor() {
        this.graph = new Map();
    }
    
    /**
     * Module depends on another module
     */
    addDependency(module, dependsOn) {
        if (!this.graph.has(module)) {
            this.graph.set(module, []);
        }
        this.graph.get(module).push(dependsOn);
    }
    
    /**
     * Check for circular dependencies (DFS)
     * A circular dependency means: A depends on B, B depends on C, C depends on A
     * This is bad - code can't even load!
     */
    hasCircularDependency() {
        const visited = new Set();      // Already checked nodes
        const recStack = new Set();     // Nodes in current path
        
        // Helper function for DFS
        const dfs = (node) => {
            visited.add(node);          // Mark as being processed
            recStack.add(node);         // Add to current path
            
            // Check all dependencies of this node
            const neighbors = this.graph.get(node) || [];
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    // Not visited yet, explore it
                    if (dfs(neighbor)) return true;  // Cycle found!
                } else if (recStack.has(neighbor)) {
                    // Found node in current path = CYCLE!
                    return true;
                }
            }
            
            // Done with this path
            recStack.delete(node);
            return false;
        };
        
        // Try DFS from each node
        for (const node of this.graph.keys()) {
            if (!visited.has(node)) {
                if (dfs(node)) return true;  // Found a cycle
            }
        }
        
        return false;  // No cycles found - all good!
    }
}

// Example usage
const deps = new ModuleDependencyGraph();
deps.addDependency('PaymentModule', 'AuthModule');
deps.addDependency('CheckoutModule', 'PaymentModule');
deps.addDependency('CheckoutModule', 'CartModule');

if (deps.hasCircularDependency()) {
    console.log("? ERROR: Circular dependency detected!");
} else {
    console.log("? No circular dependencies");
}

LeetCode Problems:

Easy: Maximum Depth of Binary Tree, Same Tree
Medium: Binary Tree Level Order Traversal, Course Schedule (Graph!)

Algorithms Every SDET Should Know

1. Sorting & Searching

/**
 * Sort tests by failure rate (descending).
 * Tests failing more often = higher priority to fix them first
 */
function prioritizeTestsByFailureRate(tests, history) {
    const getFailureRate = (test) => {
        const { total_runs, failures } = history[test.id];
        // Calculate: failures / total_runs = failure rate
        return total_runs > 0 ? failures / total_runs : 0;
    };
    
    // Sort by failure rate (highest first)
    // O(n log n) time complexity
    return tests.sort((a, b) => getFailureRate(b) - getFailureRate(a));
}

/**
 * Binary search for log entry in sorted logs
 * Much faster than checking every entry: O(log n) instead of O(n)!
 */
function binarySearchLogEntry(logs, timestamp) {
    let left = 0;                      // Start of search range
    let right = logs.length - 1;       // End of search range
    
    while (left <= right) {
        // Pick middle position
        const mid = Math.floor((left + right) / 2);
        
        if (logs[mid].timestamp === timestamp) {
            return logs[mid];          // Found it!
        } else if (logs[mid].timestamp < timestamp) {
            left = mid + 1;            // Search right half
        } else {
            right = mid - 1;           // Search left half
        }
    }
    
    return null;  // Not found
}

// Example
const logs = [
    { timestamp: 100, message: "Test started" },
    { timestamp: 150, message: "API called" },
    { timestamp: 200, message: "Error occurred" },
    { timestamp: 300, message: "Test finished" },
];

const errorLog = binarySearchLogEntry(logs, 200);
console.log(errorLog);  // Found in O(log n)!

2. Two Pointers Technique

Core Concept: Use two pointers to traverse data efficiently instead of nested loops.

/**
 * Compare two sorted test result lists
 * Find: missing tests, extra tests, in O(n+m) time
 * 
 * WHY two pointers?
 * - Naive way: Check each expected against all actual = O(n*m) nested loops (SLOW!)
 * - Two pointers: Each element visited once = O(n+m) single pass (FAST!)
 * 
 * HOW it works:
 * - Both lists are sorted
 * - Pointer i in expected, pointer j in actual
 * - Move pointers forward together intelligently
 * - Never backtrack! (This makes it O(n+m) not O(n?))
 * 
 * @param {Array} expected - sorted test IDs that should run
 * @param {Array} actual - sorted test IDs that actually ran
 */
function compareTestResults(expected, actual) {
    let i = 0, j = 0;     // Pointer i for expected, pointer j for actual
    const differences = [];
    
    // Core loop: Compare elements at current pointers
    while (i < expected.length && j < actual.length) {
        if (expected[i] === actual[j]) {
            // Same test in both - advance BOTH pointers
            // Neither list has a difference here
            i++;
            j++;
        } else if (expected[i] < actual[j]) {
            // expected has smaller value
            // This test is MISSING from actual results
            // Advance i to check next expected test
            differences.push(`Missing in actual: ${expected[i]}`);
            i++;
        } else {
            // actual has smaller value  
            // This test is EXTRA in actual results (unexpected)
            // Advance j to check next actual test
            differences.push(`Extra in actual: ${actual[j]}`);
            j++;
        }
    }
    
    // Handle remaining elements (one list exhausted, other not)
    // Everything left in expected = missing from actual
    while (i < expected.length) {
        differences.push(`Missing in actual: ${expected[i]}`);
        i++;
    }
    
    // Everything left in actual = extra (unexpected)
    while (j < actual.length) {
        differences.push(`Extra in actual: ${actual[j]}`);
        j++;
    }
    
    return differences;
}

// Example: Two sorted test result lists
const expected = [1, 2, 3, 5, 6];    // What SHOULD have run
const actual = [1, 2, 4, 5];         // What ACTUALLY ran
const diffs = compareTestResults(expected, actual);

diffs.forEach(diff => console.log(diff));
// Output:
// Missing in actual: 3
// Extra in actual: 4
// Missing in actual: 6

// Analysis:
// - Test 3 was skipped (should have run but didn't)
// - Test 4 ran unexpectedly (shouldn't have run)
// - Test 6 was skipped
// Why O(n+m) is fast: each number visited exactly once
// If we used nested loop: test 1 checked against 1,2,4,5 (4 comparisons)
//                        test 2 checked against 1,2,4,5 (4 comparisons)
//                        ... = slow for large lists!

3. Sliding Window

Core Concept: A “window” is a fixed-size range. We slide it across data like a moving filter to find patterns.

/**
 * Analyze response times in sliding window
 * 
 * Think of it like this:
 * - You have 1 hour of API request logs
 * - Every 5 seconds, you check: "Were requests slow in the last 60 seconds?"
 * - You SLIDE this 60-second window forward, checking each position
 * 
 * Why sliding window?
 * - Single pass through data = O(n) time (very fast!)
 * - Without it, checking each possible 60-sec range = O(n?) (very slow!)
 * 
 * @param {Array} responseTimes - [{timestamp: ms, duration: ms}, ...]
 * @param {number} windowSizeSeconds - window width (e.g., 60 seconds)
 */
function analyzeResponseTimes(responseTimes, windowSizeSeconds = 60) {
    const issues = [];
    let windowStart = 0;  // LEFT edge of window pointer
    
    // windowEnd pointer: moves RIGHT
    for (let windowEnd = 0; windowEnd < responseTimes.length; windowEnd++) {
        // Keep window size fixed:
        // If window is too wide (newer time - older time > 60 seconds)
        // shrink from the left by moving windowStart right
        while (responseTimes[windowEnd].timestamp - 
               responseTimes[windowStart].timestamp > windowSizeSeconds) {
            windowStart++;  // Discard oldest element, keep window fresh
        }
        
        // Now we have valid window: responseTimes[windowStart ... windowEnd]
        const windowTimes = responseTimes
            .slice(windowStart, windowEnd + 1)
            .map(rt => rt.duration);
        
        // Calculate average: sum all / count = average
        const avgTime = windowTimes.reduce((a, b) => a + b, 0) / windowTimes.length;
        
        // Is average > 2 seconds? That's slow! Record this problem period
        if (avgTime > 2000) {  
            issues.push({
                timeRange: [
                    responseTimes[windowStart].timestamp,
                    responseTimes[windowEnd].timestamp
                ],
                avgResponseTime: avgTime,
                requestsCount: windowTimes.length
            });
        }
    }
    
    return issues;
}

// Example:
// API calls at: 0ms, 100ms, 200ms, ... (every 100ms for 10 seconds)
// Each took: 500ms, 600ms, ..., 3000ms (gets slower over time)
// Window size: 60 seconds
// Result: Find periods where average latency > 2 seconds

// Time complexity: O(n) - each element visited at most 2 times
// Space complexity: O(k) - k = number of problematic periods found

4. Dynamic Programming

Core Concept: Break a big problem into smaller pieces. Solve each piece once. Combine pieces into final answer.

Problem: You have 15 minutes to run tests. Each test takes time and has an importance score. Pick tests to maximize importance.

/**
 * 0/1 Knapsack Problem using Dynamic Programming
 * 
 * The big idea:
 * - This is like a backpack problem
 * - Backpack capacity = time budget (15 minutes)
 * - Each test = item with weight (execution time) + value (importance)
 * - Goal = maximize value without exceeding capacity
 * 
 * Why Dynamic Programming?
 * - Brute force: Try all 2^n combinations (n=10 tests = 1024 tries = SLOW)
 * - DP: Build table of optimal choices, reuse results (10 tests = 150 table cells = FAST)
 * 
 * KEY INSIGHT - DP Table dp[i][t]:
 * - i = "considering first i tests"
 * - t = "with t minutes available"
 * - dp[i][t] = maximum importance achievable
 * 
 * Example: dp[3][15] means:
 * "If I only look at first 3 tests and have 15 minutes,
 *  what's the best importance score I can get?"
 * 
 * @param {Array} tests - [[testName, executionTime, importance], ...]
 * @param {number} timeBudget - total minutes available
 */
function selectTestsWithBudget(tests, timeBudget) {
    const n = tests.length;
    
    // Create DP table: (n+1) rows ? (timeBudget+1) columns
    // All cells start at 0 (no tests selected = 0 importance)
    const dp = Array(n + 1).fill(null)
        .map(() => Array(timeBudget + 1).fill(0));
    
    // Fill table row by row (each row = one more test to consider)
    for (let i = 1; i <= n; i++) {
        const [testName, time, importance] = tests[i - 1];
        
        // For each possible time budget (0 to timeBudget)
        for (let t = 0; t <= timeBudget; t++) {
            // Decision 1: Don't include this test
            // Use best importance from previous tests with same time budget
            dp[i][t] = dp[i - 1][t];
            
            // Decision 2: Include this test (if time allows)
            // This test uses 'time' minutes, leaving (t - time) minutes
            // Best importance with remaining time = dp[i-1][t-time]
            // Plus this test's importance
            if (time <= t) {
                const importanceIfIncluded = dp[i - 1][t - time] + importance;
                // Pick whichever is better: include or don't include
                dp[i][t] = Math.max(dp[i][t], importanceIfIncluded);
            }
        }
    }
    
    // RECONSTRUCTION: Backtrack to find which tests were actually selected
    // Start at dp[n][timeBudget] (answer to full problem)
    // Work backwards to understand which choices led here
    const selected = [];
    let t = timeBudget;
    
    for (let i = n; i > 0; i--) {
        // Did we include test[i]?
        // If dp[i][t] !== dp[i-1][t], then value CHANGED
        // Value only changes if we included this test!
        if (dp[i][t] !== dp[i - 1][t]) {
            // Yes! This test was included in optimal solution
            selected.push(tests[i - 1]);
            // Use up this test's time: t -= testTime
            t -= tests[i - 1][1];
        }
        // If they're equal, this test was NOT included, keep going back
    }
    
    return { 
        selected, 
        totalImportance: dp[n][timeBudget],
        timeUsed: timeBudget - t
    };
}

// EXAMPLE WALKTHROUGH:
const tests = [
    ['LoginTest',    5, 10],      // 5 min execution, importance 10
    ['PaymentTest', 10, 20],      // 10 min execution, importance 20
    ['CheckoutTest', 8, 15],      // 8 min execution, importance 15
    ['SearchTest',   3,  8],      // 3 min execution, importance 8
];

const result = selectTestsWithBudget(tests, 15);
console.log('Selected tests:', result.selected);
console.log('Total importance:', result.totalImportance);
console.log('Time used:', result.timeUsed, 'minutes');

// DP Table visualization:
//        t=0  t=1 ... t=10 ... t=15
// i=0     0    0  ...   0   ...   0  (no tests = 0 importance)
// i=1    0    0  ... 10(LoginTest) ... 10
// i=2    0    0  ... 20(PaymentTest) ... 30(both)
// i=3    0    0  ... max(...) ... depends on combinations
// i=4    ...

LeetCode for QA: Practical Plan

Why Should QA Solve LeetCode?

Technical interviews at Apple, Google, and Amazon include DSA questions. It helps you develop algorithmic thinking, which makes you a better tester. You’ll also be able to spot inefficient code during code reviews.

Medium Level (when you master Easy):

Group Anagrams - Hash Table advanced.
Top K Frequent Elements - Heap/Priority Queue
Course Schedule - Graph + Topological Sort (important!)
Product of Array Except Self - Array manipulation
Longest Substring Without Repeating Characters - Sliding Window
3Sum - Two Pointers
Binary Tree Level Order Traversal - BFS
Implement Trie - Tree structure
Word Search - Backtracking
LRU Cache - Hash Table + Doubly Linked List

8-Week Practice Plan

Week 1-2: Arrays & Hash Tables

Day 1-3: Study concepts
Day 4-7: Easy problems (2-3 per day)
Day 8-14: Medium problems (1 per day)

Week 3-4: Linked Lists & Stacks/Queues

Monday-Wednesday: Theory
Thursday-Sunday: Practice

Week 5-6: Trees & Graphs

Most important section for QA!
Dedicate more time

Week 7-8: Dynamic Programming & Algorithms

Sorting, Searching
Two Pointers, Sliding Window
Basic DP

How to Solve Problems Effectively

Methodology:

Read the problem twice.
Draw an example on paper.
Think about the approach (5-10 minutes)
Start with a brute force solution.
Optimize
Write code
Test on edge cases

Solution Template:

/**
 * TEMPLATE for solving LeetCode problems
 * Use this structure for every problem you solve
 * 
 * This helps you:
 * - Think clearly about the approach
 * - Document your solution
 * - Test edge cases systematically
 */
function solveProblem(inputData) {
    /**
     * Problem: [Problem description]
     * 
     * Approach: [Your approach]
     * Time Complexity: O(?)
     * Space Complexity: O(?)
     * 
     * Examples:
     * Input: [...]
     * Output: [...]
     */
    
    // Edge cases: Handle empty, null, single element
    if (!inputData) {
        return null;
    }
    
    // Main logic goes here
    // ...
    
    return result;
}

// Test cases: Always verify your solution works!
console.assert(solveProblem([1,2,3]) === expectedOutput, "Test 1 failed");
console.assert(solveProblem([]) === null, "Empty array test failed");
console.assert(solveProblem([1]) === expectedOutput, "Single element test failed");

Learning Resources

?? YouTube Channels (FREE!)

Russian:

Timofey Khiryanov - Algorithms and Data Structures

MIPT lectures
Very detailed with examples
YouTube playlist

CS Center - Algorithms

Academic approach

English:

NeetCode ?????

Best channel for LeetCode!
Clear explanations
Algorithm visualization
NeetCode.io
YouTube

FreeCodeCamp - Data Structures Full Course

8+ hours of free content
From beginner to pro
Watch

Web Dev Simplified (for JavaScript developers)

Great DSA explanations in JavaScript
YouTube

Fireship - short, concise videos

YouTube

?? Practice Platforms

LeetCode

?? Main platform
Free plan: 50+ free problems
Premium ($35/month):
- Company-specific questions
- Video solutions
?? Affiliate Link: Get 15% off LeetCode Premium

HackerRank

Good for beginners
FREE!
HackerRank.com

CodeSignal

Real interview tasks
CodeSignal.com

AlgoExpert

?? Paid ($99-$299)
160 curated JavaScript problems
Promo code: QA15 (15% off)
AlgoExpert.io

?? Books

“Grokking Algorithms” - Aditya Bhargava

????? Best for beginners!
Visual approach
Simple language
?? Buy on Amazon

“Cracking the Coding Interview” - Gayle McDowell

Interview prep bible
189 problems with solutions
Advice from an ex-Google engineer
?? Buy on Amazon

“JavaScript Algorithms” - Oleksii Trekhleb

Specifically for JS developers
GitHub (FREE)

?? Online Courses

Free:

JavaScript Algorithms and Data Structures (freeCodeCamp)

Completely free
300+ hours of content
freeCodeCamp.org

Coursera: Algorithms Specialization (Stanford)

Free to audit
Coursera Link

Paid (Udemy):

“JavaScript Algorithms and Data Structures Masterclass” - Colt Steele

?? $12.99 (with discount)
22+ hours
Promo code: QACAREER
?? Udemy Link - Get 85% OFF

“Master the Coding Interview: Data Structures + Algorithms” - Andrei Neagoie.

JavaScript examples
Zero To Mastery
?? Udemy Link

“The Coding Interview Bootcamp: Algorithms + Data Structures” - Stephen Grider

JavaScript focus
Real interview questions
?? Udemy Link

LinkedIn Learning:

“Programming Foundations: Algorithms”

1 month free for new users
?? LinkedIn Learning - Free Trial

?? Interactive Platforms

VisuAlgo.net

?? Algorithm visualization
VisuAlgo.net

JavaScript.info

Free JS tutorial with DSA
JavaScript.info

BigO Cheat Sheet

BigO CheatSheet

8-Week Action Plan

Weekly Schedule

Monday-Friday:

1 hour theory (video/book)
1-2 LeetCode problems
30 minutes code review of others’ solutions

Saturday:

2 hours of practice
Review the week’s problems.
Mock interview (if possible)

Sunday:

Rest or light practice
Read articles/blogs

Progress Checklist

Week 1-2: Arrays & Hash Tables

[ ] Studied theory [ ] Solved 10 Easy problems [ ] Solved 5 Medium problems [ ] Created a cheat sheet

Week 3-4: Linked Lists, Stacks, Queues

[ ] Studied theory [ ] Solved 8 Easy problems [ ] Solved 4 Medium problems [ ] Implemented own Stack/Queue

Week 5-6: Trees & Graphs

[ ] Studied BFS/DFS [ ] Solved 10 Tree problems [ ] Solved 5 Graph problems [ ] Understood topological sort

Week 7-8: Algorithms & DP

[ ] Two Pointers - 5 problems [ ] Sliding Window - 5 problems [ ] Sorting/Searching - 5 problems [ ] Basic DP - 5 problems

Track Progress

Create a spreadsheet:

Date	Problem	Difficulty	Time	Solved?	Notes
01.02	Two Sum	Easy	20 min	?	Used hash table
02.02	Valid Parens	Easy	15 min	?	Stack approach
03.02	Course Schedule	Medium	45 min	?	Need to review graphs

Real Success Stories

Story 1: From Manual QA to Apple SDET

Alex, 28 years “I was a manual QA for 3 years. Salary $60K. Decided to learn DSA.”

Timeline:

Month 1-2: Basics (Arrays, Hash Tables)
Month 3-4: Trees & Graphs
Month 5-6: Solved 150 LeetCode problems
Month 7: Started applying to FAANG
Month 8: Got an offer from Apple

Result:

Position: Software Engineer in Test
Salary: $150K + $50K bonus + $100K RSU
Location: Cupertino, CA

“The key moment - I solved a graph problem in the interview. Without DSA, I would never have gotten this offer.”

Story 2: Career Switch at 35

Maria, 35 years “Thought I was too old to learn algorithms. I was wrong.”

Background: Accountant > Manual QA > SDET

Journey:

8 weeks of intensive study (2 hours/day)
Focus on practical applications.
Solved 80 LeetCode problems (only Easy/Medium)
Got an offer from a fintech startup

Result:

Salary increased from $65K to $110K
Remote work
More interesting work

“DSA seemed scary, but I broke it into small steps. A little bit every day.”

? Key Takeaways

DSA is not just for developers - QA uses it every day
JavaScript + DSA = powerful combination for the SDET role
Start with practical examples - not theory.
Consistency is more important than intensity. Try to spend 30 minutes every day.
LeetCode is not about memorization. Focus on understanding the patterns.
Knowing DSA can make a big difference in your salary�sometimes by $50K to $ 100 K.

?? What’s Next?

In the next article, we’ll dive into Advanced Test Automation Frameworks:

Playwright deep dive (Apple requirement!)
Selenium advanced patterns
Karate for API
Building scalable frameworks
CI/CD integration

Next Article: Article 4: Automation Frameworks

Bonus: JavaScript Quick Reference

Time Complexity Examples

Understanding time complexity helps you write faster tests and spot slow code during code reviews.

// O(1) - Constant Time: Same speed regardless of input size
// Like looking at the first item in a list - instant!
const getFirst = (arr) => arr[0];  // ? Always fast

// O(log n) - Logarithmic: Cutting search space in half each time
// Like finding a word in a dictionary - very efficient!
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;  // ? Very fast even with millions of items
}

// O(n) - Linear: Look at each item once
// Like counting items in a bag - scales with size
const findMax = (arr) => Math.max(...arr);  // ? Good

// O(n log n) - Linearithmic: Good sorting algorithms
// Like organizing cards efficiently
const sorted = arr.sort((a, b) => a - b);  // ? Acceptable

// O(n?) - Quadratic: Nested loops = SLOW!
// Like comparing every student with every other student
function bubbleSort(arr) {
    // Two nested loops = 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;  // ? Avoid for large datasets
}

// Space Complexity - How much memory do we use?
// O(1) space - Don't create new structures (best)
// O(n) space - Create array of size n (acceptable)
// O(n?) space - Create 2D array (be careful!)

Was this article helpful? ??

Questions? Leave a comment!

Data Structures & Algorithms for QA Engineers

From Tester to Software Engineer in Test

You Are Here

Traditional QA Tester

A Real Story from My Experience

Solution: Topological Sort Algorithm

Where DSA is Actually Used in QA

1. Optimizing Test Coverage

2. Finding Duplicate Test Cases

3. Testing UI Navigation (BFS)

Essential Data Structures for QA

1. Arrays & Lists

2. Hash Tables (Map/Object)

3. Stacks & Queues

4. Trees & Graphs

Algorithms Every SDET Should Know

1. Sorting & Searching

2. Two Pointers Technique

3. Sliding Window

4. Dynamic Programming

LeetCode for QA: Practical Plan

Why Should QA Solve LeetCode?

Medium Level (when you master Easy):

8-Week Practice Plan

Week 1-2: Arrays & Hash Tables

Week 3-4: Linked Lists & Stacks/Queues

Week 5-6: Trees & Graphs

Week 7-8: Dynamic Programming & Algorithms

How to Solve Problems Effectively

Methodology:

Solution Template:

Learning Resources

?? YouTube Channels (FREE!)

Russian:

English:

?? Practice Platforms

?? Books

?? Online Courses

Free:

Paid (Udemy):

?? Interactive Platforms

8-Week Action Plan

Weekly Schedule

Progress Checklist

Track Progress

Real Success Stories

Story 1: From Manual QA to Apple SDET

Bonus: JavaScript Quick Reference

Time Complexity Examples