A1 FA25 Final Exam Review

Table of Contents:

• Preliminaries
• 1. HashMap and the Entry API
• 2. HashSet and Set Operations
• 3. BTreeMap and Ordered Collections
• 4. VecDeque and Circular Buffers
• 5. Iterators and Iterator Chains
• 6. Algorithm Complexity
• 7. Option and Result Types
• Final Tips for the Exam

Suggested way to use this review material

1. The material is organized by major topics.
2. For each topic, there are:
   • high level overview
   • examples
   • true/false questions
   • find the bug questions
   • predict the output questions
   • coding challenges
3. Try to answer the questions without peeking at the solutions.
4. This material focuses on the topics covered in the final third of the course, building on what you learned for midterms 1 and 2.

Exam Format:

The exam will be in four parts:

• Part 1 (10 pts): 5 questions, 2 points each -- select all that are true
• Part 2 (16 pts): 4 questions, 4 points each -- find the bug in the code and fix it
• Part 3 (12 pts): 4 questions, 3 points each -- Predict the output and explain why
• Part 4 (12 pts): 2 questions, 6 points each -- hand-coding problems

Total Points: 50

Suggested time budget for each part:

• Part 1: (~10 min)
• Part 2: (~16 min)
• Part 3: (~12 min)
• Part 4: (~22 min)

for a total of 60 minutes and then another 60 minutes to check your work (if needed).

Preliminaries

The final exam is cumulative but emphasizes the material from the final third of the course. You should be comfortable with:

• Basic Rust syntax (functions, variables, types) (see midterm 1 review)
• Structs, enums, and pattern matching
• Ownership, borrowing, and references
• Generics and traits
• Iterators and closures

See a1 midterm 2 review for more details.

This review focuses on new material: collections (HashMap, HashSet, BTreeMap, VecDeque) and algorithm complexity.

References and Dereferencing

When References Are Created

References are created with &:

#![allow(unused)]
fn main() {
let x = 5;
let r = &x;      // r is &i32
let s = "hello"; // s is already &str (string slice)
let v = vec![1, 2, 3];
let slice = &v[..]; // slice is &[i32]
}

And are common patterns in Rust code. For example, to sum a slice of integers:

#![allow(unused)]
fn main() {
fn process_ints(ints: &[i32]) -> i32 {
    let mut sum = 0;
    for int in ints {
        sum += *int;
    }
    sum
}

let ints = [1, 2, 3];
println!("sum: {}", process_ints(&ints));
}

When Double References (&&) Occur

Double references commonly appear when:

Iterating over a slice of references:

#![allow(unused)]
fn main() {
fn process(words: &[&str]) {
    for word in words {  // word is &&str

        // Rust auto-dereferences `word: &&str` to `word: &str`
        print!("word: {}, len: {} ", word, word.len());
    }
    println!();
}

let words = vec!["art", "bees"];
process(&words);
}

Automatic Dereferencing

Rust automatically dereferences in several situations:

1. Method calls (auto-deref):

#![allow(unused)]
fn main() {
let s = String::from("hello");
let r = &s;
let rr = &&s;
// All of these work - Rust auto-derefs to call len()
s.len();   // String::len(&s)
r.len();   // auto-derefs &String to String
rr.len();  // auto-derefs &&String through &String to String
}

2. Deref coercion in function arguments:

#![allow(unused)]
fn main() {
fn print_len(s: &str) { println!("{}", s.len()); }

let owned = String::from("hello");
print_len(&owned);  // &String coerces to &str automatically
print_len("hello"); // Already a &str
}

3. Comparison operators:

#![allow(unused)]
fn main() {
let x = 5;
let r = &x;
// assert!(r == 5); // ERROR! r is a reference, not a value
assert!(r == &5);  // Compares values, not addresses, but types must match
assert!(*r == 5);  // Explicit deref to i32 also works
}

When Explicit Dereferencing (*) Is Required

1. Assigning to or modifying the underlying value:

