Amazon Interview Question




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

logN

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

logN

- gevorgk on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on April 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you elaborate your answer??

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

more explanation pls

- dmelloleslie on 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 on 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 on April 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What us ":="

- Agent on 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 on 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 on 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 on 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 on December 02, 2010 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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