Amazon Interview Question






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

logN

- Anonymous April 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

logN

- gevorgk April 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you explain this more please

- BabelFish April 01, 2010 | Flag Reply
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.

- ash April 02, 2010 | Flag Reply
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 .

- spookymulder83 May 20, 2010 | Flag
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;
}

- kaka April 02, 2010 | Flag Reply
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.

- oceantin April 04, 2010 | Flag Reply
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;
}

- Anonymous April 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- propane April 06, 2010 | Flag
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)))

- Zaphod April 05, 2010 | Flag Reply
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.

- Zaphod April 05, 2010 | Flag Reply
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)

- M April 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you elaborate your answer??

- Leslie April 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

more explanation pls

- dmelloleslie April 06, 2010 | Flag
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.

- Anonymous April 12, 2010 | Flag
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

- ha April 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What us ":="

- Agent May 01, 2010 | Flag Reply
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)

- bansal.cool May 29, 2010 | Flag Reply
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?

- chenming831 June 04, 2010 | Flag Reply
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;

}
}

- Anonymous August 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- lxz December 02, 2010 | Flag Reply
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] => ?

- srinath April 09, 2017 | Flag Reply


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