#![allow(unused)]
fn main() {
let mut x = 5;
let r = &mut x;
*r += 1;  // Must deref to modify x
println!("x: {}", x);
}

2. When types don't match and coercion doesn't apply:

#![allow(unused)]
fn main() {
let words: &[&str] = &["a", "b"];
for word in words {
    // word is &&str, but HashMap wants &str as key
    let key: &str = *word;  // Explicit deref needed
}
}

3. Using entry() or insert() with reference keys:

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn count<'a>(words: &[&'a str]) -> HashMap<&'a str, i32> {
    let mut map = HashMap::new();
    for word in words {       // word: &&str
        *map.entry(*word)     // *word dereferences &&str to &str
            .or_insert(0) += 1;
    }
    map
}

let words = vec!["a", "b"];
println!("{:?}", count(&words));
println!("{:?}", words);
}

Quick Reference Table

1. HashMap and the Entry API

Module(s)

• Mastering the Entry API

Quick Review

HashMap<K, V> is a hash table that maps keys to values:

• Keys must implement Hash and Eq traits
• O(1) average lookup, insertion, and deletion
• Does NOT maintain insertion order
• f64 cannot be used directly as a key (doesn't implement Hash due to NaN)

Key Methods:

• insert(key, value) - inserts or overwrites
• get(&key) - returns Option<&V>
• get_mut(&key) - returns Option<&mut V>
• contains_key(&key) - returns bool
• remove(&key) - removes and returns Option<V>

The Entry API is the idiomatic way to insert-or-update:

#![allow(unused)]
fn main() {
*map.entry(key).or_insert(default) += 1;
}

• .entry(key) returns an Entry enum, which can be either Occupied or Vacant
• Entry API methods:
  • or_insert(default) inserts the default value if the key is not present
  • or_insert_with(f) inserts the value returned by the function if the key is not present
  • or_default() inserts the default value for the type if the key is not present
  • and_modify(f) modifies the value if the key is present

Examples

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// Basic HashMap usage
let mut scores = HashMap::new();

// .insert returns None if the key was not in the map
let mut result = scores.insert("Alice", 85);
println!("result: {:?}", result); // None, because "Alice" was not in the map

// .insert() returns Some(&value), where value is the old value if the key was
// already in the map
result = scores.insert("Alice", 87);
println!("result: {:?}", result); // Some(&85)

scores.insert("Bob", 90);

// get() returns Option
println!("scores.get(\"Alice\"): {:?}", scores.get("Alice"));  // Some(&85)
println!("scores.get(\"Carol\"): {:?}", scores.get("Carol"));  // None

// unwrap_or provides a default
println!("scores.get(\"Carol\").unwrap_or(&0): {:?}", scores.get("Carol").unwrap_or(&0));  // &0
}

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// Entry API for counting
let mut word_counts = HashMap::new();
for word in ["apple", "banana", "apple"] {
    *word_counts.entry(word).or_insert(0) += 1;
}
// word_counts: {"apple": 2, "banana": 1}
println!("word_counts: {:?}", word_counts);
}

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// Entry API - or_insert only inserts if key is missing
let mut map = HashMap::new();
*map.entry("a").or_insert(0) += 1;  // a = 1
*map.entry("a").or_insert(10) += 1; // a = 2 (10 is NOT used, key exists)
println!("map: {:?}", map);
}

True/False Questions

1. T/F: Keys in a HashMap must implement the Hash and Eq traits.

2. T/F: HashMap maintains insertion order of elements.

3. T/F: f64 can be used directly as a HashMap key.

4. T/F: The entry() API allows efficient insert-or-update operations.

5. T/F: map.get(&key) returns V directly.

6. T/F: Looking up a value by key in a HashMap is O(1) on average.

Find the Bug

Question 1:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn count_words<'a>(words: &[&'a str]) -> HashMap<&'a str, i32> {
    let mut counts = HashMap::new();
    for word in words {
        counts.entry(word).or_insert(0) += 1;
    }
    counts
}
}

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn count_words<'a>(words: &[&'a str]) -> HashMap<&'a str, i32> {
    let mut counts = HashMap::new();
    for word in words {
        *counts.entry(*word).or_insert(0) += 1;
    }
    counts
}
}

