Amazon Interview Question for SDE1s

Country: United States
Interview Type: Written Test

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

Perfect powers in linear time?

``````boolean isPerfectPower(int n) {

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

double temp = Math.log(n)/Math.log(i);

if (Math.ceiling(temp) == temp) { return true;}
}

return false;
}``````

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

your solution will not work for 125 (example): this number not perfect square but represent as 5 power 3.

my solution to check p power q presentation is (this solution checking any power is available. also trick to minimize the operation is i*i <= n):

``````static bool IsPowerPresented(int n)
{
if (n == 0)
throw new Exception("wrong input");
if (n == 1)
return true;

if (n == 2)
return true;

int temp = n;
for(int i=2; i*i <= n; i++)
{
temp = n;
while(temp > 1)
{
if (temp % i != 0)
break;
temp = temp / i;
}

if (temp == 1)
return true;
}

return false;
}``````

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

when i = 5, it will see that log(125)/log(5) = 3 which is an integer

what do you mean it doesn't work?

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

For me (C#) : Value of : Log(125)/Log(5) is coming as :
temp = 3.0000000000000004

and Ceiling value (4) not equal to temp.

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

After some changes it works perfectly. This is how I got correct answer after improving your code. Btw, your logic is awesome!

``````static boolean isPerfectPower(double n) {

for (double i = 2; i*i < n; i++) {

double temp = Math.log(n)/Math.log(i);

System.out.println(temp);
System.out.println(Math.round(temp));
if (Math.abs(Math.round(temp) - temp)<0.00000000000001) { return true;}

}

return false;
}``````

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

hey thanks! :)

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

Simple one -

Find all the prime factors of the number 'N'. If they occur in sets (or) if all the prime factors are same, then it can be expressed in form p^q.

Example : N=216, factors = {2,2,2,3,3,3}. here every prime factor has its set (i.e. {2,3} ) which is repeated, hence it can be represented in P^q format which is (2*3)^3 i.e. Product of numbers in every Set raised to the power of number of such sets.

If N=32 with prime factors (2,2,2,2,2) all are same, hence true

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

Since when is prime factorization simple?

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

Bug in question. Every number can, right? n = n ^ 1, where n and 1 are integers.

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

Given p != 1 and q != 1, the solution is

``````<?php

function div(\$der, \$dee, &\$cache) {
\$key = \$der . ',' . \$dee;
if (!isset(\$cache[\$key])) {
if (\$der % \$dee == 0) {
if (\$der == \$dee) {
\$cache[\$key] = true;
} else {
\$cache[\$key] = div(\$der / \$dee, \$dee, \$cache);
}
} else {
\$cache[\$key] = false;
}
}
return \$cache[\$key];
}

function isPower(\$n, &\$cache) {
if (!isset(\$cache[\$n])) {
\$res = false;
for (\$i = 2; \$i < \$n; \$i++) {
if (isPower(\$i, \$cache)) {
continue;
}
if (div(\$n, \$i, \$cache)) {
\$res = true;
break;
}
}
\$cache[\$n] = \$res;
}
return \$cache[\$n];
}

\$cache = [];
for (\$n = 2; \$n < 1000; \$n++) {
print \$n . ": " . (isPower(\$n, \$cache) ? "true" : "false") . "\n";
}``````

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

The idea is :
1. Factorize the no *n* into prime factors.
2. Now a factorisation is a list of ( prime, multiplicity ) pair. Check that if all the multiplicity values has a GCD >1.
See the code from here : [question?id=5742470735331328]

``````// ZoomBA
def gcd( a,b ){ // copied from wikipedia
while ( b != 0 ){
t = b ; b = a % b ; a = t
}
return a
}

def is_expressible( n ){
multiplicities =  select ( lfold ( [2:n+1] , dict() ) -> {
continue ( exists ( \$.p.keySet ) :: {  \$.o /? \$.\$.o } )
\$.p[\$.o] = 0
for ( x = n ; \$.o /? x ; x/= \$.o ){ \$.p[\$.o] += 1 }
\$.p
} ) :: { \$.o.value > 0 } -> { \$.o.value }
// calculate gcd of all the multiplicities
final_gcd = reduce ( multiplicities ) -> { gcd( \$.p , \$.o ) }
final_gcd > 1 // for a non trivial solution
}``````

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

cr.yp.to/papers/powers.pdf
here is an algorithm that interviewer wanted to hear

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

