Flipkart Interview Question for SDE-2s

• 1
of 1 vote

Team: digital platform
Country: India
Interview Type: Phone Interview

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

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

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

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

a little mess-up is due to considering size changing of sequence at least start.
I have not tested if size changes in between, will it work. Although listed few test case where it is not working.

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

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")``````

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

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
(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]));
}
}``````

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

Give input as "12131215". Your program fails

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

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

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

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

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

Your code will not work in this case "911121314", for all other cases it will work.

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

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

}``````

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

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

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

``````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

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

package findMissingSequence;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(findMissingSeq("12345789"));
}

{
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{
missingStr="";
break;
}
}
if(missingStr != "")
{
return missingStr;
}
}
return null;
}

}

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

``````package findMissingSequence;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(findMissingSeq("12345789"));
}

{
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{
missingStr="";
break;
}
}
if(missingStr != "")
{
return missingStr;
}
}
return null;
}

}``````

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

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 {

j++;
i--;
}
}

System.out.println("Missing Numbers"+LT);

}

OutPut:-
Missing Numbers[1117, 1120, 1121, 1123]

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

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

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

//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
{
i--;
j++;
}
}
System.out.println("missing numbers are ");
for(int r:arr)
{
int temp=r;
System.out.println(temp);

}

}
}``````

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

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.

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

yeah i just tried for the input {1,2,3,4..} thats it

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

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

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

will you code work for 960962963964 ?
9991001100210031004?

Comment hidden because of low score. Click to expand.
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";

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

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.

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

911 is sequence in a sense
consider sequence, 9,10,11 and if 10 is missing from sequence then it is 911

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

The problem here is identifying the number. Once number is identified above formula will work. But how to identify M and M from given stream of numbers?

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.