When I interview developers for high profile positions I ask them this first question

>14
Explain why this is the answer if you can't know in advance on which floor it breaks?
I'd try 1,2,4,8,16,32,64 and see when it breaks. When the first egg breaks, try one step at a time to be sure not to skip a step.

People who tell kids to get a CS degree should go to jail for child abuse if this is what happens when they come out

->

jokes on you, the eggs just rolling on the floor :^)

I just did right here

That's because math students are smarter than computer science students.

If it breaks on floor 63 m is going to be 31

The floor with smallest number of egg drops is the floor where you don't have any eggs left to drop.

Attached: thonk.jpg (550x497, 31K)

I don't know what's worse, this shit bait or that some jackass in HR probably uses this to interview applicants

Why though? It seems like a nice problem, considered there are more of them.

Nr 2 is not a well posed question. There is no guarantee that there is a local minimum.

>n+ (n-1) + (n-2) + (n-3) + ... + 1

Oh never mind I get it, you're taking smaller and smaller steps that that each time you take a step, you reduce the number of interval floors you nee to check.

>drop the egg from floor 50
>then floor 25
>then floor 12
>then floor 6 or adjust higher
>etc.

Medical student here, how did I do

We know it gives roughly sqrt worst case Big O performance, which beats linear.

We obviously would prefer divide and conquer for log time, but if we try it and it fails right away. our worst case perf is n/2 floors.

The real interesting question is “can we do better with 3 eggs? If so, how?

I suggested binary search algo in previous thread and got chewed out. Most if not all of the people here are retarded. Don't bother seeking validation

Would kinda suck if the answer was 37

THE OPTIMAL ANSWER IS BINARY SEARCH UNTIL YOU ONLY HAVE ONE EGG LEFT. THEN LINEAR SEARCH FROM THE MINIMUM VALUE YOU KNOW IT WILL NOT BREAK AT.

DROP THE FIRST EGG AT FLOOR 50.
IF IT BREAKS, DROP THE NEXT REPEATEDLY FROM FLOOR 1 UPWARDS UNTIL IT BREAKS.
IF IT DIDN'T BREAK, DO THE SAME STARTING AT FLOOR 50.

What is the answer to the 3rd question? There's more red balls so the chance of them getting pick and discarded is higher. Blue balls has higher chance to stay in urn but they're discarded if they got pick after a blue ball.

Answer is (log_2(100)+1)*2=14 you fucking morons

I would tell you it drops on floor 49 or 100 I would laugh at you

1. Divide and conqure. No. of eggs = log(100).

2. Gradient descent. Start at any random point. Compare the value of the current value with it's 4 neighboring points. Make the smallest of the four point the current point and repeat. This will pick out the local minima, not gobal.

3. It is 100% likely that the last ball is a red ball.

I don't get it

Binary search algorithms won't work for this problem, because they have a horrible worst case complexity. If the answer is 49, you lose the first egg on your first attempt, and them need to go one by one in order to be sure to actually find the answer.
Even going every 10 floors starting at 10 has a better worst case performance.

1: it's just fucking binary search

2: don't get what they mean by "local minimum)", but to find the minimum of an n*n grid will be O(n^2) regardless if the numbers are distinct

3: 0.2 * 0.8 = 0.16 probability red is second ball, 0.04 probability blue is second ball.
Therefore the real chance of a blue ball being removed on the first trial is 0.04 whereas 0.8+0.16 = 0.96 probability for a red ball to be chosen on the first trial. Calculate that over 99 trials and you'll get your probability.

There is no faster method than I proposed that will guarantee a result.

The input data is sorted (floors are ordered).
Binary search has logarithmic complexity.

YOU ONLY HAVE TWO EGGS, after one breaks you HAVE to linear search.

I'm reluctant to even hire people with comp sci degrees, much prefer someone with a background in natural science (I do consulting for pharmas) who incidentally knows a thing or two about programming.

This.

Honestly it makes me weep when I hear CS faggots say binary search

Yes there yes you faggot

Right fucking here

A partition of 10 is more efficient than a binary search

read this as well faggot

Look here buddy

The answer is to find the solution that will give you the answer everytime, nit the HURR IF YOU USE THIS PARTICLUAR METHID THE RESULT MIGHT BE FASTER

>There is no faster method than I proposed that will guarantee a result
>what is logarithmic search

>A partition of 10 is more efficient than a binary search
Whatever you are smoking, I want some.

I am a brainlet, neither CS nor math major, however 14 makes sense.

