## Amazon Interview Question for Software Engineer / Developers Systems Design Engineers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

``````boolean check(long N, long K) {
for (long i=0; i<N-1; i++) {
K = K/N;
}
return (K==N);
}``````

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

This seems excellent. Just one optimization.
This makes the case such as N=6 and K=7 to run faster.

``````boolean check(long N, long K) {
for (long i=0; i<N-1; i++) {
K = K/N;
if(K<N)
return false;
}
return (K==N);
}``````

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

K can't be held in long...it could be up to (1000)^1000

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

to sk:
The question says: "0<=N , K<=1000".

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

I think, by mistake it is given there otherwise N can't be greater 4

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

``````for(int i=0; i<n-1; i++){
if(k%n == 0)
k = k/n;
else
return false;
}
return true;``````

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

the best way can be ...

if ( (logK)/(logN) == N )
return true;

Here we can consider logarithm of any base as ... log(a) / log(b) = log of 'a' to the base b.
hence log(K)/log(N) == N ==> "logarithm of K to the base N" == N
==> K == N^N

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

Ex. N = 3, K = 27 taking base = 2,10 or any except 3.
In this case division of float to float may not be consistence.
log(2)27/log(2)3 = float/float ==> may not be equal to N(=3)

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

We can find the last k digits in binary using modular exponential method.

Algorithm :-
Match the digits of N^N mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Make K = K/N.
Match the digits of N^(N-1) mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Do this recursively till the exponential reduces to 0.

In the worst case when the numbers are equal all the numbers are required to be matched.

The finding of number of digits in K/N still needs to be figured out without doing the actual division.

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

I didn't get the logic with the explanation given above, can you please explain me in detail, if possible.

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

