Amazon Interview Question for SDE1s


Country: United States
Interview Type: Written Test




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

public int findDivisibleNum(int k) {
        Set<Integer> numList = new ConcurrentSkipListSet<>();
        numList.add(0);
        numList.add(1);

        for(int i = 10; i < Integer.MAX_VALUE; i = i * 10) {
            HashSet<Integer> newList = new LinkedHashSet<>();
            for(Integer num : numList) {
                newList.add(num + i);
            }
            for(Integer num : newList) {
                if(num != 0 && num % k == 0) {
                    return num;
                }
            }
            numList.addAll(newList);
        }
        return -1;
}

- srikanth February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

My assumptions:

1. Ones and Zeros number must be ~evenly~ divisible by A (probably obvious).
2. Begin the sequence at 10 ("0" and "1" aren't eligible)
3. The problem domain is constrained to <= 1111111111 (max signed int containing only 1 and 0 digits).

int smallestOneZeroMultiple(int A)
{
   for (int i = 2; 2 < 1111111111; ++i)
   {
       // Convert i from binary format to decimal "1's and 0's"
       int multiple = 0;
       for (int j = 0; i < 32; ++j)
       {
           if (i & (1 << j))
              multiple += 10 ^ j;
       }
        
       if ((multiple % A) == 0)
          return 
   }

   return -1; // Couldn't find a multiple
}

- sk3l February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Whoops, I screwed up on line 10. Want to raise 10 to the power j, not XOR 10 and j :-p

- sk3l February 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int smallestOneZeroMultiple(int divisible)
{
int mul=2;
int re=mul*divisible;
while(re<1111111111){
if(CheckOnlyOneZero(re))
return re;
mul++;
re=mul*divisible;
}
return -1;
}

bool CheckOnlyOneZero(int num){
	int i=0;
	while(num>=10){
	i=num%10;
	num=num/10;
	if(i==1 || i==0)
		continue;
	else 
		return false;
	}
		if(num==1 || num==0)
		return true;
	else 
		return false;
}

- codder007 February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

{
int isAllowed(int val){
	while(val){
		int rem;
		rem = val % 10;
		if(rem!=0 && rem!=1) return 0;
		val = val / 10;
	}
	return 1;
}

int findSmallest(int A){
	int i = 0;
	while(1){
		if(i != 0 && i % A == 0 && isAllowed(i)) {
			printf("Found:%d",i);
			return i;
		}
		i++;
	}
}

}

- IlkerBurak February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another text-based (and therefore not efficient or elegant) answer in java.

This compiles and works, but dies for A >= 396. (Interview question: why?)

public static long findCoolNumber(int a) {
    for (long result = 1; result < Long.MAX_VALUE; result++) {
      String binValue = Long.toBinaryString(result);
      long toDecimal = Long.parseLong(binValue);
      if ((toDecimal % a) == 0) {
        return toDecimal;
      }
    }

    return 0; // or other sentinal, or throw exception if you like.

  }

- auricoso2000 February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Given a number A, find the smallest number which has only 1s and 
 * 0s as its digits which divisible by the number A. For example: 
 * if the given number A is 4, the smallest number with 1s and 0s is 
 * which is divisible by 4 is 100.
 * @author lalitazad 
 */
package careercup;

public class FindNumber {

	public static void main(String args[]) {
		FindNumber n = new FindNumber();
		int digits =65;
		int [] bitsArray = new int[digits]; 
		n.createBits( digits,15,15);
	}

	// checks for flipping the bits 
	private int checkMathMul(int count, int power)
	{
		return	( count/((int)Math.pow(2, power))>=1)?1:0;
	}
	
	// generates a sum of the binary representation and divides by the divisor to check perfect divison
	private int checkForDivision(int [] arrayBits, int divisor)
	{
		int sum =0;
		for(int i=0;i<arrayBits.length;i++)
			sum+=(int) Math.pow(10, i) * arrayBits[i];
		System.out.println("sum :"+sum);
		if(sum%divisor ==0)
			return sum;
		return -1;
	}
	
	/*
	 * it creates a binary representation of the array, and check for the smallest dividend. the number is the divisor here! 
	 * */
	private  int[] createBits( int count, int number, int n)
	{
		int []bitsArray  = new int[n];
		for(int i=1;i<count;i++)
		{
			 bitsArray[0] = i%2;
			for(int x=1;x<n;x++)
				bitsArray[x]= 	checkMathMul(i, x);
							
			for(int j=bitsArray.length-1;j>=0;j--)
			System.out.print(bitsArray[j]+" ");
			System.out.println();
			int result = checkForDivision(bitsArray, number);
			if(result != -1)
			{
				System.out.println("Smallest divisor: "+result);
				return bitsArray;
			}
				
		}
		return new int []{};
		
		
	}
	
	
	
	
	
	

}

- Lazad February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implement BFS

1. verify given number is 1 if yes then return true.
2. If if it not then put 1 into queue
3. In while (true) pop queue item, Lets say it is "X"
4. if(INT_MAX/10 < X) return false
5. Multiply X by 10 mod by given number if remainder is zero then return true
6. else add the number to queue.
7. if((INT_MAX-1)/10 > X) return false
8. Multiply X by 10 and add 1 mod by given number if remainder is zero then return true
9. else add the number to queue.

- Tester February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C#
--------------

int DivisibleNmberFinder(int divisor)
{
	Queue<int> q = new Queue<int>();
	
	q.Enqueue(1);
	
	while(q.Count() > 0)
	{
		int number = q.Dequeue();
		
		if (number % divisor == 0) return number;
		else
		{
			string seed = number.ToString();
			if (seed.Length < divisor)
			{
				q.Enqueue(Convert.ToInt32(seed+"0"));
				q.Enqueue(Convert.ToInt32(seed+"1"));
			}
		}
	}
	
	return -1;
}

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

import java.util.TreeSet;

public class SmallestDivisible {

    public static long smallestDivisibleBy(int a) {
	TreeSet<Long> possibles = new TreeSet<Long>();
	possibles.add(10L);
	possibles.add(11L);

	while(!possibles.isEmpty()) {
	    long p = possibles.pollFirst().longValue();
	    if (p % a == 0) {
		return p;
	    }

	    long nextP = p * 10;
	    if (nextP > p) possibles.add(nextP);

	    nextP = nextP + 1;
	    if (nextP > p) possibles.add(nextP);
	}

	return -1;
    }


    public static void main (String[] args) {
	System.out.println(smallestDivisibleBy(Integer.parseInt(args[0])));
    }
}

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

sorry but i didnt understand the question properly i guess.
Please help me to understand......am very new to this site
my understanding is-
1. they are looking for binary of smallest number which is divisible by given number
2. the smallest number which is divisible by any number is that number itself
so they are asking for binary of same number?

- Neha February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry but i think i didnt understand question properly.
Please help me in this.....m very new to this site
My understanding is-
1. they are asking for binary number which is divisible by given number
2. least number which is divisible by any number is that number itself ....
so are they asking for binary of the same number?

- Neha February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findSmallestDivisible(int sum, int n)
{
        if( sum > INT_MAX || sum <=0) return INT_MAX;
        if(sum % n == 0) return sum;
        int min0 = findSmallestDivisible(sum * 10 + 0, n);
        int min1 = findSmallestDivisible(sum * 10 + 1, n);
        return min(min0, min1);
}

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

int findSmallestDivisible(int sum, int n)
{
        if( sum > INT_MAX || sum <=0) return INT_MAX;
        if(sum % n == 0) return sum;
        int min0 = findSmallestDivisible(sum * 10 + 0, n);
        int min1 = findSmallestDivisible(sum * 10 + 1, n);
        return min(min0, min1);
}

- Sachin February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ok, this is really easy, just generate all permutations of 0,1 digits one by one and check if they divide 4, here is a simple c++ code that does it:
int smallestZeroOneDividingN(vector<int>digits, string number, int start, int end, int n)
{
int currentNumber = string_Atoi(number);
if(currentNumber != 0 && currentNumber % n == 0)
{
return currentNumber;
}
if(start == end)
{
return -1;
}
for(int i = 0 ; i < digits.size (); i++)
{
number[start] = digits[i];
int res = smallestZeroOneDividingN(digits, number, start + 1, end, n);
if(res != -1)
return res;
}
return -1;
}

int smallestZeroOneDividingN(int n)
{
vector<int> digits;
digits.push_back(0);
digits.push_back(1);

string number = "";
for(int i = 2; i < INT_MAX; i++)
{
number.resize(i);
int res = smallestZeroOneDividingN(digits, number, 0, number.size(), n);
if(res != -1)
return res;
}
return n;
}

- Zaid March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int helper(int n, String p)
	{
		if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111 && Integer.parseInt(p)%n==0)
			return Integer.parseInt(p);
		else if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111)
			return Math.min(helper(n, p+"0"),helper(n, p+"1"));
		return Integer.MAX_VALUE;

}