You have two eggs, so you are only really allowed to break it once before the next break needs to occur on the exact floor. Therefore, you need to work your way up in increments until you get a break, and from there, you have to go floor-by-floor until you hit the exact floor.

So, why 14?

Start off dropping the egg on the 14th floor. If it breaks, the breaking floor can be as high as 14. This leaves 14 attempts. If the egg does not break at 13, you know that it is the 14th floor.

If it doesn't break at your very first attempt at 14, increase the floor by 13 to 27. If it breaks, it can be as high as 27. Because you decreased the group increment by 1, you may still discover the correct floor in 14 turns.

And it still works as we go up. 14 -> 27 -> 39 -> 50 -> 60 -> 69 -> 77 -> 84 -> 90 -> 95 -> 99 -> 100.

If you follow this sequence going up, you can guarantee that you will find the breaking floor within 14 or fewer egg drops.

I am trying to think of a mathematical explanation, but it has been a long time since I have been in a math class.

Can you provide any proof that binary search is not the optimal solution in the worst case? Go on. This should be easy.

Dropping at 50 halves your problem space with one move.

T W O E G G S
W
O

E
G
G
S

>HURR IF YOU USE THIS PARTICLUAR METHID THE RESULT MIGHT BE FASTER
Please read the last sentence of the question and then go kill yourself.

Binary search is stupid here because you could be unlucky with the numbers. If it is 49 you have to go one at a time to guarantee finding the result.

And what would be the better method??

The egg breaks on the first floor. It's not a programming question apparently.

>breaks on floor 49

Binary:
50
1
2...
...48
49

50 attempts.

Partitions of 14

14
28
42
58
43
44
45
46
47
48
49

11 attempts.

11 is a smaller number than 50.

Look at this line of text, it came from the question that you are trying to answer.
>smallest number of egg drops

Isn't 11 smaller than 50???

Sure. As I wrote before, assume the result is 49. You drop the egg at 50, and break it. Now, you have to start a linear search at floor 1 to ensure a solution, for a total of 49 additional throws, resulting in a total of 50.
Compare to throwing every 10, starting at 10. You use 5 throws to get to floor 50 (then the first egg breaks). Then you start at 41, last known good floor plus one, and throw one by one, until you get to 49, for a total of 5+8=13 throws. And the worst case for this method is floor 99, which totals 9 + 9 = 18, still better than binary at 49.

If you do binary search for 49 it wont take more than 14 eggs brainlet

>yfw you re-read it and you realize you only have 2 eggs

It isn't a programming question, these tards are just autsy

Attached: 1531713346296.jpg (1440x1557, 153K)

To clarify further and provide another example, say it breaks at 69. You would want to go 61... 62... 63... until it breaks.

By going 14 -> 27 -> 39 -> 50 -> 60 -> 69 and then 61-68 you have 14 attempts.

(log_2(100)+1)*2=14

If I were supreme dictator of the planet everyone in this thread who is defending a binary search would be shot in the head

After floor 50 breaks you do 25 and it doesnt brake, you go up at 37, then 43, then 46, then 48,then 49,less than 10 eggs lmao!!

It's not 49 its 97

Now what?

You don't know what fucking floor it breaks on you moron. Thats why you have to use max partitions

And then you try 24

>being this retarded

>I typed 97 and not 57

here you go tardlet

1st egg doesn't break at 50
not at 75
not at 87
not at 93
not at 96
not at 98
at 99

AND ANOTHER ONE

breaks at 50
breaks at 25
not at 12
not at 18
not at 21
not at 22
not at 23
at 24

LESS THEN 10 EGGS IN EACH CASES

Lets be honest, in practice most people would just iterate from the first floor.

question is "how", not "how many".
Jow Forums is dumb as fuck

Where the fuck is the discussion about problem #3?

floor breaks on 52
Can you find it faster than

14
28
42
58
43
44
45
46
47
48
49
50
51
52

Can you do it faster than 14 steps if its 52 with a binary search? Can you use that same algorithm if you had a new kind of egg with a different tensile strength and you now have no idea what floor it will break on?

Doesn't break at 50
at 75 it brakes
at 63 it breaks
not at 56
at 60 it breaks
at 58 it breaks
at 57 it breaks
we know at 56 it doesn't break

less than 10 eggs tardlet

okay see you later nerds, I'm the medfag and I have an exam to study for, stay dumb and autistic

>14 steps
>2 eggs

