Bloomberg LP Interview Question
Software Engineer / DevelopersQuestion: does that mean that one fly produces two of the same flies after a minute, or that one fly produces another fly after a minute? Does each fly that is produced reproduce?
Assuming that one fly produces another after a minute:
t[n]=total number of flies in the jar after n minutes
t[0]=1
t[1]=2
t[2]=4
..
t[60]=2^60 (when the Jar is 100% full)
t[n]=2^n
The Jar is 75% full when there are 3/4*2^60 flies. 2^n=3/4*2^60 => n ~ 59.584
But n is an integer. In the stage of reproducing, it is possible that a fly will increase in size gradually. Therefore the 75% capacity is achieved somewhere in between 59-60 minute.
From anonymous comment on July 16th,
The Jar is 75% full when there are 3/4*2^60 flies. 2^n=3/4*2^60
this is also equal to 3* 2^58 = (2+1) * 2 ^58 = 2^59 + 2^58.
It reaches to 2^59 in 59 mins.
now for it to double it takes 1 minute which means from 2^59 to 2^60 (which is 2^59 for 1 min).
If it takes 1 min for producing 2^59, how much time it will take to become 2^58?
2^58/2^59 = 1/2 min
So total time would be 59.5 mins...
correct me if I am wrong...
Let n be the number of minutes the fly replicates.
In 60 minutes, the jar is full and the total number of flies will be 2 ^ 0 + 2 ^ 1 + .. + 2 ^ n = 2 ^ (n + 1) - 1 where n = 60.
When the jar is 3/4 full after m minutes, the number of of flies is 3/4 * [2 ^ (n + 1) - 1].
We need to find m such that 2 ^ (m + 1) - 1 = 3/4 * [2 ^ (n + 1) - 1] where n = 60
Take a logarithm of base 2 of both sides and simplifies
m + 3 = log3 + (n + 1) => m = 60 + 1 - 3 + log3 = 58 + 1.58 = 59.58 minutes, approximately 59 minutes and 35 seconds
60 minutes only. As at 59 minutes it will be half filled , so the period of replicating is 1 minute (it can't replicate before that-- similar to 9 month human cycle) so there can;t be any time between 59 and 60. Jar will never be 75% . It will become 100% at 60 minute itself
- Tarun July 15, 2010