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.
Please give your comment about the solution

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;
}

- Rahul September 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

Dear Shakti,

Please dont ask fake question on specific Forums.
You can ask these question on general forum.

- Ashish September 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

U right ashish..

- Anonymous September 21, 2013 | Flag
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!!!

- Shaki September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ehsan September 22, 2013 | Flag
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

- Anonymous September 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dnt tempt me..

- Anonymous September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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--) {

- guptasunny158 September 23, 2013 | Flag
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;
	}

- ehsan September 21, 2013 | Flag Reply
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

- Kallu September 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did it on purpose lol.

- bigphatkdawg September 21, 2013 | Flag
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;
}

- Nishikant September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Meaningless ques..*** the poster..

- Anonymous September 21, 2013 | Flag
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;
}

- Nishikant September 21, 2013 | Flag Reply
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

- Libin Thambi September 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It does not work for "101113"

- ehsan September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
	}
}

- Libin Thambi September 22, 2013 | Flag
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; 
}

- Rohit September 21, 2013 | Flag Reply
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;
}

- mukesh kumar September 21, 2013 | Flag Reply
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;
}

- kumarmukesh2013 September 21, 2013 | Flag Reply
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;
}

- Anonymous September 21, 2013 | Flag Reply
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);
	}
}

- minatoruan September 23, 2013 | Flag Reply
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,... :)

- bigphatkdawg September 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Yogesh September 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool Yogesh.

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

return "414243444546";

:)

- bigphatkdawg September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Shaki September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bigphatkdawg September 21, 2013 | Flag
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;
}

- chuang24@buffalo.edu September 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I misunderstood the que. sorry~~~

- chuang24@buffalo.edu September 22, 2013 | Flag


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