## Amazon Interview Question for Developer Program Engineers

Country: United States
Interview Type: In-Person

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

This is very interesting question. Please find my generic working solution upto number of 4 digit.... In this program input parameter is String-Input, String-Lenght and digit.

``````char* findMissingEle(char str[], int len, int digit)
{
char *output;
int diff=0, place, i=0, j=0;
int num1, num2;
while(i<len-digit)
{
switch (digit)
{
case 1:
num1 = str[i];
num2 = str[i+1];
break;
case 2:
num1 = str[i];
num1 = num1*10 + str[i+1];
num2 = str[i+2];
num2 = num2*10 + str[i+3];
break;
case 3:
num1 = str[i];
num1 = num1*10 + str[i+1];
num1 = num1*10 + str[i+2];
num2 = str[i+3];
num2 = num2*10 + str[i+4];
num2 = num2*10 + str[i+5];
break;
case 4:
num1 = str[i];
num1 = num1*10 + str[i+1];
num1 = num1*10 + str[i+2];
num1 = num1*10 + str[i+3];
num2 = str[i+4];
num2 = num2*10 + str[i+5];
num2 = num2*10 + str[i+6];
num2 = num2*10 + str[i+7];
break;
}
i = i + digit;
diff = num2 - num1;
if(diff != 1)
break;
}
if(diff)
{
place = i;
len = len + digit;
output = (char*)malloc(sizeof(char)*len);
for(i=0, j=0; j<len; j++, i++)
{
if(i!=place)
output[i] = str[j];
else
{
switch (digit)
{
case 1:
output[i] = str[j]-1;
break;
case 2:
output[i++] = str[j];
output[i] = str[j+1] -1;
break;
case 3:
output[i++] = str[j];
output[i++] = str[j+1];
output[i] = str[j+2] - 1;
break;
case 4:
output[i++] = str[j];
output[i++] = str[j+1];
output[i++] = str[j+2];
output[i] = str[j+3] - 1;
break;
}
j--;
}
}
}

return output;
}``````

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

Dear Shakti,

You can ask these question on general forum.

Comment hidden because of low score. Click to expand.
-2

U right ashish..

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

This is not a fake ques..This s the 1st ques asked by the interviewer and I had 2 hours of technical rounds after lunch with him..Now IT IS UP 2 U..to answer or not!!!

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

This is a good question and if YOU misunderstood the question it does not mean that is fake.
Dont just say it is fake. why is it fake?

some samples:
input : 891112 output: 89101112
input : 100102103 output: 100101102103
input : 23242527 output 2324252627

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

geekyjumps.blogspot.in/2013/08/find-missing-number-in-given-string.html

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

Dnt tempt me..

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

Your program will fail for the following input "911913914".

Please change the for loop that you have used to this one ::

