JavaScript-Spickzettel für Vorstellungsgespräche – Teil 2

// Two Pointers - In-place array modification
const modifyArray = (arr) => {
    let writePointer = 0;
    for (let readPointer = 0; readPointer < arr.length; readPointer++) {
        if (/* condition */) {
            [arr[writePointer], arr[readPointer]] = [arr[readPointer], arr[writePointer]];
            writePointer++;
        }
    }
    return writePointer; // Often returns new length or modified position
};

// Fast and Slow Pointers (Floyd's Cycle Detection)
const hasCycle = (head) => {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
};

// Sliding Window - Fixed Size
const fixedSlidingWindow = (arr, k) => {
    let sum = 0;
    // Initialize first window
    for (let i = 0; i < k; i++) {
        sum += arr[i];
    }

    let maxSum = sum;
    // Slide window
    for (let i = k; i < arr.length; i++) {
        sum = sum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
};

// Sliding Window - Variable Size
const varSlidingWindow = (arr, target) => {
    let start = 0, sum = 0, minLen = Infinity;

    for (let end = 0; end < arr.length; end++) {
        sum += arr[end];
        while (sum >= target) {
            minLen = Math.min(minLen, end - start + 1);
            sum -= arr[start];
            start++;
        }
    }

    return minLen === Infinity ? 0 : minLen;
};

// BFS - Level Order Traversal
const levelOrder = (root) => {
    if (!root) return [];
    const result = [];
    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(currentLevel);
    }
    return result;
};

// DFS - Recursive Template
const dfs = (root) => {
    const result = [];

    const traverse = (node) => {
        if (!node) return;

        // Pre-order
        result.push(node.val);

        traverse(node.left);
        // In-order would be here
        traverse(node.right);
        // Post-order would be here
    };

    traverse(root);
    return result;
};

// Backtracking Template
const backtrack = (nums) => {
    const result = [];

    const bt = (path, choices) => {
        if (/* ending condition */) {
            result.push([...path]);
            return;
        }

        for (let i = 0; i < choices.length; i++) {
            // Make choice
            path.push(choices[i]);
            // Recurse
            bt(path, /* remaining choices */);
            // Undo choice
            path.pop();
        }
    };

    bt([], nums);
    return result;
};

// Dynamic Programming - Bottom Up Template
const dpBottomUp = (n) => {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; // Base case

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            dp[i] += dp[j] * /* some calculation */;
        }
    }

    return dp[n];
};

// Dynamic Programming - Top Down Template
const dpTopDown = (n) => {
    const memo = new Map();

    const dp = (n) => {
        if (n <= 1) return 1;
        if (memo.has(n)) return memo.get(n);

        let result = 0;
        for (let i = 0; i < n; i++) {
            result += dp(i) * /* some calculation */;
        }

        memo.set(n, result);
        return result;
    };

    return dp(n);
};

// Monotonic Stack Template
const monotonicStack = (arr) => {
    const stack = []; // [index, value]
    const result = new Array(arr.length).fill(-1);

    for (let i = 0; i < arr.length; i++) {
        while (stack.length && stack[stack.length - 1][1] > arr[i]) {
            const [prevIndex, _] = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push([i, arr[i]]);
    }
    return result;
};

// Prefix Sum
const prefixSum = (arr) => {
    const prefix = [0];
    for (let i = 0; i < arr.length; i++) {
        prefix.push(prefix[prefix.length - 1] + arr[i]);
    }
    // Sum of range [i, j] = prefix[j + 1] - prefix[i]
    return prefix;
};

// Binary Search Variations
const binarySearchLeftmost = (arr, target) => {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
};

const binarySearchRightmost = (arr, target) => {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left - 1;
};

// Trie Operations
class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) return false;
            node = node.children.get(char);
        }
        return node.isEndOfWord;
    }

    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children.has(char)) return false;
            node = node.children.get(char);
        }
        return true;
    }
}

// Union Find (Disjoint Set)
class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // Path compression
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);

        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                [rootX, rootY] = [rootY, rootX];
            }
            this.parent[rootY] = rootX;
            if (this.rank[rootX] === this.rank[rootY]) {
                this.rank[rootX]++;
            }
        }
    }
}

// O(1) - Constant
Array.push(), Array.pop(), Map.set(), Map.get()

// O(log n) - Logarithmic
Binary Search, Balanced BST operations

// O(n) - Linear
Array traversal, Linear Search

// O(n log n) - Linearithmic
Efficient sorting (Array.sort())

// O(n²) - Quadratic
Nested loops, Simple sorting algorithms

// O(2ⁿ) - Exponential
Recursive solutions without memoization