Amazon Interview Question SDE1s
Country: United States
Hi,
Thanks for posting a solution, what i perceive is ur checking for each substring starting from length 1 ? can u think of a more optimised solution? What I suggested in interview was we break down the string in factors of total length from len/2 to 1. Then he gave me the test case of 9979981000 so I checked for factors of length and prime numbers till len/2 .
so for 9979981000, i check for substrings of length 5,3,2,1.
Hi,
Glad to hear the feedback.
I think you should ask your interviewer about the relation between the total length and the order of the number, otherwise starting from 1 to n or n down to 1 won't have any statistical influence on the complexity IMHO.
You do have a good idea to jump some numbers, but your solution, jumping non-factor and non-prime are incorrect. Imagine 999999 1000000 with length 13. The correct starting number would be of length 6 but you would have missed it. What we could do instead is for example stop at length/2.
Hi,
My first solution was that we check till len/2,but clearly he was looking for more optimised approach.
Hi,
Ok here's one optimization I found:
E.g. this can get rid of trying length 4 starting number for 10 in total, 5 for 24, 7 for 24, etc:
n digit number
m digit starting number
if n % m == 0
ok go on
else
number_of_occurrence = n / m
number_of_leftovers = n % m
if number_of_leftovers >= number_of_occurrence:
not ok
else
go on
But I thinks there are better solutions, also, I'm not sure if this is valid if we have the string long enough to hold consecutive numbers from n digits to n + 2 , +3, etc like 12345678910.....99100
The question is if this is the only information about the string we have. Can we assume that the sequence of numbers in the string will always consist of the same number of digits? Are the numbers always positive? Is the sequence always increasing? Is the miising number always in between? If yes, then I propose the following:
(i) Given number of digits 'k' convert respective substrings of the length 'k' into integers. (ii) Check the differences in order to identify missing integer. There must be only one break point with difference equal to 2 in the string. If not, increase 'k' and go to (i).
A spample code is shown below:
public int missingNumber(String s) {
int N = s.length();
int out;
for (int k=1; k<=N/2; k++) { // we need at least 2 numbers
out = findMissing(s, k);
if (out != -1) return out;
}
return -1;
}
private int findMissing(Strings, int k) {
int N = s.length();
if (N%k != 0) return -1;
int[] a = new int[N/k];
for (int j=0; j<N; j += k)
a[j] = Integer.parseInt(s.substring(k, k+c));
int cnt = 0, out;
for (int k=0; k<a.length-1; k++)
if (a[k+1]-a[k] > 1) { // breakpoint
cnt++;
out = a[k]+1;
}
if (cnt == 1) return out;
return -1;
}
From the description and the test cases given, the number may not be of same length all the time:
"9979981000" -> 999 ,, 1000 is of different length.
This is an instant idea, but not a fast one:
def solve(s):
l = len(s)
for i in xrange(1,l):
h = 0
t = i
miss = -1
while t<l:
next = str(int(s[h:t]) + 1)
if next == s[t:len(next)+t]:
h = t
t = h+len(next)
continue
next = str(int(s[h:t]) + 2)
if next == s[t:len(next)+t]:
if miss != -1:
miss = -1
break
miss = int(next)-1
h = t
t = h+len(next)
continue
break
if miss != -1:
break
return miss
if __name__ == '__main__':
test = ['1234568', '9979981000','624625627']
print test
for i in test:
print solve(i)
here is working solution in java:
import java.io.*;
public class MissingConsec {
static String detectMissingConsecutive(String ip)
{
int test,con,i,j=0;
boolean isSequence=false;
int glich=-1;
for(i=1;i<=ip.length()/2;++i)
{
isSequence=true;
glich=-1;
for(j=0;j<ip.length()-i*2;)
{
test=Integer.parseInt(ip.substring(j,j+i));
con=Integer.parseInt(ip.substring(j+i,j+i*2));
if(test==con-1)
{
j+=i;
}
else if(test==con-2)
{
if(glich==-1)
{
glich=j;
j+=i;
}
else{
isSequence=false;
break;
}
}
else{
isSequence=false;
break;
}
}
if(j>=ip.length()-i*2)
isSequence=false;
if(isSequence)
break;
}
if(isSequence)
{
int temp=Integer.parseInt(ip.substring(glich,glich+i));
return ip.substring(0,glich+i)+(temp+1)+ip.substring(glich+i,ip.length());
}
return "inappropriate input";
}
public static void main(String[] st)
{
System.out.println("enter number string:");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String ip="";
try{
ip=br.readLine();
}
catch(Exception e){}
System.out.println("result of "+ip+" is "+detectMissingConsecutive(ip));
}
}
public class MissingSubString
{
public static int checkPattern(String str)
{
int len = str.length();
int finalSum=0,sum=0;
for (int i = len; i >=1; i--) {
if (len % i == 0 ||( (len %i ==1) && (str.charAt( len-1) =='0' ))) {
int [] arr = new int[i ];
sum=0;
for(int j=0;j<arr.length;j++)
{
arr[j] = Integer.parseInt( str.substring((len/i)*j,(len/i)*(j+1)) );
sum += arr[j];
}
if(str.charAt( len-1) =='0' ) {
sum -=arr[arr.length-1];
arr[arr.length-1] =arr[arr.length-1] * 10;
sum +=arr[arr.length-1];
}
finalSum=0;
for(int k=arr[0];k<=arr[arr.length-1];k++)
{
finalSum +=k;
}
if((finalSum-sum)<arr[arr.length-1] && (finalSum-sum)>0)
return finalSum-sum;
}
}
return 0;
}
public static void main(String [] args)
{
String str="9799100";
System.out.println(checkPattern(str));
}
}
Hi pradeep
Thanks for writing a perfectly working code, but can u plz specify where have u achieved optimization?
thanks...
I have a working version that runs in O(nlogn).
private static void Main()
{
var str = "99799810001001";
Console.WriteLine("Missing number: {0}",FindMissingNumber(str));
}
public static string FindMissingNumber(string str){
if (string.IsNullOrEmpty(str)) return string.Empty;
int len = 1, curIdx=0, missing=-1;
int strLen = str.Length;
while(true){
if (curIdx >= strLen) break;
if (curIdx+len >strLen) break;
if (curIdx+len+len > strLen) break;
var current = str.Substring(curIdx,len);
var next = str.Substring(curIdx+len,len);
int curInt,nextInt,possibleNextInt;
if (!Int32.TryParse(current,out curInt)) return string.Empty;
if (!Int32.TryParse(next,out nextInt)) return string.Empty;
int diff = nextInt - curInt;
if (diff == 1){ //In sequence, continue
curIdx+=len;
} else if (diff == 2) { //Missing number possibly
if (missing>0) { //repeateadly missing number - startover
curIdx = 0;
len++;
} else{
curIdx+=len;
missing = curInt+1;
}
}else{ //not in sequence - may be
if (curIdx+len+len+1 > strLen) return string.Empty;
var possibleNext = str.Substring(curIdx+len,len+1); //Check for 999, 1000 case a possible next could be 1+length of the current number
if (!Int32.TryParse(possibleNext,out possibleNextInt)) return string.Empty;
diff = possibleNextInt - curInt;
if (diff == 1){ //Hey! In sequence again
curIdx+=len;
len++; //Length should be incremented from now on from (say 3 to 4 in the case of 999 and 1000)
} else if (diff == 2) { //Missing number logic
if (missing>0) {
curIdx = 0;
len++;
} else{
curIdx+=len;
len++;
missing = curInt+1;
}
}else{ //No matter what, incorrect sequence start over.
curIdx = 0;
len++;
}
}
}
if (curIdx + len < strLen) return string.Empty;
if (missing == -1) return string.Empty;
return missing.ToString();
}
}
Here is my solution, in C++11. Unfortunately, I could not find something better than O(N^2) yet.
std::string findMissingNumber(const std::string &str)
{
auto addOne = [](const std::string &number) -> std::string
{
std::string copy = number;
bool carry = true;
for (auto it = copy.rbegin(); it != copy.rend(); ++it)
{
if (*it == '9')
*it = '0';
else
{
++(*it);
carry = false;
break;
}
}
if (carry)
copy.insert(copy.begin(), '1');
return copy;
};
auto findMissingNumber = [&addOne, &str](const size_t &nbDigits) -> std::string
{
std::string missingNumber = "";
std::string readNumber = str.substr(0, nbDigits);
for (size_t i = nbDigits; i < str.length(); )
{
std::string expectedNumber = addOne(readNumber);
if (i + expectedNumber.length() > str.length())
return "";
readNumber = str.substr(i, expectedNumber.length());
if (readNumber != expectedNumber)
{
if (missingNumber != "")
return "";
std::string nextExpectedNumber = addOne(expectedNumber); // skip one
if (i + nextExpectedNumber.length() > str.length())
return "";
readNumber = str.substr(i, nextExpectedNumber.length());
if (readNumber != nextExpectedNumber)
return "";
missingNumber = expectedNumber;
}
i += readNumber.length();
}
return missingNumber;
};
size_t nbDigits = str.length() / 2;
while (nbDigits > 0)
{
std::string missingNumber = findMissingNumber(nbDigits);
if (missingNumber != "")
return missingNumber;
--nbDigits;
}
return "";
}
int DigCount(int num)
{
int i;
for (i = 0; num >= pow(10, i); i++)
{
}
return i;
}
string FindMissed(string str)
{
for(int i = 1; i < str.size(); i++)
{
int curPos = 0;
int curNum;
int prevNum = -1;
int missedNum;
int curDigCount = i;
int nextDigCount = i;
int missedCount = 0;
for(;;)
{
if(prevNum > 0)
{
curDigCount = DigCount(prevNum + 1);
nextDigCount = DigCount(prevNum + 2);
}
if(curPos + curDigCount >= str.size())
{
break;
}
curNum = atoi(str.substr(curPos, curDigCount).c_str());
if(prevNum > 0)
{
if(curNum == prevNum + 1)
{
curPos += curDigCount;
prevNum = curNum;
if(curPos == str.size() - 1)
{
break;
}
else
{
continue;
}
}
else
{
if(curPos + nextDigCount >= str.size())
{
missedCount = 0;
break;
}
else
{
curNum = atoi(str.substr(curPos, nextDigCount).c_str());
if(curNum == prevNum + 2)
{
curPos += nextDigCount;
missedNum = prevNum + 1;
prevNum = curNum;
missedCount++;
if(curPos == str.size() - 1)
{
break;
}
else
{
continue;
}
}
else
{
break;
}
}
}
}
else
{
prevNum = curNum;
curPos += curDigCount;
continue;
}
}
if(missedCount == 1)
{
return to_string(missedNum);
}
}
return "";
}
A little long, but It is easy to understand I think
import java.io.ObjectInputStream.GetField;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String ch = "9798100";
System.out.println(getMissingNumber(ch));
}
public static long getMissingNumber(String sequence)
{
try
{
Long.parseLong(sequence);
boolean found = false;
String numberCharString = ".";
long missignNumber = -1;
while((numberCharString.length()<=sequence.length())&&(!found))
{
String[] numbers = sequence.split("(?<=\\G"+numberCharString+")");
long number1, number2;
if(numbers.length>=2)
{
int i = 0;
for(i=0;i<numbers.length-1;i++)
{
number1 = Long.parseLong(numbers[i]);
number2 = Long.parseLong(numbers[i+1]);
if(number2 - number1==1){}
else if(number2 - number1==2){missignNumber = number1 + 1;}
else {
String subString = sequence.substring(sequence.indexOf(numbers[i])+numbers[i].length(), sequence.length());
String[] numbersS = subString.split("(?<=\\G"+numberCharString+".)");
int j=0;
for(j=0;j<numbersS.length;j++)
{
number2 = Long.parseLong(numbersS[j]);
if(number2 - number1==1){}
else if(number2 - number1==2){missignNumber = number1 + 1;}
else {found = false; break; }
number1 = Long.parseLong(numbersS[j]);
}
if(j==numbersS.length-1)
{ found=true;
return missignNumber;
}
else
{
found = false;
break;
}
}
}
if((i==numbers.length-2)||(found))
{
found=true;
return missignNumber;
}
else
{
numberCharString=numberCharString+".";
}
}
}
return -1;
}
catch(Exception e)
{
System.out.println("string error");
return -1;
}
}
}
private static int FindMissing(string str)
{
int x;
if (!int.TryParse(str, out x))
return -1;
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= max; i++)
{
if (str.Length % i != 0)
{
continue;
}
int prev = -1;
int missing = -1;
for (int j = 0; j < str.Length; j++)
{
sb.Append(str[j]);
if (sb.Length == i)
{
int curr = int.Parse(sb.ToString());
if (prev != -1)
{
if (prev + 1 != curr)
{
if (missing == -1)
{
missing = prev + 1;
}
else
{
missing = -1;
break;
}
}
}
prev = curr;
sb.Clear();
}
}
sb.Clear();
if (missing != -1)
{
return missing;
}
}
return -1;
}
What about this..
#include<iostream>
#include<conio.h>
//#include<map.h>
using namespace std;
int getStringPattern(char *str,int &lenght)
{
char pattern[100];;
pattern[0]=str[0];
str++;
int currentcount=0;
while(*str!='\0')
{
int count=0;
if(pattern[count]!=(*str))
{
currentcount++;
pattern[currentcount]=*str;
}
else
{
char *ptr=str;
while(pattern[count]==*ptr)
{
count++;
ptr++;
}
// pattern[count]='\0';
break;
}
str++;
}
pattern[currentcount+1]='\0';
int val=atoi(pattern);
lenght=currentcount+1;
// cout<<val<<endl;
return val;
}
int getMissingNumber(char *str,int val,int lenght)
{
char temppattern[100];
val++;
itoa(val,temppattern,10);
str=str+lenght;
while((*str)!='\0')
{
int count=0;
while((temppattern[count]) !='\0' && (temppattern[count])==(*str))
{
count++;
str++;
}
if(temppattern[count]!='\0')
return val;
else
val++;
}
}
int main()
{
char str[]="622462266227";
int lenght=0;
int val=getStringPattern(str,lenght);
val=getMissingNumber(str,val,lenght);
cout<<"Missing value "<<val<<endl;
getch();
}
public static int missingSubStr(string s) {
int res = 0;
int ind = 0;
bool done = false;
while (!done)
{
ind++;
int i = ind,n,notFound=0;
string str = s.Substring(0, ind);
n = Convert.ToInt32(str);
n++;
while (i < s.Length && notFound < 2) {
str = n.ToString();
for (int j = 0; j < str.Length; j++) {
if (str[j] != s[i]) {
res = n;
notFound++;
i -= j;
break;
}
i++;
}
n++;
}
if (ind == s.Length || notFound == 1) {
done = true;
}
}
return res;
}
A simple solution using recursion. The iteration version should be faster if you have time to develop, also using other languages than Python should be faster...
- gameboy1024 January 19, 2015def verify(string, next_number, next_index, missing): # If we are already at the end, we are done. if next_index == len(string): return missing # If the next number is not what we expected if string[next_index:next_index + len(str(next_number))] != str(next_number): # If we already skipped some number, the input then is not valid. if missing != None: return None # Else we try to skipped the number and try the next one. return verify(string, next_number + 1, next_index, next_number) # If it's a match we go on to the next one. else: return verify(string, next_number + 1, next_index + len(str(next_number)), missing) string = "9989991001" for l in xrange(1, int(len(string) / 2) + 1): start = int(string[0:l]) missing = verify(string, start + 1, l, None) if missing != None: print missing exit() print "No missing number or more than one missing numbers"