Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #11975 > unrolled thread

Re: Hardest Google Interview Question

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Hardest Google Interview Question Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-23 00:02 -0700
    Re: Hardest Google Interview Question Willem <willem@toad.stack.nl> - 2011-10-23 08:53 +0000
      Re: Hardest Google Interview Question Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-23 02:21 -0700
        Re: Hardest Google Interview Question Willem <willem@toad.stack.nl> - 2011-10-23 09:40 +0000
          Re: Hardest Google Interview Question Richard Damon <news.x.richarddamon@xoxy.net> - 2011-10-23 11:48 -0400
      Re: Hardest Google Interview Question arnuld <sunrise@invalid.address> - 2011-10-25 05:26 +0000
    Re: Hardest Google Interview Question Mark Bluemel <mark_bluemel@pobox.com> - 2011-10-25 08:52 +0100
      Re: Hardest Google Interview Question falk@rahul.net (Edward A. Falk) - 2011-10-25 19:47 +0000
      Re: Hardest Google Interview Question Sjouke Burry <b@p.nl> - 2011-10-26 22:51 +0000

#11975 — Re: Hardest Google Interview Question

On Oct 23, 8:39 am, divya bisht <bisht88.di...@gmail.com> wrote:
> Hardest Google Interview Question
>
> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
>
Drop from first floor. If it doesn't break, pick up the egg, and try
the second floor, and so on. When it breaks, you know the critical
floor.
--
Visit my website, lots of programming goodies
http://www.malcolmmclean.site11.com/www

[toc] | [next] | [standalone]

#11978

Malcolm McLean wrote:
) On Oct 23, 8:39?am, divya bisht <bisht88.di...@gmail.com> wrote:
)> Hardest Google Interview Question
)>
)> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
)>
) Drop from first floor. If it doesn't break, pick up the egg, and try
) the second floor, and so on. When it breaks, you know the critical
) floor.

If this is the puzzle I think it is, you're supposed to have two eggs, and
the question is to determine the minimal number of drops which guarantees
an answer.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#11981

On Oct 23, 10:53 am, Willem <wil...@toad.stack.nl> wrote:
> Malcolm McLean wrote:
>
> ) On Oct 23, 8:39?am, divya bisht <bisht88.di...@gmail.com> wrote:
> )> Hardest Google Interview Question
> )>
> )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
> )>
> ) Drop from first floor. If it doesn't break, pick up the egg, and try
> ) the second floor, and so on. When it breaks, you know the critical
> ) floor.
>
> If this is the puzzle I think it is, you're supposed to have two eggs, and
> the question is to determine the minimal number of drops which guarantees
> an answer.
>
The obvious method is a binary search. However you are only allowed to
break a maximum of two eggs, and you have 100 floors to search, so it
won't work.

[toc] | [prev] | [next] | [standalone]

#11982

Malcolm McLean wrote:
) On Oct 23, 10:53?am, Willem <wil...@toad.stack.nl> wrote:
)> Malcolm McLean wrote:
)>
)> ) On Oct 23, 8:39?am, divya bisht <bisht88.di...@gmail.com> wrote:
)> )> Hardest Google Interview Question
)> )>
)> )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
)> )>
)> ) Drop from first floor. If it doesn't break, pick up the egg, and try
)> ) the second floor, and so on. When it breaks, you know the critical
)> ) floor.
)>
)> If this is the puzzle I think it is, you're supposed to have two eggs, and
)> the question is to determine the minimal number of drops which guarantees
)> an answer.
)>
) The obvious method is a binary search. However you are only allowed to
) break a maximum of two eggs, and you have 100 floors to search, so it
) won't work.

The obvious method with 2 eggs is to use the first egg in increments of 10
floors until it breaks, and then use the second on the 10-floor interval
below the floor where the first one broke.  19 drops worst case, IICC.

But you can do better than that.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#11993

