Data Structures & Algorithms

fn main() {
    let mut v: Vec<i32> = Vec::with_capacity(4);
    v.push(10);
    v.push(20);
    v.extend([30, 40, 50]);

    println!("len = {}, first = {}, last = {:?}", v.len(), v[0], v.last());
    println!("slice [1..3] = {:?}", &v[1..3]);
    println!("contains 30? {}", v.contains(&30));
    println!("get(99) = {:?}", v.get(99));

    v.insert(0, 5); // O(n): shifts every element right
    v.retain(|&x| x % 20 != 0);
    println!("{:?}", v);
}

struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self { Stack { items: Vec::new() } }
    fn push(&mut self, value: T) { self.items.push(value); }
    fn pop(&mut self) -> Option<T> { self.items.pop() }
    fn peek(&self) -> Option<&T> { self.items.last() }
    fn len(&self) -> usize { self.items.len() }
}

fn main() {
    let mut s = Stack::new();
    s.push("a");
    s.push("b");
    s.push("c");
    println!("peek = {:?}, len = {}", s.peek(), s.len());
    while let Some(top) = s.pop() {
        print!("{} ", top);
    }
    println!();
    println!("empty pop = {:?}", s.pop());
}

use std::collections::HashMap;

fn main() {
    let text = "the cat and the hat and the bat";
    let mut counts: HashMap<&str, usize> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }

    println!("the = {}", counts["the"]);
    println!("dog = {:?}", counts.get("dog"));

    // HashMap order is random per run: sort before printing.
    let mut pairs: Vec<(&str, usize)> = counts.into_iter().collect();
    pairs.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
    for (word, n) in pairs {
        println!("{word}: {n}");
    }
}

use std::collections::{BTreeMap, HashSet};

fn main() {
    let mut scores = BTreeMap::new();
    scores.insert("mia", 91);
    scores.insert("ada", 88);
    scores.insert("zed", 75);
    scores.insert("bob", 88);

    // BTreeMap iterates in sorted key order, every run.
    for (name, score) in &scores {
        println!("{name} {score}");
    }
    let first_half: Vec<_> = scores.range("a".."m").map(|(k, _)| *k).collect();
    println!("names before m: {:?}", first_half);

    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5].into_iter().collect();
    let mut both: Vec<_> = a.intersection(&b).copied().collect();
    both.sort();
    println!("in both: {:?}, 5 in a? {}", both, a.contains(&5));
}

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    queue.push_back("ada");
    queue.push_back("bob");
    queue.push_back("cy");
    println!("serving {:?}", queue.pop_front());
    println!("serving {:?}", queue.pop_front());

    // A deque works from both ends.
    queue.push_front("vip");
    queue.push_back("dee");
    println!("front = {:?}, back = {:?}", queue.front(), queue.back());
    println!("all = {:?}", queue);

    let v: Vec<_> = queue.into_iter().collect();
    println!("as vec = {:?}", v);
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut max_heap = BinaryHeap::from(vec![4, 9, 1, 7]);
    max_heap.push(5);
    print!("max-heap pops:");
    while let Some(x) = max_heap.pop() {
        print!(" {x}");
    }
    println!();

    let mut min_heap = BinaryHeap::new();
    for x in [4, 9, 1, 7, 5] {
        min_heap.push(Reverse(x));
    }
    let Reverse(smallest) = min_heap.pop().unwrap();
    println!("smallest = {smallest}, next = {:?}", min_heap.peek());

    // Tasks: lowest number = most urgent.
    let mut tasks = BinaryHeap::new();
    tasks.push(Reverse((2, "write tests")));
    tasks.push(Reverse((1, "fix outage")));
    tasks.push(Reverse((3, "update docs")));
    while let Some(Reverse((p, task))) = tasks.pop() {
        println!("p{p}: {task}");
    }
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

// Top-k largest: keep a min-heap of size k. O(n log k).
fn top_k(nums: &[i32], k: usize) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for &n in nums {
        heap.push(Reverse(n));
        if heap.len() > k {
            heap.pop(); // drop the smallest of the k+1
        }
    }
    let mut out: Vec<i32> = heap.into_iter().map(|Reverse(n)| n).collect();
    out.sort_unstable_by(|a, b| b.cmp(a));
    out
}

fn main() {
    println!("{:?}", top_k(&[5, 1, 9, 3, 7, 8, 2], 3));
}

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct List {
    head: Option<Box<Node>>,
    len: usize,
}

impl List {
    fn new() -> Self { List { head: None, len: 0 } }

    fn push_front(&mut self, value: i32) {
        // take() moves the old head out, leaving None behind.
        let old = self.head.take();
        self.head = Some(Box::new(Node { value, next: old }));
        self.len += 1;
    }

