CareerCup

A very very very vague question. Can you please specify when Amazon said : "best" what did they mean? Example : One can buy 450 Nano cars for the price of one Rolls Royce.
That is best or RR is best?

i'm assuming we're trying to spend the least amount of money on toys so all the kids get to play.

this can be solved with recursion. so:

findLowestPrice(toyList, numKids) {
    //missing stop conditions
    toy = toyList.pop();
    priceIfToyIsNotUsed = findLowestPrice(toyList, numKids);
    priceIfToyIsUsed = findLowestPrice(toyList, numKids - toy.maxKids);
    if (priceIfToyIsNotUsed > priceIfToyIsUsed + toy.price) {
        solution.push(toy); //global var
        return priceIfToyIsUsed + toy.price;
    }
    return priceIfToyIsNotUsed;
}

i'm assuming we're trying to spend the least amount of money so that all the kids get to play - per shop.
it can be solved by recursion each time taking one toy out of the list and deciding whether it should or shouldn't be in the solution based on whether toy.price + getCheapestPrice(remainingToys, remainingKids - toy.maxKids) > getCheapestPrice(remainingToys, remainingKids)

we sort the toys list based on the price/maxChildren in ascending order and can start picking the toys till we all the children have something to play with a few edge cases to be handled

public class ShoppingToyComparator implements Comparator<Shop> {

	@Override
	public int compare(Shop o1, Shop o2) {
		int result = 0;
		int i = 0;
		while (result == 0) {
			Toy t1 = o1.getToys().get(i);
			Toy t2 = o2.getToys().get(i);
			result = t1.getPrice() - t2.getPrice();
			if (result == 0) {
				result = t2.getMaxChildren() - t1.getMaxChildren();
			}
			i++;
		}
		return result;
	}

}