- noob March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The easiest way is to keep multiplying the number by every possible integer and checking if the result has only 1's and zeros.

- Ray April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int x = 10;
            int num = 4; //input 
            while (x % 4 != 0)
            {
                x = x * 10;
            }
            Console.WriteLine(x);

            Console.ReadLine();

        }

- deepika April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int x = 10;
            int num = 4; //input 
            while (x % 4 != 0)
            {
                x = x * 10;
            }
            Console.WriteLine(x);

            Console.ReadLine();

        }

- deepika April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

#define INT_MAX 0xFFFFFFFF
int add = 1;

int min(int num1, int num2)
{
if (num1 == -1 && num2 == -1)
{
//couldn't find the min divisible in int range
return -1;
}
else if (num1 == -1)
{
//no divisible in other path
return num2;
}
else if(num2 == -1)
{
//no divisible in other path
return num1;
}
//if both positive
return (num1<num2) ? num1 : num2;
}

int findmindiv(int num, int n)
{
if (num >= INT_MAX || num<=0 || n == 0) return -1;
if (num % n == 0) return num;
int min0 = findmindiv(num * 10 + 0, n);
int min1 = findmindiv(num * 10 + 1, n);
return min(min0, min1);
}

void main()
{
int n;
int more = 1;
while (more == 1)
{
printf("Enter the number:");
scanf_s("%d", &n);
printf("Min divisible made of just 1s and 0s is: %d\n\n", findmindiv(1, n));

printf("More?:");
scanf_s("%d", &more);
}

getch();
}

