## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Written Test

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

It is very simple problem. For every start to end first digit, we need to create a tree. For example 500000 to 600000 is given range that we need to create a binary tree where left child is one less than the parent digit and right child is 1 greater the parent digit.

After the tree constructed, take root and do all traversal to all possible leaf at level count ( decimal points of start ) and generate a number for such branch.

Check is this number is in limit, if yes print it. Like this keep doing till the first digit <= last. No need to do traverse like this for(int i=start;i<end+1;i++).

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

Can you shed some more light on below para?

"After the tree constructed, take root and do all traversal to all possible leaf at level count ( decimal points of start ) and generate a number for such branch."

If I understood correctly, traversing through a big tree will also cost O(h), which is almost equal to O(n). So I guess there might not be much difference asymptotically. Please correct me if I'm wrong.

It would be helpful if you can provide a Pseudocode for your approach.

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

``````I don't know if the solution proposed here is good or bad but definitely an alternative solution:

Suppose range given is: 400 - 500
4
5            3
6   4      4     2
with 4 as root we have two choices i.e. 3(4 - 1) and 5(4+1),once you have 3 digits(remember the range has only 3 numbers) print it :)``````

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

Krish, I am not traversing in n elements rather, I am traversing in possible sulution. For an example if i need to find a number between 100 to 200, then possible tree would be

1
0 1
-1 1 0 2

Now you need to check
10-1 (This will not be checked as it reached to 0 )
101
110
112

This means you don't have to traverse 100 to 200 elements (99 elements ). Please correct if I am wrong.

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

``````public class SpecialPropetyNos {
public static void main(String[] args) {
int Limit = 4;
for (int nos=0;nos<10;nos++){
generateNos(nos, (Limit-1));
}
}

private static void generateNos(int nos, int limit) {
if (limit == 0){
System.out.println(nos);
return;
}
if ( nos%10 != 9)
generateNos( ((nos*10)+ (nos%10+1)), (limit-1) );

if( ((nos%10)-1 ) > -1 ){
generateNos(((nos*10)+(nos%10-1)), (limit-1));
}
}
}``````

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

Can you explain this?

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

Here, instead of range I assumed that one is asked to generate all 4 digit nos with special property (Code could be easily modified to generate nos in the range)

Logic: start with unit (0 to 9), now at 10 only nos allowed are (unit+1) & (unit-1), similarly at hundered (ten+1) & (ten-1), so on
For above 0 & 9 are exception, since (0-1) will take you back & (9+1) would again go out of bound.
Have a look at following diagram
0 - 10 - 010 - 1010
- 210 - 1210
- 3210

1- 01 - 101 - ...
- 21- 121 - . ..
- 131- ...

.....
9 - 89 - 789
- 989

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

"You are given a range", what range, can you explain more?

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

``````#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
//long l=8987656;
long l=89876564;
long temp_num = l;
int prev = -1;
int cur;
bool isSpecial=true;
while(temp_num)
{
cur = temp_num%10;
temp_num = temp_num/10;
if (prev == -1)
prev = cur;
else
{
if(cur != prev+1 && cur != prev-1)
{
isSpecial = false;
break;
}
prev = cur;
}
}
cout<<"Number "<<l<<" is special? "<<isSpecial;
}``````

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

//function to check weather the given number satisfies the property
//i.e 8987656 returns true
//ie.8987657 returns false

//for number 8987656 val1= 5 and val2=6 for first iteration.

bool findProperty(int num)
{

int val1=0;
int val2=-1;

while(num>0)
{
val1=num%10;
num=num/10;

if(val2!=-1)
{
int result=val1-val2;
if(result ==1 || result ==-1)
{

}
else
return false;
val2=val1;
}
else
val2=val1;

}
return true;
}

findnumbaer()
{
for (int i=range_start;i<=range_end;i++)
{
bool flag=findProperty(i);
if(flag)
std::cout<<i;
std::endl;

}

}

Please correct if I am wronge.

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

Isn't the question asking to generate nos not verify them?

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

