Flipkart Interview Question SDE-2s
Team: digital platform
Country: India
Interview Type: Phone Interview
A bit messy, but a quick working solution in Python regardless of digit length.
def findMissingN(string):
"""
in: "960961962964"
out: 963
in 12345789
out: 6
"""
def getDigits(start):
digits = 0
while start:
start = start / 10
digits += 1
return digits
def scan(num, string):
"""
see if _string_ starts with num
"""
next = int(string[:getDigits(num)])
return num == next
def returnMissing(start, string):
"""
start - starting integer
string - the rest of the string
"""
i = 1
jumped = False
early = False
while string:
if scan(start+1, string):
start += 1
digit = getDigits(start)
string = string[digit:]
elif scan(start+2, string) and not jumped:
start += 2
digit = getDigits(start)
string = string[digit:]
jumped = True
skipped_n = start - 1
else:
# wasn't +1 or +2
early = True
break
if not early:
return skipped_n
else:
return None
for i in range(1, len(string)/2):
start = int(string[0:i])
ret = returnMissing(start, string[i:])
if ret:
return ret
print findMissingN("910911913")
It's probably simpler to just look at my code, but here's a description.
I iteratively assume M is 1-digit, 2-digits, 3-digits, up to (len+1)/2 digits where len is length of input.
I then have a helper method that takes 3 parameters:
(1) current string
(2) number that I expect the string to start with
(3) whether I have already skipped any number
If current string is empty, then return 0 to indicate success.
Elsif current string starts with the number I expect, then call the method recursively on the remaining string and (number + 1)
Elsif I have already skipped a number, then return -1 to indicate failure.
Elsif the recursive call on current string and number returns 0 (success), return the number I just skipped.
Else return -1 to indicate failure.
class MissingNumber {
public static int missing(String s) {
int len = s.length();
for(int i=1; i<(len+1)/2; i++) {
String prefix = s.substring(0, i);
int candidate = Integer.parseInt(prefix);
int result = check(s.substring(i), candidate+1, false);
if(result > 0)
return result;
}
return -1;
}
public static int check(String current, int expected, boolean skipped) {
String prefix = "" + expected;
if(current.length() == 0)
return 0;
else if(current.startsWith(prefix))
return check(current.substring(prefix.length()), expected + 1, skipped);
else if(skipped)
return -1;
else if(check(current, expected + 1, true) == 0)
return expected;
else return -1;
}
public static void main(String[] args) {
System.out.println(missing(args[0]));
}
}
///
public class FindMissingNumberFromString {
public static void main(String args[]) {
String value = "12341235123612371238124012411242";// "1213141517181920";
int x = 0;
int y = 0;
for (int count = 1; count <= value.length() / 2; count++) {
while (x < value.length() - count) {
Integer current = Integer.parseInt(value
.substring(x, x + count));
Integer predicted = current + 1;
x = x + count;
Integer actual = Integer
.parseInt(value.substring(x, x + count));
if (predicted.intValue() == actual.intValue()) {
System.out.println("OK" + current);
} else if (actual.intValue() == predicted.intValue() + 1) {
System.out.println("OK"+(predicted.intValue()-1));
System.out.println("Missing one is: "
+ predicted.intValue());
System.exit(0);
} else
break;
}
x = 0;
y = 0;
}
}
}
\\\
Tried with some hit and run, tested well with digit 1, 2, 3,4.... hope should be working given the small time to solve in an interview :P
public class FindMissingNumberFromString {
public static void main(String args[]) {
String value = "12341235123612371238124012411242";// "1213141517181920";
int x = 0;
int y = 0;
for (int count = 1; count <= value.length() / 2; count++) {
while (x < value.length() - count) {
Integer current = Integer.parseInt(value
.substring(x, x + count));
Integer predicted = current + 1;
x = x + count;
Integer actual = Integer
.parseInt(value.substring(x, x + count));
if (predicted.intValue() == actual.intValue()) {
System.out.println("OK" + current);
} else if (actual.intValue() == predicted.intValue() + 1) {
System.out.println("OK"+(predicted.intValue()-1));
System.out.println("Missing one is: "
+ predicted.intValue());
System.exit(0);
} else
break;
}
x = 0;
y = 0;
}
}
}
All these test cases are working
//string str = "960961962964";
//string str = "123457891011";
//string str = "12345789";
//string str = "123412351237";
//string str = "123112321234";
//string str = "293031323335";
//string str = "99101";
//string str = "99100101103104";
//string str = "99101";
string str = "911";
class FindMissing
{
private string astr;
public int missingNo = -1;
public FindMissing(string astr)
{
this.astr = astr;
Perform();
}
private void Perform()
{
int i = 0;
for (; i < astr.Length/2 ; i++)
{
int abc = Convert.ToInt16(astr.Substring(0, i+1));
bool a = DoCheck(abc.ToString().Length, abc + 1, true);
if (true == a)
break;
}
}
private bool DoCheck(int startIndex, int expectedNo, bool isLastok)
{
int abc = Convert.ToInt16(astr.Substring(startIndex, expectedNo.ToString().Length));
bool isCont = (expectedNo == abc) ? true : false;
if (false == isCont)
missingNo = expectedNo;
if (isCont == false && isLastok == false)
{
return false;
}
else
{
if (startIndex + expectedNo.ToString().Length < astr.Length)
{
if (true == DoCheck(startIndex + expectedNo.ToString().Length, abc+1, isCont))
return true;
}
else
return true;
}
return false;
}
}
string str("1000110002100031000510006");
for(int i=1; i< str.length(); i++)
{
int missing = findMissing(str, i);
if(missing > 0)
{
printf(" % d\n\n",missing);
break;
}
}
int findMissing(string & str, int length)
{
int missing = -1 ;
int pos = 0;
string sub;
string nextSub ;
int subNumber ;
int nextSubNumber ;
sub = str.substr(pos,length) ;
subNumber = atoi(sub.c_str()) ;
nextSub = str.substr(pos+length,length) ;
nextSubNumber = atoi(nextSub.c_str()) ;
if( (nextSubNumber - subNumber) > 2 || nextSubNumber < subNumber)
{
return missing ;
}
else
{
while (1) {
pos += length ;
if(pos + length > str.length())
{
break;
}
sub = nextSub ;
subNumber = nextSubNumber ;
nextSub = str.substr(pos,length) ;
nextSubNumber = atoi(nextSub.c_str()) ;
if(nextSubNumber - subNumber == 2)
{
missing = nextSubNumber - 1 ;
break ;
}
}
}
return missing ;
}
string str("1000110002100031000510006");
for(int i=1; i< str.length(); i++)
{
int missing = findMissing(str, i);
if(missing > 0)
{
printf(" % d\n\n",missing);
break;
}
}
int findMissing(string & str, int length)
{
int missing = -1 ;
int pos = 0;
string sub;
string nextSub ;
int subNumber ;
int nextSubNumber ;
sub = str.substr(pos,length) ;
subNumber = atoi(sub.c_str()) ;
nextSub = str.substr(pos+length,length) ;
nextSubNumber = atoi(nextSub.c_str()) ;
if( (nextSubNumber - subNumber) > 2 || nextSubNumber < subNumber)
{
return missing ;
}
else
{
while (1) {
pos += length ;
if(pos + length > str.length())
{
break;
}
if(nextSubNumber - subNumber == 2)
{
missing = nextSubNumber - 1 ;
break ;
}
sub = nextSub ;
subNumber = nextSubNumber ;
nextSub = str.substr(pos,length) ;
nextSubNumber = atoi(nextSub.c_str()) ;
}
}
return missing ;
}
works as far as the string length of individual numbers are same
package findMissingSequence;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(findMissingSeq("12345789"));
}
static String addOne(String st)
{
if(st.charAt(st.length()-1) =='9')
{
return new String(st.substring(0,st.length()-1) + '0');
}
return new String(st.substring(0,st.length()-1) + (char)(st.charAt(st.length()-1)+1));
}
static String findMissingSeq(String Seq)
{
String missingStr="";
String preStr;
int len=Seq.length();
for(int i=1;i<len/2;i++)
{ preStr="";
for(int j=0;(j+i)<len+1; j=j+i)
{ String curr_str=Seq.substring(j,j+i);
if(preStr=="")
{ preStr=Seq.substring(j,j+i);}
else if(addOne(preStr).equals(curr_str))
{
preStr=addOne(preStr);
}
else if(addOne(addOne(preStr)).equals(curr_str)){
missingStr=addOne(preStr);
preStr=addOne(addOne(preStr));
}
else{
missingStr="";
break;
}
}
if(missingStr != "")
{
return missingStr;
}
}
return null;
}
}
package findMissingSequence;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(findMissingSeq("12345789"));
}
static String addOne(String st)
{
if(st.charAt(st.length()-1) =='9')
{
return new String(st.substring(0,st.length()-1) + '0');
}
return new String(st.substring(0,st.length()-1) + (char)(st.charAt(st.length()-1)+1));
}
static String findMissingSeq(String Seq)
{
String missingStr="";
String preStr;
int len=Seq.length();
for(int i=1;i<len/2;i++)
{ preStr="";
for(int j=0;(j+i)<len+1; j=j+i)
{ String curr_str=Seq.substring(j,j+i);
if(preStr=="")
{ preStr=Seq.substring(j,j+i);}
else if(addOne(preStr).equals(curr_str))
{
preStr=addOne(preStr);
}
else if(addOne(addOne(preStr)).equals(curr_str)){
missingStr=addOne(preStr);
preStr=addOne(addOne(preStr));
}
else{
missingStr="";
break;
}
}
if(missingStr != "")
{
return missingStr;
}
}
return null;
}
}
This can be one of the
public static void main(String[] args) {
int a[] = {2111,2112,2113,2114,2115,2116,2118,2119,2122,2124,2126,2128};
int j =a[0];
List <Integer> LT = new ArrayList<Integer>();
for (int i =0; i<a.length;i++){
if(j==a[i]){
j++;
continue;
}else {
LT.add(j);
j++;
i--;
}
}
System.out.println("Missing Numbers"+LT);
}
OutPut:-
Missing Numbers[1117, 1120, 1121, 1123]
How about the following solution:
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000
void reverse(char *str){
int i = 0;
int j = strlen(str) - 1;
char temp;
while (i < j) {
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}
char * getnext(char *first){
int len_first = strlen(first);
int j=0;
int i,carry=1,value,sum;
char *res = (char *)malloc((len_first+1)*sizeof(char));
for(i=len_first-1;i>=0;i--){
sum = (int)((first[i]-'0')+carry);
if(sum >= 10){
carry = 1;
value = sum%10;
}
else{
carry = 0;
value = sum;
}
res[j++] = (char)(((int)'0')+value);
}
if(carry)
res[j++] = (char)(((int)'0')+carry);
res[j] = '\0';
reverse(res);
return res;
}
int main(void) {
char inp[MAX];
gets(inp);
int len = strlen(inp);
int i,next_len,curr_start,curr_len;
char *next_str,*curr_str;
int missing_count;
char *missing;
for(i=1;i<len/2+1;i++){
curr_start = 0;
curr_len = i;
missing_count=0;
while(curr_start+curr_len<len){
curr_str = (char *)malloc((curr_len)*sizeof(char));
strncpy(curr_str,inp+curr_start,curr_len);
curr_str[curr_len]='\0';
next_str = getnext(curr_str);
next_len = strlen(next_str);
char *temp = (char *)malloc(next_len*sizeof(char));
strncpy(temp,inp+curr_start+curr_len,next_len);
temp[next_len]='\0';
//printf("1CURR: %s Next: %s Next Shd: %s\n",curr_str,temp,next_str);
if(strcmp(next_str,temp) == 0){
curr_start +=curr_len;
curr_len = next_len;
}
else{
//printf("Mismatch\n");
missing_count++;
if(missing_count>1){
free(missing);
break;
}
missing = (char *)malloc(strlen(temp)*sizeof(char));
strcpy(missing,next_str);
missing[strlen(temp)]='\0';
next_str = getnext(next_str);
//printf("2CURR: %s Next: %s Next Shd: %s\n",curr_str,temp,next_str);
if(strcmp(next_str,temp) == 0){
curr_start +=curr_len;
curr_len = next_len;
}
else{
missing_count++;
free(curr_str);
free(next_str);
break;
}
}
}
if(missing_count == 1)
break;
}
//printf("------------------------\n");
puts(missing);
return 0;
}
//This wont Find missing if array contains a duplicate element .
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
public class traverse_num {
public static void main(String args[]){
List<Integer> arr=new ArrayList<Integer>();
int a[]={1,2,3,4,5,7,8,9};
int j=a[0];
for(int i=0;i<a.length;i++)
{
if(j==a[i])
{
j++;
continue;
}else
{
arr.add(j);
i--;
j++;
}
}
System.out.println("missing numbers are ");
for(int r:arr)
{
int temp=r;
System.out.println(temp);
}
}
}
Here in question it is mentioned that there is no prior information about the values of M and N. So there is no range specified.
O(N) Solution.
#include <iostream>
#include <string>
int find_number_length(std::string& s, size_t l=1) {
std::string n1 = s.substr(0, l);
std::string n2 = s.substr(l, l);
int a = std::stoi(n1);
int b = std::stoi(n2);
if((b - a) == 1)
return l;
return find_number_length(s, l+1);
}
int find_missing(std::string& s, size_t l) {
int a, b;
a = std::stoi(s.substr(0, l));
for(int i = 1; i < s.length() / l; ++i) {
b = std::stoi(s.substr(l * i, l));
if((b - a) > 1) {
// Found missing number
return a + 1;
}
a = b;
}
return 0;
}
int main() {
std::string s1{"960961962964"};
std::string s2{"12345789"};
std::cout << find_missing(s1, find_number_length(s1)) << std::endl;
std::cout << find_missing(s2, find_number_length(s2)) << std::endl;
return 0;
}
i have listed few test cases, can you check if they are working.
string str = "960961962964";
string str = "123457891011";
string str = "12345789";
string str = "123412351237";
string str = "123112321234";
string str = "293031323335";
string str = "99101";
string str = "99100101103104";
string str = "911";
911 is not a sequence... I didn't consider numbers changing size and I assume at least the first pair should be in a sequence.
Follow code is not working for some test case. specifically where digit size is changing from 9 to 10.
Two identified test cases which are not working are written.
I think with some changes they should work.
idea is:
try to figure out starting number, for that purpose 3 numbers are retrieved from string and checked for increasing order with difference of one.
Started with considering that digit size will be 1 and continue till digit size is (stringsize/2).
- SK January 30, 2014bool findMissing (string str, int dsize, int ssize) { int i = 0; int missing = 0; bool tripped = false; while (1) { if ((i+2*dsize) >= ssize) { break; } if (tripped == true) { tripped = false; dsize += 1; } string A = string(str,i,dsize); int a = atoi (A.c_str()); string B; string C; if ( ((a+1)%100) == 0) { tripped = true; B = string(str,i+dsize, dsize+1); C = string(str,i+(dsize+ dsize+1), dsize+1); } else { B = string(str,i+dsize, dsize); C = string(str,i+2*dsize, dsize); } int b = atoi (B.c_str()); int c = atoi (C.c_str()); cout << "a: " << a << ", b:" << b << ". c:" << c << endl; if (c == 0) { if ( ((a+2) == b) ) { missing = a+1; i += dsize; continue; } } if ( ((a+1) == b) && ((b+1) ==c) ) { i += dsize; continue; } else if ( ((a+1) == b) && ((b+1) !=c) && ((b+2) == c) ) { missing = b+1; i += dsize; continue; } else if ( ((a+1) != b) && ((a+2) ==b) && ((a+3) == c) ) { missing = a+1; i += dsize; continue; } else { missing = 0; break; } } if (missing != 0) { cout << "Missing is: " << missing << endl; return true; } return false; } int main () { //work //string str = "960961962964"; //doesnot work //string str = "123457891011"; //work //string str = "12345789"; //work //string str = "123412351237"; //work //string str = "123112321234"; //work //string str = "293031323335"; //work //string str = "99101"; //work //string str = "99100101103104"; //does not work string str = "911"; int len = str.length(); int i = 0; int ret = false; for (i = 1; i <= len/2; i++) { ret = findMissing (str, i, len); if (ret == true) { break; } } }