Amazon Interview Question for Software Development Managers


Country: India




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

Number should be as small as possible (e.g. 40 -> 58, not 85), easily remedied by following the procedure and adding the digit to a priority queue if the next product is >= 10.

However, the above algorithm still doesn't work for 12. The algorithm will follow 2 * 2 * 3 -> 4 * 3 -> 34, but the answer ought to be 26.

Operating on the principle of using fewest digits by combining as many small factors as possible is nice, but instead of an array of single digit primes, consider using all digits from 9 to 2:

PriorityQueue<Integer> digits = new PriorityQueue<Integer>();
for(int factor = 9; factor > 1; factor--) {
	while(N % factor == 0) {
		N /= factor;
		digits.add(factor);
	}
}
if(N != 1) return -1;

Just poll all elements of the priority queue and concatenate, will yield smallest K.

- Booley January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Good solution.

I think it's possible to use a Stack instead of a priority queue because the numbers are added in a non increasing order, hence there's no point for the data structure itself to maintain the order of its elements.

public static int getK(int n){
		if (n<1){return -1;}
		if (n==1){return 1;}
		
		Stack<Integer> factors = new Stack<Integer>();
		int rem = n;
		for (int d=9;d>=2;d--){
			while (rem % d == 0){
				factors.push(d);
				rem/=d;
			}
		}
		int k = 0;
		while (!factors.isEmpty()){k = 10*k + factors.pop();}
		
		return (rem==1) ? k : (-1);
	}

- IvgenyNovo January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

// divide the number from 9 to 2
// if given number is divided by more then once from one digit then divide
record all the divider
and then sort the divider in ascending order

bool findAllDivident( int p_number, vector<int> &p_divident ){

      int l_startDivide = 9;
      int l_index=0;
      for(; l_startDivide >= 2 && p_number != 1; ){
 
           if( (p_number % l_startDivide ) == 0 ){
                 p_divident.push_back( l_startDivide ) ;
                 p_number /= l_startDivide;
           }
           else 
              l_startDivide--;
      }
      return p_number == 1? true : false;
      

}

//after that sort the vector we will get lowest number

- Aalok January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

h+t+t+p://ideone.com/Kc7xHM

- Aalok January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int productOfDigitsEqualToNumber(int inputNumber) {
        if (0 <= inputNumber && inputNumber <= 9) {
            return inputNumber;
        }
        if (inputNumber < 0) {
            inputNumber = Math.abs(inputNumber);
        }
        int smallestNumber = 0;
        int factor = 1;
        while (inputNumber > 1) {
            for (int i = 9; i > 1; i--) {
                if (inputNumber % i == 0) {
                    inputNumber = inputNumber / i;
                    smallestNumber = smallestNumber + i * factor;
                    factor = factor * 10;
                    if (inputNumber == 1) {
                        return smallestNumber;
                    }
                    break;
                } else if (i == 2) {
                    return -1;
                }
            }
        }
        return -1;

}

- techpanja January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. To be the smallest number, all the digits have to be in ascending order.
2. To get those digits, keep dividing N with numbers from 2 thru 9 (Lets say this is "i" in a for loop of 2 thru 9).
3. If N is divisible by i, divide and store the result of the division back in N. Keep this "i" as left most digit of the result. If N is still divisible, repeat this step without incrementing the for loop counter (i).
4. One more last point, to get the lowest number run the loop in reverse, i.e. from 9 thru 2.
5. Finally after all divisions done, we should get N = 1 for a success use case. Else make the result as -1.
6. Break from the loop if you get N = 1.

Sample Input: 100
N = 100
Start i = 9 (100 is not divisible by 9). Keep decrementing i by 1.
Hence i = 8, 7, 6, 5 (100 is divisible by 5)
    N = N / i. thats N = 100/5 = 20. Keep i as the leftmost digit of the result. result = 5.
    N is still divisible by 5.
    N = N / i. thats N = 20/5 = 4. Keep i as the leftmost digit of the result. result = 55.
    Now N is no more divisible by 5.
Decrement i by 1. i = 4 (4 is divisible by 4)
    N = N / i. thats N = 4/4 = 1. Keep i as the leftmost digit of the result. result = 455.
Now N = 1, Exit.
Result = 455

Sample Input: 16
N = 16
Start i = 9 (16 is not divisible by 9)
Decrement i by 1. i = 8 (16 is divisible by 8)
    N = N / i. thats N = 16/8 = 2. Keep i as the leftmost digit of the result. result = 8.
Decrement i by 1. i = 7 (100 is not divisible by 7). Keep decrementing i by 1.
Hence i = 6, 5, 4, 3, 2 (2 is divisible by 2)
    N = N / i. thats N = 2/2 = 1. Keep i as the leftmost digit of the result. result = 28.
Now N = 1, Exit.
Result = 28

Here is the java code...