Question 2:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn merge_maps(map1: HashMap<String, i32>, map2: HashMap<String, i32>) -> HashMap<String, i32> {
    let mut result = map1;
    for (key, value) in map2 {
        result.insert(key, result.get(&key).unwrap() + value);
    }
    result
}
}

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn merge_maps(map1: HashMap<String, i32>, map2: HashMap<String, i32>) -> HashMap<String, i32> {
    let mut result = map1;
    for (key, value) in map2 {
        *result.entry(key).or_insert(0) += value;
    }
    result
}
}

Predict the Output

Question 1:

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert("Alice", 85);
    scores.insert("Bob", 90);
    scores.insert("Alice", 95);
    
    let alice_score = scores.get("Alice").unwrap_or(&0);
    let carol_score = scores.get("Carol").unwrap_or(&0);
    
    println!("{} {}", alice_score, carol_score);
}

Question 2:

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<&str, i32> = HashMap::new();
    
    *map.entry("a").or_insert(0) += 1;
    *map.entry("b").or_insert(5) += 1;
    *map.entry("a").or_insert(10) += 1;
    
    let a = map.get("a").unwrap();
    let b = map.get("b").unwrap();
    println!("{} {}", a, b);
}

Coding Challenge

Challenge: Implement most_frequent

Write a function that takes a slice of integers and returns the value that appears most frequently. Return None if the slice is empty.

use std::collections::HashMap;

fn most_frequent(numbers: &[i32]) -> Option<i32> {
    // Your code here
}

fn main() {
    let nums = vec![1, 2, 2, 3, 3, 3, 4];
    println!("{:?}", most_frequent(&nums)); // Should print Some(3)
    println!("{:?}", most_frequent(&[]));   // Should print None
}

use std::collections::HashMap;

fn most_frequent(numbers: &[i32]) -> Option<i32> {
    if numbers.is_empty() {
        return None;
    }
    
    let mut counts = HashMap::new();
    for &num in numbers {
        *counts.entry(num).or_insert(0) += 1;
    }
    
    counts.into_iter()
        .max_by_key(|&(_, count)| count)
        .map(|(num, _)| num)
}

fn main() {
    let nums = vec![1, 2, 2, 3, 3, 3, 4];
    println!("{:?}", most_frequent(&nums)); // Should print Some(3)
    println!("{:?}", most_frequent(&[]));   // Should print None
}

2. HashSet and Set Operations

Quick Review

HashSet stores unique values:

• Elements must implement Hash and Eq traits
• O(1) average lookup, insertion, deletion
• Automatically removes duplicates
• Does NOT maintain insertion order

Key Methods:

• insert(value) - returns bool (true if new)
• contains(&value) - returns bool (true if value is in the set)
• remove(&value) - returns bool (true if value was in the set)

Set Operations:

• intersection(&other) - returns a set with elements in both sets
• union(&other) - returns a set with elements in either set
• difference(&other) - returns a set with elements in self but not other
• symmetric_difference(&other) - returns a set with elements in one but not both

Examples

#![allow(unused)]
fn main() {
use std::collections::HashSet;

// Creating HashSets
let set1: HashSet<i32> = vec![1, 2, 3, 4].into_iter().collect();
let set2: HashSet<i32> = vec![3, 4, 5, 6].into_iter().collect();

// Set operations
let inter: HashSet<_> = set1.intersection(&set2).copied().collect();
println!("inter: {:?}", inter); // inter = {3, 4}

let uni: HashSet<_> = set1.union(&set2).copied().collect();
println!("uni: {:?}", uni); // uni = {1, 2, 3, 4, 5, 6}

let diff: HashSet<_> = set1.difference(&set2).copied().collect();
println!("diff: {:?}", diff); // diff = {1, 2} (in set1 but not set2)

let sym_diff: HashSet<_> = set1.symmetric_difference(&set2).copied().collect();
println!("sym_diff: {:?}", sym_diff); // sym_diff = {1, 2, 5, 6}

// Checking membership
let has_three = set1.contains(&3);  // true
println!("has_three: {}", has_three);

// HashSet for uniqueness
let words = vec!["apple", "banana", "apple", "cherry"];
let unique: HashSet<_> = words.into_iter().collect();
println!("unique: {:?}", unique); // unique = {"apple", "banana", "cherry"}
}