lol. interviewer would faint.

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

``````import java.util.Random;
import java.util.Scanner;

public class PerfectPower {
public static void main(String[] args) {
int N;
Scanner sc = new Scanner(System.in);
N = new Random().nextInt(Integer.MAX_VALUE);
System.out.println(isPerfectPower(N));
sc.close();
}

static boolean isPerfectPower(int N){
int limit = (int)Math.sqrt(N);
for(int j = limit;j>=2;j--){
//for(int j = 2;j<=limit;j++){
int num =N;
while(num%j==0 && num>1)num=num/j;
if(num==1)
return true;
}
return false;
}
}``````

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

Sorry, I was trying to find with for loop was better so used random function and run the code a million time.
Please replace the line for fetching random number by

``N = sc.nextInt();``

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

Complexity of this algorithm is O(k*n^1/2). Where k is the minimum q value.

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

C#, Assumption:input number is a positive integer
----------------------------------------------------------------
///

bool IsPower(int num)
{
if (num <= 3) return false;

IList<int> primeList = new List<int>();
int count = 0;
while(num % 2 == 0)
{
num /= 2;
count++;
}

for(int i = 3; i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
num /= i;
count++;
}

}

if (primeList.Count() == 0) return false; // a prime number which is greater than 3

using (var enumerator = primeList.GetEnumerator())
{
enumerator.MoveNext();
var current = enumerator.Current;

if (current == 1) return false;

while(enumerator.MoveNext())
{
if (current != enumerator.Current) return false;

}
}

return true;
}

\\\

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

``````boolean canBeExpressedInP&Q(int N){

int [] array=new int[(int)Math.sqrt(N)];// create array to count the number of prime factor.
int n=N;
Arrays.fill(array,0);// fill with zero
for(int i=2;i<=Math.sqrt(N);i++){          // N=216=> 2*108(N=108) that's why Math.sqrt(N)
while(N%i==0){
array[i]++;// count number of prime like 216=2*2*2*3*3*3, array[2]=3 and array[3]=3
N=N/i;      // divide N every time we get any prime factor
}
}
//Now check array if all elements are equal excluding zero element.
int max=0;
for(int i=2; i<sqrt(n);i++){
if(array[i]!=0 && max==0){// first time max is initialize with 3, for N=216,
max=array[i];
}
else if(array[i]!=0 && array[i]!=max){
return false;
}
}// end of for loop., array[0]=0, array[1]=0, array[2]=3, array[3]=3;
return true;
}``````

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

``````bool pq(int n)
{
int i = 2;
std::map<int, int> counts;

if (n < 0)
return false;

while (n > 1) {
if (n % i == 0) {
counts[i]++;
n = n / i;
} else {
i++;
}
}

int c = -1;

for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
if (c == -1) {
c = iter->second;
} else {
if (c != iter->second)
return false;
}
}

if (c > 1)
return true;

return false;
}``````

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

``````bool pq(int n)
{
int i = 2;
std::map<int, int> counts;

if (n < 0)
return false;

while (n > 1) {
if (n % i == 0) {
counts[i]++;
n = n / i;
} else {
i++;
}
}

int minCount = INT_MAX;

for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
if (iter->second > 0 && iter->second < minCount)
minCount = iter->second;
}

if (minCount < 2 || minCount == INT_MAX)
return false;

for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
if (iter->second % minCount)
return false;
}

return true;
}``````

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

Take it the other way:

``````#include <stdio.h>

int main(void)
{
int i, val, cnt, n = 26345 * 26345;

for (i = 2; i * i <= n; i++) {
val = i;
cnt = 1;
while (n != val && !(n % val)) {
cnt++;
val *= i;
}
if (n == val) {
printf("%d=%d^%d\n", n, i, cnt);
break;
}
}
return 0;
}``````

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

``````public static boolean expression(int number){
if(number==1){
System.out.println("expression:1^1");
return true;
}
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int i=2;i*i<=number;i++){
if(number%i==0){
}
}
boolean canBeExpressed = false;
for(int i=0;i<arr.size();i++){
if(getPQExpression(arr.get(i),number)){
canBeExpressed =true;
}
}
return canBeExpressed;
}
private static boolean getPQExpression(int factor, int number) {
int count = 0;
while(number%factor==0){
number = number/factor;
count++;
}
if(number==1) {
System.out.println("expression:"+factor +"^"+count);
return true;
}
return false;
}
public static void main(String[] args) {
expression(125);

}``````

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

