## xyz Interview Question

Country: India

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

``````/*
Given a string consisting only of digits, find the missing number.
For instance, given the string 596597598600601602
the missing number is 599. You may assume all the numbers are
positive integers and the sequence increases by one at each number
except the missing number. The numbers will have no more
than six digits and the string will have no more than
four hundred characters.

Your task is to write a function to find the missing number in the sequence.
If there should no missing number whatsoever, return a value of -1

/*
Solution:
consider sequences like 9|10|11|13 or 98|100|101|102

just try the starting number and then try for the next+1 and next+2,
if more than one next+2 were found stop, etc...

relatively straight forward, considering the special cases

runtime: at most 6*n (which is not possible): anyway it is O(N)
space: O(1)
*/

#include <string>
#include <iostream>

using namespace std;

// gets the integer at position i with length m, returns it or -1, if none
int GetValue(const string& str, int i, int m)
{
if (i + m > str.length()) return -1;
int value = 0;
for (int j = 0; j < m; j++)
{
int c = str[i + j] - '0';
if (c < 0 || c > 9) return -1;
value = value * 10 + c;
}
return value;
}

int FindMissingNumber(const string& str)
{
// note: it's easy to get rid of the logs but the code is just
// not understandable with all those counters
for (int m = 1; m <= 6; ++m)
{
int n = GetValue(str, 0, m);
if (n == -1) break;
int missingNo = -1;
bool fail = false;
for (int i = m; i != str.length(); i += 1 + log10l(n))
{
if ((missingNo == -1) &&
(GetValue(str, i, 1 + log10l(n + 2)) == n + 2))
{
missingNo = n + 1;
n+=2;
}
else if (GetValue(str, i, 1 + log10l(n + 1)) == n + 1)
{
n++;
}
else
{
fail = true;
break;
}
}
if (!fail) return missingNo;
}
}

int main()
{
cout << "596597598600601602: " << FindMissingNumber("596597598600601602") << endl;
cout << "89101113: " << FindMissingNumber("89101113") << endl;
cout << "11111211311411511: " << FindMissingNumber("11111211311411511") << endl;
cout << "909192939495969798100101: " << FindMissingNumber("909192939495969798100101") << endl;
cout << "9899101102: " << FindMissingNumber("9899101102") << endl;
}``````

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

``````static void Main(string[] args)
{
var result = Pattern("596597598600601602");
Console.WriteLine(Analyze("596597598600601602",result));
}

static int Pattern(string sequence)
{
for(int i=0; i < 6; i++)
{
int firstDigit = int.Parse(sequence.Substring(0, i + 1));
int secondDigit = int.Parse(sequence.Substring((i+1)*1,i+1));
int thirdDigit = int.Parse(sequence.Substring((i+1)*2,i+1));

if (firstDigit + 1 == secondDigit || secondDigit + 1 == thirdDigit)
return i + 1;
}

return 0;

}

static int Analyze(string sequence,int len)
{
int current = 0, prev=0;
for(int i =0; i < sequence.Length ; i=i+len)
{
current = int.Parse(sequence.Substring(i,len));
if(prev != 0)
if (prev + 1 != current)
return prev + 1;

prev = current;
}

return -1;
}``````

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

``````static void Main(string[] args)
{
var result = Pattern("596597598600601602");
Console.WriteLine(Analyze("596597598600601602",result));
}

static int Pattern(string sequence)
{
for(int i=0; i < 6; i++)
{
int firstDigit = int.Parse(sequence.Substring(0, i + 1));
int secondDigit = int.Parse(sequence.Substring((i+1)*1,i+1));
int thirdDigit = int.Parse(sequence.Substring((i+1)*2,i+1));

if (firstDigit + 1 == secondDigit || secondDigit + 1 == thirdDigit)
return i + 1;
}

return 0;

}

static int Analyze(string sequence,int len)
{
int current = 0, prev=0;
for(int i =0; i < sequence.Length ; i=i+len)
{
current = int.Parse(sequence.Substring(i,len));
if(prev != 0)
if (prev + 1 != current)
return prev + 1;

prev = current;
}

return -1;
}``````

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