True/False Questions

1. T/F: HashSet automatically removes duplicate values.

2. T/F: Elements in a HashSet must implement Hash and Eq traits.

3. T/F: HashSet maintains elements in sorted order.

4. T/F: The intersection() method returns elements common to two sets.

5. T/F: Checking if an element exists in a HashSet is O(n).

Find the Bug

Question:

#![allow(unused)]
fn main() {
use std::collections::HashSet;

fn find_common<T: PartialEq>(set1: &HashSet<T>, set2: &HashSet<T>) -> HashSet<T> {
    set1.intersection(set2).cloned().collect()
}
}

#![allow(unused)]
fn main() {
use std::collections::HashSet;
use std::hash::Hash;

fn find_common<T: Hash + Eq + Clone>(set1: &HashSet<T>, set2: &HashSet<T>) -> HashSet<T> {
    set1.intersection(set2).cloned().collect()
}
}

Predict the Output

Question:

use std::collections::HashSet;

fn main() {
    let set1: HashSet<&str> = vec!["apple", "banana", "cherry"].into_iter().collect();
    let set2: HashSet<&str> = vec!["cherry", "date", "elderberry"].into_iter().collect();
    
    let inter: HashSet<_> = set1.intersection(&set2).copied().collect();
    println!("inter: {:?}", inter);

    let diff: HashSet<_> = set1.difference(&set2).copied().collect();
    println!("diff: {:?}", diff);

    let sym_diff: HashSet<_> = set1.symmetric_difference(&set2).copied().collect();
    println!("sym_diff: {:?}", sym_diff);
    
    println!("{} {} {}", inter.len(), diff.len(), sym_diff.len());
}

inter: {"cherry"}
diff: {"banana", "apple"}
sym_diff: {"elderberry", "apple", "date", "banana"}
1 2 4

Coding Challenge

Challenge: Find duplicates

Write a function that takes a slice of integers and returns a Vec containing only the values that appear more than once. The result should not contain duplicates itself.

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

fn find_duplicates(numbers: &[i32]) -> Vec<i32> {
    // Your code here
}

fn main() {
    let nums = vec![1, 2, 2, 3, 3, 3, 4, 5, 5];
    println!("{:?}", find_duplicates(&nums)); // [2, 3, 5] (order may vary)
}

use std::collections::HashSet;

fn find_duplicates(numbers: &[i32]) -> Vec<i32> {
    let mut seen = HashSet::new();
    let mut duplicates = HashSet::new();
    
    for &num in numbers {
        if !seen.insert(num) {
            // insert returns false if value already existed
            duplicates.insert(num);
        }
    }
    
    duplicates.into_iter().collect()
}

fn main() {
    let nums = vec![1, 2, 2, 3, 3, 3, 4, 5, 5];
    println!("{:?}", find_duplicates(&nums)); // [2, 3, 5] (order may vary)
}

3. BTreeMap and Ordered Collections

Quick Review

BTreeMap<K, V> is a sorted map based on B-trees:

• Keys are always in sorted order
• Keys must implement Ord trait (not Hash)
• O(log n) lookup, insertion, deletion
• Efficient for range queries
• Iteration yields key-value pairs in sorted key order

When to use BTreeMap vs HashMap:

• HashMap: faster single-key operations (O(1) vs O(log n))
• BTreeMap: need sorted order, range queries, or keys don't implement Hash

Examples

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "three");
map.insert(1, "one");
map.insert(4, "four");

