← Go home

Kids With The Greatest Number of Candies (Rust)

May 12, 2020

After some time of focusing on other things (work, learning DynamoDB, building a Slack Clone), I’m back to Rust… and coding questions. Two of my low hanging fruits. 🍒

My homework: pick a random, easy problem on Leetcode to solve in Rust.

Thought process

How do I solve this in Type/JavaScript?

const kidsWithCandies = (candies: number[], extraCandies: number) => {
  const max = Math.max(...candies)
  const result = candies.map(e => {
    return e + extraCandies >= max
  })
  return result
}

Time complexity?

O(n) - I’m going to stupidly assume that destructureing has a time complexity of O(n), so that’s one iteration over my collection. (I should look this up later…). Then .map() also has a time complexity of O(n)

O(n) + O(n) = O(2n)

… but constants drop out of complexity (link), so…

O(n) is the answer.

Solution in Rust

impl Solution {
    pub fn kids_with_candies(candies: Vec<i32>, extra_candies: i32) -> Vec<bool> {
        let max: &i32 = candies.iter().max().unwrap();

        let mut result: Vec<bool> = Vec::new();

        for &i in &candies {
            if i + extra_candies >= *max {
                result.push(true);
            } else {
                result.push(false);
            }
        }

        result
    }
}

Things I needed to google

What is a greedy algorithm?. Fundamentally, I don’t really know what this entails, and I know I should.

How do I find the max value in a Vec?.

Wtf is Borrowing in rust?

Things I definitely still don’t really understand.

& - passing by [references] in Rust.

When and why to use unwrap().

Differences between Arrays, Vectors, and Slices

Next steps

Maybe I’m selling myself short by picking questions that are too easy, but it is a super nice transition specifically for the goal of learing Rust. But maybe I should find the historically classic algorithms and understand those from a theoretical level instead, then come back and learn Rust. I dunno. In the end, there’s just too much to learn.

Just gotta keep at it.

Tags: coderustinterview questionleet codealgorithm
Kevin Wang

👋 I'm Kevin Wang. Jazz GuitaristBaristaReceptionist Front End Engineer
This is my ever growing sandbox of sorts⛱.

Comments

Create Post

You must log in to comment.

Be the first to comment!