    fn pop_front(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.value
        })
    }

    fn reverse(&mut self) {
        let mut prev: Option<Box<Node>> = None;
        let mut cur = self.head.take();
        while let Some(mut node) = cur {
            cur = node.next.take();
            node.next = prev;
            prev = Some(node);
        }
        self.head = prev;
    }

    fn to_vec(&self) -> Vec<i32> {
        let mut out = Vec::new();
        let mut cur = &self.head;
        while let Some(node) = cur {
            out.push(node.value);
            cur = &node.next;
        }
        out
    }
}

fn main() {
    let mut list = List::new();
    for x in [3, 2, 1] {
        list.push_front(x);
    }
    println!("{:?} len={}", list.to_vec(), list.len);
    list.reverse();
    println!("reversed {:?}", list.to_vec());
    println!("pop {:?}, now {:?}", list.pop_front(), list.to_vec());
}

#[derive(Debug)]
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn insert(slot: &mut Option<Box<Node>>, value: i32) {
    match slot {
        None => *slot = Some(Box::new(Node { value, left: None, right: None })),
        Some(node) if value < node.value => insert(&mut node.left, value),
        Some(node) if value > node.value => insert(&mut node.right, value),
        Some(_) => {} // duplicate: ignore
    }
}

fn contains(slot: &Option<Box<Node>>, value: i32) -> bool {
    match slot {
        None => false,
        Some(node) if value == node.value => true,
        Some(node) if value < node.value => contains(&node.left, value),
        Some(node) => contains(&node.right, value),
    }
}

fn in_order(slot: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(node) = slot {
        in_order(&node.left, out);
        out.push(node.value);
        in_order(&node.right, out);
    }
}

fn height(slot: &Option<Box<Node>>) -> usize {
    match slot {
        None => 0,
        Some(n) => 1 + height(&n.left).max(height(&n.right)),
    }
}

fn main() {
    let mut root = None;
    for v in [50, 30, 70, 20, 40, 60, 80, 30] {
        insert(&mut root, v);
    }
    let mut sorted = Vec::new();
    in_order(&root, &mut sorted);
    println!("in-order: {:?}", sorted);
    println!("has 60? {}  has 65? {}", contains(&root, 60), contains(&root, 65));
    println!("height = {}", height(&root));
}

use std::collections::VecDeque;

fn bfs(adj: &Vec<Vec<usize>>, start: usize) -> (Vec<usize>, Vec<Option<usize>>) {
    let mut dist = vec![None; adj.len()];
    let mut order = Vec::new();
    let mut queue = VecDeque::new();
    dist[start] = Some(0);
    queue.push_back(start);
    while let Some(u) = queue.pop_front() {
        order.push(u);
        for &v in &adj[u] {
            if dist[v].is_none() {
                dist[v] = Some(dist[u].unwrap() + 1);
                queue.push_back(v);
            }
        }
    }
    (order, dist)
}

fn dfs(adj: &Vec<Vec<usize>>, u: usize, seen: &mut Vec<bool>, order: &mut Vec<usize>) {
    seen[u] = true;
    order.push(u);
    for &v in &adj[u] {
        if !seen[v] {
            dfs(adj, v, seen, order);
        }
    }
}

fn main() {
    // 0 - 1, 0 - 2, 1 - 3, 2 - 3, 3 - 4   (5 is isolated)
    let edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)];
    let mut adj = vec![Vec::new(); 6];
    for &(a, b) in &edges {
        adj[a].push(b);
        adj[b].push(a);
    }

    let (order, dist) = bfs(&adj, 0);
    println!("BFS order: {:?}", order);
    println!("distance:  {:?}", dist);

    let mut seen = vec![false; adj.len()];
    let mut dfs_order = Vec::new();
    dfs(&adj, 0, &mut seen, &mut dfs_order);
    println!("DFS order: {:?}", dfs_order);
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn dijkstra(adj: &Vec<Vec<(usize, u64)>>, start: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; adj.len()];
    let mut heap = BinaryHeap::new();
    dist[start] = 0;
    heap.push(Reverse((0u64, start)));
    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue; // stale entry: a shorter path was already found
        }
        for &(v, w) in &adj[u] {
            let nd = d + w;
            if nd < dist[v] {
                dist[v] = nd;
                heap.push(Reverse((nd, v)));
            }
        }
    }
    dist
}

fn main() {
    let mut adj = vec![Vec::new(); 4];
    adj[0].push((1, 4));
    adj[0].push((2, 1));
    adj[2].push((1, 2));
    adj[1].push((3, 1));
    println!("{:?}", dijkstra(&adj, 0));
}

fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    let (mut lo, mut hi) = (0, items.len()); // search [lo, hi)
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if items[mid] == target {
            return Some(mid);
        } else if items[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    None
}

fn main() {
    let v = [2, 5, 8, 12, 16, 23, 38];
    println!("by hand: {:?} {:?}", binary_search(&v, 23), binary_search(&v, 7));
    println!("std:     {:?} {:?}", v.binary_search(&23), v.binary_search(&7));

    let mut sorted = vec![10, 20, 40];
    let pos = sorted.binary_search(&30).unwrap_or_else(|i| i);
    sorted.insert(pos, 30);
    println!("inserted: {:?}", sorted);

    // partition_point: first index where the predicate turns false.
    println!("first >= 12 at {}", v.partition_point(|&x| x < 12));
}

#[derive(Debug)]
struct Player {
    name: &'static str,
    score: u32,
    age: u32,
}

fn main() {
    let mut nums = vec![5, 3, 9, 1, 3];
    nums.sort_unstable();
    println!("{:?}", nums);
    nums.sort_by(|a, b| b.cmp(a)); // descending
    println!("{:?}", nums);

    let mut players = vec![
        Player { name: "zoe", score: 90, age: 30 },
        Player { name: "ann", score: 75, age: 25 },
        Player { name: "bob", score: 90, age: 22 },
    ];
    players.sort_by_key(|p| p.age);
    let names: Vec<_> = players.iter().map(|p| p.name).collect();
    println!("by age: {:?}", names);

    players.sort_by(|a, b| b.score.cmp(&a.score).then_with(|| a.name.cmp(b.name)));
    for p in &players {
        println!("{} {} {}", p.name, p.score, p.age);
    }

    let mut prices: Vec<f64> = vec![3.5, 1.25, 2.0];
    prices.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", prices);
}

fn merge_sort(v: &[i32]) -> Vec<i32> {
    if v.len() <= 1 {
        return v.to_vec();
    }
    let mid = v.len() / 2;
    let (left, right) = (merge_sort(&v[..mid]), merge_sort(&v[mid..]));
    let mut out = Vec::with_capacity(v.len());
    let (mut i, mut j) = (0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            out.push(left[i]);
            i += 1;
        } else {
            out.push(right[j]);
            j += 1;
        }
    }
    out.extend_from_slice(&left[i..]);
    out.extend_from_slice(&right[j..]);
    out
}

fn main() {
    println!("{:?}", merge_sort(&[38, 27, 43, 3, 9, 82, 10]));
}

use std::collections::HashMap;

fn fib_naive(n: u64, calls: &mut u64) -> u64 {
    *calls += 1;
    if n < 2 { n } else { fib_naive(n - 1, calls) + fib_naive(n - 2, calls) }
}

fn fib_memo(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n < 2 {
        return n;
    }
    if let Some(&v) = memo.get(&n) {
        return v;
    }
    let v = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    memo.insert(n, v);
    v
}

fn fib_table(n: usize) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        (a, b) = (b, a + b);
    }
    a
}

fn main() {
    let mut calls = 0;
    println!("naive fib(25) = {} after {} calls", fib_naive(25, &mut calls), calls);
    println!("memo  fib(90) = {}", fib_memo(90, &mut HashMap::new()));
    println!("table fib(90) = {}", fib_table(90));
}

// dp[a] = fewest coins that sum to exactly a, or None if impossible.
fn min_coins(coins: &[usize], amount: usize) -> Option<usize> {
    let mut dp: Vec<Option<usize>> = vec![None; amount + 1];
    dp[0] = Some(0);
    for a in 1..=amount {
        for &c in coins {
            if c <= a {
                if let Some(prev) = dp[a - c] {
                    dp[a] = Some(match dp[a] {
                        Some(best) => best.min(prev + 1),
                        None => prev + 1,
                    });
                }
            }
        }
    }
    dp[amount]
}

fn lcs(a: &str, b: &str) -> usize {
    let (a, b): (Vec<char>, Vec<char>) = (a.chars().collect(), b.chars().collect());
    let mut dp = vec![vec![0; b.len() + 1]; a.len() + 1];
    for i in 1..=a.len() {
        for j in 1..=b.len() {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }
    dp[a.len()][b.len()]
}

fn main() {
    println!("coins for 11 with [1,2,5]: {:?}", min_coins(&[1, 2, 5], 11));
    println!("coins for 3 with [2]: {:?}", min_coins(&[2], 3));
    println!("LCS(\"abcde\", \"ace\") = {}", lcs("abcde", "ace"));
}