Amazon Interview Question for Software Development Managers


Country: India




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

what we can do in this question is initialize an array like this:-
arr={1,0,0,0,0,0,0,0,0,0}

this array represent the occurrence of a digit as
arr[0] for 0 occurrence, arr[1] for 1 occurrence....

Now,

if(n!=0)
{
for(int i=1;i<n; i++) //this will increase the series from 1 to n
{
while(i!=0)
{
int rem= i%10;
arr[rem]= arr[rem]+1;
//this increase the value of rem digit by 1 in arr array
//for ex:-
//if the value of i is 456 then
//rem will be 456%10 i.e 6 and now arr[rem] will be //arr[6] and it will increased by 1.

i=i/10;
}
}
}
for(int i=0; i<=9; i++)
cout<<arr[i]; //this will print the occurrence of all the digit

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

The N value can go upto 10^9. You have to optimise the problem, otherwise u will get a time limit exceeded.

- user124 February 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = new int[10];
		Arrays.fill(array, 0);
		array[0]++;
		int N= 12;
		for(int i=1;i<=N;i++){

			int temp=i;
			while(temp>0){
				int rem= temp%10;
				array[rem]++;
				temp=temp/10;
			}

		}
		for(int k=0;k<10;k++){
			System.out.println(array[k]);	
		}

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

>>> candidates = range(0,13)
>>> for i in range(0,10):
	print 'Occurences of %s' % (i)
	reduce (str.__add__, map (lambda x: str(x), candidates)).count(str(i))

	
Occurences of 0
2
Occurences of 1
5
Occurences of 2
2
Occurences of 3
1
Occurences of 4
1
Occurences of 5
1
Occurences of 6
1
Occurences of 7
1
Occurences of 8
1
Occurences of 9
1

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

Code:

public static void main(String[] args) {
		int N = 552;
		digitOccurrences(N);
	}
	
	
	public static void digitOccurrences(int N)
	{
		int[] count = new int[10];
		count[0] = 1;
		for (int i = 1; i <= N; i++)
		{
			//# of digits in i
			int numDigits = 1;
			while(i/(int)Math.pow(10, numDigits) > 0)
			{
				numDigits++;
			}
			
			//evaluate i and add all digits to counter array
			int temp = i;
			while(numDigits > 0)
			{
				int k = temp / (int)Math.pow(10, numDigits-1);
				count[k]++;
				temp -= k * (int)Math.pow(10, numDigits-1);
				numDigits--;
			}	
		}
		//print occurrences
		for(int j = 0; j < 10; j++)
		{
			System.out.println(count[j]);
		}
	}

Output:
106
216
216
215
215
161
105
105
105
105

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

main()
{
int a[10], range, rem=0,quot =0, i;

printf("\n What range you want ? : ");
scanf("%d",&range);

bzero(a,10*sizeof(int));
a[0] =1;

while(range)
        {
                if(range < 10)
                {
                        rem = range%10;
                        a[rem] +=1;
                        range--;
                }
                else
                {
                        quot    =       range/10;
                        a[quot] +=1;
                        rem     =       range%10;
                        a[rem] +=1;
                        range--;
                }

        }

printf("\n");
for(i=0; i < 10; i++)
printf("Num of %ds %d\n", i,a[i]);

}

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

My approach would be to count appearances of each digit according to the number of digits in the range instead of the range itself, in other words I'll count the number of appearances of each digit 0-9 as the lsb, the 2nd digit from the lsb, the 3rd digit from the lsb and so forth. This would result in an O(logn) algorithm.

Given n and some digit 0<=d<=9, how do we count the number of times the digit d appears in n? First, we'll need to divide it to two cases: d=0 and 1<=d<=9.

1. 1<=d<=9. We want to count how many times d appears in the range 0...n as the i-th digit (from the lsb). Let k = 10^(i+1). How many times does d appear as the i-th digit in the range 0...k? It's easy to see that it appears exactly k/10 times (For example: How many times does the digit 1 appear as the second digit in the range 0...100? It appears exactly 10 times for the numbers 10,11,12,...,19). The same applies to the range k+1,...,2k and so on.
Hence, (n/k)*(k/10) is the number of appearances (of d as the i-th digit) in the range 0...Integer(n/k)*k.
We're not done yet though because there may be a remainder from the division of n by k which we didn't handle. Let us look at the remainder 0 <= n % k < k. If (n % k) / (k/10) is greater than d that means the remainder (n % k) > d*(k/10) which means that the digit d appears as the i-th digit in the remainder k/10 times as well (For example: for the number n=120 and d=1, the remainder n % 100 = 20. Then, 20/10 = 2 > 1 which means that there are 10 more appearances of 1 as the i-th digit in the remainder: 10,11,12,...,19).
If (n % k)/(k/10)<d then there are no appearances of d as the i-th digit in the remainder.
All that's left is to handle the case where (n % k)/(k/10)==d. In this case, the number of appearances would be (n % k) % (k/10) + 1 (1 is added because the count starts from 0). For example: n=115 and d=1: (115 % 100) / (100/10) == 1 and (115 % 100) % 10 +1 = 5+1=6 which accounts for the appearance of d=1 as the 2nd digit in the numbers 110 (10 in the remainder), 111 (11), ... , 115 (15).
These observations allow us to calculate the number of appearances of 1<=d<=9 as the i-th digit in the range 0...n with O(1) run-time complexity.

