Google Interview Question
Below is my analysis:
64-bit max int number is 9,223,372,036,854,775,807
4Ghz speed means 4,000,000,000 cycles / sec
For 1 cycle it takes 1 / 4,000,000,000 sec = 0.00000000025 sec
Lets the below code takes 20 machine cycles to run the for loop each time for one number to verify
for( ; val > 0; val++)
{
// cout << val << endl;
}
So, total time take is
9,223,372,036,854,775,807 * 0.00000000025 * 20 seconds ~= 74 years
Small correction to above analysis:
int max number is 2^63 - 1 (Not 2^64)
2^63 / 2^32 seconds = 68 years
And the for loop will take around 20 cycles to run each loop
so total time will be 68 * 20 = 1360 years
1GHz = 10^9 HZ
1HZ = cycles per second
signed long = 2^63-1
cpu cycles for 'inc': suppose 1
(((2**63-1)*1)/10**9) / 60 / 60 / 24 = 292 years
I think the key here is to demonstrate if 4Ghz gives you any clue to complete the math without calculator.
So let's assume increment takes one cycle, 4ghz will be able to increment 32 bit in one second.
So now I know it will take one second to increment lower 32 bits one time, which means it will take 4 billion seconds to increase the whole 64 bit ... which is divided by 60 is roughly 66 million minutes ... and so on
Default is signed integer whose range is from -(2^32) to (2^32)-1
1GHz = 1000MHz = 10^6KHz = 10^9Hz (cycles per second)
Since initially the value is 0 we have to increment 2^32 times to overflow the counter.
Assuming it takes one cycle to increment by 1 it takes (2^32)/(10^9) seconds which is 4.2949673 seconds.
isnt it 2^64 -1 ??, for four bit integer the max value is 15, which is 2 ^ 4 -1 . correct me if am making any mistake below.
1hz is 1 cycle per second
4ghz, 1/ (4 * 10^9) will give the time taken per cycle.
assuming each increment takes a cycle we have 2 ^ 64 cycles. ignoring the -1
(2 ^ 64) / ( (4 * 10^9) * 60 * 60 * 24 * 365 ) ~= 146 years.
is this correct?
4gig ~= 2^32, assuming each instruction sent to cpu increments the counter by 1, it will take 2^64/2^32, ie..2^32 seconds (136 years) to increment it.
- Harshal July 08, 2011