Skip to content

Latest commit

 

History

History
350 lines (249 loc) · 7.85 KB

08_01_2025.md

File metadata and controls

350 lines (249 loc) · 7.85 KB
Course By Link
The Last Algorithms Course You'll Need
The Primeagen

Graph

DFS on Adjacency List

function walk(
    graph: WeightedAdjacencyList,
    curr: number,
    needle: number,
    seen: boolean[],
    path: number[],
): boolean {
    // basecase
    if (curr === needle) {
        path.push(curr);
        return true;
    }

    if (seen[curr]) {
        return false;
    }

    seen[curr] = true;

    // recurse

    // prev
    path.push(curr);

    // recurse
    const edges = graph[curr];

    for (let i = 0; i < edges.length; i++) {
        const edge = edges[i];

        if (walk(graph, edge.to, needle, seen, path)) {
            return true;
        }
    }

    // post
    path.pop();

    return false;
}

export default function dfs(
    graph: WeightedAdjacencyList,
    source: number,
    needle: number,
): number[] | null {
    const seen: boolean[] = new Array(graph.length).fill(false);
    const path: number[] = [];

    walk(graph, source, needle, seen, path);

    if (!path.length) return null;

    return path;
}

Algorithm

  • DFS on Adjacency List
  • Because we are using adjacency list, we can just get the edges from the current node
  • We can use seen array to mark the node as visited
  • We can use path array to store the path that we've visited-
  • We start at the source node and recurse to the next node until we find the needle
  • If we find the needle, we can return the path
  • If we don't find the needle, we can return null

Complexity

  • Time: O(V + E)
  • Space: O(V)

Notes

  • DFS is a stack based algorithm, so in pre step, we push the current node to the path, and in post step, we pop the current node from the path. In between, we recurse to the next node

Dijkstra's Shortest Path

function hasUnvisited(seen: boolean[], dists: number[]): boolean {
    return seen.some((s, i) => !s && dists[i] < Infinity);
}

function getLowestUnvisited(seen: boolean[], dists: number[]): number {
    let idx = -1;
    let lowestDistance = Infinity;

    for (let i = 0; i < seen.length; i++) {
        if (seen[i]) {
            continue;
        }

        if (lowestDistance > dists[i]) {
            lowestDistance = dists[i];
            idx = i;
        }
    }

    return idx;
}

export default function dijkstra_list(
    source: number,
    sink: number,
    arr: WeightedAdjacencyList,
): number[] {
    const seen = new Array(arr.length).fill(false);
    const prev = new Array(arr.length).fill(-1);
    const dists = new Array(arr.length).fill(Infinity);

    dists[source] = 0;

    while (hasUnvisited(seen, dists)) {
        const curr = getLowestUnvisited(seen, dists);

        seen[curr] = true;

        const adjs = arr[curr];

        for (let i = 0; i < adjs.length; i++) {
            const edge = adjs[i];

            if (seen[edge.to]) {
                continue;
            }

            const dist = dists[curr] + edge.weight;

            if (dist < dists[edge.to]) {
                dists[edge.to] = dist;
                prev[edge.to] = curr;
            }
        }
    }

    const out: number[] = [];

    let curr = sink;

    while (prev[curr] !== -1) {
        out.push(curr);
        curr = prev[curr];
    }

    out.push(source);
    return out.reverse();
}

Algorithm

  • check if there are any unvisited nodes

  • get the lowest unvisited node

  • mark the current node as visited

  • get the adjacent nodes

  • for each adjacent node, calculate the distance

  • if the distance is less than the current distance, update the distance and the previous node

  • repeat until there are no unvisited nodes

Complexity

  • Time: O(V^2 + E)
  • Space: O(V)

Notes

  • Dijkstra's algorithm is a greedy algorithm that finds the shortest path from the source to the sink

  • We should use a priority queue (min heap) to get the lowest unvisited node, that way we can reduce the time complexity to O(V log V + E)

  • We will apply min heap to:

    • get the lowest unvisited node
    • update the distance

Hash table

All you need to know about hash table is here: https://youtu.be/KyUTuwz_b7Q

It just super neet !

LRU (Least Recently Used) Cache

Algorithm

  • We can use a doubly linked list to store the key value pairs
  • We can use a hash table to store the key and the node in the linked list
  • We can use a head and a tail to keep track of the least recently used and the most recently used node
  • When we access a key, we can move the node to the tail
  • When we add a key, we can add it to the tail
  • When we remove a key, we can remove it from the head

Implementation

class Node<T> {
    value: T;
    next?: Node<T>;
    prev?: Node<T>;
}

export default class LRU<K, V> {
    private length: number;
    private head?: Node<V>;
    private tail?: Node<V>;
    private lookup: Map<K, Node<V>>;
    private reverseLookup: Map<Node<V>, K>;

    constructor(private capacity: number = 10) {
        this.length = 0;
        this.head = this.tail = undefined;
        this.lookup = new Map<K, Node<V>>();
        this.reverseLookup = new Map<Node<V>, K>();
    }

    update(key: K, value: V): void {
        const node = this.lookup.get(key);

        if (!node) {
            const newNode = this.createNode(value);
            this.prepend(newNode);

            this.lookup.set(key, newNode);
            this.reverseLookup.set(newNode, key);

            this.length++;
            this.trimCache();
        } else {
            node.value = value;

            this.detach(node);
            this.prepend(node);
        }
    }

    get(key: K): V | undefined {
        const node = this.lookup.get(key);

        if (!node) {
            return undefined;
        }

        this.detach(node);
        this.prepend(node);

        return node.value;
    }

    private createNode(value: V) {
        return { value };
    }

    private detach(node: Node<V>): void {
        if (node.prev) {
            node.prev.next = node.next;
        }

        if (node.next) {
            node.next.prev = node.prev;
        }

        if (this.head === node) {
            this.head = this.head.next;
        }

        if (this.tail === node) {
            this.tail = this.tail.prev;
        }

        node.next = undefined;
        node.prev = undefined;
    }

    private prepend(node: Node<V>): void {
        if (!this.head) {
            this.head = this.tail = node;
            return;
        }

        this.head.prev = node;
        node.next = this.head;

        this.head = node;
    }

    private trimCache(): void {
        if (this.length <= this.capacity) {
            return;
        }

        const tail = this.tail as Node<V>;
        this.detach(this.tail as Node<V>);

        const key = this.reverseLookup.get(tail) as K;

        this.lookup.delete(key);
        this.reverseLookup.delete(tail);

        this.length--;
    }
}

Complexity

  • Lookup: O(1)
  • Insert: O(1)
  • Delete: O(1)

Because we are using a hash table and a doubly linked list, we can achieve O(1) time complexity for all operations

For example,

  • Lookup: We can get the node from the hash table with the key in O(1) time, then we can get the data from the node in O(1) time
  • Insert: We can create a new node in O(1) time, then we can detach the node from the linked list in O(1) time, then we can prepend the node to the linked list in O(1) time
  • Delete: We can get the node from the hash table with the key in O(1) time, then we can detach the node from the linked list in O(1) time, then we can delete the node from the hash table in O(1) time

Notes

  • LRU cache is a cache that removes the least recently used item when the cache is full
  • We can use a doubly linked list to store the key value pairs
  • We can use a hash table to store the key and the node in the linked list

Wrapping up

"people don't have awesome opportunities, so don't waste it" - The Primeagen