``````public class FindMissingNumber {

public static int digit = 1;
public static int count = 0;

public static void main(String[] args) {

//		 String number = "1213141516171819202122242526272829303132";
//		 String number = "7891011121314151617181920222324";
//		 String number = "91011910129101391014910159101791018";
//		 String number = "234235237238239";
//		 String number = "234235234237234238";
String number = "123456123457123459123460";
//		String number = "1234123612371238";
Integer firstNo = getFirstNo(number);
System.out.println("First No : " + firstNo);
// Approch O(n)
Integer missingNo = findMissingNo(firstNo, number);
System.out.println("Missing No : " + missingNo);
}

private static Integer findMissingNo(Integer firstNo, String number) {
Integer tempNoOne = firstNo;
Integer tempNoTwo;
digit=String.valueOf(firstNo).length();
count=digit;
while(count<number.length()){
tempNoTwo=getNo(number, tempNoOne);
if((tempNoTwo-tempNoOne)==2){
return ++tempNoOne;
}else{
tempNoOne=tempNoTwo;
}
}
return -1;
}

private static Integer getFirstNo(String no) {
int testPassed = 0;
int firstNo = getNo(no, 0);
int curNo = firstNo;
int nexNo = getNo(no, curNo);
while (true) {
int diff = nexNo - curNo;
if (diff == 1 || diff == 2) {
curNo = nexNo;
testPassed++;
if ((digit == 1 && testPassed == 6)
|| (digit == 2 && testPassed == 4)
|| ((digit == 3 || digit == 4 || digit == 5 || digit == 6) && testPassed == 2))
return firstNo;
nexNo = getNo(no, curNo);
} else {
count = 0;
testPassed = 0;
digit++;
curNo = getNo(no, 0);
firstNo = curNo;
nexNo = getNo(no, curNo);

}
}
}

private static int getNo(String no, int curNo) {
String number = "";
if (curNo != 0
&& String.valueOf((curNo + 1)).length() > String.valueOf(curNo)
.length())
++digit;
for (int i = 0; i < digit; i++)
number = number + no.charAt(count++);
return Integer.valueOf(number);
}``````

}

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

``````public class FindMissingNumber {

public static int digit = 1;
public static int count = 0;

public static void main(String[] args) {

//		 String number = "1213141516171819202122242526272829303132";
//		 String number = "7891011121314151617181920222324";
//		 String number = "91011910129101391014910159101791018";
//		 String number = "234235237238239";
//		 String number = "234235234237234238";
String number = "123456123457123459123460";
//		String number = "1234123612371238";
Integer firstNo = getFirstNo(number);
System.out.println("First No : " + firstNo);
// Approch O(n)
Integer missingNo = findMissingNo(firstNo, number);
System.out.println("Missing No : " + missingNo);
}

private static Integer findMissingNo(Integer firstNo, String number) {
Integer tempNoOne = firstNo;
Integer tempNoTwo;
digit=String.valueOf(firstNo).length();
count=digit;
while(count<number.length()){
tempNoTwo=getNo(number, tempNoOne);
if((tempNoTwo-tempNoOne)==2){
return ++tempNoOne;
}else{
tempNoOne=tempNoTwo;
}
}
return -1;
}

private static Integer getFirstNo(String no) {
int testPassed = 0;
int firstNo = getNo(no, 0);
int curNo = firstNo;
int nexNo = getNo(no, curNo);
while (true) {
int diff = nexNo - curNo;
if (diff == 1 || diff == 2) {
curNo = nexNo;
testPassed++;
if ((digit == 1 && testPassed == 6)
|| (digit == 2 && testPassed == 4)
|| ((digit == 3 || digit == 4 || digit == 5 || digit == 6) && testPassed == 2))
return firstNo;
nexNo = getNo(no, curNo);
} else {
count = 0;
testPassed = 0;
digit++;
curNo = getNo(no, 0);
firstNo = curNo;
nexNo = getNo(no, curNo);

}
}
}

private static int getNo(String no, int curNo) {
String number = "";
if (curNo != 0
&& String.valueOf((curNo + 1)).length() > String.valueOf(curNo)
.length())
++digit;
for (int i = 0; i < digit; i++)
number = number + no.charAt(count++);
return Integer.valueOf(number);
}
}``````

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

