Amazon Interview Question
Developer Program EngineersCountry: United States
Interview Type: In-Person
Dear Shakti,
Please dont ask fake question on specific Forums.
You can ask these question on general forum.
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!!!
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;
}
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
#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;
}
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;
}
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
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;
}
}
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;
}
#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;
}
#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;
}
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;
}
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);
}
}
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,... :)
Pattern pattern =Pattern.compile{'3'}
Matcher m =pattern.matcher(4142434546)
String output=m.replaceFIrst('344') or m.replaceAll('344')
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
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.
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;
}
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
- Rahul September 22, 2013