Attached: 1530982531344.png (560x632, 141K)

>(log_2(100)+1)*2
Mr. Brainwojak, please tell me how you came up with this idea. What is the logic behind it?

You have two eggs, assume that the correct answer was 24 th floor.

>drop from 50
< 1st egg is die
>drop from 25
< 2nd egg is die

floor breaks at 50

you drop at 50 it doesn't
breaks on 75
breaks on 63
breaks on 57
breaks on 53
breaks at 52
does not breaks at 51

get fucked shitbrain, less than 10 eggs

see

first egg breaks at 58 and second egg breaks at 52 retard

14 steps only 2 of them involve an egg breaking

Are you this retarded?

it's just log_2(100)+1 peabrain

it now breaks at 26

Can you explain why your going to check 38 instead of 12 if I know you are not suppose to know its breaking at 26?

n-1, n-2, so on. n+ (n-1) + (n-2) + (n-3) + ... + 1

The only correct answer is binary search because this is the proven and understandable standard.
Coming up with original ideas costs money.

it breaks at 50
at 25 it doesn't break
because at 25 it doesn't break you check up, and now you can even reuse the egg you dropped at 25 and you drop it at 37 retardino, not 38, the next floor you drop it is 25+(50-25) div 2

Are you being retarded on purpose? You have two eggs and an unlimited number of throws. If the second egg breaks and you still haven't found the floor (like in your example for floor 24), your algorithm is wrong because it doesn't solve the problem at all, which is worse than solving it suboptimally. I'm pretty sure you're either trolling or don't understand the problem.

>apply shitty MUH 14 algo to 100 floors problem
>upper management comes in, Dubai prince wants to drop eggs from 13337 story building
>algo falls apart hilariously
>company bankrupt
Binary search master race still operating, learn your lessons, kids.

binary search doesn't work for this, you only have two eggs. Read the thread.

T W O E G G S

>breaks at 50
>breaks at 25
Where do you get the third egg from to determine that it breaks at 24?

Go suck a dick you engineer or go fuck a doll you CS major

there is nowhere in the problem that says you are only given two eggs or that you can't go at walmart to buy yourself more eggs to find the question
I mean sure the first sentence says two eggs, but then it doesn't say you are allowed only those eggs to break

also it's impossible to find the answer with only two eggs

Yeah well get more than 2 eggs.

Binary search does work because you dont break the egg dropping it from lower floors, so you can run down and pick it up again. If the egg does break... you're done- you found the floor.

It isnt the most efficient way though.

Maybe you should read the question. You only get two eggs.
>Don't read RFP
>break both eggs with shitty binary search
>engineer is fired and blacklisted and personally sued
>company goes bankrupt

>nowhere in the problem does it say you have only two eggs
It says so in the first 4 words.

If you are going to be this autistic at a job interview I would bring you back for more interviews just to waste your time.

>its impossible to find the answer with only two eggs

Explain how partitions of 14 makes it impossible with only two eggs.

Disregard, i meant linear search, bottom-up, not binary.

> you can't go at walmart to buy yourself more eggs to find the question
I mean sure the first sentence says two eggs, but then it doesn't say you are allowed only those eggs to break

yeaah I'm sure it goes well, if you include this in your answer.

explain ME how a partition of 14 allows you only two eggs to use

be sure to include in your interview how with only two guesses you can find a number from 1 to 100

What a fucking retard.
The logic is the same as binary search.
You start with 50
25
12
6
3
1

It takes 6 tries at most

((log_2(13337)+1)*2)-1=28

Replace 14 with 28

I honestly hope you are just a troll at this point

>be sure to include in your interview how with only two guesses you can find a number from 1 to 100
my female intuition

Reminder the optimal algorithm is LINEAR SEARCH because it only breaks 1 egg and is not some exotic bullshit algorithm that only works for a 100 story building.

By not using binary search

Not OP but the problem here is your first egg breaks at 50, and your second egg breaks at 25, and then you only did two drops and can't drop anymore.

I'm still not sure how to prove that 14 is the right answer.

Show me a situation where you can't find the floor with two eggs and partitions of 14.

Show me a situation where you can find that it breaks on the 24th floor with only two eggs.

I bet most of the wise guys that ask these questions in the interviews wouldn't come up with the answer if they didn't know it already.

>only works for a 100 story building
((log_2(x)+1)*2)-1

Describe to me a building with X stories where partitions wouldn't work

No because then the egg survives at 25 so you go up instead of down.