Amazon Interview Question for Software Engineer / Developers


Team: payments
Country: India




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

Best Explantation for this problem
stackoverflow.com/questions/20945790/count-the-number-of-ks-between-0-and-n

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

Sorry the sample input output did not come properly.
please find it here.

drive.google.com/file/d/0B2MCIfvwfpg2WW1XdjgwS282Q1U

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

This problem can be solved very efficiently with recursion. The algorithm below runs in O(log(n)).

def getNumberOfOcurrencesOfDigits(int N) {
		def result = [0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0]
		
		def addToAll = getNumberOfOcurrencesOfDigits(N, result)
		
		(0..9).each {
			result[it] += addToAll
		}
		
		return result
	}
	
	def getNumberOfOcurrencesOfDigits(int N, result) {
		int Nby10 = N / 10
		int Nmod10 = N % 10
		
		(1..Nmod10).each {
			result[it]++ 
		}
		
		if(Nby10 > 0) {
			return Nby10 + getNumberOfOcurrencesOfDigits(Nby10, result)			
		} else {
			return 0
		}
	}

Thanks for sharing!

- carlosgsouza February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@carlosgsouza
Could you please write Java or C++ or C?

- samar February 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice but wrong... at least you're on the right track

one remaining problem:
N = 12345
In the first iteration your are right that every digit has to appear 1234 times in the right most place.
In the second iteration N = 1234, now every digit in the right most place has to appear 123 times according to your logic, but as there is a degree of freedom it has to apper 123 times * 10
In the next step N = 123, every digit has to apper 12 times but is supported by two degrees of freedom -> 12*100

- Markus March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>


main()
{
int num = 0;
printf(" ENter a page number");
scanf("%d" , &num);
int pos =1;
int r;
int count[10], c,i, tpos;
for(c = 0 ; c < 10 ; c++)
count[c] =0;

while(num > 0)
{
r = num%10;
num = num/10;
for(i = 0; i <10 ; i++)
{
tpos = pos/10;
while(tpos > 0)
{
count[i] +=r* tpos;
tpos= tpos/10;
}
if(i <= r)
count[i] += 1;
}
pos = pos*10;
}
count[0]-=2;
for(i = 0; i < 10 ; i ++)
{
printf("\n number %d , count % d", i , count[i]);
}
}

- vijay.naga February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this too it wont work, it would time out

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

This was an online test and My solution passed only 10 out of 15 cases. remaining 5 cases timed out.

My solution was for i =1 to n , convert i to string and concatenation string.
at the end find the number of occurrence in the string.

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

Can be solved depending on the number of digits.

First lets identify the pattern of frequency of usage of each digit

0-9 : 1
10-99 : 10+10
100-999 : 100+100+100

let N be the input number and A be an array to store frequency of digits
Scan the number from left to right and extract each digit out of it. Let the digit be k and position be j e.g. N = 4375 for k = 4, j = 3

For each digit in N
	for i = 0 to k-1
		for x = 0 to 9
			A[x]+= 10^(j-1)
	A[k] += N%10^j

- kr.neerav February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

initialize an array of int[10] from 0 .. 9
for each i in N keep getting reminder of i / 10 and increment array for each value found.

public static void getNumberOfOcurrencesOfDigits(int n) {

		int[] sums = new int[10];
		for (int i = 0; i < 10; i++) {
			sums[i] = 0;
		}
		sums[0]++;

		for (int i = 1; i <= n; i++) {
			int rem = i % 10;
			int div = i / 10;
			sums[rem]++;

			while (div > 0) {
				rem = div % 10;
				div = div / 10;
				sums[rem]++;
			}
		}

		for (int i = 0; i < sums.length; i++) {
			System.out.println(i + " = " + sums[i]);
		}
	}

- guilhebl February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will time out , try for 1000000000,

try it on some online compilier and check if if it finishes within 15 sec

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

Any other efficient code, this is creating millions of strings and destroying.

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

Here is a simple and pretty straightforward solution in Java:

long time = System.currentTimeMillis();
		int number = 138493;
		int[] result = {0,0,0,0,0,0,0,0,0,0}; //array of size 10 for each digit
		int previousDivisor = 1;
		int divisor = 10;
		int allIncrement = 0;
		while(true){
			int dividedValue = number / divisor;
			if(dividedValue > 0){
				allIncrement += dividedValue;
			}
			int rest = (number % divisor) / previousDivisor;

			for(int i=1;i<=rest;i++){
				result[i]++;
			}
			if(dividedValue == 0){
				break;
			}
			previousDivisor *= 10;
			divisor *= 10;
		}

		System.out.println("Time: "+ (System.currentTimeMillis() - time));

		for(int i=0;i<result.length;i++){
			result[i]+=allIncrement;
			System.out.println("Number of occurrences of "+i+" is equal to: "+result[i]);
		}

This seems to work, complexity is O(logn) where n = input number or maybe in other words O(N) for N = (""+number).lenght()

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

public int[] countOccur(int n){
int[] occurence = new int[10];
int count = getshiftCount(n, occurence, 0, 1);
for (int i = 0; i < 10; i++){
occurence[i] += count;
}
if (n > 10){
occurence[0]--;
}
return occurence;
}

private int getshiftCount(int n, int[] occurence, int last, int power) {
int grade = n / 10;
int remainder = n % 10;
for (int i = 0; i < remainder; i++){
if (grade == 0 && i == 0){
continue;
}
occurence[i] += power;
}
occurence[remainder] += last + 1;
if (grade > 0){
return grade + getshiftCount(grade, occurence, remainder * power + last, power * 10);
} else {
return 0;
}
}

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

you can try with 125, the answer is :
23
50
20
14
14
14
13
13
13
13

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

public static void main(String[] args) {
		int s[] = new int[10];
		int number = 999; // 189 +3=192 for 1000
		doSum(s, number, number, 0, 0);
		printSums(s);
	}

	private static void doSum(int[] s, int orig, int num, int low, int pow) {
		int n = num / 10;
		int r = num % 10;
		if (n == 0 && r == 0)
			return;
		for (int i = 0; i < s.length; i++) { // lowest digit
			s[i] = s[i] + n * (int) Math.pow(10, pow);
		}
		for (int i = 0; i <= r; i++) {
			if ((pow == 0 || i < r)) {
				s[i] = s[i] + 1 * (int) Math.pow(10, pow);
			} else {
				s[i] = s[i] + low + 1;
			}
		}
		s[0] = s[0] - (int) Math.pow(10, pow);
		doSum(s, orig, n, orig % (int) Math.pow(10, pow + 1), pow + 1);
	}

	private static void printSums(int[] sums) {
		for (int i = 0; i < sums.length; i++) {
			System.out.println("Digit " + i + "=" + sums[i]);
		}
	}

- nickjohk September 13, 2014 | 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