package temp2;
import java.util.Scanner;

public class praiseq {

public static void main(String[] args) {
double num,p=1,q=1;
Scanner s = new Scanner(System.in);
System.out.println("enter a value");
num = s.nextInt();
do{
p++;
q=1;
do{
q++;
System.out.println("" + p + q);
if(Math.pow(p,q) == num){
System.out.println(num + "is in the form of p^q");
System.exit(0);
}
}while(Math.pow(p,q) < num);

}while(Math.pow(p,2) <= num);

if(Math.pow(p,q) != num){
System.out.println(num + "is NOT in the form of p^q");
System.exit(0);
}
}

}

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

``````public static void main(String[] args) {
int n = 250;
findsol(n, 0);
}

private static int findsol(int num, int count) {

for (int i = num; i > 0 && count < 2; i--) {
if (Math.sqrt(i) % 1 != 0) {
continue;
} else {
count++;
int j = num - i;
int result = 0;
if (!(count >= 2) && j != 0)
result = findsol(j, count);
if (i + result == num && count < 3) {
System.out.print((int) Math.sqrt(i) + " ");
return i;
}
if (count >= 2)
return 0;
count = 0;
}

}
return 0;
}``````

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

``````int num1 = 1025;

HashSet<Integer> primeFactors = new HashSet<Integer>();

for(int i = 2; i< num1; i++) {
int remainder = num1 % i;
boolean aPrime = false;
for(Integer j : primeFactors) {
if(i % j == 0) {
aPrime = true;
}
}

if(remainder == 0 && !aPrime) {
}
}

if(primeFactors.size() > 1) {
System.out.println(num1+" cannot be represented as p^q");
} else {
System.out.println(num1+" can be represented as p^q");
}``````

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

Check out this one simple solution..

``````#include <bits/stdc++.h>
#define ll long long
using namespace std;

bool solve(ll n) {

int b;
for(int a = 2; a <= sqrt(n); a++) {
b = 1;
ll temp = pow(a,b);
while(temp <= n && temp > 0) {
if(temp == n) {
cout << a << " raised to the power of " << b << " = " << n << endl;
return true;
}
else {
b++;
temp = pow(a,b);
}
}

}

return false;
}

int main()
{

int n;
cin >> n;
if(!solve(n)) cout << "No" << endl;

return 0;
}``````

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

``````import java.io.BufferedReader;
import java.io.IOException;

public class PerfectSquareNumber {

public static void main(String[] args) throws IOException{
System.out.print("Please enter an integer : ");

int sqrt = (int) Math.sqrt(number);
if(sqrt*sqrt == number) {
System.out.println(number+" is a perfect square number!");
}else {
System.out.println(number+" is NOT a perfect square number!");
}

}
}``````

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

import java.io.IOException;

public class PerfectSquareNumber {

public static void main(String[] args) throws IOException{
System.out.print("Please enter an integer : ");

int sqrt = (int) Math.sqrt(number);
if(sqrt*sqrt == number) {
System.out.println(number+" is a perfect square number!");
}else {
System.out.println(number+" is NOT a perfect square number!");
}

}
}

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

how about using binary search solve this problem
will be O(logn)

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

A brute-force method in java. Can be improved with memoization et al, and most likely has overflow errors.

``````//
//  Assumes that p and q are both > 1, so n must be >= 4.
//
public static boolean nCanBePToTheQ(long n) {
if (n <= 4) {
return true;
}

for (int p = 2; p < n; p++) {
// trivial reject if n isn't a multiple of p
if ((n % p) != 0) {
continue;
}

for (int q = 2; q < n; q++ ) {
long pToTheQ = (long) Math.pow(p, q);
if (pToTheQ > n) {
break;
}

if (pToTheQ == n) {
System.out.printf("Woo-hoo! %d^%d == %d", p, q, n);
return true;
}
}
}

return false;
}``````

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

{{
#include <stdio.h>

int main(void) {
int num=4,temp=0,p=0,q=0;
int i,j;
for(i=2;i<=num/2;i++)
{
for(j=1;j<=num/2;j++)
{
if(pow(i,j)==num){temp=1;p=i;q=j;}
}
}
if(temp==1)
{
printf("no. found p=%d and q=%d",p,q);
}
return 0;
}
}}

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.