// Iteration is in sorted key order
for (k, v) in map.iter() {
    println!("{}: {}", k, v);
}
// Output:
// 1: one
// 3: three
// 4: four

// First and last keys
let first = map.keys().next();      // Some(&1)
let last = map.keys().last();       // Some(&4)

// Range queries
for (k, v) in map.range(2..=4) {
    println!("{}: {}", k, v);
}
// Output: 3: three, 4: four
}

True/False Questions

1. T/F: BTreeMap stores keys in sorted order.

2. T/F: Insertion into a BTreeMap is O(1).

3. T/F: BTreeMap requires keys to implement the Hash trait.

4. T/F: Iterating over a BTreeMap yields key-value pairs in sorted key order.

5. T/F: BTreeMap is faster than HashMap for all operations.

Predict the Output

Question:

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();
    scores.insert("Charlie", 85);
    scores.insert("Alice", 95);
    scores.insert("Bob", 90);
    
    let first_key = scores.keys().next().unwrap();
    let last_key = scores.keys().last().unwrap();
    println!("{} {}", first_key, last_key);
}

4. VecDeque and Circular Buffers

Quick Review

VecDeque is a double-ended queue:

• O(1) push/pop from both ends
• Implemented as a circular/ring buffer
• Can be used as a stack OR a queue
• Grows dynamically like Vec

Key Methods:

• push_front(value) - add to front
• push_back(value) - add to back
• pop_front() - remove from front, returns Option<T>
• pop_back() - remove from back, returns Option<T>
• front() / back() - peek without removing

Use Cases:

• Queue (FIFO): push_back + pop_front
• Stack (LIFO): push_back + pop_back
• Rolling windows / circular buffers

Examples

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

let mut deque: VecDeque<i32> = VecDeque::new();

// Building a deque
deque.push_back(1);   // [1]
deque.push_back(2);   // [1, 2]
deque.push_front(3);  // [3, 1, 2]
deque.push_back(4);   // [3, 1, 2, 4]

// Removing elements
let front = deque.pop_front();  // Some(3), deque is [1, 2, 4]
let back = deque.pop_back();    // Some(4), deque is [1, 2]

// Using as a queue (FIFO)
let mut queue = VecDeque::new();
queue.push_back("first");
queue.push_back("second");
let next = queue.pop_front();  // Some("first")

// Iteration
for val in deque.iter() {
    println!("{}", val);
}
}

True/False Questions

1. T/F: VecDeque allows efficient O(1) insertion and removal at both ends.

2. T/F: VecDeque is implemented as a circular buffer.

3. T/F: VecDeque can only store elements that implement Copy.

4. T/F: push_front() and push_back() are the primary insertion methods.

5. T/F: VecDeque maintains elements in sorted order.

6. T/F: VecDeque::push_front() is O(n).

Predict the Output

Question 1:

use std::collections::VecDeque;

fn main() {
    let mut buffer: VecDeque<i32> = VecDeque::new();
    buffer.push_back(1);
    buffer.push_back(2);
    buffer.push_front(3);
    buffer.push_back(4);
    buffer.pop_front();
    
    let sum: i32 = buffer.iter().sum();
    println!("{}", sum);
}

Question 2:

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::new();
    q.push_back(10);
    q.push_back(20);
    q.push_back(30);
    
    let first = q.pop_front().unwrap();
    q.push_back(first + 5);
    
    for val in q.iter() {
        print!("{} ", val);
    }
    println!();
}

Coding Challenge

Challenge: Implement a Rolling Average

Write a function that calculates the running (cumulative) average at each position. The running average at position i is the mean of all elements from index 0 to i.

fn running_average(values: &[f64]) -> Vec<f64> {
    // Your code here
}

fn main() {
    let data = vec![2.0, 4.0, 6.0, 8.0];
    let result = running_average(&data);
    println!("{:?}", result); // Should print [2.0, 3.0, 4.0, 5.0]
}