``````public class glassdoor2{

public boolean check(int i){
int prev=i%10;
int curr;
i=i/10;
while (i>0)
{
curr=i%10;
if ((prev-curr==1)||(prev-curr==-1))
prev=curr;
else
return false;

i=i/10;
}

return true;
}

public void compute(int start,int end)
{
for(int i=start;i<end+1;i++)
{
if(check(i))
System.out.println(i);
}
}

public static void main(String[] args){
glassdoor2 g = new glassdoor2();
g.compute(1000,400000);
}``````

asymptotic solution is O(n*d). worst case O(n2).

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

This can be quite easily done by recursion. This is an interview question, and not a real life example. So the emphasis is on doing something elegant, not long. Here is a recursive solution that accomplishes this:

``````void specialNum(int num, int st, int end) {
if (num > end)
return;

if (num > st) cout << num <<" ";

int digit = num % 10;

if (digit < 9)
sn(num*10+digit+1, st, end);

if (digit > 0)
sn(num*10+digit-1, st, end);
}

void specialNum(int st, int end) {
for (int i=1; i < 10; i++)
sn(i, st, end);
}

int main() {
int startRange = 10, endRange = 200000;
specialNum(startRange, endRange); //will print out numbers as specified in question
return 0;
}``````

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

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

logic is:
range is 100 to 200
answer to this would be: 123 right along with others...
so how can we get 123?
start from 1, 12, 121, 123 and others....
from 1 we can get 12 by (1*10+1%10+1)
from 12 we can get 121 by (12*10+12%10-1)
from 12 we can get 123 by (12*10 + 12%10 -1)
so basically start from 1 till 9 and you will cover all the ranges.As soon as the number increase beyond the start range print it and if it crosses end range return the recursive function, basically boundary cases.

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

small correction:
logic is:
range is 100 to 200
answer to this would be: 123 right along with others...
so how can we get 123?
start from 1, 12, 121, 123 and others....
from 1 we can get 12 by (1*10+1%10+1)
from 12 we can get 121 by (12*10+12%10-1)
from 12 we can get 123 by (12*10 + 12%10 +1)
so basically start from 1 till 9 and you will cover all the ranges.As soon as the number increase beyond the start range print it and if it crosses end range return the recursive function, basically boundary cases.

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

it should start from 101 and not 123

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

``````package com.trails;

public class NumberGenerator {
static int start = 4565676;
static int end = 8987656;

static int sDigit;
static int eDigit;

public static int getDigit(int number){
int counter = 0;
while(number != 0){
counter++;
number = number / 10;
}
return counter;
}

public static int getFirstDigit(int number){
while(getDigit(number) != 1){
number = number / 10;
}

return number;
}

public static void main(String[] args) {
sDigit = getDigit(start); // Find total number of Digit
eDigit = getDigit(end); // Find total number of Digit

int firstNode = getFirstDigit(start); // Get first digit of end
int lastNode = getFirstDigit(end); // Get first digit of end

// Till first digit <= last digit
while(firstNode <= lastNode){
generateNumbers(firstNode, firstNode, 1);
firstNode++;
}
}

private static void generateNumbers(int number, int currentNode, int digit) {
// if current number of digits are more than start digits and number is in range
if(digit >= sDigit && number >= start && number <= end){
System.out.print(number+ ",");
return;
}

// If number contains more digits than the end stop immediately
if(digit > eDigit)
return;

//If current digit for processing is 0, stop this branch
if(currentNode != 0)
generateNumbers(10 * number + (currentNode-1), currentNode - 1, digit + 1);

//If current digit for processing is 9, stop this branch
if(currentNode != 9)
generateNumbers(10 * number + (currentNode + 1), currentNode + 1, digit + 1);
}
}``````

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

It will print :

4565676,4565678,4567654,4567656,4567676,4567678,4567876,4567878,4567898,5432101,5432121,5432123,5432321,5432323,5432343,5432345,5434321,5434323,5434343,5434345,5434543,5434545,5434565,5434567,5454321,5454323,5454343,5454345,5454543,5454545,5454565,5454567,5456543,5456545,5456565,5456567,5456765,5456767,5456787,5456789,5654321,5654323,5654343,5654345,5654543,5654545,5654565,5654567,5656543,5656545,5656565,5656567,5656765,5656767,5656787,5656789,5676543,5676545,5676565,5676567,5676765,5676767,5676787,5676789,5678765,5678767,5678787,5678789,5678987,5678989,6543210,6543212,6543232,6543234,6543432,6543434,6543454,6543456,6545432,6545434,6545454,6545456,6545654,6545656,6545676,6545678,6565432,6565434,6565454,6565456,6565654,6565656,6565676,6565678,6567654,6567656,6567676,6567678,6567876,6567878,6567898,6765432,6765434,6765454,6765456,6765654,6765656,6765676,6765678,6767654,6767656,6767676,6767678,6767876,6767878,6767898,6787654,6787656,6787676,6787678,6787876,6787878,6787898,6789876,6789878,6789898,7654321,7654323,7654343,7654345,7654543,7654545,7654565,7654567,7656543,7656545,7656565,7656567,7656765,7656767,7656787,7656789,7676543,7676545,7676565,7676567,7676765,7676767,7676787,7676789,7678765,7678767,7678787,7678789,7678987,7678989,7876543,7876545,7876565,7876567,7876765,7876767,7876787,7876789,7878765,7878767,7878787,7878789,7878987,7878989,7898765,7898767,7898787,7898789,7898987,7898989,8765432,8765434,8765454,8765456,8765654,8765656,8765676,8765678,8767654,8767656,8767676,8767678,8767876,8767878,8767898,8787654,8787656,8787676,8787678,8787876,8787878,8787898,8789876,8789878,8789898,8987654,8987656

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

Given input range limits: low and high (both inclusive).
Assume that you are generating numbers of length, say N.

Have a driver function that sets the value of the first number, first 'low' upto 'high'. then call a recursive function that does +1 and -1 to the previous value.
Code here [tested]:

``````#include<stdio.h>
#include<stdlib.h>

#define N 4

int low = 3;
int high = 6;

void spl_number( int a[], int pos )
{
if( pos == N )
{
printf("\n");
for( int i=0; i< N; i++ )
printf("%d ",a[i]);
}
else
{
if( a[pos-1]-1 >= low )
{
a[pos] = a[pos-1] - 1;
spl_number(a,pos+1);
}
if( a[pos-1]+1 <= high )
{
a[pos] = a[pos-1] + 1;
spl_number(a,pos+1);
}
} // end else

} // end spl_number

void driver(int a[])
{
for( int num=low; num<= high; num++ )
{
a=num;
spl_number(a,1);
}
}
int main()
{
int a[N] = { 0 };

driver(a);

return 0;
}``````

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

public class SpecialNumber {

static String mainData = "0123456789";
public static void main(String[] args) {
printSpecialNo("","0123456789",3);
}

private static void printSpecialNo(String res, String data, int n) {
if(n==0) {
//print
System.out.println(res);
return;
}
for(int i=0;i<data.length();i++)
printSpecialNo(res+data.charAt(i), getData(data,i), n-1);
}

private static String getData(String data, int i) {
String modifiedData="";
int b = Integer.parseInt(data.charAt(i)+"");
for(int j=0;j<mainData.length();j++) {
int a = Integer.parseInt(mainData.charAt(j)+"");

if(Math.abs(a-b)==1)
modifiedData+=Integer.toString(a);
}
return modifiedData;
}

}

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

The problem becomes much more tractable if the special no. is treated as a string.
The recursive logic goes something like this:
for every number n in the given range:
spl_no_str = n + spl_no_str(n-1);
and
spl_no_str = n + spl_no_str(n+1);

``````static void printRange(int a, int b)
{

int n = b-a + 1;

//loop for length of string
for(int i = 2; i<=n ; i++)
{
// loop for starting digit of spl no.
for(int j = a ; j<=b ; j++)
{

specialNo(j,"", a,b, i);

}

}

}

static void specialNo(int n, String s, int a, int b, int l)
{

if(s.length() <=l)
{
s = s + n;

if(s.length() == l)
{
System.out.println(s);

}
if(n+1<=b)
specialNo( n+1, s, a, b, l);
if(n-1>=a)
specialNo( n-1, s, a, b, l);
}

}``````

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.

### 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.