## Amazon Interview Question

Comment hidden because of low score. Click to expand.
0
of 0 vote

logN

Comment hidden because of low score. Click to expand.
0
of 0 vote

logN

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you explain this more please

Comment hidden because of low score. Click to expand.
0
of 0 vote

so according to Anon, 3^6 can be calculated in 2.58 steps? please explain.

Comment hidden because of low score. Click to expand.
0

Its actually ceil(2.58) steps i.e. 3 steps.
For 3^6 you calculate a = (3x3x3) in 2 steps and a x a in 1 step .

Comment hidden because of low score. Click to expand.
0
of 0 vote

if we have to calculate 2^10 , instead of multiplying 10 times, we just calculate pow(4,5) and so on. Copied the below code from somewhere, hope it helps

function power_for_quicker( value, power ) {
var result = 1;
while ( power != 0 ) {
if ( power & 1 == 0 ) {
value = value * value;
power = power / 2;
} else {
result = result * value;
power = power - 1;
}
}
return result;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The smallest number of multiplications should be log(n).

suppose you have aaaaaaaaaaaaaa....... First calculate axa, which is the 1st multiplication, then you do axa x axa, which used the 2nd multiplication, then axaxaxa x axaxaxa which is 3rd multiplication, keep going. It takes log_2 (n) multiplications.

Comment hidden because of low score. Click to expand.
0
of 0 vote

number_of_multiplication = Power/2;
if(Power%2 >0){
++number_of_multiplication;
}

Comment hidden because of low score. Click to expand.
0

@kaka and @anonymous.. we can use only := and x

Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't think so...
floor(log_2(n))+ (n-pow_2(floor(log_2n)))

Comment hidden because of low score. Click to expand.
0
of 0 vote

if b = 2^n -1 (m is integer), it takes 1/2*n mutliplications approximately.

Comment hidden because of low score. Click to expand.
0
of 0 vote

a^n=a^n/2 ⋅a^n/2 if n is even;
a^(n–1)/2 ⋅a^(n–1)/2 ⋅a if n is odd.

Θ(lgn)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

more explanation pls

Comment hidden because of low score. Click to expand.
0

it should be a^((n-1)/2).a^((n+1)/2) if n is odd.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. first compute N1 and N2 defined as:
N1 = floor(log2(n))
N2 = n - 2 ** N1

2. the number of multiplications needed is,
m = N1 + (# of bits set to 1 in N2)

(example)
the following is the example when n = 14:
N1 = floor(log2(14)) = 3
N2 = n - 2 ** N1 = 14 - 8 = 6
m = 3 + 2 = 5

a ** 14 is computed as follows using 5 multiplications.
a2 = a * a
a4 = a2 * a2
a8 = a4 * a4
a12 = a8 * a4
a14 = a12 * a2

Comment hidden because of low score. Click to expand.
0
of 0 vote

What us ":="

Comment hidden because of low score. Click to expand.
0
of 0 vote

2*LOG(N) IN WORST Case

A^n = a^N/2 *A^N/2 (N EVEN)
A^N = A^N/2* A^N/2*A (N IS ODD)
1) t(N) = T(N/2) +1 FOR EVEN
2) T(N) = T(N/2) +2 FOR ODD

for worst case we need to consider the 2nd case.
assuming number is power is like somwthing like 2^n -1 then after divison
power will always be odd.

so, t(n) = 2 + t(n/2)
t(n/2) = 2+ t(n/4)
t(n/4) = 2+ t(n/8)
t(n)= 2+ 2 +2 +..
--------------------
(log(n) steps)
t(n) = 2log(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Then how can a calculator knows how many multiplications it should do since there is no addition? Anybody can write down the codes?

Comment hidden because of low score. Click to expand.
0
of 0 vote

//x^n
int pow(int x, int n)
{
if ( n == 0 )
return 1;

if ( n == 1 )
return x;

if ( n == 2 )
return x * x;

if ( n % 2 == 0 )
return pow ( x * x, n/2);

return pow(x*x, n/2)*x;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check Jeff Edmonds' book "How to think about algorithms"

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a dynamic programing question. We need to figure out
d[1] => 1 (just 2)
d[2] => 1(2x2)
d[3] => 2 (2x2x2)
d[4] => 2 (d[2]+d[2])
d[5]= > 3 (d[4]+d[1])
d[6] => 3 (d[3] + d[3])
:
:
d[n] => ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.