fn running_average(values: &[f64]) -> Vec<f64> {
    let mut result = Vec::new();
    let mut sum = 0.0;
    
    for (i, &value) in values.iter().enumerate() {
        sum += value;
        let avg = sum / (i + 1) as f64;
        result.push(avg);
    }
    
    result
}

fn main() {
    let data = vec![2.0, 4.0, 6.0, 8.0];
    let result = running_average(&data);
    println!("{:?}", result); // Should print [2.0, 3.0, 4.0, 5.0]
}

5. Iterators and Iterator Chains

Quick Review

Iterator Creation:

• iter() - yields &T (immutable references)
• iter_mut() - yields &mut T (mutable references)
• into_iter() - consumes collection, yields owned T

Key Iterator Methods:

• map(|x| ...) - transform each element
• filter(|x| ...) - keep elements matching predicate
• fold(init, |acc, x| ...) - accumulate into single value
• collect() - consume iterator into collection
• sum() - sum all elements
• count() - count elements
• take(n) - take first n elements
• skip(n) - skip first n elements
• enumerate() - yields (index, value) pairs

Important: Iterator adaptors (map, filter, etc.) are lazy - they don't execute until consumed by a method like collect(), sum(), or for loop.

Examples

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3, 4, 5, 6];

// Filter and map
let result: Vec<i32> = numbers.iter()
    .filter(|&&x| x % 2 == 0)  // keep even: [2, 4, 6]
    .map(|x| x * 2)            // double: [4, 8, 12]
    .collect();

// Sum
let sum: i32 = numbers.iter().sum();  // 21

// Filter, map, take
let result: Vec<i32> = numbers.iter()
    .filter(|&&x| x % 2 == 1)  // keep odd: [1, 3, 5]
    .map(|x| x * x)            // square: [1, 9, 25]
    .take(2)                   // first 2: [1, 9]
    .collect();

// Enumerate
for (i, val) in numbers.iter().enumerate() {
    println!("Index {}: {}", i, val);
}

// Fold for custom accumulation
let product: i32 = numbers.iter()
    .fold(1, |acc, x| acc * x);  // 720
}

True/False Questions

1. T/F: Iterator methods like map() and filter() are lazily evaluated.

2. T/F: The collect() method transforms an iterator into a collection.

3. T/F: Calling .iter() on a Vec transfers ownership of the elements.

4. T/F: The fold() method requires an initial accumulator value.

5. T/F: Iterator chains are evaluated from right to left.

Find the Bug

Question 1:

#![allow(unused)]
fn main() {
fn double_evens(numbers: &[i32]) -> Vec<i32> {
    numbers.iter()
        .filter(|&x| x % 2 == 0)
        .map(|x| x * 2)
}
}

#![allow(unused)]
fn main() {
fn double_evens(numbers: &[i32]) -> Vec<i32> {
    numbers.iter()
        .filter(|&x| x % 2 == 0)
        .map(|x| x * 2)
        .collect()
}
}

Question 2:

#![allow(unused)]
fn main() {
fn sum_positive(numbers: &[i32]) -> i32 {
    numbers.iter()
        .filter(|x| x > 0)
        .sum()
}
}

#![allow(unused)]
fn main() {
fn sum_positive(numbers: &[i32]) -> i32 {
    numbers.iter()
        .filter(|&&x| x > 0)  // or .filter(|x| **x > 0)
        .sum()
}
}

Predict the Output

Question 1:

fn main() {
    let numbers = vec![1, 2, 3, 4, 5, 6];
    let result: Vec<i32> = numbers.iter()
        .filter(|&x| x % 2 == 1)
        .map(|x| x * x)
        .take(2)
        .collect();
    println!("{:?}", result);
}

Question 2:

fn main() {
    let data = vec![10, 20, 30, 40, 50];
    let result: i32 = data.iter()
        .skip(1)
        .take(3)
        .filter(|&&x| x > 25)
        .sum();
    println!("{}", result);
}

Question 3:

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    
    let sum: i32 = numbers.iter()
        .enumerate()
        .filter(|(i, _)| i % 2 == 0)
        .map(|(_, v)| v)
        .sum();
    
    println!("{}", sum);
}

