xyz Interview Question
Country: India
static void Main(string[] args)
{
var result = Pattern("596597598600601602");
Console.WriteLine(Analyze("596597598600601602",result));
Console.ReadLine();
}
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;
}
static void Main(string[] args)
{
var result = Pattern("596597598600601602");
Console.WriteLine(Analyze("596597598600601602",result));
Console.ReadLine();
}
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;
}
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);
}
}
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);
}
}
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);
}
}
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);
}
}
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);
}
}
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)
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.
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.
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"));
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))
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))
- Chris August 26, 2016