## 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
of 0 votes

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
of 0 votes

@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
of 0 votes

Can you elaborate your answer??

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

more explanation pls

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

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] => ?

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More