public static void main(String[] args) {
		int number = 100;
		int result = 0;
		int count = 1;
		for (int i = 9; i > 1; i--) {
			while (0 == number % i) {
				result = i * count + result;
				number /= i;
				count *= 10;
			}
			if (1 == number) break;
		}

		if (1 != number) result = -1;
		System.out.println(result);
	}

- gourahari.das January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// divide the number from 9 to 2
// if given number is divided by more then once from one digit then divide
record all the divider
and then sort the divider in ascending order

bool findAllDivident( int p_number, vector<int> &p_divident ){

      int l_startDivide = 9;
      int l_index=0;
      for(; l_startDivide >= 2 && p_number != 1; ){
 
           if( (p_number % l_startDivide ) == 0 ){
                 p_divident.push_back( l_startDivide ) ;
                 p_number /= l_startDivide;
           }
           else 
              l_startDivide--;
      }
      return p_number == 1? true : false;
      

}

//after that sort the vector we will get lowest number

- Aalok January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the below solution will do.

[1] Find the largest single digit divisor of given number, this digit will form the rightmost digit of K
[2] Next repeat [1] to find the next largest single digit divisor of the quotient of [1] which is less than or equal to digit found in [1]. The digit so found is the immediate left digit of K
[3] If no digit could be found and quotient is > 9 return -1

Examples:

N K Quotient
-----------------------------------
40 8 5
58 1
K=58


N K Quotient
-----------------------------------
26 2 13

As Quotient is > 13, so K =-1

N K Quotient
-----------------------------------
12 6 2
26 1

K=26

- Sayanatn January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done using recursion as below.

void smallestNum(int N)
{
	cout << endl << "In recursion N is:" << N <<endl;
	int iQuotient;
	static int i;
	static int iSmallestNo[10] ;
	bool isNotPrime = false;

	for(int iDivisor=9;iDivisor > 1;iDivisor--)
	{
		if(!(N % iDivisor))
		{
			isNotPrime = true;
			iQuotient = N/iDivisor;
			cout << endl << "quotient is :"<<iQuotient;
			cout << endl << "divisor is :" << iDivisor;
			iSmallestNo[i] = iDivisor;
			i++;
			cout << endl << "w is :" << iSmallestNo;
			if(iQuotient > 1)
				smallestNum(iQuotient);
			
			break;
			
		}
	}
	int count = --i;
	if(!(isNotPrime))
	{
		iSmallestNo[0] =  -1;
	}
	cout << "\n finally smallest number is :";
	while(count>=0)
	{
		cout << iSmallestNo[count];
		count--;
	}
}

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

Yet another solution:
}}}
public static int calculateSmallestK(int N) {

int K = -1;
int buf = N;
int order = 1;

while ( buf > 9) {
if(isPrime(buf)) return -1;
for (int i = 9; i >= 2; i--) {
if (buf % i == 0) {
if (K==-1) K=0;
buf = buf / i;
K += i * order;
order *= 10;
i=9;
}
}
}
return K;
}

static boolean isPrime(int n) {
for(int i=2;i<n;i++) {
if(n%i==0)
return false;
}
return true;
}
}}}

- Anonymous February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yet another solution in plain java:

public static int calculateSmallestK(int N) {

		int K = -1;
		int buf = N;
		int order = 1;

		while ( buf > 9) {
			if(isPrime(buf)) return -1;
			for (int i = 9; i >= 2; i--) {
				if (buf % i == 0) {
					if (K==-1) K=0;
					buf = buf / i;
					K += i * order;
					order *= 10;
					i=9;
				}
			}
		}
		return K;
	}
	
	static boolean isPrime(int n) {
	    for(int i=2;i<n;i++) {
	        if(n%i==0)
	            return false;
	    }
	    return true;
	}

- Valera February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i=9; k=0;
while (N!=1 && i<10 && i>0) {
	if(N%i==0)
	{
		a[k++] = i;
		i=9;
		N=N/i;
	}
	else {
		i=i-1;
	}
}

if(N!=1) {return -1;}

for(i=a.length;i>0;i--)
{
	print(a[i]);
}

- test July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using recursion:

#include <iostream>

using namespace std;

int append( int num, int digit )
{
   return 10*num + digit;
}

int calc( int val, int result = 0 )
{
  if( val < 10 ) return val;

  for( int i = 9; i > 1; i-- )
  {
    if( val % i == 0 )
    {
      int sub = calc( val / i, result );
      if( sub > 0 )
        return append(sub, i);
    }
  }

  return -1;
}

main()
{
  int num;

  cout << "Number: ";
  cin  >> num;

  cout << calc(num) << endl;
}

- Jason September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        int num = 20;
        String numbers = "";
        while (num != 1) {
            for (int i = 9; i <= 9 && i != 0; i--) {
                if (num % i == 0) {
                    numbers += "" + i;
                    num = num / i;
                    i = 9;
                    break;
                }
            }
           
        }
        int result=0; 
        int givenNum = Integer.parseInt(numbers); 
        while(givenNum!=0) {
            result = result *10 + givenNum%10;
            givenNum/=10;
        }
        System.out.println(result);
    }

