Data Structures in Rust

// Fixed-size array [T; N] - stack-allocated
let mut nums: [i32; 5] = [10, 20, 30, 40, 50];

nums[0] = 99;                        // O(1) - direct index
let third = nums[2];                 // O(1) - read by index

// Iterate and transform
let doubled: Vec<i32> = nums.iter().map(|x| x * 2).collect();

// Search and sort
nums.sort();                         // O(n log n) - in-place
let idx = nums.binary_search(&30);   // O(log n) - Result<usize, usize>
let has = nums.contains(&40);        // O(n) - linear scan
let sum: i32 = nums.iter().sum();    // O(n)

let mut names: Vec<String> = vec!["Alice".into(), "Bob".into()];

names.push("Charlie".into());          // O(1) amortized
names.insert(1, "Diana".into());       // O(n) - shifts elements right
names.remove(0);                       // O(n) - shifts elements left
names.pop();                           // O(1) - remove last

let has = names.contains(&"Bob".into()); // O(n) - linear scan
let first = &names[0];                  // O(1) - direct index

// Sort and dedup
names.sort();                           // O(n log n)
names.dedup();                          // O(n) - remove consecutive dups
names.retain(|n| n.len() > 3);         // O(n) - filter in place

// Vec as stack - push/pop from the end
let mut stack: Vec<i32> = Vec::new();

stack.push(10);                     // O(1)
stack.push(20);
stack.push(30);

let top = stack.last();             // O(1) - peek -> Some(30)
let val = stack.pop();              // O(1) - pop -> Some(30)

// Interview pattern: valid parentheses
fn is_valid(s: &str) -> bool {
    let mut st: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' => st.push(')'),
            '[' => st.push(']'),
            '{' => st.push('}'),
            _ => if st.pop() != Some(c) { return false; },
        }
    }
    st.is_empty()
}

use std::collections::VecDeque;

let mut queue: VecDeque<&str> = VecDeque::new();

queue.push_back("Task A");         // O(1) - enqueue
queue.push_back("Task B");
queue.push_back("Task C");

let front = queue.front();         // O(1) - peek -> Some("Task A")
let val = queue.pop_front();       // O(1) - dequeue -> Some("Task A")

// Interview pattern: BFS level-order
fn bfs(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut q = VecDeque::new();
    let mut result = vec![];
    if let Some(r) = root { q.push_back(r); }
    while !q.is_empty() {
        let level: Vec<i32> = (0..q.len())
            .filter_map(|_| q.pop_front())
            .inspect(|n| { /* push children */ })
            .map(|n| n.borrow().val)
            .collect();
        result.push(level);
    }
    result
}

use std::collections::HashMap;

let mut map: HashMap<&str, i32> = HashMap::new();
map.insert("apple", 3);              // O(1)
map.insert("banana", 5);             // O(1)

map.insert("apple", 10);             // O(1) - update
let has = map.contains_key("banana"); // O(1)
map.remove("banana");                 // O(1)

// Safe lookup with default
let count = map.get("cherry").copied().unwrap_or(0); // O(1)

// Interview pattern: Two Sum
fn two_sum(nums: &[i32], target: i32) -> Vec<usize> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        if let Some(&j) = seen.get(&(target - num)) {
            return vec![j, i];
        }
        seen.insert(num, i);
    }
    vec![]
}

use std::collections::HashSet;

let mut set: HashSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();

set.insert(6);                    // O(1) - true (added)
set.insert(3);                    // O(1) - false (duplicate)
set.remove(&1);                   // O(1)
let has = set.contains(&4);      // O(1) - true

// Set operations
let other: HashSet<i32> = [4, 5, 6, 7].into_iter().collect();
let inter: HashSet<_> = set.intersection(&other).collect(); // {4, 5, 6}
let union: HashSet<_> = set.union(&other).collect();
let diff: HashSet<_> = set.difference(&other).collect();

// Interview pattern: contains duplicate
fn contains_duplicate(nums: &[i32]) -> bool {
    let mut seen = HashSet::new();
    nums.iter().any(|n| !seen.insert(n))  // insert returns false if dup
}

use std::collections::LinkedList;

let mut list = LinkedList::new();

