I doubt such high-level policies and politics would affect a lowly software engineer like you or I, if we were to work at Google.
And you might not like Google's policies but I doubt you'll find a company of comparable size whose policies you do like. Ahem Microsoft. That doesnt mean they arnt great places to work and have a lot to offer. But whatever.
Google Interview Puzzle : 2 Egg Problem
That was an interesting problem. Thanks for sharing.
Here's some example code demonstrating (what we have found to be) the optimal searching pattern for an arbitrary number of total floors:
Obviously this could (and should) be cleaned up considerably, but I tossed it here, in this format, in case anyone wanted to see it working.
edit:
that should have been "sqrt( 1.0f + 8.0f ..." not "sqrt( 1.0f - 8.0f ..."
[Edited by - toucel on December 8, 2006 5:52:36 PM]
Here's some example code demonstrating (what we have found to be) the optimal searching pattern for an arbitrary number of total floors:
unsigned int topFloor = 100; unsigned int brakeFloor = 14; unsigned int maxStep = (unsigned int)ceil( (sqrt( 1.0f + 8.0f*(float)topFloor ) - 1.0f) / 2.0f ); unsigned int step = maxStep; unsigned int curFloor = step; unsigned int drops = 0; while (1) { drops++; cout << "1st egg from #" << curFloor; if (curFloor >= brakeFloor) { cout << " *\n"; if (step > 1) { for (unsigned int i = step - 1; i > 0; --i) { drops++; cout << "\t2nd egg from #" << curFloor - i; if ( curFloor - i >= brakeFloor) { cout << " *"; break; } cout << "\n"; } } break; } cout << "\n"; curFloor += --step; if (curFloor > topFloor) { step = topFloor - (curFloor - step); curFloor = topFloor; } } cout << "\n\nTotal number of drops: " << drops << "\n\n";Obviously this could (and should) be cleaned up considerably, but I tossed it here, in this format, in case anyone wanted to see it working.
edit:
that should have been "sqrt( 1.0f + 8.0f ..." not "sqrt( 1.0f - 8.0f ..."
[Edited by - toucel on December 8, 2006 5:52:36 PM]
Here is kind of a cleaned up version...
[Edited by - toucel on December 8, 2006 5:09:08 PM]
int getNumberOfDrops(unsigned int floor, unsigned int topFloor){ if (floor < 1 || floor > topFloor) return -1; unsigned int step = (int)ceil( (sqrt( 1.0f + 8.0f*(float)topFloor ) - 1.0f) / 2.0f ); unsigned int curFloor = step; unsigned int drops = 0; while (++drops) { if (curFloor >= floor) { for (unsigned int i = step - 1; i > 0 && step > 1; --i) { drops++; if ( curFloor - i >= floor) break; } return drops; } curFloor += --step; if (curFloor > topFloor) { step = topFloor - (curFloor - step); curFloor = topFloor; } } return drops;}...getNumberOfDrops(13, 100); //returns 14...[Edited by - toucel on December 8, 2006 5:09:08 PM]
If all you want is the number of drops in the worst case for two 'breaks'...
unsigned int getMaxNumberOfDrops(unsigned int floorsCount){ unsigned int maxFloorCovered = 0, attempts = 0; while (maxFloorCovered < floorsCount) { ++attempts; maxFloorCovered = (attempts*(attempts+1)) / 2; } return attempts;}
or a little more simply:
this is simply solving the quadratic formula (and because we are dealing with integers rounding to the highest int)
x(x + 1) / 2 >= 100
x*x + x >= 200
ax*x + bx + c >= 0
a = 1
b = 1
c = -200
( -b +- sqrt( b*b - 4ac ) ) / 2 =
( -1 + sqrt( 1 - 4*-200 ) ) / 2 =
(sqrt( 1 + 800 ) - 1) / 2
note we do not need to consider the alternate case given to us by the quadratic formula because we are dealing with positive whole numbers in this case.
unsigned int getMaxNumberOfDrops(unsigned int floorsCount){ return (unsigned int)ceil( (sqrt( 1.0 + 8.0*floorsCount ) - 1.0) / 2.0 );}this is simply solving the quadratic formula (and because we are dealing with integers rounding to the highest int)
x(x + 1) / 2 >= 100
x*x + x >= 200
ax*x + bx + c >= 0
a = 1
b = 1
c = -200
( -b +- sqrt( b*b - 4ac ) ) / 2 =
( -1 + sqrt( 1 - 4*-200 ) ) / 2 =
(sqrt( 1 + 800 ) - 1) / 2
note we do not need to consider the alternate case given to us by the quadratic formula because we are dealing with positive whole numbers in this case.
Quote:Original post by AndreTheGiant
I doubt such high-level policies and politics would affect a lowly software engineer like you or I, if we were to work at Google.
And you might not like Google's policies but I doubt you'll find a company of comparable size whose policies you do like. Ahem Microsoft. That doesnt mean they arnt great places to work and have a lot to offer. But whatever.
So "everyone probably does it" is a reason to ignore personal ethics and "go along to get along?" This isn't about "oh, but MS does it to," this is about it being done at all. So no, I will not work for a large company if all large companies do this kind of shit.
Ok, I can respect that.
Im just saying that your refusal to work at a company like that doesnt hurt them one bit. Unless of course you consider yourself to be the worlds best programmer or something. Assuming that Google is a great place to work (which I believe), then youre only hurting yourself and no one else by refusing to work there.
Im just saying that your refusal to work at a company like that doesnt hurt them one bit. Unless of course you consider yourself to be the worlds best programmer or something. Assuming that Google is a great place to work (which I believe), then youre only hurting yourself and no one else by refusing to work there.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