``for (int i = str.length() / 2; i >=1 ; i--) {``

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

``````public static String missedNumber(String string) {
int missedNo = -1;
int n = string.length();
int next, temp, len, missedIndex = 0;

for (int l = 1; l <= n / 2; l++) {
next = Integer.valueOf(string.substring(0, l)) + 1;
len = l;
for (int i = l; i < n;) {

if (next / Math.pow(10, l) >= 1  &&  (next - 1) / Math.pow(10, l) < 1)
len++;

if (i + len <= n)
temp = Integer.valueOf(string.substring(i, i + len));
else
break;

if (temp == next) {
next++;
} else if (temp == next + 1 && missedNo == -1) {
missedNo = next;
missedIndex = i;
next++;
} else if ((next + 1) / Math.pow(10, l) == 1) {
temp = Integer.valueOf(string.substring(i, i + len + 1));
if (temp == next + 1 && missedNo == -1) {
missedNo = next;
missedIndex = i;
len++;
next += 2;
} else
break;
} else {
missedNo = -1;
break;
}
i += len;
}
if (missedNo != -1) {
break;
}
}
if (missedNo != -1) {
String before = string.substring(0, missedIndex);
String missed = String.valueOf(missedNo);
String after = string.substring(missedIndex, n);
return before.concat(missed).concat(after);
} else
return null;
}``````

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

Hey guys, I strongly feel except Ehsan, nobody has understand question properly. Come on, its Amazon question. Interviewer has just given one example. It doesn't mean that we have write program for just for that example.

Given numbers can be in any range (single digit, double and to any extent) and can be mixed digit numbers too (like can start with 2 digit number and can go to 3 digit number: Below sample inputs can help you to understand question better:

123567 // 1 digit numbers
45464849 // 2 digit numbers
9899100102103 // mixed digit numbers

Refer Question id=5564407157358592

Hope this helps

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

I did it on purpose lol.

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

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

int main()
{
//char *str = "1231123212331234123512371238";
char *str = "4142434546";
int numdigit = 1;

int len = strlen(str);
char *ptr = str;
int bufflen = len/3;
char buff[10] = {0};
int num1,num2,num3;

while((ptr) && *ptr != '\0')
{
strncpy(buff,ptr,numdigit);
num1 = atoi(buff);
memset(buff,0,10);
strncpy(buff,ptr+numdigit,numdigit);
num2 = atoi(buff);
memset(buff,0,10);
strncpy(buff,ptr+2*numdigit,numdigit);
num3 = atoi(buff);
memset(buff,0,10);

if((num2 != num1 +1) && (num3 == num1 + 3))
{
printf("Missing number is : %d\n",num1+1);
break;
}
else if((num2 != num1 +1) && (num3 != num1 + 2))
{
ptr = str;
numdigit += 1;
continue;
}
ptr = ptr + numdigit*2;
}
return 0;
}

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

Meaningless ques..*** the poster..

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

In my previous code there was an issue I fixed it in following code.

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

int main()
{
//char *str = "1231123212331234123512371238";
//char *str = "4142434546";
//char *str = "99100101103104";
char *str = "9101113141516";
int numdigit = 1;

int len = strlen(str);
char *ptr = str;
char buff[10] = {0};
int num1,num2,num3,offset;

while((ptr) && *ptr != '\0')
{
offset = 0;
strncpy(buff,ptr,numdigit);
num1 = atoi(buff);
memset(buff,0,10);
offset = snprintf(buff,10,"%d",num1+1);
memset(buff,0,10);
strncpy(buff,ptr+numdigit ,offset);
num2 = atoi(buff);
memset(buff,0,10);
strncpy(buff,ptr+ offset + numdigit,offset);
num3 = atoi(buff);
memset(buff,0,10);

if((num2 != num1 +1) && (num3 == num1 + 3))
{
printf("Missing number is : %d\n",num1+1);
break;
}
else if((num2 != num1 +1) && (num3 != num1 + 2))
{
ptr = str;
numdigit += 1;
continue;
}
ptr = ptr + offset + numdigit;
numdigit =offset;
}
return 0;
}

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

``````public class MissingNumber {

public static void main(String[] args) {

String str = "9899100101103104105";
long [] strArray = new long[str.length()/2];
String numS = "";
int num = 0;
int nextNum = 0;
long seq = 0;
for (int i = 0; i < str.length()/2; i++) {
numS = ""+str.charAt(i);
nextNum = Integer.valueOf(numS);
if(num!=0){
nextNum = num * 10 + nextNum;

}
num = nextNum;
strArray[i]= nextNum;

}
for (int i = strArray.length-1; i >= 0 && strArray[i]!=0; i--) {

if(checkSequence(strArray[i],str)){
seq = strArray[i];

break;
}

}
for(int i = 0; true ; i++){

if(!str.contains(Long.toString(seq+i))){
System.out.println("The missing number is ::::: "+(seq+i));
break;
}
}

}
static boolean checkSequence(long l,String str){
int count = 0;
for(int i = 0; i<5 ; i++){
if(count!=2 && str.contains(Long.toString(l+i))){
continue;
}
else if (count < 1){
count++;
}else{
return false;
}
}
return true;
}
}``````

Algorithm:
1. Split the string to long array to find the sequence.
2. For example, String s = "123" should converted into {1,12,123}
3. Using long array, start from the end and check for the missing number to find the correct sequence.
4. After finding the sequence find the missing number

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

It does not work for "101113"

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

posted wrong version of code

``````public class MissingNumber {

public static void main(String[] args) {

String str = "101113";
long [] strArray = new long[str.length()/2];
String numS = "";
int num = 0;
int nextNum = 0;
long seq = 0;
for (int i = 0; i < str.length()/2; i++) {
numS = ""+str.charAt(i);
nextNum = Integer.valueOf(numS);
if(num!=0){
nextNum = num * 10 + nextNum;

}
num = nextNum;
strArray[i]= nextNum;

}
for (int i = strArray.length-1; i >= 0 && strArray[i]!=0; i--) {

if(checkSequence(strArray[i],str)){
seq = strArray[i];

break;
}

}
for(int i = 0; true ; i++){

if(!str.contains(Long.toString(seq+i))){
System.out.println("The missing number is ::::: "+(seq+i));
break;
}
}

}
static boolean checkSequence(long l,String str){
//System.out.println(l);
long indexCheck = 0;
int count = 0;
for(int i = 0; i<3 ; i++){
if(count!=2 && str.contains(Long.toString(l+i))){
if(i!=0&&str.indexOf(Long.toString(indexCheck))!=0){
if(str.indexOf(Long.toString(l+i)) > str.indexOf(Long.toString(indexCheck))&&str.indexOf(Long.toString(l+i))%str.indexOf(Long.toString(indexCheck))!=0){
count++;
if(count==2){
return false;
}
}else if(str.indexOf(Long.toString(indexCheck)) > str.indexOf(Long.toString(l+i))&&str.indexOf(Long.toString(indexCheck))%str.indexOf(Long.toString(l+i))!=0){
count++;
if(count==2){
return false;
}
}
}

if(str.indexOf(Long.toString(l+i))>0){
indexCheck = l+i;
}

continue;
}
else if (count < 1){
count++;
}else{
return false;
}
}
return true;
}
}``````

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

``````public StringBuilder validate(string[] S, string N)
{
if(S.length==0)
return true;
stringbuilder R = new StringBuilder();
for(int i=1;i<S.length/2;i++)
{
int Num = convert.toint32(S.substring(0,i));
for(int j=i;j<S.length;j+i)
{
int Next = convert.toint32(S.substring(j,i));
if(Num != next +1);
{
if(next>convert.toInt32(N))
R.Append(S.substring(0,j))
R.Append(N);
R.Append(S.substring(i+j,S.length-1);
return R;
}
}
}
if(S.substring(0,N.length-1))>N)
{
R.Append(N);
R.Append(S)
}
if(S.substring(S.length-1-N.length-1,S.length-1))<N)
{
R.Append(S)
R.Append(N);
}
return R;
}``````

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

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

char str[10]="4142434546";
char new_buff[12];
int i,j;

void fun1()
{
for(i=0;i<12;i+=2)
{
new_buff[i]=str[i];
new_buff[i+1]=str[i+1];
if(str[i+1]=='3')
{
i=i+2;
break;
}
}
}

void fun2()
{
for(;j<12;j=j+2)
{
new_buff[j]=str[i];
new_buff[j+1]=str[i+1];
i=i+2;
}
}

int main()
{
fun1();
new_buff[i]='4';
new_buff[i+1]='4';
j=i+2;
fun2();
printf("str:%s new_buff:%s\n",str,new_buff);
return 0;
}

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

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

char str[10]="4142434546";
char new_buff[12];
int i,j;

void fun1()
{
for(i=0;i<12;i+=2)
{
new_buff[i]=str[i];
new_buff[i+1]=str[i+1];
if(str[i+1]=='3')
{
i=i+2;
break;
}
}
}

void fun2()
{
for(;j<12;j=j+2)
{
new_buff[j]=str[i];
new_buff[j+1]=str[i+1];
i=i+2;
}
}

int main()
{
fun1();
new_buff[i]='4';
new_buff[i+1]='4';
j=i+2;
fun2();
printf("str:%s new_buff:%s\n",str,new_buff);
return 0;
}

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

Here's a complete code. In every iteration of the main loop it checks whether the first and the second OR the first and the third numbers formed so far belong to an ascending sequence. If such a combination is found, it calculates the sum of the sequence, given the last valid entry found and compares it with the actual sum of the complete sequence i.e., n(n+1)/2.

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

int NumValue(const string s)
{
int num=0;
for(size_t index=0;index<s.length();index++)
num=(num*10)+(s[index]-'0');
return num;
}
void CalculateSum(const string str,const string baseStr, int p, int flag, int &sum, int &count, int n, int baseNum)
{
string nextStr;
int nextNum=0;

while(p<n)
{
nextStr=str.substr(p,baseStr.length()+flag);
nextNum=0;
nextNum=NumValue(nextStr);
count++;
sum+=nextNum-baseNum;
p+=baseStr.length()+flag;
}
}

void findMissingValue(const string str)
{
if(str.size()==0)
return;

int k=1;
string s1,s2,s3,s4;
int flag=0;
int i,j,p,val,diff,missing;
int n1,n2,n3;
int count=1,sum=0;
int n=str.length();

for(i=0;i<n;i++)
{
n1=n2=n3=0;
j=i+1;
s1=str.substr(0,i+1);
s2=str.substr(j,j);
s3=str.substr(j,j+1);

n1=NumValue(s1);
n2=NumValue(s2);
n3=NumValue(s3);

if(n1==n2-1 || n1==n3-1)
{
if(n1==n2-1)
{
s3=str.substr(j+s2.length(),s2.length()+flag);
n3=0;
n3=NumValue(s3);
if(n2==n3-1)
flag=0;
else
flag=1;

s3=str.substr(j+s2.length(),s2.length()+flag);
n3=0;
n3=NumValue(s3);

p=j+2*s2.length()+flag;
if((n3+1)%10==0)
flag++;

CalculateSum(str, s2,p,flag,sum,count,n,n3);
}
else if(n1==n3-1)
{
p=j+s3.length()+flag;
if((n3+1)%10==0)
flag++;
CalculateSum(str,s3,p,flag,sum,count,n,n3);
}

val=(count*(count+1))/2;
diff=val-sum;
missing=n3+diff;
printf("Missing Element:\t%d\n",missing);
}
else
k++;
}
}

int main()
{
string str="7891012";//"9899100101103";//"4142434546";//"99899910001002";//"99100102103";//
cout<<str<<endl;
findMissingValue(str);

return 1;
}``````

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

``````import java.util.Stack;

public class HelloWorld {
public static void main(String[] args) {
HelloWorld hw = new HelloWorld();
System.out.printf(hw.insertMissingNumber("99799899910011002"));
}

public String insertMissingNumber(String str) {
int[] array = new int[str.length()];
char[] digits = str.toCharArray();

for(int index = 0; index < str.length(); index++) {
array[index] = digits[index] - '0';
}

int digitLength = 1;
while (digitLength < digits.length + 1) {
int position = 0;
int tempLength = digitLength;
while (position + tempLength < digits.length) {
Stack<Integer> stack1 = getNextValue(array, position, tempLength, 1);
Stack<Integer> stack2 = getNextValue(array, position, tempLength, 2);

if(getLengthMatched(array, position + tempLength, stack2) >= tempLength) {
return String.format("%s%s%s",
str.substring(0, position + tempLength),
getString(stack1),
str.substring(position + tempLength));
}

int lengthMatched = getLengthMatched(array, position + tempLength, stack1);
if(lengthMatched >= tempLength) {
position = position + tempLength;
tempLength = lengthMatched;
continue;
}
break;
}
digitLength++;
}
return str;
}

private Stack<Integer> getNextValue(int[] array, int position, int length, int step) {
Stack<Integer> stack = new Stack<Integer>();
int last = position + length - 1;
do {
stack.push((array[last] + step) % 10);
step = (array[last] + step) / 10;
last--;
} while (last >= position);

if(step > 0) {
stack.push(step);
}
return stack;
}

private int getLengthMatched(int[] array, int position, Stack<Integer> stack) {
int len = 0;
while(stack.isEmpty() == false) {
if(array[position] == stack.pop()) {
position++;
len++;
} else {
break;
}
}
return len;
}

private String getString(Stack<Integer> stack){
int val = 0;
while (stack.isEmpty() == false) {
val = val * 10 + stack.pop();
}
return String.format("%s", val);
}
}``````

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

The way you stated it make it easy though:
Make sure str buffer has room for the extra numbres <--

``````int i;
for(i=0; i < n-1; i+=2)
if( str[i+1] == 3 )
break;

//at this point, i points to 4, i+1 points to 3  (the "43")
dig=4;
while(i=='4') {
str[i+1] = dig++;
i+=2;
}
//at this point str[i]=NUL byte (one past last number)
str[i] = 4, str[i+1]=dig, str[i+2] = '\0'``````

//Fill in error handles for border cases , and fix the bugs,... :)

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

Pattern pattern =Pattern.compile{'3'}
Matcher m =pattern.matcher(4142434546)
String output=m.replaceFIrst('344') or m.replaceAll('344')

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

Cool Yogesh.

If that's allowed, then this is fair game:

``return "414243444546";``

:)

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

Thank u 2 all fr commenting 2 my questn..The Simple ever solution is..

just cpy and paste it into browxy site..

CODE:
import java.io.*;

public class Test{
public static void main(String args[]){
String Str = "4142434546";

System.out.print("Return Value :" );
System.out.println(Str.replaceFirst("43", "4344" ));
}
}

OUTPUT:
Return Value :414243444546

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

An interviewer won't ask such a simple question AND allow you to call these library functions. Doubt it.

Plus if the question is so simple, he/she is looking for you to write loops in an efficient manner. replaceFirst goes through a regex engine (but it won't backtrack in this case) and works with immutable strings. If this is allowed, you could do it just as easily manually by copying the original string to a new one yourself in a loop.

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

``````public String insertChar(String str, String a){
String subStr1 = str.substring(0,4);
String subStr2 = str.substring(4);
String newString = subStr1 + a + subStr2;
return newString;
}``````

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

I misunderstood the que. sorry~~~

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.