Rust Built-In Data Structures for Coding Interviews

You picked Rust for your coding interview. The borrow checker is about to become your fourth panel of interviewers, and unlike the humans, it gives zero partial credit.

The good news: Rust's standard library ships with exactly the collections you need for 95% of interview problems. The bad news: each one carries ownership semantics that Java or Python never forced you to think about, and the worst moment to discover them is during a live screen. This guide covers every collection you'll actually reach for, the complexity behind each, and the traps that turn a working solution into a compile error at the worst possible time.

---

Seven Collections Cover 95% of Rust Interviews

Pick the right one in under ten seconds.

Problem type	Collection	Key tradeoff
Dynamic array, stack operations	Vec<T>	O(1) amortized push; O(n) front removal
Frequency count, memoization, visited	HashMap<K, V>	O(1) avg; unordered
Membership only	HashSet<T>	O(1) avg; no values
Sorted keys, range queries, floor/ceil	BTreeMap<K, V>	O(log n) all ops; ordered
Sorted unique values	BTreeSet<T>	O(log n); predecessor/successor
Top-K, Dijkstra, task scheduling	BinaryHeap<T>	O(log n) push/pop; max-heap
BFS queue, monotonic deque	VecDeque<T>	O(1) both ends

---

Vec<T>: The One You Always Start With

Every interview sequence starts as a Vec. It is a contiguous heap allocation that doubles capacity on growth, giving amortized O(1) push. Dynamic array analysis applies directly.

let mut v: Vec<i32> = Vec::new();
let mut v2: Vec<i32> = Vec::with_capacity(100);

v.push(3);
v.push(1);
v.push(4);

v.pop();                             // O(1), returns Option<T>
v.len();                             // O(1)
v[0];                                // O(1), panics on OOB
v.get(0);                            // O(1), returns Option<&T>

v.sort_unstable();                   // O(n log n)
v.sort_unstable_by(|a, b| b.cmp(a)); // descending
v.sort_unstable_by_key(|x| -x);      // sort by derived key

Operation	Time
push / pop (back)	O(1) amortized
Insert / remove at index	O(n)
Index access	O(1)
contains	O(n)
sort_unstable	O(n log n)

Prefer sort_unstable over sort. The stable variant allocates a scratch buffer to preserve equal-element order. For interviews that guarantee is almost never needed, and sort_unstable is measurably faster.

v.remove(i) is O(n): it shifts every element right of i leftward. If order doesn't matter, v.swap_remove(i) is O(1). It copies the last element into position i and shortens the vector by one. Interviewers love this as a follow-up. Know it before you need it.

---

HashMap<K, V> and HashSet<T>: The Interview Workhorses

Rust's HashMap uses SipHash 1-3 by default, which is DoS-resistant. For interview problems with no adversarial input you won't notice the speed difference. O(1) lookup analysis applies here. What you will notice is the entry API, which exists to prevent you from doing something terrible.

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

let mut freq: HashMap<char, i32> = HashMap::new();

*freq.entry('a').or_insert(0) += 1;

freq.get(&'a');             // Option<&i32>
freq.contains_key(&'a');    // bool, O(1)
freq.remove(&'a');          // O(1), returns Option<V>
freq.len();                 // O(1)

for (k, v) in &freq { /* borrows */ }
for (k, v) in freq  { /* consumes */ }

Operation	Time
get / contains_key	O(1) avg
insert / remove	O(1) avg
Full iteration	O(capacity)

The entry API is not optional. Writing if map.contains_key(k) { ... } else { map.insert(k, v) } performs two lookups and two borrow checks. The borrow checker doesn't think that's fine, and neither should you. entry() does both in one:

*counts.entry(word).or_insert(0) += 1;
map.entry(key).or_insert_with(|| expensive_computation());

HashSet is HashMap with unit values. Same complexity, no .entry() needed:

let mut seen: HashSet<(i32, i32)> = HashSet::new();
seen.insert((0, 0));
seen.contains(&(0, 0));  // O(1)

---

BTreeMap<K, V> and BTreeSet<T>: When Order Actually Matters

BTreeMap stores keys in sorted order via a B-tree (not a red-black tree like C++'s std::map). Every key access is O(log n), but the payoff is range queries, ordered iteration, and floor/ceiling lookups that HashMap simply cannot do.

use std::collections::BTreeMap;

let mut map: BTreeMap<i32, &str> = BTreeMap::new();
map.insert(10, "ten");
map.insert(5,  "five");
map.insert(20, "twenty");

// range query: O(log n + k) where k is elements returned
for (k, v) in map.range(5..=15) {
    println!("{}: {}", k, v);
}

map.keys().next();          // smallest key, O(log n)
map.keys().next_back();     // largest key, O(log n)

// predecessor: largest key strictly less than 8
map.range(..8).next_back(); // Some((&5, &"five"))

Operation	Time
get / insert / remove	O(log n)
range query	O(log n + k)
First / last key	O(log n)
Full iteration	O(n)

Pick BTreeMap when the problem mentions "find the smallest X larger than Y", "all events in a time window", or "median of a stream". Pick HashMap when you only need O(1) point lookups and order is irrelevant.

BTreeSet gives sorted unique membership with the same range API. Predecessor lookup is set.range(..val).next_back() and successor is set.range(val+1..).next(). Memorize those two. They show up constantly in interval and sweep problems.

---

BinaryHeap<T>: Max-Heap by Default (Yes, Really, Max)

Rust's BinaryHeap is a max-heap. pop() returns the largest element. This is the exact opposite of Python's heapq. Forgetting it once during practice is fine. Forgetting it live, on a minimum-cost problem, watching your solution pass the first two test cases and then explode spectacularly on the third, that's an experience. More detail on the underlying structure is at the heap data structure guide.

use std::collections::BinaryHeap;

let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);