- Lefteris Bab October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The people saying to brute force divide by 2 - 9 are missing the elegance of this problem (thus showing the interviewer that they tend to brute force things).

A number is always either prime or composite. If it is composite then it can be broken into a product of primes. Prime decomposition is unique. The prime decomposition of 26 is 13 and 2. Since 13 is not a single digit number, 26 cannot be expressed as several 1 digit numbers multiplied together. Hence why in the example the problem returns k=-1.

If a given N does have a solution it will be of the form (2^a)(3^b)(5^c)(7^d)
Check for divisibility by 2,3,5 and 7 using the modulo operation. Use this to find the values of a,b,c and d.

while a>=3, subtract 3 from a and add an 8 to the end of your number
while a>=1 and b>=1, subtract 1 from a and 1 from b and add a 6 between 5 and 7
while a>=2, subtract 2 from a and add a 4 between 3 and 5.
while b>=2, subtract 2 from b and add a 9 to the end of your number.


expand all your numbers out (eg 2^a becomes 22222....a times).
And that's it.

- IIAOPSW February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1) Divide number in multiple of 2,3,5,7 of number. For given number: 2 * 2 * 5 *5
2) Backward, keep on multiplying adjacent number as long as multiple is a single digit (< 10) and create new digit and put new digit in place of that number. for given number: 4 * 5* 5
3) repeat step 2, u wont have to do it much.concatenate digits in sorted order. Result it: 455
4) if number can not be divided into multiple of 2, 3, 5, 7 only, then return -1

Example: 40 =>  2 * 2 * 2 * 5 = 8 * 5 =  5 * 8 = 40
Example: 1260 => 2 * 2 * 3 * 3 * 5 * 7 = 4 * 9 * 5 *  7 = 4 * 5 * 7 * 9 = 4579
Example: 12 => 2 * 2 * 3 = 2 * 6 = 26

- SK January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@booley.
yes, u r right.
Well, it can be modified a bit. Instead of multiplying digits from front, we can do it from backward and then print digits in sorted order.
changing it.

- SK January 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static void Main(string[] args)
        {
            int sayi = Convert.ToInt32(Console.ReadLine());
            //iteration number
            int donmeSayisi = sayi / 2;
            //list of numbers that can divide "sayi" 
            List<int> bolenListesi = new List<int>();
            for (int i = 2; i <= donmeSayisi; i++)
            {
                if (sayi % i == 0)
                {
                    bolenListesi.Add(i);
                    sayi = sayi / i;
                    i--;
                }
            }
            //returns -1
            if (bolenListesi.Any(a => a > 9) || bolenListesi.Count == 0)
            {
                Console.WriteLine(-1);
            }
            //returns number
            else
            {
                int donme = bolenListesi.Count - 1;
                for (int i = donme; i >0 ; i--)
                {
                    if (bolenListesi[i] * bolenListesi[i - 1] < 10)
                    {
                        bolenListesi[i] = bolenListesi[i] * bolenListesi[i - 1];
                        bolenListesi.RemoveAt(i - 1);
                    }
                }
                //Sort it
                List<int> liste = new List<int>();
                for (int i = 0; i < bolenListesi.Count; i++)
                {
                    liste.Add(0);
                }
                foreach (int item in bolenListesi)
                {
                    int c = 0;
                    foreach (int item1 in bolenListesi)
                    {
                        if (item > item1)
                        {
                            c++;
                        }
                    }
                    int b = liste.Count(a => a == item);
                    liste[c + b] = item;
                }
                bolenListesi = liste;
                bolenListesi.RemoveAll(a=>a<1);
                Console.WriteLine(string.Join("", bolenListesi));
            }
            Console.ReadLine(); 
        }

it works

- Anonymous January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about this?

int smallestK(int N)
{
    int e2 = 0; int e3 = 0; int e5 = 0; int e7 = 0;

    while (N % 2 == 0) { e2++; N /= 2; }     // number of factor 2
    while (N % 3 == 0) { e3++; N /= 3; }     // number of factor 3
    while (N % 5 == 0) { e5++; N /= 5; }     // number of factor 5
    while (N % 7 == 0) { e7++; N /= 7; }     // number of factor 7

    if (N != 1)  
        return -1;

    int a = e2 % 3;
    int b = e2 / 3;

    int k = 0; 

    if (a == 1)
        k = 2;
    else if (a == 2)
        k = 4;

    while (b-- > 0) k = k * 10 + 8;

    a = e3 % 2;
    b = e3 % 2;

    if (a)
        k = k * 10 + 3;

    while (b-- > 0) k = k * 10 + 9;
    while (e5-- > 0) k = k * 10 + 5;
    while (e7-- > 0) k = k * 10 + 7;

    return k;
}

- Jason January 28, 2014 | 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