Garmin Interview Question: Write an algorithm in any pro... | Glassdoor

Interview Question

Software Engineer Interview Olathe, KS

Write an algorithm in any programming language for

  calculating the amount of change needed. As a follow up, can you modify this algorithm to avoid using the division operator?

Interview Answer

2 Answers


Initially I incorrectly used the modulus operator, but later in the interview recalled the correct usage which should have been division.

Interview Candidate on Sep 11, 2010

Garmin would probably like to see this in C, but here's a quick solution in Java that doesn't need division:

    private static int countDenominations(int n, int[] denominations) {
        return countDenominationsHelper(n, denominations, 0);

    private static int countDenominationsHelper(int n, int[] denominations, int i) {
        if (n == 0) {
            return 1;

        if (n = denominations.length) {
            return 0;

        return countDenominationsHelper(n - denominations[i], denominations, i) +
                    countDenominationsHelper(n, denominations, i + 1);

guy on Dec 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.