Setting up Rust

This course teaches data structures in Rust. A data structure is a way of arranging data in memory so that some jobs are quick: finding an item, adding one, taking one out. An algorithm is a step-by-step method for solving a problem. We start with data structures, because most algorithms are really about choosing the right one.

Why Rust? Because Rust makes you say who owns each value and who is only borrowing it. That is exactly what data structure code is about, so the language will teach you something real along the way. You don't need to know Rust yet. Each lesson explains what it uses, when it first shows up. You do need a little programming from any language: variables, loops, and functions.

Here is what you need before lesson 1:

• Rust, installed on your computer. It comes with a tool called cargo, which builds your code, runs it, and runs your tests.
• A project folder, which cargo makes for you.
• A text editor. Any editor works. Visual Studio Code with the rust-analyzer extension is a common choice, but it is not required.

You will do the same three things in every lesson. Make a project once. Then edit a file, run the tests, and repeat until the tests pass.

The tests matter more than they look. A test is a small piece of code that calls your function with an input and checks the answer. When a test passes, you know that case works. When you change something later, the tests tell you straight away if you broke it. Every piece of Rust on these pages has tests like this, and they were all run before the page was built.

1. Install Rust. Go to rustup.rs and follow the steps for your system. On Windows you download a small installer and run it. On Linux and macOS you paste one command into a terminal. When it finishes, open a new terminal and check that it worked:

cargo --version

You should see a version number. If you see an error such as "command not found", close the terminal and open a fresh one, because the installer changes a setting that only new terminals pick up.

2. Make a project. In a terminal, go to the folder where you keep your work and run these two commands:

cargo new --lib rust-dsa-practice
cd rust-dsa-practice

cargo new makes the folder. The --lib flag makes a library crate. A crate is Rust's word for one package of code, and a library crate is a crate meant to be called by other code, which is perfect for testing functions. Your code goes in src/lib.rs.

3. Write a function. Replace what is in src/lib.rs with these two functions.

pub fn add(a: i32, b: i32) -> i32 {
    a + b
}

Read add as: take two i32 values (a 32-bit whole number) and give back an i32. The last expression, a + b, has no semicolon, and that is on purpose. In Rust, the last expression in a function is its result.

pub fn sum(nums: &[i32]) -> i32 {
    let mut total = 0;
    for n in nums {
        total += n;
    }
    total
}

sum introduces the first idea about ownership. The parameter nums: &[i32] is a slice: a view of a run of numbers. The & means borrowed. The function can look at the numbers, but it doesn't own them and can't keep them. The caller still owns its data and gets it back untouched. That is why you can call sum and then use the same numbers again afterwards.

4. Write tests, and run them. Add this at the bottom of src/lib.rs.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_works() {
        assert_eq!(add(2, 3), 5);
    }

    #[test]
    fn sum_of_nothing_is_zero() {
        assert_eq!(sum(&[]), 0);
    }
}

#[cfg(test)] means "only build this when testing", so the tests never end up in your finished program. #[test] marks a function as a test. assert_eq!(a, b) checks that two values are equal and fails the test if they're not. use super::*; lets the tests see the functions above them. Now run:

cargo test

running 2 tests
test tests::add_works ... ok
test tests::sum_of_nothing_is_zero ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

If you see ok twice, you are set up. If cargo prints an error instead, read it from the top. Rust's error messages are long, but the first few lines usually say what is wrong and which line.

You will use three things from Rust itself in every lesson.

println! prints a line of text. The ! means it is a macro, a bit of code that writes code, which is why it can take any number of arguments. Inside the quotes, {} prints a value, and {:?} prints it in a debugging layout, which works for lists and options too.

fn main() {
    println!("Hello, DSA in Rust!");
}

cargo has more commands than cargo test. You'll meet them in the next section.

The Rust Playground is a website that compiles and runs Rust for you, so you can try something without installing anything. Every Rust block on these pages has two buttons. Copy puts the code on your clipboard. Run in Rust Playground opens the same code in the Playground in a new tab, ready to run. If the code on the page is only a piece of a program, it is wrapped in a main function first, so it runs as it is. Try it on the block above.

There's no data structure to measure yet, so here are the cargo commands you'll use.

From lesson 1, each lesson has a cost table like this one, but for the operations on a data structure. It uses Big O notation, which is a way of saying how the work grows as the input gets bigger. n is the number of items. O(1) means the work is the same however large n is. O(n) means it grows in step with n: twice as many items, about twice the work. O(n²) means it grows with the square: twice as many items, about four times the work. You don't need the maths. You need to be able to say which one an operation is.

Each lesson ends with problems. For every one: read it, try it in the Playground or in your own project, and open the hints one at a time only when you are stuck. The solution is there to compare against, not to copy. A solution you peeked at too early teaches much less than one you fought for.

pub fn count_evens(nums: &[i32]) -> usize {
    todo!("count how many numbers are even")
}

pub fn count_evens(nums: &[i32]) -> usize {
    nums.iter().filter(|&&n| n % 2 == 0).count()
}

pub fn largest(nums: &[i32]) -> Option<i32> {
    todo!("the biggest number, or None for an empty slice")
}

pub fn largest(nums: &[i32]) -> Option<i32> {
    let mut best = *nums.first()?;
    for &n in nums {
        if n > best {
            best = n;
        }
    }
    Some(best)
}

pub fn running_total(nums: &[i32]) -> Vec<i32> {
    todo!("each position holds the sum so far")
}

pub fn running_total(nums: &[i32]) -> Vec<i32> {
    let mut total = 0;
    let mut out = Vec::with_capacity(nums.len());
    for &n in nums {
        total += n;
        out.push(total);
    }
    out
}

This section is in every lesson. It says, in plain words, how the topic turns up in coding tests and interviews. For this first lesson it is about the setting, not the topic.

• Check the language list first. Online coding tests let you pick from a list of languages. Some platforms offer Rust and some don't, so look at the list for your test before you decide to use Rust there. If Rust isn't on it, the ideas in this course still carry over to the language that is.
• Practise in the language you will use. The first time you use a language should not be in a timed test. Rust has a few rules that take time to feel natural, and the practice problems here are a good place to meet them.
• Learn to explain, not only to write. Interviewers often ask you to say what your code does and what it costs. Getting used to saying "this walks the slice once, so it is O(n)" out loud is part of the practice.
• Know your editor. In a test you may have only a plain box to type in. Try writing a few of these solutions without autocomplete.

Made by VeraStack Labs