public class FindMissingNumber {

public static int digit = 1;
public static int count = 0;

public static void main(String[] args) {

// String number = "1213141516171819202122242526272829303132";
// String number = "7891011121314151617181920222324";
// String number = "91011910129101391014910159101791018";
// String number = "234235237238239";
// String number = "234235234237234238";
String number = "123456123457123459123460";
// String number = "1234123612371238";
Integer firstNo = getFirstNo(number);
System.out.println("First No : " + firstNo);
// Approch O(n)
Integer missingNo = findMissingNo(firstNo, number);
System.out.println("Missing No : " + missingNo);
}

private static Integer findMissingNo(Integer firstNo, String number) {
Integer tempNoOne = firstNo;
Integer tempNoTwo;
digit=String.valueOf(firstNo).length();
count=digit;
while(count<number.length()){
tempNoTwo=getNo(number, tempNoOne);
if((tempNoTwo-tempNoOne)==2){
return ++tempNoOne;
}else{
tempNoOne=tempNoTwo;
}
}
return -1;
}

private static Integer getFirstNo(String no) {
int testPassed = 0;
int firstNo = getNo(no, 0);
int curNo = firstNo;
int nexNo = getNo(no, curNo);
while (true) {
int diff = nexNo - curNo;
if (diff == 1 || diff == 2) {
curNo = nexNo;
testPassed++;
if ((digit == 1 && testPassed == 6)
|| (digit == 2 && testPassed == 4)
|| ((digit == 3 || digit == 4 || digit == 5 || digit == 6) && testPassed == 2))
return firstNo;
nexNo = getNo(no, curNo);
} else {
count = 0;
testPassed = 0;
digit++;
curNo = getNo(no, 0);
firstNo = curNo;
nexNo = getNo(no, curNo);

}
}
}

private static int getNo(String no, int curNo) {
String number = "";
if (curNo != 0
&& String.valueOf((curNo + 1)).length() > String.valueOf(curNo)
.length())
++digit;
for (int i = 0; i < digit; i++)
number = number + no.charAt(count++);
return Integer.valueOf(number);
}
}

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

``````public class FindMissingNumber {

public static int digit = 1;
public static int count = 0;

public static void main(String[] args) {

//		 String number = "1213141516171819202122242526272829303132";
//		 String number = "7891011121314151617181920222324";
//		 String number = "91011910129101391014910159101791018";
//		 String number = "234235237238239";
//		 String number = "234235234237234238";
String number = "123456123457123459123460";
//		String number = "1234123612371238";
Integer firstNo = getFirstNo(number);
System.out.println("First No : " + firstNo);
// Approch O(n)
Integer missingNo = findMissingNo(firstNo, number);
System.out.println("Missing No : " + missingNo);
}

private static Integer findMissingNo(Integer firstNo, String number) {
Integer tempNoOne = firstNo;
Integer tempNoTwo;
digit=String.valueOf(firstNo).length();
count=digit;
while(count<number.length()){
tempNoTwo=getNo(number, tempNoOne);
if((tempNoTwo-tempNoOne)==2){
return ++tempNoOne;
}else{
tempNoOne=tempNoTwo;
}
}
return -1;
}

private static Integer getFirstNo(String no) {
int testPassed = 0;
int firstNo = getNo(no, 0);
int curNo = firstNo;
int nexNo = getNo(no, curNo);
while (true) {
int diff = nexNo - curNo;
if (diff == 1 || diff == 2) {
curNo = nexNo;
testPassed++;
if ((digit == 1 && testPassed == 6)
|| (digit == 2 && testPassed == 4)
|| ((digit == 3 || digit == 4 || digit == 5 || digit == 6) && testPassed == 2))
return firstNo;
nexNo = getNo(no, curNo);
} else {
count = 0;
testPassed = 0;
digit++;
curNo = getNo(no, 0);
firstNo = curNo;
nexNo = getNo(no, curNo);

}
}
}

private static int getNo(String no, int curNo) {
String number = "";
if (curNo != 0
&& String.valueOf((curNo + 1)).length() > String.valueOf(curNo)
.length())
++digit;
for (int i = 0; i < digit; i++)
number = number + no.charAt(count++);
return Integer.valueOf(number);
}
}``````

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

