STOP RIGHT THERE YOU CUM GUZZLING WHALE VAGINA

STOP RIGHT THERE YOU CUM GUZZLING WHALE VAGINA

>A building has (input) N floors. One of the floors is the highest floor an egg can be dropped from without breaking.
If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.
>You are given two identical eggs, find the minimal number of drops (output) it will take in the worst case to find out the highest floor from which an egg will not break.

2.

O(N / 2)

Drop from middle, if it breaks start from floor 1 and work your way up.

If it doesn't break, start from middle + 1 and work your way up.

Forgive me for being a brainlet but if I were to program this, would the highest floor an egg wouldn't break from be a random int 1 to N or >1 &

tard detected
If you do that:
>let k be the highest floor
>for k=49, N=100:
>egg breaks at 50
>You now have to test each one floor: starting from 1 and making 50 tests total
Now consider checking every, say, 20 (for N=100):
>worst case scenario is you need around 25 tests

Or you can do it like an sort of shell sort approach.

Start a 1/4 up, if it breaks, test the lower 1/4.If it doesn't break, try 2/4. If it breaks at 2/4. Test 1/4+1 up to 2/4-1. If it doesn't break, try at 3/4. etc...

Generalise that in order to show that you're not a mental midget.

>k=19, N=100
>egg breaks at 20 (attempts, n=1)
>have to test every step i for i in range 1 to n-1
There's gotta be a general solution to finding partitions that's better though.

Don't feel like it
You also have to note that it's better to have the tests spaced out somewhat closer together near the end than in the beggining
there is, but I'm a lazy tard

>You also have to note that it's better to have the tests spaced out somewhat closer together near the end than in the beggining
So step/partitions are a logarithmic function.

If you start at sqrt(N), the maximum number of steps is 2*sqrt(N)-1 when moving through the floors in a naive way. But when you reach the top, you'll want to recurse to sqrt(sqrt(N)). That gets you down to 2*sqrt(N)-2 for sufficiently large value of N. After that, I'm not sure you can optimize further.

>If it doesn't break, start from middle + 1 and work your way up.
Ahh, you didn't think it through, brainlet.
Since the egg isn't broken, you can split the upper amount of floors in half, and do the drop with the first egg, until it breaks.

Then, with the second egg you only do the floors from the second last drop until the last drop.

Just do a binary search, you fucking faggot

log n

You're not Mr.birb >:o

Theoretical limit is O(sqrt(N)) for 2 eggs, but for specific N, you can find a slightly better solution.

3 eggs is cube-root of N.

not pure log n, since there are two eggs, and you use the second one to find the max floor.

>Ahh, you didn't think it through, brainlet.
>Since the egg isn't broken, you can split the upper amount of floors in half, and do the drop with the first egg, until it breaks.
Oh, yeah right.

If a stair has N steps, and you can climb either one or two steps for each step. How many permutations of ways to climb those stairs is there?

I was asked this on an interview for a position at Google (and I nailed it, but didn't get the job because I wasn't a culture fit).

Create a generating function of a = a-1 + a-2.

Also known as?

The Fibbonacci sequence.

Correctomundo

Try round(n/2)=a
For i

O(log(N)) if you do a binary search

Binary search doesn't work since you only get two eggs. Worst case scenario is N/2.

Array(0)=a
i=1

>Worst case scenario is N/2.
See and +

he meant for binary seearch

That's not technically binary search though. That's just partitioning it into two and searching linearly. You can partition it into 3 or 4 or 5 or whatever, hence the general solution is

>That's just partitioning it into two and searching linearly.
Well, yes, that's my point. Binary search doesn't work and you need a more sophisticated algorithm such as

divide and conquer?

I can do 1000 floors with 44 drops.

The idea is of this problem is to powergame the algorithm so that it is specifically optimized for the worst case (at the expense of the average case). This is why binary search answers are wrong.

Enlighten me senpai

Please explain

The worst cases should be equal, if they're not you're wasting drops somewhere else that could be used on that worst case.
That means the number of first egg drops plus the number of possible floors once it breaks (because must linear search with 2nd egg) should stay at a constant.
What is this constant?

A stair that has only one step can only be climbed in one way, by taking one step.

A stair that has two steps can be climbed in two ways, either by taking one+one step or by taking a single two-step step.

A stair with three steps is the sum of the above, you can either climb it one+one+one, or two+one or one+two, giving you three ways to climb it.

So for N steps, the function becomes f(N) = f(N-1) + f(N - 2)

>generating function for simple recurrence
boi

Every vertex of a graph has at least N neighbors, prove there is a cycle that's at least N+1 long.

It's 45 drops for 1000 floors you fucking brainlet

There was a thread about finding new relevant questions for interviews.
This would be dope to test recursion skills.

>a vagina in a vagina in a vagina in a vagina

1 because I'm not a retard and know that eggs break when dropped from damn near any height

They're fucking eggs, they'll break from one story. There has got to be a better way to set up this problem.

It's vaginas all the way down.

>inb4 muh titanium eggs

O(N/2 + 1).

Start dropping from bottom. Move 2 floors higher. Continue if it doesn't break. When it breaks, move one floor down. If it breaks then, it's the floor. If it doesn't, the right one is higher one.

You can use only two eggs and if at one point it breaks then you didn't find out the point, the algorithm cant continue etc.

That's the worst solution yet.

Do your own homework.

I'd rather make an omelet.

Start from the middle. If it breaks, move half-way down. If it doesn't, half-way up and so on..

>Start from the middle. If it breaks, move half-way down
And it breaks there as well. Now you've wasted your two eggs and you didn't find the floor.

...

>..find the minimal number of drops
Please tell me how you plan to find 1/100 floors in two tries.
>>>reddit

one egg 1/3 of the way up, the other 1/6. work in quarters or halves from there.

>Please tell me how you plan to find 1/100 floors in two tries.
Not in two tries, but in 2 * sqrt(N) tries.

I can do it in 0. It's a fucking egg - it breaks every time.

What if the building is on the moon or somewhere else where gravity is reduced?

Or the building is really small?

Or under water, or where air is blowing upwards so the fall is slowed down due to the displacement effect?

Obviously they're not chicken eggs.

That adds extra conditions to the problem. If we could just do that then we'd have infinite solutions to every problem.

must be either directed or undirected with vertexcount > 2 or you can easily disprove by a 2-chain

the egg will always break if dropped from the third floor
so 0

> create army of chickens
> wait for them to drop eggs
> hav moar egz
> drop one egg every floor

ADVANCED ALGORITHMS, BRO

>tfw you're a System Administrator(R) Master Race(TM) and you don't have time for this shit.
Kill yourselves, code monkeys.

It’s undirected.
Obviously doesn’t hold for N=1, but I believe it hold for N>1, including 2.

It's pretty apparent no one else is going to answer the original question.

ceiling((sqrt(8 n + 1) - 1) / 2)

2 drops.

You drop it at the bottom floor, just above the floor. It does not crack. You drop it from the second floor. No egg can survive a two story drop.