- Anonymous July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{}}

- Anonymous July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def multiple(n):
    q = Queue.Queue()

    q.put('1')
    while True:
        cur_num = q.get()
        if int(cur_num) % n == 0:
            return cur_num
        q.put(cur_num+'0')
        q.put(cur_num+'1')

- sumitgaur.iiita December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String multiple(int A) {

        Queue<String> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        String temp;
        queue.add("1");
        while (!queue.isEmpty())
        {
            temp = queue.poll();
            int rem = mod(temp,A);
            if (rem==0) return temp;

            if (!visited.contains(rem))
            {
                visited.add(rem);
                queue.add(temp+"0");
                queue.add(temp+"1");
            }
        }

        return "";
    }

    public static int mod(String s,int n)
    {
        int rem = 0;
        int len = s.length();
        for (int i=0;i<len;i++)
        {
            rem = rem*10 + (s.charAt(i)-'0');
            rem = rem%n;
        }

        return rem;
    }

- Rahul August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

FOR MULTIPLES WITH ANY NUMBER OF DIGITS:

struct node{
    string s;
    int rem;
    node(string t, int x){
        this->s = t;
        this->rem = x;
    }
};

string smallestMultiple(int n) {
    queue<node> q;
    q.push(node("1",1%n));
    
    vector<int> seen(n,0);
    
    while(q.size()){
        node x = q.front(); q.pop();
        
        if(x.rem == 0)  
            return x.s;
        
        int rem0 = (10*x.rem)%n, rem1 = (10*x.rem +1)%n;
        
        string s0 = x.s+"0", s1= x.s+"1";
        
        if(!seen[rem0])     q.push(node(s0,rem0)), seen[rem0]=1;
            
        if(!seen[rem1])     q.push(node(s1,rem1)), seen[rem1]=1;
    }
    
    return "-1";
}