@vinay :- We can calculate the last D digits of any exponential by modular exponential method, i.e. b^e mod (10^d) would give me the last d digits of b^e in O(lg e).
Here, what I am trying to do is to find the last d digits of N^N where d is number of digits in K/N (don't know yet how to calculate this), which I am matching with the last d digits of K.
Doing this recursively, dividing K and N^N with N and then finding the digits in N^(N-1) and matching the same, till all digits are matched.
Though there are things that need to be added to make it complete, but I think it should make the idea clear.

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

Why can't you simply use a if condition like the following :

``if( (N*(Log (N))) == log(K) )``

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

It's N*lg N == lg K.
But how would you calculate lg K and lg N? Wouldn't they require some exponential calculations?

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

``it shouldn't be  if(log((base_n)k)==n)....?``

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

How to calculate log((base_n)k ? Java provides native method for calculating log. If that can be used and is constant time (don't know) then I think the above would work.
Otherwise calculating the same would require calculating N^N which we want to avoid.

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

``@Achilles: u are right.. internally to compute log(base_n)K, it'll take the same time as computing N^N.. but we can check unit digit of k just to check whether it's divisible by n or not, so if not then n^n!=k, it'll be in constant time and if yes,then i think it'll take same time as to compute n^n..``

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

Since we know bounds on n.
We can pre-process and store the digits of n^n as array of long's.

Now for any call to the funtion we represent k as array of long's, pick the appropriate pre-processed array corresponding to n and then compare the arrays.

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

you can calculate sum = k / n; if sum == 0 then return false, else you can calculate next, if you can divide n times;

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

if K<=1000 then how can N be greater than 4. Wha's the worry??

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

no pls ignore that K<=1000, it s typo.. k can be ie N^N can be of 1000 digits !!!

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

this problem can be solved even linear algorithm , but I think O(logn) double squaring algorithm can be used to make it faster , but with only 1000 digits , Java's BigClass implementation is the way to go , or u can write ur own Big Class .

/* Bug may exists beware */

``````public static boolean check(int n,String k) {

BigInteger N = new BigInteger(n+"");
BigInteger K = new BigInteger(k);
BigInteger res = new BigInteger("1");

if (N.compareTo(K) ==0 )
return true ;

for (int i = 1 ; i  <= n ; i++) {

res = N.multiply(res) ;
//System.out.println(res);
if (res.compareTo(K)>0)
return false ;
if (res.compareTo(K) ==0 )
return true ;

}
return false ;

}

System.out.println(check(30,"101010101010010101010101010101010100110010101010101001010101010101010011"));``````

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

Set of (K, N) such that (N^N = K) and (0 <= K <= 1000) = [(1, 1), (2, 4), (3, 81), (4, 256)]
Now we can simply check whether (N,K) are part of this pair.

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

> no pls ignore that K<=1000, it s typo.. k can be ie N^N can be of 1000 digits !!!

Ok, this was not mentioned in original question, hence I missed.

O(1) solution with no overhead of large numbers.

ghci> let powerCheck n k = n == logBase n k
ghci> powerCheck 2 4
True
ghci> powerCheck 3 26
False
ghci> powerCheck 10000000 6565656 False ghci> powerCheck 9 387420489
True

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

I think then u may need Magic ;-)

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

I do not know how efficient it is but I have a O(n) solution.
if we just try to see that for each element in (0 to n-1)[ Zn as in the abstract algebra] appear in K. if all of them appear n times it is n^n then it is other wise not

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

Initially we can check whether n is a factor of k or not
if(k%n==0)
then only we need to check further, otherwise return false directly.

and if it returns true then we can check whether n is even or odd in that way we need to loop only for logarithmic time that is greater improvement .

if n is even then proceed in multiples of n
eg:
if(n%2==0){
int flag=n;
for(i=0;i<n;i++)
{
k=k/flag;
if(k==1) return true;
flag=flag*flag;
}
return false;
}
similar could be handled for n being odd only 1 more iteration required in that case.

so in this case we didn't need to check again and again for same value of n and value of n increases in each iteration.. that is n, n^2, n^4, n^16..... so the algorithm runs in logarithmic time, that is greater improvement than naive approach.

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

Can you clarify what you mean here? Are you given only k? n? or both

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

all are +ve integers

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

Cool. So you are given both n and k. Am I right?

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

I think the question is, given a number find whether it is perfect square or not...
ex.

15 false
16 true
30 false
100 true

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

No it's n to the power n i.e. n^n Example
3^3 = 27 true
2^2 = 5 false

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

if(Math.pow(n,n)==k)

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

Cannot use any predefined function

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

how about nlog(n) == log(k)? however i am using predefined log function.

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

n is too too big....

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

if n is too big then how can u use int for n

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

``````private static bool EqualPower(int n, int k) {
if (n >= k) {
return false;
}

int pow = n;
for (int i = 1; i < n; i++) {
pow *= n;
}
if (pow == k) {
return true;
}
return false;
}``````

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

given n and k such that n^n=k
divide k/n untill 1 and count the loop ,if count==n is satisfied return true

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

n is too too big.... I answered curious by mistake....

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

Modular Exponential problem
N <= 1000, that means N can be expressed in 10 bits

``````function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result``````

modular_Pow(N, N, K)

since exponent N is 10 bit, while loop will iterate 10 times.
If the return result is 0 then N^N is divible by K

running time of this alogithm is (log N)

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

@banerjee36, did you try below approach

Here is the logn approach

``````int power(int n,int k)
{
int p;
if(k==0)
return 1;
else
{
p=power(n,k/2);
p*=p;
if(k&1)
p*=n;
return p;
}
}

int main()
{
int n=3,k=27;
power(n,n)==k?printf("Yes"):printf("No");
return 0;
}``````

***ideone.*com/oEpgE***

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

boolean isKnpown(int n, int k) {
int temp=k;
for ( int i = 1; i <=n ; i++ ) {
if ( temp%n != 0 ) {
return (false);
}
temp= temp/n;

}
return true;
}

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

Sum of first n odd numbers will be square
This gives a solution to without multiplication.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

basically N^2 = K or N = Sqrt(K)
its easier to check this even for K = 1000, N = Sqrt (K)... is easier to check....

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

We need to check the Nth root of K and not simply sqrt

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.