Amazon Interview Question
Software Engineer / Developers Systems Design EngineersCountry: India
Interview Type: Phone Interview
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);
}
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
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.
I didn't get the logic with the explanation given above, can you please explain me in detail, if possible.
@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.
Why can't you simply use a if condition like the following :
if( (N*(Log (N))) == log(K) )
It's N*lg N == lg K.
But how would you calculate lg K and lg N? Wouldn't they require some exponential calculations?
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.
@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..
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"));
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.
> 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
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.
I think the question is, given a number find whether it is perfect square or not...
ex.
input answer
15 false
16 true
30 false
100 true
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
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)
- sqw June 11, 2012