heap.peek(); // Some(&4), O(1)
heap.pop();  // Some(4), O(log n)
heap.len();  // O(1)

Operation	Time
push	O(log n)
pop	O(log n)
peek	O(1)
Build from Vec	O(n)

For a min-heap, wrap every value in std::cmp::Reverse. This is not a hack. It is the intended API.

use std::cmp::Reverse;

let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(3));

let Reverse(smallest) = min_heap.pop().unwrap(); // 1

For Dijkstra, use Reverse((cost, node)) as a tuple. Tuples compare lexicographically so cost is the primary sort key. No custom Ord implementation needed for simple cases.

There is no decrease-key. The standard workaround is lazy deletion: push a new (new_cost, node) entry without removing the stale one, then skip any popped entry where cost > dist[node]. This is the correct pattern. Every real Dijkstra implementation in Rust uses it.

---

VecDeque<T>: BFS Lives Here

VecDeque is a ring buffer. Push and pop are O(1) at both front and back. It is the right structure for BFS, monotonic deque problems, and any sliding window that needs front removal.

use std::collections::VecDeque;

let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(1);
queue.push_back(2);
queue.push_front(0);  // [0, 1, 2]

queue.pop_front();    // Some(0), O(1)
queue.pop_back();     // Some(2), O(1)
queue.front();        // peek front, O(1)
queue.back();         // peek back, O(1)

Do not use Vec as a BFS queue. vec.remove(0) shifts every remaining element left: O(n) per dequeue. A 500-node BFS silently becomes O(n²). You'll pass the small examples, fail the large ones, and spend five minutes staring at your code while your interviewer writes something down.

---

What Rust's Standard Library Doesn't Include

• No built-in sorted Vec. Keep a Vec sorted manually and use binary_search or partition_point.
• No segment tree or Fenwick tree. Implement by hand. Index with usize, keep the size as a power of two.
• LinkedList<T> exists, but the standard library's own docs recommend against it. The borrow checker and pointer-chasing are a miserable combination. The one interview use case that makes it tempting (LRU cache with O(1) delete-in-place) is better served by HashMap plus VecDeque. Yes, you will feel clever setting up a linked list in Rust. The compiler will immediately disagree.

---

Five Traps That Bite Rust Interview Candidates

These are not theoretical. They are things real candidates have hit in real interviews while people with notepads watched.

1. usize underflow panics in debug, wraps silently in release.

let i: usize = 0;
let prev = i - 1; // panic in debug; usize::MAX in release

Cast to i64 before any arithmetic that might go negative. Left-boundary checks and reverse-iteration offsets hit this constantly.

2. String indexing does not compile.

let s = String::from("hello");
let c = s[0]; // compile error: cannot index `String` with `usize`

For ASCII problems, use s.as_bytes()[i], which returns a u8 directly. For full Unicode, s.chars().nth(i) works but is O(n). Most interview problems are ASCII so .as_bytes() is the fast path.

3. f64 does not implement Ord.

NaN != NaN, so f64 only implements PartialOrd. Sort a Vec<f64> with sort_by(|a, b| a.total_cmp(b)). Inserting f64 keys into a BTreeMap requires a newtype wrapper. The compiler will tell you this immediately and bluntly. At least someone will.

4. The borrow checker blocks mutating a collection while iterating it.

for neighbor in &graph[node] {
    graph[*neighbor].push(node); // compile error: can't borrow mutably
}

Collect neighbors into a local Vec first, then mutate. Or use index variables that defer the mutable borrow until after the loop body. The borrow checker is not wrong here. The algorithm design was.

5. BinaryHeap is a max-heap. Reverse<T> is not a workaround.

Not wrapping in Reverse and hoping the logic cancels out is the wrong pattern. BinaryHeap<Reverse<T>> in the type signature is the correct pattern and it also communicates intent to whoever reads the code next, including your interviewer.

---

One Problem, Five Collections Working Together

use std::collections::{HashMap, BinaryHeap};
use std::cmp::Reverse;

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq: HashMap<i32, usize> = HashMap::new();
    for n in &nums {
        *freq.entry(*n).or_insert(0) += 1;
    }

    // keep a min-heap of size k; pop the lowest-frequency element
    // when the heap exceeds k, leaving only the top k
    let mut heap: BinaryHeap<Reverse<(usize, i32)>> = BinaryHeap::new();
    for (&num, &count) in &freq {
        heap.push(Reverse((count, num)));
        if heap.len() > k {
            heap.pop();
        }
    }

    heap.into_iter().map(|Reverse((_, num))| num).collect()
}

entry handles counting, Reverse flips the heap direction, and tuple comparison lets cost and value live together without a custom struct. This pattern shows up in dozens of problems. Practice it until the types are automatic.

---

The fastest way to find out which of these you actually reach for under pressure is to run them in a real interview. SpaceComplexity runs voice-based DSA mocks with rubric feedback on communication, problem decomposition, code quality, and edge-case handling. Rust's borrow checker doesn't forgive hesitation, and neither does a real interviewer.

For the broader Rust interview picture beyond data structures, see the Rust for Coding Interviews cheat sheet, which covers idioms, sorting comparators, and the full gotcha list.

---

Further Reading

• std::collections, Rust Standard Library
• HashMap in std::collections
• BinaryHeap in std::collections
• BTreeMap in std::collections
• The Rust Programming Language, Chapter 8: Common Collections