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?
Answer

Interview Answer

2 Answers

0

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
0

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.