``````public class FindMissingNumber {

public static int digit = 1;
public static int count = 0;

public static void main(String[] args) {

//		 String number = "1213141516171819202122242526272829303132";
//		 String number = "7891011121314151617181920222324";
//		 String number = "91011910129101391014910159101791018";
//		 String number = "234235237238239";
//		 String number = "234235234237234238";
String number = "123456123457123459123460";
//		String number = "1234123612371238";
Integer firstNo = getFirstNo(number);
System.out.println("First No : " + firstNo);
// Approch O(n)
Integer missingNo = findMissingNo(firstNo, number);
System.out.println("Missing No : " + missingNo);
}

private static Integer findMissingNo(Integer firstNo, String number) {
Integer tempNoOne = firstNo;
Integer tempNoTwo;
digit=String.valueOf(firstNo).length();
count=digit;
while(count<number.length()){
tempNoTwo=getNo(number, tempNoOne);
if((tempNoTwo-tempNoOne)==2){
return ++tempNoOne;
}else{
tempNoOne=tempNoTwo;
}
}
return -1;
}

private static Integer getFirstNo(String no) {
int testPassed = 0;
int firstNo = getNo(no, 0);
int curNo = firstNo;
int nexNo = getNo(no, curNo);
while (true) {
int diff = nexNo - curNo;
if (diff == 1 || diff == 2) {
curNo = nexNo;
testPassed++;
if ((digit == 1 && testPassed == 6)
|| (digit == 2 && testPassed == 4)
|| ((digit == 3 || digit == 4 || digit == 5 || digit == 6) && testPassed == 2))
return firstNo;
nexNo = getNo(no, curNo);
} else {
count = 0;
testPassed = 0;
digit++;
curNo = getNo(no, 0);
firstNo = curNo;
nexNo = getNo(no, curNo);

}
}
}

private static int getNo(String no, int curNo) {
String number = "";
if (curNo != 0
&& String.valueOf((curNo + 1)).length() > String.valueOf(curNo)
.length())
++digit;
for (int i = 0; i < digit; i++)
number = number + no.charAt(count++);
return Integer.valueOf(number);
}``````

}

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

``````ector<int> get(string s,int digit)
{
vector<int> v;
int i=0;
while(i<s.size())
{
int x = atoi(s.substr(i,digit).c_str());
v.push_back(x);

i+=digit;
if(x+1/pow(10,digit)>0){digit++;}
}
return v;
}

int check(vector<int> v)
{
int cnt = 0;
for(int i=1;i<v.size();i++){if(v[i]!=v[i-1]+1){cnt++;}}
if(cnt!=1){return -1;}
int x = 0;
for(int i=1;i<v.size();i++){if(v[i]!=v[i-1]+1){return v[i-1]+1;}}
return -1;

}

int main()
{
string s;
cin>>s;
int i;
for(i=1;i<=6;i++)
{
int x = check(get(s,i));
if(x!=-1){cout<<x<<"\n";break;}
}
return 0;
}``````

Time complexity : O(n)
Space complexity : O(n)

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

Python implementation

``````def missing(r): # R is a string of numbers
if not r:
return -1
check_missing, inc, start, missing = True, 1, 0, -1
seq = inc
while (check_missing):
x, y, z = int( r[start:start+inc] or 0), int( r[start+inc:start+2*inc] or 0 ), int( r[start+2*inc:start+3*inc] or 0 )

if (((x+1) == y and (y+1)== z) or ((x+2) == y and (y+1)==z) or ((x+1) == y and (y+2)==z) or ((x+2) == y) ):
seq, check_missing = inc, False
else:
inc = inc + 1
if check_missing and ((start+3*inc) > len(r)):
raise ValueError("No sequence")

find_missing, f = True, 0
while(find_missing):
if (int(r[f:f+seq])+2==int(r[f+seq:(f+2*seq)])):
missing, find_missing = int(r[f:f+seq])+1, False
else:
f = f+seq
if ((f+seq) >= len(r)):
find_missing = False
return missing``````

I tried a few test cases as well.

``````class MyTests(unittest.TestCase):
def get_val(self, myseq):
return mycode.test.missing(myseq)

def test_missing_no_missing(self):
self.assertEqual(self.get_val("121314151617181920212223242526272829303132"), -1, "Values don't match.")

def test_missing_start(self):
self.assertEqual(self.get_val("57"), 6, "Values don't match.")

def test_missing_last(self):
self.assertEqual(self.get_val("55565759"), 58, "Values don't match.")

def test_missing_triple(self):
self.assertEqual(self.get_val("596597598600601602"), 599, "Values don't match.")

def test_missing_single(self):
self.assertEqual(self.get_val("568910"), 7, "Values don't match.")``````