On 10/23/11 5:40 AM, Willem wrote:
> Malcolm McLean wrote:
> ) On Oct 23, 10:53?am, Willem<wil...@toad.stack.nl>  wrote:
> )>  Malcolm McLean wrote:
> )>
> )>  ) On Oct 23, 8:39?am, divya bisht<bisht88.di...@gmail.com>  wrote:
> )>  )>  Hardest Google Interview Question
> )>  )>
> )>  )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
> )>  )>
> )>  ) Drop from first floor. If it doesn't break, pick up the egg, and try
> )>  ) the second floor, and so on. When it breaks, you know the critical
> )>  ) floor.
> )>
> )>  If this is the puzzle I think it is, you're supposed to have two eggs, and
> )>  the question is to determine the minimal number of drops which guarantees
> )>  an answer.
> )>
> ) The obvious method is a binary search. However you are only allowed to
> ) break a maximum of two eggs, and you have 100 floors to search, so it
> ) won't work.
>
> The obvious method with 2 eggs is to use the first egg in increments of 10
> floors until it breaks, and then use the second on the 10-floor interval
> below the floor where the first one broke.  19 drops worst case, IICC.
>
> But you can do better than that.
>
>
> SaSW, Willem

These sort of questions aren't really all that great for interviews, as 
they are the sort of thing that if you have seen this particular one 
before, it becomes trivial, if not, it requires a bit of thought, and 
the pause to do that becomes unnatural in the interview. They much more 
test how the interviewee handles being flustered under pressure than 
problem solving. Unless you are interviewing for something like tech 
support where your expect them to be hit with weird questions as part of 
their line of work, they aren't that good of a measure.

As to this particular one, the key is to turn the problem around a bit. 
If we ask how tall of a building can we measure with n drops and m 
broken eggs.

If we are only allowed to break 1 egg, then the only way to solve it is 
to start at the lowest floor and keep moving up, until we break, and 
thus we can measure an n story building.

If we are allowed to break 2 eggs, then we can say that for the first 
drop, assuming it breaks, we have n-1 drops left, so by above we could 
measure n-1 floor below, so if we drop from the n story, and it break, 
we can use our second allowed break to figure out which floor it would 
happen at. If it doesn't, then we have n-1 drop left, and by the same 
logic we can go up n-1 more stories, to floor n+(n-1) for this drop. 
Continuing on, we eventually get to the floor n+(n-1)(n-2)...+1 which is 
known to be floor n*(n+1)/2 (the formula for triangle numbers)

we can then extend this to breaking 3 eggs, and we will end up 
sequencing on the pyramid numbers (the sum of triangle numbers), but 
this is beyond what we need to do for this problem.

Since we have a 100 story building, this requires an n of at least 14. 
So we drop the first egg from floor 14, if it doesn't break the next 
from floor 27, then 35, 46, ... and when we break an egg, you start from 
the floor above which you last didn't break and move up.

Of course, the real flaw with the problem is it assumes something that 
is unlikely, that both eggs would have broken from exactly the same 
height, and that drops from a lower height don't affect the height that 
the egg can stand before it does break. If you don't make these 
unwarranted assumptions I don't think it is possible to find a solution.

[toc] | [prev] | [next] | [standalone]

#12070

> On Sun, 23 Oct 2011 08:53:31 +0000, Willem wrote:

> If this is the puzzle I think it is, you're supposed to have two eggs,
> and the question is to determine the minimal number of drops which
> guarantees an answer.

My best guess, interviewer is trying to check guy's algorithmic analysis 
skills





-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#12075

On 10/23/2011 08:02 AM, Malcolm McLean wrote:
> On Oct 23, 8:39 am, divya bisht<bisht88.di...@gmail.com>  wrote:
>> Hardest Google Interview Question
>>
>> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....

I never follow blogspot links, I understood them to be basically bait 
for click farming.

[toc] | [prev] | [next] | [standalone]

#12093

In article <j85q1v$sfc$1@dont-email.me>,
Mark Bluemel  <mark_bluemel@pobox.com> wrote:
>
>I never follow blogspot links, I understood them to be basically bait 
>for click farming.

Google finally cracked down on it a year or so ago; now most of
the blogspot blogs are legitimate.  AFAIK, that is.

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

[toc] | [prev] | [next] | [standalone]

#12133

Mark Bluemel <mark_bluemel@pobox.com> wrote in
news:j85q1v$sfc$1@dont-email.me: 

> On 10/23/2011 08:02 AM, Malcolm McLean wrote:
>> On Oct 23, 8:39 am, divya bisht<bisht88.di...@gmail.com>  wrote:
>>> Hardest Google Interview Question
>>>
>>> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.
>>> ... 
> 
> I never follow blogspot links, I understood them to be basically bait 
> for click farming.
> 
> 

Hear, hear!!!.nl

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web