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; 
	}
	return -1; // not found or no missing number
}


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

- Chris August 26, 2016 | Flag Reply
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));
            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;
        }

- Anonymous August 27, 2016 | Flag Reply
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));
            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;
        }

- Ranjeeth August 27, 2016 | Flag Reply
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);
	}

}

- Ankit Garg (Sapient) August 27, 2016 | Flag Reply
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);
	}
}

- Ankit Garg (Sapient) August 27, 2016 | Flag Reply
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);
}
}

- Ankit Garg (Sapient) August 27, 2016 | Flag Reply
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);
	}
}

- Ankit Garg August 27, 2016 | Flag Reply
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);
	}

}

- Ankit Garg August 27, 2016 | Flag Reply
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)

- kevseb1993 August 28, 2016 | Flag Reply
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.

- Siiddhhuu August 28, 2016 | Flag Reply
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.

- Sidhu August 28, 2016 | Flag Reply
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"));

- vish193 August 30, 2016 | Flag Reply
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))

- Sugali Vijay August 31, 2016 | Flag Reply
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))

- Sugali Vijay August 31, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More