Amazon Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
working code...
int main()
{ for (int i=4545;i<=4589;i++)
{
if((i%100)==i)
{
if((i%11)!=0)
cout<<i<<"\n";
}
else if((i%1000)==i)
{char buff[3];
int k= sprintf(buff,"%d",i);
if((buff[0]!=buff[1])&&(buff[1]!=buff[2])&&(buff[2]!=buff[0]))
cout<<i<<"\n";
}
else if((i%10000)==i)
{char buff[4];
int k= sprintf(buff,"%d",i);
if((buff[0]!=buff[1])&&(buff[1]!=buff[2])&&(buff[2]!=buff[0])&&(buff[2]!=buff[3])&&(buff[1]!=buff[3])&&(buff[0]!=buff[3]))
cout<<i<<"\n";
}
}
Few things:
1) your code does not work unless you change it for what the last comment pointed out.
2) your code will only work for numbers < 9999
3) please use the code indentation, It was a pain to read your code. (Writing Code? Surround your code with
and
to preserve whitespace. )
4) you complicate yourself too much.
public static void printList() {
for (int i = 45; i < 4578; i++) {
if (i % 100 == i) {
if (i % 11 != 0) {
System.out.println(i);
}
}
else if (i % 1000 == i) {
if (i % 111 != 0) {
System.out.println(i);
}
} else if (i % 10000 == i) {
if (i % 1111 != 0) {
System.out.println(i);
}
}
}
}
Full code:With WRONG OUTPUT:
import java.io.*;
public class Subbu{
public static void main(String args[]) {
for (int i = 50; i < 150; i++) {
if (i % 100 == i) {
if (i % 11 != 0) {
System.out.println(i);
}
}
else if (i % 1000 == i) {
if (i % 111 != 0) {
System.out.println(i);
}
} else if (i % 10000 == i) {
if (i % 1111 != 0) {
System.out.println(i);
}
}
}
}}
Wrong output:
50
51
52
53
54
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
78
79
80
81
82
83
84
85
86
87
89
90
91
92
93
94
95
96
97
98
100
101
102
103
104
105
106
107
108
109
110
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
Total wrong output with 144,100,101 etc.,the poster (simple logic) did't understand the ques..properly..
Too lazy to write the code, however here's my pseudo-code.
1. Loop 45 to 4578 (call num)
2. Calculate long bcd = binaryCodedDecimal of num
3. Calculate long flag = ~0; //Binary pattern now is 111111111.....11111
4. Loop 0th digit to 3rd digit of bcd. //Each digit is four bits. So 0th is first four,
//1st is 4th to 7th etc..
5. Check corresp bit digit of flag.
6. If '1' Reset that bit & move on to next bcd digit
7. Else if '0' reject num //Num already occurs in bcd representation
8. If all four bcd digits visited & passes the test -> print num
9. Consider next num (outer for loop)
To add to what I said above, I think getting all the four bcd digits is very simple:-
int pattern = ~((~0)<<4);
int digit1 = bcd & pattern;
int digit2 = bcd & (pattern>>4);
int digit3 = bcd & (pattern>>8);
int digit4 = bcd & (pattern>>12);
Please correct any errors
Oops mistake, I meant
int pattern = ~((~0)<<4);
int digit1 = pattern & bcd;
int digit2 = pattern & (bcd>>4);
int digit3 = pattern & (bcd>8);
int digit4 = pattern & (bcd>>12);
The same idea as Itanium's, but extensible to more than 4 digits:
class NonRepeatingDigits
{
static public void main (String args[])
{
System.out.println(
"Print numbers between 45 to 4578 without repeating digits.");
for (int i = 45; i < 4578; i++)
{
if (isNonRepeating(i, 0))
System.out.println(i);
}
}
private static boolean isNonRepeating(int n, int mask)
{
if (n == 0)
return true;
int digitBit = 1 << ((n % 10) + 1);
if ((mask & digitBit) > 0)
return false;
else
return isNonRepeating(n / 10, mask | digitBit);
}
}
Two more things:
1. I think in my approach I avoid the overhead of recursion.
2. int digitBit = 1 << ((n % 10) + 1);
I dont understand why you add 1? I would just have:
int digitBit = 1 <<((n%10));
@Paul B program in C...
#include<stdio.h>
#include<conio.h>
int isNonRepeatable (int n, int mask)
{
if(n==0)
return 1;
int digitBit = 1 << ((n%10)+1);
if((mask & digitBit)>0)
return 0;
else
return isNonRepeatable (n/10, mask | digitBit);
}
int main()
{
for(int i =45 ; i < 100;i++)
{
if(isNonRepeatable(i,0))
printf("%d\n",i);
}
getch();
clrscr();
return 0;
}
Hi Paul,
I tested your code and it seems like getting the wrong o/p. It is working till 99 and then its skipping few integers
96
97
98
102
103
In this case it missed 100 and 101. And I am thinking the following approach
Hashtable h = new Hashtable();
for(i=45;i<=4578;i++)
{
temp = 0;
int num = i;
int flag =0;
while(n)
{
temp = n%10;
if(0== flag)
h.put(temp);
flag = 1;
if(h.Contains(temp))
{
if(n/10==0)
++i;
}
else
break;
n = n/10;
}
reset the hashtable here
print i;
}
Instead of checking all numbers between 45 and 4578, we can do a sort of N choose K approach. In this case, choose 2,3 or 4 digits out of the 10 digits.
bool used[10];
void Print(int cur_number) {
if (cur_number >= 45)
printf("%d\n", cur_number);
for (d = cur_number == 0; d < 10; d++) // if number is 0, we start at digit 1
if (!used[d]) {
new_number = cur_number * 10 + d;
if (new_number <= 4578) {
used[d] = true;
Print( new_number );
used[d] = false;
}
}
}
// call Print(0)
Here's a C-esque solution for you.
void
dont_print_repeats(int start, int finish)
{
int digit,
duplicate = 0,
bits = 0;
while (start <= finish)
{
bits = 0;
duplicate = 0;
number = start;
while (number != 0 && !duplicate)
{
digit = start % 10;
if (bits & (1 << digit))
{
duplicate = 1;
}
bits |= (1 << digit);
number /= 10;
}
if (!duplicate)
cout << start;
start++;
}
}
My python solution with tests
def nums(count, digits={0,1,2,3,4,5,6,7,8,9}, zero=True):
"""Print number without repeating digits and at most count digits long
Argumetns:
count - number of digits
digits - allowed digits
zero - is all leading digits a zeroes (need to account for
numbers with most significant digit to be zero, and
not treat them as repeating)
Example:
>>> list(nums(2))[:15]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15]
# solution for problem (just use filter on nums)
>>> list(filter(lambda val: val >= 45 and val <= 4578, nums(4)))
... # doctest: +ELLIPSIS
[45, 46, ..., 4571, 4572, 4573, 4576, 4578]
"""
if not count:
yield 0
return
for digit in digits:
pos = 10 ** (count - 1)
if zero and digit == 0:
for num in nums(count - 1, digits, True):
yield num
else:
for num in nums(count - 1, digits - {digit}, False):
yield digit * pos + num
if __name__ == '__main__':
import doctest
doctest.testmod()
public class PrintNum2 {
public static void main(String[] args){
Print:
for(int l =0; l<10; l++){
for(int k =0; k<10; k++){
for(int j =0; j<10; j++){
for(int i =0; i<10; i++){
int num = (l*1000+k*100+j*10+i);
if(((l==k)&&(k==0)&&(i!=j)&&(i!=k)&&(num>45))||((i!=j)&&(i!=k)&&(i!=l)&& (j!=k)&& (j!=l)&& (k!=l)))
{
System.out.println(num);
if(num >= 4578)
break Print;
}
}
}
}
}
}
}
JUST COPY PASTE IN BROWXY WEBSITE:(CODE WITH LITTLE BUGS)
##THANK U nitin466##
import java.io.*;
public class PrintNum2 {
public static void main(String[] args){
Print:
for(int l =0; l<10; l++){
for(int k =0; k<10; k++){
for(int j =0; j<10; j++){
for(int i =0; i<10; i++){
int num = (l*1000+k*100+j*10+i);
if(((l==k)&&(k==0)&&(i!=j)&&(i!=k)&&(num>45))||((i!=j)&&(i!=k)&&(i!=l)&& (j!=k)&& (j!=l)&& (k!=l)))
{
System.out.println(num);
if(num >= 457)
break Print;
}
}
}
}
}
}
}
OUTPUT:
46
47
48
49
51
52
53
54
56
57
58
59
61
62
63
64
65
67
68
69
71
72
73
74
75
76
78
79
81
82
83
84
85
86
87
89
91
92
93
94
95
96
97
98
123
124
125
126
127
128
129
132
134
135
136
137
138
139
142
143
145
146
147
148
149
152
153
154
156
157
158
159
162
163
164
165
167
168
169
172
173
174
175
176
178
179
182
183
184
185
186
187
189
192
193
194
195
196
197
198
213
214
215
216
217
218
219
231
234
235
236
237
238
239
241
243
245
246
247
248
249
251
253
254
256
257
258
259
261
263
264
265
267
268
269
271
273
274
275
276
278
279
281
283
284
285
286
287
289
291
293
294
295
296
297
298
312
314
315
316
317
318
319
321
324
325
326
327
328
329
341
342
345
346
347
348
349
351
352
354
356
357
358
359
361
362
364
365
367
368
369
371
372
374
375
376
378
379
381
382
384
385
386
387
389
391
392
394
395
396
397
398
412
413
415
416
417
418
419
421
423
425
426
427
428
429
431
432
435
436
437
438
439
451
452
453
456
457
public void nonRepeatingDigitsInNumber(int from, int to)
{
String[] sampleString = {"11","22","33","44","55","66","77","88","99","00"};
for(int i=from;i<=to;i++)
{
String numberString = ""+i;
boolean flag=false;
for(int j=0;j<sampleString.length;j++){
if(numberString.contains(sampleString[j]))
flag=true;
}
if(!flag)
System.out.println(i);
}
}
a C++ version for both cases:
check_number_strict (455 is not allowed)
check_number(455 is allowed -> checks for multiples of 11)
#include<iostream>
using namespace std;
void check_number_strict(int number) {
int digit = number % 10,temp;
int local = number /10;
while(local > 0) {
temp = local % 10;
if(temp != digit) {
cout<<number<<endl;
return;
}
local = local/10;
}
}
void check_number(int number) {
if(number %11 != 0) {
cout<<number<<endl;
}
}
int main(int argc, const char* argv[]) {
int i;
for(i= 45; i < 4578; i++) {
check_number_strict(i);
check_number(i);
}
}
/**
* This is the naive solution
* @author AnnaQ
*/
class solution1{
solution1(){
//Print two digit numbers
for(int i=4;i<10;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
if((10*i+j)<45) continue;
System.out.println(""+i+j);
}
}
//Print three digit numbers
for(int i=1;i<10;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
for(int k =0;k<10;k++){
if(k==j||k==i)continue;
System.out.println(""+i+j+k);
}
}
}
//Print four digit numbers
for(int i=1;i<5;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
for(int k =0;k<10;k++){
if(k==j||k==i)continue;{
for(int l = 0; l<10;l++){
if(l==k||l==j||l==i)continue;
if((1000*i+100*j+10*k+l)>4578) continue;
System.out.println(""+i+j+k+l);
}
}
}
}
}
}
}
/**
* This is the naive solution
* @author AnnaQ
*/
class solution1{
solution1(){
//Print two digit numbers
for(int i=4;i<10;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
if((10*i+j)<45) continue;
System.out.println(""+i+j);
}
}
//Print three digit numbers
for(int i=1;i<10;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
for(int k =0;k<10;k++){
if(k==j||k==i)continue;
System.out.println(""+i+j+k);
}
}
}
//Print four digit numbers
for(int i=1;i<5;i++){
for(int j=0;j<10;j++){
if(i==j)continue;
for(int k =0;k<10;k++){
if(k==j||k==i)continue;{
for(int l = 0; l<10;l++){
if(l==k||l==j||l==i)continue;
if((1000*i+100*j+10*k+l)>4578) continue;
System.out.println(""+i+j+k+l);
}
}
}
}
}
}
}
Frame a string based on the input range 45 to 4578
"1111 2222 3333 4444 555 666 777 888 999"
this string contains all the possible repeated digits between 45 to 4578 starting from 55 to 4444
Convert the number to string say 45 -> "45" then check if the above string contains this string
if yes, then it has repeating digits
foreach number in the range
convert the number to string
if pattern.contains(string)
repeated digits
else
no repeated digits
Divide the problem into 3 cases:
1) Number of valid 2-digit numbers (i.e. non-repeating digits) >= 45
2) Number of valid 3-digit numbers with non-repeating digits
3) Number of valid 4-digit numbers >= 4578
The algorithm for each case is to start with printing different combinations and then add checks for non-repeating and value.
package interviewquestions;
public class InterviewQuestions {
public static void main(String args[]) {
int a = 0;
int b = 0;
int c = 4;
int d = 5;
for (int i = 45; i <= 4578; i++) {
if (a == 0 && b == 0) {
if (c != d) {
System.out.print(c);
System.out.print(d);
System.out.println();
}
} else if (a == 0 && b > 0) {
if (d != c && b != c) {
System.out.print(b);
System.out.print(c);
System.out.print(d);
System.out.println();
}
} else {
if (a != b && b != c && c != d) {
System.out.print(a);
System.out.print(b);
System.out.print(c);
System.out.print(d);
System.out.println();
}
}
d++;
if (d > 9) {
d = 0;
c++;
}
if (c > 9) {
c = 0;
b++;
}
if (b > 9) {
b = 0;
a++;
}
}
}
}
public class fourtyFiveTO4578 {
public static void main(String args[]){
//45 to 4578 -no duplicate numbers allowed
String duplicateNumbers="11 22 33 44 55 66 77 88 99 00";
for (int i = 45; i <= 4578; i++) {
String temp = "" + i;
if (!duplicateNumbers.contains(temp)) {
System.out.println(temp);
}
}
}
}
How about this in Java?
public class SkipRepeatingDigits {
public static void main(String[] args) {
NEXT_NUMBER:
for (int i = 45; i <= 4578; i++) {
boolean[] digits = new boolean[10];
for (int number = i; number != 0; number /= 10) {
if (digits[number % 10]) {
continue NEXT_NUMBER;
}
digits[number % 10] = true;
}
System.out.println(i);
}
}
}
Output:
45
46
47
48
49
50
51
52
53
54
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
78
79
80
81
82
83
84
85
86
87
89
90
91
92
93
94
95
96
97
98
102
103
104
105
106
107
108
109
120
123
124
125
126
127
128
129
130
132
134
Or this in Java depending on the definition of repeating digits.
Output is a little bit different.
public class SkipRepeatingDigits {
public static void main(String[] args) {
NEXT_NUMBER:
for (int i = 45; i <= 4578; i++) {
int previous_digits = -1;
for (int number = i; number != 0; number /= 10) {
if (previous_digits == number % 10) {
continue NEXT_NUMBER;
}
previous_digits = number % 10;
}
System.out.println(i);
}
}
}
Output:
45
46
47
48
49
50
51
52
53
54
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
78
79
80
81
82
83
84
85
86
87
89
90
91
92
93
94
95
96
97
98
101
102
103
104
105
106
107
108
109
120
121
123
124
125
126
127
128
129
130
131
132
134
135
136
137
138
139
140
public class Main {
public static void printNonRepeating(int start, int end){
for(int i = start; i < end; i++){
int[] digits = new int[10];
Boolean repeated = false;
int tmp = i;
digits[tmp%10] = 1;
while(tmp/10 != 0){
tmp = tmp/10;
if(digits[tmp%10] == 1){
repeated = true;
} else {
digits[tmp%10] = 1;
}
}
if(!repeated){
System.out.println(i);
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
printNonRepeating(1, 1000);
}
}
import java.util.HashMap;
public class NoRepeatedNumbers {
public static void main(String args[]) {
for (int i = 45; i <= 4578; i++) {
String number = i + "";
HashMap<Character, Integer> count = new HashMap<Character, Integer>();
int numberOfchars = 0;
for (int j = 0; j < number.length(); j++) {
if(!count.containsKey(number.charAt(j))){
count.put(number.charAt(j), 1);
numberOfchars++;
}
else
break;
}
if(numberOfchars == number.length())
System.out.println(number);
}
}
}
Here is my solution in Ruby:
#!/usr/bin/env ruby
require 'set'
include Math
a = 45
b = 4578
n1 = log10(a).floor
n2 = log10(b).ceil
solutions = [a.to_s.reverse.split("").collect{|e| e.to_i}]
d = [*(0..9)]
solutions = []
n1.upto(n2) do |n|
d.combination(n).collect do |c|
c.permutation do |e|
next if e[0] == 0
v = e.inject(0){|t,v| t = 10*t + v}
solutions << v if v <= b && v >= a
end
end
end
solutions.sort!
p solutions
// Only try to make it O(n) based on 4 digits input and it's not scalable, O(n) solution is more scalable.
public void printNoRepeat(int start, int end)
{
int a=0, b=0, c=0, d=0;
for (int i = start; i < end; i++)
{
if (i > 999)
{
a = i % 10;
b = (i % 100 - i%10) / 10;
c = (i % 1000 - i%100) / 100;
d = (i - i % 1000) / 1000;
if (a == b || a == c || a == d || b == c || b == d || c == d) continue;
}
if (i > 99)
{
a = i % 10;
b = (i % 100 - i%10) / 10;
c = (i % 1000 - i%100) / 100;
if (a == b || a == c || b == c ) continue;
}
if (i > start)
{
a = i % 10;
b = (i % 100 - i%10) / 10;
if (a == b) continue;
}
Console.Write("{0}, ",i);
}
}
public class NumberWithUniqueDigit
{
public static void main(String[] args)
{
System.out.println("Print numbers between 45 to 4578 without repeating digits.");
for (int i = 45; i < 4578; i++)
{
if (isNonRepeating(i))
{
System.out.println(i);
}
}
}
private static boolean isNonRepeating(int n)
{
boolean flag=true;
String num =""+n;
boolean char_set[]=new boolean[256];
for(int i=0;i<num.length();i++)
{
int val=num.charAt(i);
if(char_set[val]!=true)
{
char_set[val]=true;
}
else
{
flag=false;
break;
}
}
return flag;
}
}
How about simple regular expressions?
#!/usr/bin/env python
import re
def non_repeat(num):
num_str = str(num)
is_repeat = False
for digit in num_str:
if is_repeat:
break
if len(re.findall(digit,str(num))) > 1:
is_repeat = True
return is_repeat
if __name__ == '__main__':
for i in range(45,4578):
if not non_repeat(i):
print i
Wow! Way to go and make it an easy "Fuck off. We won't hire you".
1) Can't spell (ok if your native language is not english)
2) Can't take criticism (not ok)
3) Swears at the drop of a hat (fucking hell no)
morons_of_the_world++;
1)cmt wth ur name..
2)no cmt is worth without name
3)U Anonymous Motherf**r.
4)cme wth ur mom to gve me "BL*WJOB".
5)thn cmt byeeeee..
In Java
- venkateshpoosarla September 25, 2013