Reviews appreciated.

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

Python implementation

``````def missing(r): # R is a string of numbers
if not r:
return -1
check_missing, inc, start, missing = True, 1, 0, -1
seq = inc
while (check_missing):
x, y, z = int( r[start:start+inc] or 0), int( r[start+inc:start+2*inc] or 0 ), int( r[start+2*inc:start+3*inc] or 0 )

if (((x+1) == y and (y+1)== z) or ((x+2) == y and (y+1)==z) or ((x+1) == y and (y+2)==z) or ((x+2) == y) ):
seq, check_missing = inc, False
else:
inc = inc + 1
if check_missing and ((start+3*inc) > len(r)):
raise ValueError("No sequence")

find_missing, f = True, 0
while(find_missing):
if (int(r[f:f+seq])+2==int(r[f+seq:(f+2*seq)])):
missing, find_missing = int(r[f:f+seq])+1, False
else:
f = f+seq
if ((f+seq) >= len(r)):
find_missing = False
return missing``````

I tried a few test cases as well.

``````class MyTests(unittest.TestCase):
def get_val(self, myseq):
return mycode.test.missing(myseq)

def test_missing_no_missing(self):
self.assertEqual(self.get_val("121314151617181920212223242526272829303132"), -1, "Values don't match.")

def test_missing_start(self):
self.assertEqual(self.get_val("57"), 6, "Values don't match.")

def test_missing_last(self):
self.assertEqual(self.get_val("55565759"), 58, "Values don't match.")

def test_missing_triple(self):
self.assertEqual(self.get_val("596597598600601602"), 599, "Values don't match.")

def test_missing_single(self):
self.assertEqual(self.get_val("568910"), 7, "Values don't match.")``````

Reviews appreciated.

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

Javascript solution

``````var MN = MN || {};
MN.findMissing = function(str) {
if(str.length === 0) {
console.log("Valid number string not provided");
return;
}

var numLength = 1;
var maxNumLength = false;
// Find the first number. Max can be six digits
if (str.length >= 12) {
var num1 = Number(str.substring(0,6));
//console.log(num1);
var num2 = Number(str.substring(6,12));
//console.log(num2);
if((num2-num1) === 1) {
numLength = 6;
maxNumLength = true;
}
}

if(!maxNumLength){
var testLength = 10
while(testLength > 1) {
var num1 = Number(str.substring(0,Math.floor(testLength/2)));
var num2 = Number(str.substring(Math.floor(testLength/2), testLength));
if(num2 - num1 === 1) {
numLength = Math.floor(testLength/2);
break;
}
testLength--;
}
}

var l  = str.length;
var start = 0;
var end = numLength;
while(end != (l)){
var val1 = Number(str.substring(start, end));
var val2 = Number(str.substring(end, (end+numLength)));
if(val2 - val1 !== 1) {
return (val1+1);
}
start = end;
end = end + numLength;
}

return -1;
};

console.log(MN.findMissing("567568569570571572573"));
console.log(MN.findMissing("1234123512361238"));``````

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

a = raw_input("Enter a missed number series:\t")
b=[]
j=0
for i in range(2,len(a),2):
b.append(a[j:i])
j=i
c=[]
j=0
for i in range(3,len(a),3):
c.append(a[j:i])
j=i
z = [a,b,c]
for k in z:
a = [(int(k[i+1])-int(k[i])) for i in range(len(k)-1)]
vijaychari = []
for m in a:
if int(m)<0:
vijaychari.append(int(m))
if len(vijaychari)==0:
for i in range(len(k)-1):
if (int(k[i+1])-int(k[i]))==2:
print ("The missing letter is: \t%d"%(int(k[i])+1))

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

``````a = raw_input("Enter a missed number series:\t")
b=[]
j=0
for i in range(2,len(a),2):
b.append(a[j:i])
j=i
c=[]
j=0
for i in range(3,len(a),3):
c.append(a[j:i])
j=i
z = [a,b,c]
for k in z:
a = [(int(k[i+1])-int(k[i])) for i in range(len(k)-1)]
vijaychari = []
for m in a:
if int(m)<0:
vijaychari.append(int(m))
if len(vijaychari)==0:
for i in range(len(k)-1):
if (int(k[i+1])-int(k[i]))==2:
print ("The missing letter is: \t%d"%(int(k[i])+1))``````

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.