## Interview Question

Software Engineer Interview

-Sydney

Google## Suppose that you earn 100% annual interest (APY) on $1 initial deposit. How long before you'll be as rich as Bill Gates ($63 billion)? Given a number, e.g., 314159, as an array [3,1,4,1,5,9], increment it: change it to [3,1,4,1,6,0].

Answer

## Interview Answers

17 Answers

▲

6

▼

Taking just the information we are given and ignoring taxes etc. 100% annual (compound) interest is the same as doubling your investment every year. So for the first four years it would go like this: $1, $2, $4, $8, $16, $32, ... Look familiar? Therefore: 63 Billion = 2^x or x = log2(63 billion) In an interview we wouldn't be able to throw this into a calculator so we would need to do it by hand. We can estimate powers of 2 as powers of 1000: 2^10 ~= 1000^1 2^20 ~= 1000^2 etc. Therefore 63 billion = 63 * 1000^3 or approximately = 63 * 2^30 We know that 64 is 2^6 so we can substitute that with the 63 to get: 2^6 * 2^30 which = 2^36 log2 of 2^36 is 36 Therefore you would have $63 billion after 36 years. Now if we validate with the calculator we see that after 36 years we would actually have about $68/$69 billion. While if we only waited until 35 years we would only have $34 billion.

Sam on

▲

2

▼

It toke ^ 10 to for 2 to reach 1k. So it will take ^ 30 to reach 1b. Then u need another ^ 6 to just pass 63b. S the answer is 36 years.

Gus on

▲

1

▼

Possible Java Array Incrememnt Function

Anonymous on

▲

1

▼

#!/usr/bin/python -tt arr = [3,1,4,1,5,9] def incArr(a, p=-1): """To increase the argument number represented by an array of digit from MSD to LSD by one.""" if (p < 0): p = len(a) if (p == 0): a[0:0] = [1] elif (a[p-1] == 9): a[p-1] = 0 incArr(a, p-1) else: a[p-1] = a[p-1] + 1 incArr(arr) print arr

Jacky on

▲

0

▼

#!/usr/bin/env perl my @a = (3,1,4,1,5,9); my $n = join "", @a; print ++$n;

Kostas on

▲

0

▼

Update (I missed the part where you need to give back an array) : #!/usr/bin/env perl my @a = (3,1,4,1,5,9); my $n = join "", @a; $n++; my @b = split //, $n; #@b contains your answer

Kostas on

▲

0

▼

Golf: perl -MData::Dumper -e'@a=(3,1,4,1,5,9);$b=join "",@a;print Dumper([split //,++$b]);'

Kostas on

▲

0

▼

The first answer should be 6 years

Shri on

▲

0

▼

An int is ~4billion , 32 bits , can solve it from there as 37.

anonymous on

▲

0

▼

def shift(arr): arr = reduce(lambda x,y: x+y,arr) def incr_arr(arr,arrlen): arr_len = arrlen #print arr #print arr_len # base case arr_len = 0 if arr_len == 0: arr[0:0] = [1] # base case arr_len = 1 elif arr_len == 0 and arr[0] ==9: arr[0,1] = [1,0] # all other cases elif arr[arr_len-1]==9: arr[arr_len-1] = 0 incr_arr(arr,arr_len-1) else: arr[arr_len-1] = arr[arr_len-1]+1 # test cases arr = [9,9]; print arr,"---",; arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [9];print arr,"---",; arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [0,1]; print arr,"---",;arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [1,9]; print arr,"---",;arr_len = len(arr); incr_arr(arr, arr_len); print arr

Anonymous on

▲

0

▼

def incr_arr(arr,arrlen): arr_len = arrlen #print arr #print arr_len # base case arr_len = 0 if arr_len == 0: arr[0:0] = [1] # base case arr_len = 1 elif arr_len == 0 and arr[0] ==9: arr[0,1] = [1,0] # all other cases elif arr[arr_len-1]==9: arr[arr_len-1] = 0 incr_arr(arr,arr_len-1) else: arr[arr_len-1] = arr[arr_len-1]+1 # test cases arr = [9,9]; print arr,"---",; arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [9];print arr,"---",; arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [0,1]; print arr,"---",;arr_len = len(arr); incr_arr(arr, arr_len); print arr arr = [1,9]; print arr,"---",;arr_len = len(arr); incr_arr(arr, arr_len); print arr

Anonymous on

▲

0

▼

Was good

Anonymous on

▲

0

▼

yes definitely it should be in 36year right

fasahat khan from karachi pakistan B-64 blk 4-A Gulshan e iqbal karachi journalist society 75300 on

▲

0

▼

int main() { cout > Balance; return 0; Year=1balance: 2 Year=2balance: 4 Year=3balance: 8 Year=4balance: 16 Year=5balance: 32 Year=6balance: 64 Year=7balance: 128 Year=8balance: 256 Year=9balance: 512 Year=10balance: 1024 Year=11balance: 2048 Year=12balance: 4096 Year=13balance: 8192 Year=14balance: 16384 Year=15balance: 32768 Year=16balance: 65536 Year=17balance: 131072 Year=18balance: 262144 Year=19balance: 524288 Year=20balance: 1.04858e+06 Year=21balance: 2.09715e+06 Year=22balance: 4.1943e+06 Year=23balance: 8.38861e+06 Year=24balance: 1.67772e+07 Year=25balance: 3.35544e+07 Year=26balance: 6.71089e+07 Year=27balance: 1.34218e+08 Year=28balance: 2.68435e+08 Year=29balance: 5.36871e+08 Year=30balance: 1.07374e+09 Year=31balance: 2.14748e+09 Year=32balance: 4.29497e+09 Year=33balance: 8.58993e+09 Year=34balance: 1.71799e+10 Year=35balance: 3.43597e+10 Year=36balance: 6.87195e+10

Iyad on

▲

0

▼

// Possible Java Array Incrememnt Function public static void inc(ArrayList input) { for (int i = input.size() - 1; i >= 0; i--) { if (input.get(i) == 9) { if (i == 0) { input.set(i, 1); input.add(0); } else { input.set(i, 0); } } else { input.set(i, input.get(i) +1); break; } } }

Lachlan on

▲

0

▼

Sorry for TYPO (if there are) Each element in the array is a digit in which its value is an integer between 0 to 9. We start with the Least Significant Bit (LSB) at the array and add increase it by 1. For example if the number is 123 than the array will look like: [1, 2, 3] What we do is 3 + 1 = 4 If the result of the operation is smaller than 9 than we write the result at the cell which represent this digit at the array. In the above example the result of the increase will be: [1, 2, 4] When the result is bigger than 9 than we we write 0 at the cell which represent this digit at the array and remember to add 1 at the next stage (the next stage we add 1 to the next Significant bit). For example to increase 129 [1, 2, 9] we perform 9 + 1. the result is 10 than we write 0 in the LSB (where the digit 9 used to be) [1, 2, 0] Next we continue to increase the next Significant bit , in that example we increase 2. i.e and again ask if the result is bigger than 9. 1 + 2 So, in our example, after the next step, it will look like : [1, 3, 0] we continue to do so up until the result of the digit is less than 10. Please pay attention to the following case (overlap) [9, 9, 9] I will leave you all my dear to treat it ;)

The Dude on

▲

1

▼

@Sam That's not actually correct as you have not considered the first year where money increases from $1 to $2, so the correct answer is 37 years...

Sarp on

## Add Answers or Comments

To comment on this, Sign In or Sign Up.