Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Here's a simple recursive solution which remembers previous results and therefore can might qualify as dynamic programming under the weak definition
public class ButtonsWithRanges {
private static int POSSIBLE = 1;
private static int IMPOSSIBLE = -1;
private static int [][] buttonBounds = {
{ 300, 310 },
{ 400, 420 },
{ 500, 515 }
};
public static boolean isPossible(int min, int max){
int [] results = new int[max+1];
results[0] = POSSIBLE;
for(int i = min ; i <= max; i++){
if(!isPossibleImpl(i, results)) return false;
}
return true;
}
private static boolean isPossibleImpl(int amount, int [] results){
if(amount < 0) return false;
if(results[amount] != 0) return results[amount] > 0; // handles the 0 case
int nButtons = buttonBounds.length;
for(int b = 0 ; b < nButtons; b++){
int bmin = buttonBounds[b][0];
int bmax = buttonBounds[b][1];
for(int d = bmin; d <= bmax; d++){
if(isPossibleImpl(amount-d, results)) {
results[amount] = POSSIBLE;
return true;
}
}
}
results[amount] = IMPOSSIBLE;
return false;
}
public static void main(String[] args) {
int min = 1200, max = 1261;
System.out.println("Range=["+min+","+max+"], isPossible="+isPossible(min, max));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
static boolean isGeneratable[];
public static void fillArray(int max)
{
isGeneratable = new boolean[max + 1];
for(int i=300; (i <=310) && (i <= max ); i++)
isGeneratable[i] = true;
for(int i=400; (i <=420) && (i <= max); i++)
isGeneratable[i] = true;
for(int i=500; (i <=515) && (i <= max); i++)
isGeneratable[i] = true;
for(int i=515; i <= max; i++)
{
for(int j=1;j<=i && !isGeneratable[i] ; j++)
{
isGeneratable[i] = isGeneratable[j] && isGeneratable[i-j];
}
}
}
public static void printResult(int min,int max)
{
for(int i= min; i<=max; i++)
{
int startIndex = i;
int endIndex = i;
while(i<=max && !isGeneratable[startIndex])
{
startIndex++;
i++;
}
endIndex = startIndex;
while(i<=max && isGeneratable[endIndex])
{
endIndex++;
i++;
}
endIndex--;
if(endIndex >= startIndex)
System.out.println("[" + startIndex + " , " + endIndex + " ] " );
}
}
public static void main (String[] args) throws java.lang.Exception
{
fillArray(2000);
printResult(0,2000);
}
}
@Sathya - agreed, perhaps an interval based data structure(to store only the range(s) for which the denominations can be generated) is a better idea than boolean array.
Here is a dynamic programming solution, it can be optimized as some combinations are checked more then once.
However it allows you to do any combination of A, B, C and repeat them as many time as needed.
To run set low and high with initial value of 0 and min and max as the searched range.
public static boolean isBuidable(int low, int high, int min, int max) {
if(low <= min && max <= high)
return true;
if(low > min)
return false;
return isBuidable(low+300, high+310, min, max) ||
isBuidable(low+400, high+420, min, max) ||
isBuidable(low+500, high+515, min, max);
}
Here is another version - a combination of recursion and dynamic programming.
This takes more space (stack grows for recursion and allocating huge array), but runs faster (don'n need to calculate every single element in array and a lot of recursive calls will be skipped with first if statement)
static bool f(bool[] reachable, int low, int high, int min, int max)
{
if (reachable[low] && reachable[high]) return false ;
reachable[low] = true;
reachable[high] = true;
if (low > min)
{
return false;
}
if (high < min)
{
bool retval = ( f(reachable, low + 300, high + 310, min, max) ||
f(reachable, low + 400, high + 420, min, max) ||
f(reachable, low + 500, high + 515, min, max));
//if(retval == true) Console.WriteLine(low + "-" + high);
return retval;
}
//Console.WriteLine(low + "-" + high);
return true;
}
Notice that if min>=8000, whatever max is, the answer is yes, because I can get all the range by pushing button 400-420 for 20 times or more. So I need only generate all the ranges under 8000( or even smaller), then the search for [min, max] can be done in O(log N). Here is the code:
static void prepare(std::vector<int> & ranges)
{
//generate bitmap
int edge = 8000; //400 / (420 - 400) * 400
std::vector<bool> vec(edge);
int mi1, mi2;
int mi, ma;
for(int i = 0;300 * i < edge;++i){
mi1 = 300 * i;
if(mi1 >= edge)
break;
for(int j = 0;400 * j < edge;++j){
mi2 = mi1 + 400 * j;
if(mi2 >= edge)
break;
for(int k = 0;500 * k < edge;++k){
mi = mi1 + mi2 + 500 * k;
if(mi >= edge)
break;
ma = 310 * i + 420 * j + 515 * k;
for(;mi <= ma && mi < edge;++mi)
vec[mi] = true;
if(ma >= edge)
while(vec[edge - 1])
--edge;
}
}
}
//scan for ranges
ranges.clear();
bool state = true;
for(int i = 0;i < edge;++i){
if(state != vec[i]){
if(state)
ranges.push_back(i);
else
ranges.push_back(i - 1);
state = !state;
}
}
if(!state)
ranges.push_back(edge - 1);
assert(!ranges.empty());
assert((ranges.size() & 1) == 0);
//printVec(ranges); //show the ranges cannot be generated
}
bool canGet(int min, int max)
{
static std::vector<int> ranges;
assert(min <= max);
if(ranges.empty())
prepare(ranges);
//fast check
if(min < 300)
return false;
if(min > ranges.back())
return true;
//find index of min
std::vector<int>::const_iterator wh = std::lower_bound(ranges.begin(), ranges.end(), min);
if(wh != ranges.end() && *wh == min)
return false;
int mi = wh - ranges.begin();
//find index of max
wh = std::lower_bound(ranges.begin(), ranges.end(), max);
if(wh != ranges.end() && *wh == max)
return false;
int ma = wh - ranges.begin();
assert(mi <= ma);
return (ma == mi && (mi & 1) == 0);
}
After prepare(), the invalid ranges are stored in vector 'ranges', the left work is to search min and max in 'ranges' and determine whether [min, max] contains invalid ranges.
Here is the test cases:
int main()
{
std::cout<<canGet(1871, 1871)<<"\n";
std::cout<<canGet(1899, 1899)<<"\n";
std::cout<<canGet(1799, 1870)<<"\n";
std::cout<<canGet(1800, 1870)<<"\n";
std::cout<<canGet(1800, 1871)<<"\n";
std::cout<<canGet(1872, 1898)<<"\n";
}
1. The described problem of only 3 given intervals (300,310),(400,420) and (500,515) is finite and can be solved in O(1) run-time and space complexity by simply checking whether [min,max] intersects with any of the following intervals:
(-infinity,300),(310,400),(420,500),(515,600),(620,700),(730,800),(840,900),(935,1000),(1040,1100),(1150,1200),(1260,1300),(1355,1400),(1460,1500),(1570,1600),(1680,1700),(1775,1800),(1880,1900),(1990,2000),(2195,2200).
2. The general problem of n intervals (n buttons where each can generate 0<a_k to b_k ml of water for any 1<=k<=n) I think can be solved using a variant of the dynamic programming algorithm to solve the unbounded knapsack problem.
The total weight is max, the element weights are each interval's starting point. We'll also store the end point for each combination of intervals and the goal would be to find for each number j, a combination of intervals for which the sum of the starting points is as close as possible to j while the sum of the end points is as large as possible. All that's left is to check whether for every number in the range of [min,max] there is an interval combination such that the sum of the starting points is lesser/equal than the number and the sum of the ending points is greater/equal than the number.
private static boolean isLegal(Point[] intervals){
if (intervals==null){return false;}
for (int i=0;i<intervals.length;i++){
if ((intervals[i].x>intervals[i].y) || (intervals[i].x<=0)){return false;}
}
return true;
}
private static Point[][] buildDP(Point[] intervals, int max){
if ((intervals==null) || (max<=0) || (!isLegal(intervals))){return null;}
Point[][] dp = new Point[intervals.length+1][max+1];
for (int i=0;i<dp.length;i++){
for (int j=0;j<dp[i].length;j++){dp[i][j] = new Point(0,0);}
}
for (int i=1;i<dp.length;i++){
for (int j=1;j<dp[i].length;j++){
if ((intervals[i-1].x<=j) && (
((dp[i][j-intervals[i-1].x].x)+intervals[i-1].x > dp[i-1][j].x) ||
(((dp[i][j-intervals[i-1].x].x)+intervals[i-1].x == dp[i-1][j].x) &&
((dp[i][j-intervals[i-1].x].y)+intervals[i-1].y >= dp[i-1][j].y)))){
dp[i][j].x = (dp[i][j-intervals[i-1].x].x)+intervals[i-1].x;
dp[i][j].y = (dp[i][j-intervals[i-1].x].y)+intervals[i-1].y;
}
else {
dp[i][j].x = dp[i-1][j].x;
dp[i][j].y = dp[i-1][j].y;
}
}
}
return dp;
}
public static boolean canRangeBeGenerated(Point[] intervals, int min, int max){
if ((intervals==null) || (min>max) || (min<=0) || (!isLegal(intervals))){return false;}
Point[][] dp = buildDP(intervals,max);
if (dp==null){return false;}
for (int j=min;j<=max;j++){
if (dp[intervals.length][j].y<j){return false;}
}
return true;
}
check if the numbers lie within the following range
[300-310] [400-420] [500-515][700-730][800-825][900-935][1200-1245]
if they do lie then answer is yes else it is no(where no means all numbers cannot be generated)
you misunderstood the question, the range could be bigger than 515, kind of want to get combinations of buttons, not a single button
- Sathya December 19, 2013Generate(int min, int max){ bool isPossible = new bool[max+1]; for(int i=300; i<516; i++) if((i>299 && i<311) || (i>399 && i<421) || (i>499 && i<516)) isPossible[i] = true; for(int i=516; i<=max; i++){ if(!isPossible[i]) for(int j=300; j<311 && !isPossible[i]; j++) if(isPossible[i-j]) isPossible[i]=true; if(!isPossible[i]) for(int j=400; j<421 && !isPossible[i]; j++) if(isPossible[i-j]) isPossible[i]=true; if(!isPossible[i]) for(int j=500; j<516 && !isPossible[i]; j++) if(isPossible[i-j]) isPossible[i]=true; } for(int i=min; i<=max; i++) if(!isPossible[i]) return false; return true; }