Miscellaneous

"Cache policies (LRU, LFU, ARC), OOP design, system design, concurrency problems, brainteasers."

Deep Dive Tutorial

Some algorithms are too specific to belong to a broad category but important enough to know cold. Boyer-Moore majority vote is linear and constant space. Puzzle solvability is a parity check on inversions. BFS on encoded board state handles small state-space puzzles. These appear in interviews and contests; knowing the pattern instantly makes them trivial.

Boyer-Moore Majority Vote

key

Majority element appears > n/2 times. Boyer-Moore finds it in O(n) time, O(1) space.

Intuition: Pair each non-majority element with a majority element and cancel them. The majority element survives because it has more than half the votes.

For n/3 majority: maintain 2 candidates simultaneously.

Boyer-Moore majority vote — O(n) time, O(1) space

// Find element appearing > n/2 times (guaranteed to exist)
function majorityElement(nums) {
    let candidate = nums[0], count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) { candidate = nums[i]; count = 1; }
        else if (nums[i] === candidate) count++;
        else count--;
    }
    return candidate; // guaranteed majority exists
}

// Find all elements appearing > n/3 times
function majorityElementII(nums) {
    let cand1 = 0, cand2 = 1, cnt1 = 0, cnt2 = 0;
    for (const n of nums) {
        if (n === cand1) cnt1++;
        else if (n === cand2) cnt2++;
        else if (cnt1 === 0) { cand1 = n; cnt1 = 1; }
        else if (cnt2 === 0) { cand2 = n; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    // Verify (candidates aren't guaranteed to be majority)
    cnt1 = cnt2 = 0;
    for (const n of nums) {
        if (n === cand1) cnt1++;
        else if (n === cand2) cnt2++;
    }
    const res = [];
    if (cnt1 > nums.length / 3) res.push(cand1);
    if (cnt2 > nums.length / 3) res.push(cand2);
    return res;
}

BFS on State Space (Sliding Puzzles)

lightbulb

Sliding puzzle pattern: Encode board as string. BFS from start state, target = goal string. Each state = one BFS level. Answer = levels to reach goal.

Key trick: Find the blank position in the string, swap it with valid neighbors (accounting for 2D adjacency in flattened index).

Sliding puzzle BFS — encoded state space

// 2×3 board: find min moves to reach [[1,2,3],[4,5,0]]
function slidingPuzzle(board) {
    const target = '123450';
    const start = board.flat().join('');
    if (start === target) return 0;

    // 2D neighbors in flattened index for a 2×3 grid
    const neighbors = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]];

    const visited = new Set([start]);
    const queue = [[start, 0]];

    while (queue.length) {
        const [state, steps] = queue.shift();
        const zero = state.indexOf('0');
        for (const neighbor of neighbors[zero]) {
            const arr = state.split('');
            [arr[zero], arr[neighbor]] = [arr[neighbor], arr[zero]];
            const next = arr.join('');
            if (next === target) return steps + 1;
            if (!visited.has(next)) { visited.add(next); queue.push([next, steps+1]); }
        }
    }
    return -1;
}

// General pattern for small state-space BFS:
// 1. Encode state as string/number
// 2. BFS with visited set
// 3. Generate all valid next states

15-Puzzle Solvability (Inversion Count)

lightbulb

A 15-puzzle is solvable if and only if:
- Width is ODD: inversions count is even
- Width is EVEN: inversions count + row of blank from bottom is odd

Inversion: pair (i,j) where i < j but tile[i] > tile[j] (ignoring 0).

This is a parity argument — every legal move preserves parity mod 2.

15-Puzzle solvability check

function isSolvable(board) {
    const n = board.length;
    const flat = board.flat();
    let inversions = 0;
    let blankRow = 0;

    // Count inversions
    for (let i = 0; i < flat.length; i++) {
        if (flat[i] === 0) { blankRow = Math.floor(i / n); continue; }
        for (let j = i + 1; j < flat.length; j++) {
            if (flat[j] !== 0 && flat[i] > flat[j]) inversions++;
        }
    }

    if (n % 2 === 1) {
        return inversions % 2 === 0; // odd width: inversions must be even
    } else {
        // even width: inversions + blank row from bottom must be odd
        const blankFromBottom = n - 1 - blankRow;
        return (inversions + blankFromBottom) % 2 === 1;
    }
}

Reservoir Sampling

Reservoir sampling — pick k random items from stream

// Pick 1 random item from stream of unknown length
// Each item has equal 1/n probability
class ReservoirSampler {
    constructor() { this.reservoir = null; this.count = 0; }
    add(item) {
        this.count++;
        // Accept with probability 1/count
        if (Math.random() * this.count < 1) this.reservoir = item;
    }
}

// Pick k items: maintain reservoir of size k
// For each new item i (0-indexed): replace random position in reservoir
// with probability k/(i+1)
function reservoirSample(stream, k) {
    const res = stream.slice(0, k);
    for (let i = k; i < stream.length; i++) {
        const j = Math.floor(Math.random() * (i + 1));
        if (j < k) res[j] = stream[i];
    }
    return res;
}

Worked Problems

Easy

Hard

Random Pick with Weight

Medium

Solve ↗

Miscellaneous

Deep Dive Tutorial

Boyer-Moore Majority Vote

BFS on State Space (Sliding Puzzles)

15-Puzzle Solvability (Inversion Count)

Reservoir Sampling

Worked Problems

More Worked Problems