Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
For small min and max values brute force recursive just works:
def canFillTheCup(min: Int, max: Int, buttonAmounts: Seq[Int]): Boolean = {
if (buttonAmounts.exists(ba => min <= ba && ba <= max)) {
true
} else {
buttonAmounts.exists(ba => min - ba > 0 && canFillTheCup(min - ba, max - ba, buttonAmounts))
}
}
Just find there is a number that exists within the min_max range divisible by options and their combinations
- Mani May 14, 2018In this example that would be (3,4,7,10,11)
You don't need to calculate for each value in min-max range of cup. just calculate for minimum value, if the remainder is any one of the options+combinations array, we should be returning a true.
The solution can be optimised further as it's an O(n*k) still.