Google | Onsite | Coke Machine
5465

Given a coke machine with a series of buttons. If you press a button it will get you a certain range of coke. Find out if it's possible to get the target range of coke. You can press buttons any number of times.

Example 1:

Input: buttons = [[100, 120], [200, 240], [400, 410]], target = [100, 110]
Output: false
Explanation: if we press first button it might give us 120 volume of coke, not in the target range.

Example 2:

Input: buttons = [[100, 120], [200, 240], [400, 410]], target = [90, 120]
Output: true
Explanation: press first button and you will always get amount of coke in the target range.

Example 3:

Input: buttons = [[100, 120], [200, 240], [400, 410]], target = [300, 360]
Output: true
Explanation: press first and second button and you will always get amount of coke in the target range.

Example 4:

Input: buttons = [[100, 120], [200, 240], [400, 410]], target = [310, 360]
Output: false
Explanation: we can press 1st button 3 times or 1st and 2nd button but it's possible to get only 300, not in the target range.

Example 5:

Input: buttons = [[100, 120], [200, 240], [400, 410]], target = [1, 9999999999]
Output: true
Explanation: you can press any button.
My Java solution

DFS + memo: https://leetcode.com/playground/FHFNnBNR

Comments (19)