Module 4Arrays & VecLesson 2 of 2322 min

Vec Interview Operations

push, pop, insert, remove, get, len, is_empty, clear — complexity and patterns.

Vec is the interview default list

rust

fn main() {
    let mut v = vec![1, 2, 3];
    v.push(4);                 // O(1) amortized back
    let x = v.pop();           // O(1) Option
    println!("popped={x:?} now={v:?}");
    v.insert(0, 99);           // O(n) — shifts
    let y = v.remove(1);       // O(n) — shifts
    println!("removed={y} now={v:?}");
}

Output

popped=Some(4) now=[1, 2, 3]
removed=1 now=[99, 2, 3]

Read safely

rust

v.get(i) // Option<&T> — no panic
v[i]     // panics if OOB

Complexity cheat sheet

Op	Complexity

----	------------

push/pop back	amortized O(1)

index get/set	O(1)

insert/remove middle	O(n)

contains (linear scan)	O(n)

Two-pointer / partition

In-place algorithms usually mutate &mut [T] or &mut Vec<T>.

Challenge

Implement fn second_largest(xs: &[i32]) -> Option<i32> without sorting (one pass).

Tips

Avoid insert(0) in hot loops
get(i) over [i] when unsure
with_capacity if you know n

Try it live

Vec Interview OperationsRust 2021

Loading editor…

Output

Press Run to compile and execute.