- rexwulf October 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

package com.shashi.carrercup;

/**
*
* @author shashi
*/
public class FindNumber {

public static void main(String args[])
{
FindNumber n=new FindNumber();
System.out.print(n.getNumber(4));
}
public int getNumber(int number)
{
//check for invalid condition
if(number<0)
return 0;
//if not do some operations
//let take maximum 8 bit digit
int max=11111111;
int current;
int c1=0;
for(int i=2;i<max;i++)
{
//take the current number
boolean check=false;
current=number*i;
//copy number
c1=current;
while(current>0)
{
int rem=current%10;
if(rem == 0 || rem == 1 )
{
current=current/10;
if(current == 0)
{
check=true;
break;
}
}
else
{
break;
}
}
//you got first min if check is true
if(check)
break;
}
return c1;
}





}

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

package careercup;

public class FindNumber {

public static void main(String args[]) {
FindNumber n = new FindNumber();
n.findIfDivisible(4);
//System.out.print(n.getNumber(4));
}

public int findIfDivisible(int num)
{
int i,count=0;
for( i=10;;i=i*10)
{
if(i%num==0)
break;
//i=i*10;
count++;
if(count>100)
return -1;

}
System.out.println(i);
return i;
}





}

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

We know that any number that only has 1s an 0s can be interpreted as a bit string.
We know that since our maximum bitstring for long is 1111111111 that this is the bit representing 1023.

So we simply find a conversion from all integers from 1 to 1023 (inclusive) to their corresponding bitstring values then check if this bitstring can divide our given number.

It is possible to avoid the overhead of String to long conversion by simply writing your own method for the conversion from int to long directly.

The function convertDecToLong runs in 32 operations since it will bitshift at most 32 times. Running this operations something around 1023 times will give us an estimated ~32000 operations - much better than the brute force of 1111111111 operations.

public static long min(int n) {

        for (int i = 0; i <= 1023; i++) {

                long possibility = convertDecFromBin(i);

                if (isDivisible(possibility, n)) {

                        return possibility;
                }
        }

        return -1;
}

public static long convertDecFromBin(int n) {
       
        long output = 0;
        int x = n;
        int currentDecPlace = 0;
        while (x != 0) {
 
                output = ((x & 1) == 1) ? (output + (long)Math.pow(10, currentDecPlace)) : output;
                currentDecPlace++;
                x >>= 1;
        }
 
        return output;
}

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

static void Main(string[] args)
        {
            int x = 10;
            int num = 4; //input 
            while (x % 4 != 0)
            {
                x = x * 10;
            }
            Console.WriteLine(x);

            Console.ReadLine();

        }

- deepika April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This can be done using a decimal to binary conversion.

<?php

function findBin($n) {
  $b = '';
  while ($n >=1) {
    if ($n % 2 == 0) {
      $b = '0' . $b;
    } else {
      $b = '1' . $b;
    }
    $n = (int) ($n / 2);
  }
  return $b;
}

function findSmallest($n) {
  $p = 1;
  $b = findBin($p);
  while ($b % $n != 0) {
    $p++;
    $b = findBin($p);
  }
  return $b;
}

for ($i = 1; $i < 10; $i++) {
  var_dump(findSmallest($i));
}

- paulz February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually the smallest number divisible by A is A itself; I assume that zero doesn't count. So all we need is to call findBin(A).

- ranan.fraer February 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ ranan.fraer : Could you explain this for A = 5 where the smallest number divisible by A with only ones and zeroes is "10" ?

- mrsurajpoudel.wordpress.com February 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
System.out.println("No Answer for this number");
return 0;
}
}
return tens;
}

- Sriman February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
System.out.println("No Answer for this number");
return 0;
}
}
return tens;
}

- Sriman February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.


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