root
Posts:
54
Registered:
8/26/09


Re: the hourglass problem
Posted:
Jan 1, 2012 12:51 AM


RichD <r_delaney2001@yahoo.com> wrote: > You're given a 7 minute, and a 4 minute, sand > hourglass. Measure a 9 minute interval, in the first > 9 minutes. (no 'setup' period) > > ok, this is trivial. But as computer nerds, we're > interested in general solutions. So, given hourglasses > of n and m minutes: > > 1) Can you devise a formula which generates a list of > all possible intervals produced by them? > > 2) And an algorithm, which generates the interval, > for any given number on the list. > > Of course, this is solvable via brute force, but we > want something efficient. > > PS The problem stated above is a Google > interview question! Which lowers my estimate of > their intellectual prowess. > >  > Rich
This problem is very interesting. After you realize how to get 9 minutes, you then realize you are able to get 4 minutes, 7 minutes, and then every integer minute thereafter. So the numbers realizable without delay are: 4,7,8,9,10,11,12........
Then, clearly, with a 7 minute delay you can generate every integer minute.

