23Rust

Solution of Interview question 23.1.

best borrows the vector immutably and is used after push, which needs a mutable borrow: E0502. In C++ the push could reallocate and leave best dangling (Interview question 22.9). Fix by ending the borrow before mutating: copy the i64 out (let best = levels[0];), or read it after the push by index.

/// Push a new level and return the old best: copy the value out, then mutate.
pub fn push_level(levels: &mut Vec<i64>, new_level: i64) -> Option<i64> {
    let best = levels.first().copied();
    levels.push(new_level);
    best
}

What the interviewer is looking for: the aliasing rule, the C++ bug it prevents, and a zero-cost fix.

Solution of Interview question 23.2.

let archived = fills; moves the vector; fills is no longer valid (E0382). Fixes: borrow instead (let archived = &fills;), which costs nothing but ties archived’s life to fills; or clone (fills.clone()), which copies the heap buffer. Use fills.len() before the move if only the length is needed.

What the interviewer is looking for: move semantics, and choosing between borrowing and cloning by cost.

Solution of Interview question 23.3.

201 then 200. Each let creates a new binding that shadows the previous one; the inner block’s shadow ends with the block. No binding is mutable: shadowing is not mutation, and the values are not overwritten.

What the interviewer is looking for: shadowing versus mutability and scope.

Solution of Interview question 23.4.

The borrow checker reasons about the vector as a whole: two &mut into it at once are two mutable borrows of the same value (E0499), even for different indices. Split the borrow with split_at_mut, which returns two disjoint mutable slices (Listing 23.2), or use indices and do the update in two statements.

What the interviewer is looking for: why disjointness is not visible to the checker, and split_at_mut.

Solution of Interview question 23.5.

fn best<’a>(a: &’a str, b: &’a str) -> &’a str. The lifetime promises that the result is valid as long as both inputs are, so the caller may not use it after either input is gone; the compiler needs it because the result may borrow from either (E0106).

What the interviewer is looking for: the lifetime annotation and its meaning for callers.

Solution of Interview question 23.6.

top is a local that is dropped when the function returns, so a reference to it would dangle: E0515. Return the value, -> i64, which for an integer costs nothing; for a large value return it by value (moved) or a reference into the input.

What the interviewer is looking for: the lifetime of locals and returning by value.

Solution of Interview question 23.7.

drop ignored, end of main, drop b, drop first, drop second, drop a. let _ = binds nothing, so the value is dropped at once; locals are dropped in reverse declaration order (_b, _p, _a); a struct’s fields are dropped in declaration order (first then second), whereas C++ destroys members in reverse declaration order (Interview question 22.2).

What the interviewer is looking for: the three drop rules, including the let _ trap and the contrast with C++.

Solution of Interview question 23.8.

The iterator holds &’a [u8] and a position and returns &’a [u8] slices of the buffer (Listing 23.3): each field lives as long as the buffer, not as long as the iterator, so fields can be kept after the iterator is gone. The crate’s tests check the fields of a sample message and empty fields.

What the interviewer is looking for: a struct with a lifetime and returned slices tied to the buffer.

Solution of Interview question 23.9.

*map.entry(sym).or_insert(0) += v;: the entry API finds or creates the slot once and returns a mutable reference to it, where a get followed by an insert would hash twice. The crate’s volume_by_symbol does this.

What the interviewer is looking for: the entry API and why it avoids a second lookup.

Solution of Interview question 23.10.

Generic: one copy per strategy type, calls resolved at compile time and inlinable, larger code, the strategy fixed at compile time. Trait object: one copy, an indirect call through a vtable per message (a few nanoseconds and no inlining), strategies chosen at run time from configuration. On a hot path with few strategy types, generics; for a plug-in architecture, dyn. A trait is not object-safe if a method is generic, returns Self, or takes self by value without a Sized bound. The crate checks that both dispatches give the same result.

What the interviewer is looking for: monomorphisation against vtables, the trade-off, and object safety.

Solution of Interview question 23.11.

Rc counts references non-atomically, so two threads cloning or dropping it could corrupt the count: it is not Send, and thread::spawn requires its closure to be Send (E0277). Use Arc, whose count is atomic. Send: a value may be moved to another thread. Sync: a shared reference may be used from several threads at once (a type is Sync if &T is Send); Cell is Send but not Sync, Mutex<T> makes a Send T usable as Sync.

What the interviewer is looking for: atomic against non-atomic counting, and the precise definitions of the two traits.

Solution of Interview question 23.12.

The assertion that $n$ does not exceed the slice’s length, checked once before the loop, guarantees that every index $i < n$ is in bounds, so the unchecked read never goes out of bounds; the safety comment states the invariant. It would be unsound if the check were removed, weakened to a debug_assert! (absent in release builds), or placed after the loop, or if the slice could shrink during the loop (it cannot, being borrowed immutably). Check mechanically with Miri, which interprets the code and detects out-of-bounds reads, and with a test that the function panics on a bad n (the crate has one). Often the compiler removes the bounds checks of the safe version anyway (One Quant Book 13, chapter 9).

What the interviewer is looking for: the invariant that makes unsafe sound, where it would break, and Miri.

Solution of Interview question 23.13.

/// A counter shared by threads: fetch_add loses no increment; Relaxed suffices for a count.
pub fn count_in_threads(threads: usize, per_thread: u64) -> u64 {
    let c = Arc::new(AtomicU64::new(0));
    let handles: Vec<_> = (0..threads)
        .map(|_| {
            let c = Arc::clone(&c);
            thread::spawn(move || {
                for _ in 0..per_thread {
                    c.fetch_add(1, Ordering::Relaxed);
                }
            })
        })
        .collect();
    for h in handles {
        h.join().expect("thread panicked");
    }
    c.load(Ordering::Relaxed)
}

fetch_add is a single atomic read-modify-write, so no increment is lost whatever the ordering; Relaxed is enough for a pure count read after the threads are joined (joining synchronises). A stronger ordering is needed when the counter publishes other data: a producer that writes a message and then increments a sequence number needs Release on the increment and the consumer Acquire on the read (One Quant Book 13, chapter 11). The crate’s test counts 400 000 increments from four threads exactly.

What the interviewer is looking for: atomic read-modify-write, and when ordering matters beyond the counter itself.