loading...
Cover image for A common recursion interview challenge
Coderbyte

A common recursion interview challenge

elisabethgross profile image elisabethgross Updated on ・3 min read

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:

Alt Text

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!

Posted on by:

elisabethgross profile

elisabethgross

@elisabethgross

I am a full stack engineer, passionate about solving complex problems and collaborating with driven teams! I have 4+ years of experience working at small to mid sized startups.

Coderbyte

Coderbyte is a web application built to help you practice programming and improve your coding skills.

Discussion

markdown guide
 

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);
};
 
 

Thanks for the article! This was a fun challenge. I'm not the best with vanilla javascript, so all critiques welcomed.

Here's what I came up with:

const ChangeCalculator = function() {
    const values = {
        quarter: 25,
        dime: 10,
        nickel: 5,
        penny: 1
    };

    let allowedCoins, allowedCoinsTemp, amountLeft, solutions, solutionIndex;

    /**
     * Add a single solution to the solutions array
     * using the allowed coins.
     * @return {ChangeCalculator}
     */
    this.addSolution = () => {
        // Order is important here. Highest to lowest denomination.
        ['quarter', 'dime', 'nickel', 'penny'].forEach((coin) => {
            if (allowedCoinsTemp[coin] > 0 && amountLeft >= values[coin]) {
                amountLeft -= values[coin];
                allowedCoinsTemp[coin]--;
                solutions[solutionIndex][coin]++;
                return this.addSolution();
            }
        });

        // Base case (amountLeft == 0)
        return this;
    };

    /**
     * Calculate all solutions to make change for a given amount of cents
     * @param  {int} cents
     * @return {array}
     */
    this.calculate = (cents) => {
        this.resetSolutions();
        this.setMaxCoins(cents);

        do {
            this.nextSolution(cents)
                .addSolution()
                .setAllowedCoins();
        } while (solutions[solutionIndex].penny != cents);

        // return solutions; If you want to see all the solutions, 
        // but the problem requested number of ways.
        return solutions.length;
    };

    /**
    * Prepare to calculate the next solution
    * @param  {int} cents
    * @return {ChangeCalculator}
    */
    this.nextSolution = (cents) => {
        solutionIndex++;
        amountLeft = cents;
        solutions.push({
            quarter: 0,
            dime: 0,
            nickel: 0,
            penny: 0
        });

        return this;
    };

    /**
     * Reset the solutions variables before doing calculations
     * @param {int} cents
     */
    this.resetSolutions = () => {
        solutionIndex = -1;
        solutions = [];
    };

    /**
     * Set the number of each coin that may be used.
     */
    this.setAllowedCoins = () => {
        if(allowedCoins.quarter > 0) {
            allowedCoins.quarter--;
        } else if (allowedCoins.dime > 0) {
            allowedCoins.dime--;
        } else if (allowedCoins.nickel > 0) {
            allowedCoins.nickel--;
        }

        allowedCoinsTemp = Object.assign({}, allowedCoins);
    };

    /**
     * Set the maximum amount of each coin type that may be used.
     * @param {int} cents
     */
    this.setMaxCoins = (cents) => {
        allowedCoins = {
            quarter: Math.floor(cents / values.quarter),
            dime: Math.floor(cents / values.dime),
            nickel: Math.floor(cents / values.nickel),
            penny: cents
        };

        allowedCoinsTemp = Object.assign({}, allowedCoins);
    };
};

To run it:

const calculator = new ChangeCalculator();
const solutions = calculator.calculate(42);
console.log(solutions);
 
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
}
 

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.

 

Will make sure to do this in the next article. Stay tuned!

 

I'd like to share a solution that I developed for a same kind of problem here

editor.p5js.org/jithunni.ks/sketch...