A common recursion interview challenge

#javascript #career #codenewbie #challenge

Hey everyone! Welcome back to Code Review, a series of coding challenges and job related content released weekly. We took a brief hiatus for the holiday season, but we’re back and ready to show 2020 all we got. Our team at Coderbyte has been hacking away given the extra time away from our day jobs and we have some big things planned for 2020.

Newsletter 📫

First, I'm excited to mention our new newsletter! We’re going to be sending out a small, feature reveal snippet every time we release something big, so our community is the first to know when we break out something new. Give us your email here and we'll add you to our "first to know" list :) Let’s get started on this week’s challenge. Cheers to 2020! 🎉

The Problem:

Given an infinite amount of quarters, dimes, nickels, and pennies, write a function that returns the number of ways of representing n cents with coins.

Some tips when it comes to recursion

Recursion can get overwhelming at times. Something that really helps me relax when it comes to coming up with an approach to a recursive problem is remembering that by definition, recursive solutions are made up of solutions to smaller subproblems.

Take the classic "calculate the nth Fibonacci number" challenge. In case you haven’t heard this one - the Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. We can take a bottom-up approach, where we’ll try and solve the problem for a simple case and build on it from there. The most simple case for this problem is getting the 0th number of the Fibonacci series which will return 0 as per the definition of the series. Let's build on that to get the 1st number which will return 1, also per the definition. To calculate the 2nd number of the Fibonacci series we add 0 and 1 and we get another 1. To calculate the 3rd number, we add 1 and 1 and we get 2. And the series continues as follows 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ....

This can be summarized as follows: fibonacci(0) will always be 0; fibonacci(1) will always be 1. After that, fibonacci(n) will be the sum of the two preceding numbers aka fibonacci(n-1) and fibonacci(n-2).

In this problem, always returning 1 when n is 1 and 0 when n is 0 are the base cases, which you can think of as the smallest subproblems you can break the problem down into.

This is what that looks like in code:

function fibonacci(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

Big-O

Often to find the Big-O of a recursive solution, it helps to draw the code paths as a recursion tree. For the example above:

The rule is this: the amount of branches each node has in the tree is the base of the power and the levels in the tree are the exponent. So for this example, the Big-O is O(2^n) because each function call splits into 2 function calls. And the number of levels of the tree corresponds to n.

Have fun all and see you next with the solution and a brand new challenge!

Top comments (6)

Alex Parra • Jan 6 '20

Nice series!
Would like to share for others that the nth Fibonacci number can be calculated in O(1) with the Binet Formula as I’ve learned it recently too.
Here’s my version of it:

/**
 * Binet's Formula - Calculate the Fib of the nth 'n' term
 */
const fibOfN = n => {
  const { pow, sqrt, floor } = Math;
  const Phi = (sqrt(5) + 1) / 2;
  const fibOfN = (pow(Phi, n) - pow(-Phi, -n)) / sqrt(5);
  return floor(fibOfN);
};

elisabethgross • Jan 10 '20

Nice!

Idan Arye • Jan 6 '20

use std::collections::{BinaryHeap, HashMap};
use std::cmp::{Eq, PartialEq, Ord, PartialOrd};
use std::hash::Hash;

enum CoinType {
    Quarter,
    Dime,
    Nickel,
}

impl CoinType {
    fn in_pennies(&self) -> u64 {
        match self {
            Self::Quarter => 25,
            Self::Dime => 10,
            Self::Nickel => 5,
        }
    }
}

const COIN_TYPES: [CoinType; 3] = [CoinType::Quarter, CoinType::Dime, CoinType::Nickel];

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
struct Task {
    start_from: usize,
    amount_left: u64,
}

impl Task {
    fn subtask_factors(&self) -> Option<impl Iterator<Item = Task>> {
        let coin_type = COIN_TYPES.get(self.start_from)?;
        let worth = coin_type.in_pennies();
        let max = self.amount_left / worth;
        let &Task { amount_left, start_from } = self;
        Some((0..max + 1).map(move |n| Task {
            start_from: start_from + 1,
            amount_left: amount_left - (n * worth),
        }))
    }
}

fn num_change_permutations(amount: u64) -> u64 {
    let mut tasks = BinaryHeap::<Task>::new();
    tasks.push(Task {
        start_from: 0,
        amount_left: amount,
    });

    let mut memoized = HashMap::<Task, u64>::new();

    while let Some(task) = tasks.pop() {
        if let Some(it) = task.subtask_factors() {
            let mut task_result = Some(0);
            for subtask in it {
                if let Some(&subtask_result) = memoized.get(&subtask) {
                    if let Some(task_result) = task_result.as_mut() {
                        *task_result += subtask_result;
                    }
                } else {
                    task_result = None;
                    tasks.push(subtask);
                }
            }
            if let Some(task_result) = task_result {
                if task.start_from == 0 {
                    return task_result;
                }
                memoized.insert(task, task_result);
            } else {
                tasks.push(task);
            }
        } else {
            memoized.insert(task, 1);
        }
    }
    0
}

Samuele Zanca • Jan 6 '20 • Edited

Nice article!

If you also touch on the topic of memoisation and how to convert recursive solutions to an iterative processes (+stacks), imho, this will be a really helpful sub series.