Coding Challenge

Challenge: Count elements in range

Write a function that counts how many elements in a slice fall within a given range [low, high] (inclusive).

fn count_in_range(numbers: &[i32], low: i32, high: i32) -> usize {
    // Your code here - use iterator methods
}

fn main() {
    let nums = vec![1, 5, 10, 15, 20, 25];
    println!("{}", count_in_range(&nums, 5, 20)); // Should print 4
}

fn count_in_range(numbers: &[i32], low: i32, high: i32) -> usize {
    numbers.iter()
        .filter(|&&x| x >= low && x <= high)
        .count()
}

fn main() {
    let nums = vec![1, 5, 10, 15, 20, 25];
    println!("{}", count_in_range(&nums, 5, 20)); // Should print 4
}

6. Algorithm Complexity

Quick Review

Big O Notation describes how runtime grows with input size:

Common Operations:

*amortized

Graph Algorithms:

• BFS (Breadth-First Search): uses a queue (FIFO)
• DFS (Depth-First Search): uses a stack (LIFO)

True/False Questions

1. T/F: A Vec::push() operation is O(1) amortized.

2. T/F: Searching for a key in a HashMap is O(n) in the average case.

3. T/F: Sorting a vector with .sort() is O(n log n).

4. T/F: Graph BFS traversal uses a queue data structure.

5. T/F: Inserting into a BTreeMap is O(1).

7. Option and Result Types

Quick Review

Option - for values that might not exist:

• Some(value) - contains a value
• None - no value

Result<T, E> - for operations that might fail:

• Ok(value) - success with value
• Err(error) - failure with error

Common Methods:

• unwrap() - get value or panic
• unwrap_or(default) - get value or default
• unwrap_or_else(|| ...) - get value or compute default
• ? operator - propagate errors (Result) or None (Option)
• is_some() / is_ok() - check variant
• map(|x| ...) - transform if Some/Ok

Examples

#![allow(unused)]
fn main() {
// Option
let maybe_value: Option<i32> = Some(5);
let no_value: Option<i32> = None;

let x = maybe_value.unwrap_or(0);  // 5
let y = no_value.unwrap_or(0);     // 0

// Result
fn divide(a: i32, b: i32) -> Result<i32, String> {
    if b == 0 {
        Err(String::from("division by zero"))
    } else {
        Ok(a / b)
    }
}

let result = divide(10, 2);  // Ok(5)
let error = divide(10, 0);   // Err("division by zero")

// Using ? to propagate
fn calculate(a: i32, b: i32) -> Result<i32, String> {
    let quotient = divide(a, b)?;  // Returns Err early if divide fails
    Ok(quotient * 2)
}
}

True/False Questions

1. T/F: Option::unwrap() will panic if the value is None.

2. T/F: The ? operator can be used to propagate errors from Result.

3. T/F: Some(5) and None are both variants of Option<i32>.

4. T/F: Result<T, E> is used for operations that might fail with an error.

5. T/F: unwrap_or(default) returns the contained value or a provided default.

Final Tips for the Exam

1. HashMap vs BTreeMap: Use HashMap for fast O(1) lookups. Use BTreeMap when you need sorted keys or range queries.

2. Entry API: Always use entry().or_insert() for counting patterns instead of get().unwrap().

3. HashSet trait bounds: Remember that HashSet requires Hash + Eq, not just PartialEq.

4. Iterator laziness: Remember to call .collect() or another consumer - map/filter alone don't execute!

5. Reference patterns in closures:

   • iter() yields &T
   • filter(|x| ...) receives &&T when used with iter()
   • Use |&x| or |&&x| to destructure

6. VecDeque for both ends: Use VecDeque when you need efficient push/pop from both front and back.

7. Complexity matters: Know that HashMap is O(1), BTreeMap is O(log n), and sorting is O(n log n).

8. Understand references and when to dereference: Remember that iterators yield references, not values.

9. Review the preliminaries as well!

Good luck on your final exam! 🦀