2. d=0. This case is slightly trickier because 0 cannot appear as msb (We cannot count 10 appearances of 0 as the 2nd digit in the range 10). Still, we'll try and solve it with a similar but slightly modified approach. Let us look again at (n/k) - k is the same as in (1), the number of appearances of 0 as the i-th digit in the range 0...k-1 is 0 because all the numbers in that range have i digits or less. On the other hand, in the range k...2k-1 it appears k/10 times (For instance, d=0 appears 0 times as the 2nd digit in the range 0...99 but it appears appears 10 times in as the 2nd digit in the range 100...199 and another 10 times in the range 200...299). So the number of appearances of d=0 as the i-th digit in the range 0...Integer(n/k)*k is Math.max((n/k)-1,1)*(k/10).
As before, we're not quite done yet because n/k might have a remainder. But the remainder n % k has at most i digits, when should we count d=0 as msb considering that remainder? Using the same idea as in (1), we'll count it relative to k/10. If n % k >= k/10 that means we need to count k/10 appearances in the remainder (For instance: n=110, n % 100 = 10 and 10 >= 100/10 which means we have 10 appearances in the remainder: 100(00), 101(01),...,109(09)). If n % k < k/10 then the number of appearances is (n % (k/10)) + 1.

The resulting (slightly confusing) code is:

private static int countForDigit(int n, int d){
		if ((n<0) || (d<0) || (d>9)){return 0;}
		if ((n==0) && (d==0)){return  1;}
		
		int res = 0;
		for (int k=10;(k==10) && ((n/k)>0) || (n/(k/10)>0);k*=10){
			if (k==10){res+=(n/k) + ((n % k >= d) ? 1 : 0);}
			else {
				if (d>0){
					res+=(n/k)*(k/10) + ((((n % k)/(k/10))) > d ? k/10 : (((n % k)/(k/10) == d) ? ((n % k) % (k/10))+1 : 0));
				}
				else{
					res+=(Math.max((n/k)-1, 0))*(k/10) + Math.min((n/k),1)*((n % k >= (k/10)) ? (k/10) : (n % (k/10)) + 1);
				}
			}
		}
		
		return res;
	}
	
	public static int[] getAllDigitsCount(int n){
		if (n<0){return null;}
		
		int[] count = new int[10];
		for (int d=0;d<count.length;d++){count[d]=countForDigit(n,d);}
		
		return count;
	}

Complexity: 10*O(logn) = O(logn) run-time complexity.

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

#include<stdio.h>
#include<conio.h>
void main(){
int n,i,temp,rem;
int arr[]={0,0,0,0,0,0,0,0,0,0};
printf("Enter the number: ");
scanf("%d",&n);
for(i=0;i<=n;i++){
temp=i;
if(temp!=0){
while(temp!=0){
rem=temp%10;
arr[rem]+=1;
temp=temp/10;
}
}
else
arr[0]+=1;
}
for(i=0;i<10;i++)
printf("\nNumber of %ds is: %d",i,arr[i]);
getch();
}

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

This is the simple solution came to my mind......you can check it for any numbers......

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

geekyjumps.blogspot.in/2014/01/given-number-n-now-find-number-of.html

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

// Find number of occurrences of 0 to 9 upto 1 to 100

public class FindNumOfOccurrences {
	public static void main(String[] args) {
		findCount(9);
	}
	

	public static void findCount(int num)
	{
int count=0;
		
		for(int i=0;i<100;i++)
		{
			int a=i/10;
			int b=i%10;
			
			if(a==num)
				count++;
			
			if(b==num)
				count++;
		}
		
		System.out.println("Number of "+ num +"'s= "+count);
	}
	
}

- Ravi Kumar February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solutions.

public static void main(String[] args){
int num = 56705678;
findDigitalOccurences(num);

}
public static void findDigitalOccurences(int n) {
int[] digitals = new int[10];
Arrays.fill(digitals, 0); /*may skip since the default value of array element are all 0; */

int num = n;

while (num / 10 >= 1) {
int a = num % 10;
num = num / 10;
digitals[a]++;
}
digitals[num]++;

for (int k = 0; k < 10; k++) {
System.out.println(digitals[k]);
}

}

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

If I understood the problem statement correctly, one wants to find the number of occurrences of each digit in an integer. For example, n=9838556. has 1x "9", 2x "8", 1x "3", 2x "5", and 1x "6". The pseudo code can be a while loop that terminates as follows:

counters [10] ; is an array of counters initially set to 0 where each element represents a digit between 0 and 9. In this example at the end of the program counters[9]=1, counters[8]=2, .....

n=9838556 ;as an example

While (true) {
if (n==0) break ;break out of the while loop while all digits counted
counters[n mod 10]++ ;increment counter for the digit
n=(n-(n mod 10))/10
}

; The above algorithm is super fast as the number of loops depend on the number of digits in an integer. For example, an integer that has 20 digits, will be processed by looping 20 times.

- Kamran M January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach:

Heapify on the input array. When you traverse the root nodes of each branch, the indexes can give you the counts (number of repetitions) of each number

This is applicable when you can alter the positions of numbers in input array.

- prasadbgv July 08, 2018 | 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