list.push_back(10);              // O(1)
list.push_back(20);
list.push_front(5);             // O(1)

let front = list.front();       // O(1) - peek -> Some(5)
let back = list.back();         // O(1) - peek -> Some(20)
list.pop_front();               // O(1) - remove front
list.pop_back();                // O(1) - remove back

let has = list.contains(&10);   // O(n) - linear scan
let len = list.len();           // O(1)

// Note: std LinkedList has no index access - O(n) traversal only
// For interview problems, prefer defining a custom ListNode:
// struct ListNode { val: i32, next: Option<Box<ListNode>> }

use std::collections::BTreeSet;

let mut sorted = BTreeSet::new();
for &v in &[5, 3, 8, 1, 9] { sorted.insert(v); }
// Maintains sorted order: {1, 3, 5, 8, 9} (B-tree)

sorted.insert(4);                    // O(log n)
sorted.remove(&3);                   // O(log n)
let has = sorted.contains(&8);      // O(log n) - true

let min = sorted.iter().next();      // O(log n) - Some(1)
let max = sorted.iter().next_back(); // O(log n) - Some(9)

// Range queries - powerful for interval problems
let range: Vec<_> = sorted.range(4..9).collect(); // [4, 5, 8]
let range_incl: Vec<_> = sorted.range(4..=9).collect(); // [4, 5, 8, 9]

use std::collections::BTreeMap;

let mut tm = BTreeMap::new();
tm.insert("banana", 2);             // O(log n)
tm.insert("apple", 5);
tm.insert("cherry", 1);
tm.insert("date", 3);

let val = tm.get("apple");          // O(log n) -> Some(5)
tm.remove("cherry");                // O(log n)

// Iterates in sorted key order
for (key, val) in &tm {
    println!("{key}: {val}");        // apple: 5, banana: 2, date: 3
}

// Range and navigation
let first = tm.iter().next();                   // ("apple", 5)
let last = tm.iter().next_back();               // ("date", 3)
let sub: Vec<_> = tm.range("apple"..="cherry").collect();

use std::collections::BinaryHeap;

// Max-heap by default
let mut heap = BinaryHeap::new();

heap.push(30);                     // O(log n)
heap.push(10);
heap.push(20);

let max = heap.peek();             // O(1) - Some(30)
let val = heap.pop();              // O(log n) - Some(30)

// Min-heap: wrap in Reverse
use std::cmp::Reverse;
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(30));
min_heap.push(Reverse(10));
let min = min_heap.pop();          // Some(Reverse(10))

// Build heap from vec - O(n)
let heap = BinaryHeap::from(vec![5, 3, 8, 1, 9]);

use std::collections::HashMap;
use std::sync::{Arc, Mutex};

// Option 1: Mutex + HashMap (standard library)
let cache = Arc::new(Mutex::new(HashMap::<String, i32>::new()));
{
    let mut map = cache.lock().unwrap();    // acquire lock
    map.insert("hits".into(), 0);           // O(1)
    *map.entry("hits".into()).or_insert(0) += 1; // atomic increment
}  // lock released here

// Option 2: dashmap crate (concurrent HashMap, no global lock)
// use dashmap::DashMap;
// let cache = DashMap::new();
// cache.insert("hits", 0);             // O(1) - shard-level lock
// cache.entry("hits").and_modify(|v| *v += 1); // atomic update
// let val = cache.get("hits");         // O(1) - read lock on shard

// Slices &[T] - zero-copy view into contiguous memory
let data = vec![1, 2, 3, 4, 5];
let slice: &[i32] = &data[1..4];       // O(1) - view of [2, 3, 4]

// Mutable slice
let mut buf = vec![10, 20, 30, 40];
let part: &mut [i32] = &mut buf[..2];  // O(1) - mutable view
part[0] = 99;                          // mutates original

// Split without allocation
let (left, right) = data.split_at(3);  // O(1) - [1,2,3] and [4,5]

// Byte slices for binary parsing
let bytes: &[u8] = b"Hello, World!";
let header = &bytes[..5];              // O(1) - b"Hello"
let body = &bytes[7..];               // O(1) - b"World!"

// Chunks for batch processing
for chunk in data.chunks(2) {          // [[1,2], [3,4], [5]]
    println!("{chunk:?}");
}