Twitter Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

Add all the numbers in the array = r1.
calculate sum of n natural numbers using n*(n+1)/2 = r2
substract r1 from r2 you will get the result

- kishore25kumar December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
7
of 7 votes

you are right bro...your solution is true ..but what if i say integer sizes goes beyond limit..than it will not work..:)
solution for that will be ..=====

1.) XOR all no.s from 1 to n.let XOR be X
2) .XOR all array elements .let say XOR be Y
3) X xor Y is our answer

- rvndr December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One-liner in ruby:

def find_missing(arr, n)
	arr.reduce(:^) ^ (1..n).reduce(:^)
end

- Anonymous June 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Add All the number of given array
Let's say it's sum is K

Now we know , {1,2,3,4,5,......n} is an Arithmetic series with a = 1, d = 1

it's sum is K' = (n x (n+1) / 2)

Now the missing element can easily be obtained from subtracting K from K'
i.e. missing number/element = K' - K

- shravan40 December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The previous answers are definitely the way you would want to solve the problem, but when n is large, if you're not able to use a BigInt library you would need to do it another way.

You could sort the array, call it A, and then compute A[i+1]-A[i] until you find the value 2...in which case you're missing A[i]+1.

If you choose to count sort your list of numbers into array A, you simply find the index i for which A[i]=0.

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorting the array is O(log(n)) though

- rk January 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use Binary search

BinarySearch(int a[],int low,int high) 
{
mid=(low+high)/2
if(low <  high) return -1;
else if(a[mid-1]==(mid-1) && a[mid]==(mid+1)) return mid;
else if (a[low]==low)  BinarySearch(a,mid+1,high) 
else if (a[high]==high)  BinarySearch(a,low,mid+1)

}

- CHETAN KUMAR BV December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The array isn't sorted already I thought.

- Anonymous February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in O(n)

/*
You have n - 1 numbers from 1 to n. Your task is to find the missing number.

I.e. 
n = 5 
v = [4, 2, 5, 1] 
The result is 3.
*/

#include <iostream>
#include <vector>

int sum_of_sequential(std::vector<int>& vec) {
	auto begin = vec.begin();
	auto end = vec.end() - 1;
	
	int res = *end - *begin;
	res++;
	
	return ((res * (res + 1))/2);
}

int sum_of_elements(std::vector<int>&vec) {
	int sum = 0;

	for(int i : vec) 
		sum += i;
	return sum;
}

int main() {
	std::vector<int> vec{1, 2, 4, 5};
	int sum = sum_of_sequential(vec);
	int tot = sum_of_elements(vec);
	std::cout << sum - tot << std::endl;
}

- Felipe Cerqueira December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use the summation equation for a sorted array with values from 1-n to find the intended sum and subtract the actual sum from that value to find our answer.

var arr = [1, 2, 3, 5, 6, 7, 8, 9, 10]; //4 is the missing value

	function findMissing(arr){

		//Calculate the sum of the intended amount using the summation equation
		var max = arr.length + 1;
		var sum = (max * (max + 1))/2;

		//Calculate the sum of all actual elements
		var actualSum = 0;
		for(var i = 0 ; i < arr.length; i++){

			actualSum += arr[i];
		}

		//Return the difference of the two to find the missing element.
		return sum - actualSum;
	}

The above example works for an array with sorted values from 1-n, but what if we have an unsorted array with values from 10-n? We can use the summation equation again to normalize the values of the intended sum. Once we find that value, we simply subtract the actaul sum from that value and we have our missing element.

var unSortedArr = [11, 13, 14, 16, 10, 17, 19, 18, 20, 12]; //Min is 10 and max is 20
	function unsortedFindMissing(unSortedArr, max, min){ 

//Get the amount to subtract from the actual sum by normalizing (e.g from 10-20 to 1-10)
		
		//Use the sumation equation to find the amount to subtract
		var sum = ((max*(max+1))/ 2) - ((min*(min-1))/2);
		 
		//Calculate the sum of the actual elements
		var actualSum = 0;
		for(var i = 0; i < unSortedArr.length; i++){

			actualSum += unSortedArr[i]; 
		}

		return sum - actualSum;

	}

- post-punk December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindMissingNumber {

    private FindMissingNumber() {

    }

    // does not work for zero.
    public static int findMissingNumber(int[] inputArray) {
        int xor1 = 1;
        int xor2 = inputArray[0];
        int length = inputArray.length;
        for (int i = 2; i <= length + 1; i++) {
            xor1 = xor1 ^ i;
        }
        for (int i = 1; i < length; i++) {
            xor2 = xor2 ^ inputArray[i];
        }
        return xor1 ^ xor2;
    }

    // does not work for zero.
    public static int findMissingNumberUsingFormula(int[] inputArray) {
        int sum = 0;
        for (int i : inputArray) {
            sum = i + sum;
        }
        // actual size of array is length + 1 since one number is missing.
        int length = inputArray.length + 1;
        int factor = length * (length + 1) / 2;
        return  factor - sum;
    }
}

- techpanja December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution works for finding 1 or more than one missing number in the input array. Input doesn't have to be given sorted.

Running Time: O(n)
Space: Extra HashSet needed

public static void find_missing_number2(Integer[] v){
        if(v.length < 1) {
            System.out.println("No values provided in input integer");
            System.out.println();
            return;
        }
        System.out.println("The missing number(s) is/are: ");
        HashSet<Integer> hs = new HashSet<Integer>();
        for(int i : v)
            hs.add(i);
        int maxN = v[0];
        int minN = v[0];
        for(int i : v){
            if(i > maxN) maxN = i;
            if(i < minN) minN = i;
        }
        boolean missing = false;
        for(int j = minN; j <= maxN; j++){
            if(!(hs.contains(j))){
                missing = true;
                System.out.println(j);
            }
        }
        if(!missing) System.out.println("There are no missing numbers in the input array");
        System.out.println();
    }
    public static void main(String[] args){
        //some rudimentary testing
        Integer[] b = new Integer[0];
        Integer[] vv = new Integer[]{5, 3, 2, 1};
        Integer[] v = new Integer[]{2, 3, 5, 9};
        Integer[] c = new Integer[]{0, 3, 2, 1};
        find_missing_number2(b);
        find_missing_number2(vv);
        find_missing_number2(v);
        find_missing_number2(c);

    }

Output:
No values provided in input integer

The missing number(s) is/are:
4

The missing number(s) is/are:
4
6
7
8

The missing number(s) is/are:
There are no missing numbers in the input array

- AsteroidXVI December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why do you want to work with arrays? Not a good idea. You should represent numbers as link lists and write an operation sum two numbers and you're just fine even with large numbers.

- Mindy January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Method: plus 1 to n named SUM : n*(n-1)/2
SUM - sum of array -> result

2. Method: scan num-> arr[num]*=-1(num = n will do nothing)
scan second time -> find the positive num -> if have then the index is missing
-> if don't have , then n is missing

- huihancarl February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

make an array of bool with size of n, initialize all to false, mark boolArray[i] = true if you find the ith number in the original array. run through the bool one last time to figure which index has false. you will get your number. O(n) solution

- Choms February 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
        Karumanchi book: Searching, Problem 13-17 Find the missing number
        Given a list of n - 1 integers in the range of 1 to n. No duplicates in list.
        Ex. input: [1, 2, 4, 6, 3, 7, 8] output: 5
        Regular solution:
            1. Get the sum of numbers, sum = n * (n + 1) / 2
            2. Subtract all the numbers from sum and you will get the missing number
        O(n) time complexity
        XOR solution for when the numbers go beyond the max allowed integer range:
            1. XOR all the array elements, let the result of XOR be X
            2. XOR all numbers from 1 to n. Let XOR be Y.
            3. XOR of X and Y gives the missing number
        Time complexity O(n), space complexity O(1)
     */
    public static int findMissingNumber(int[] numbers, int number)
    {
        int X = 0, Y = 0;
        int i;
        for (i = 0; i < numbers.length; i++)
        {
            X ^= numbers[i];
        }
        for (i = 1; i <= number; i++)
        {
            Y ^= i;
        }
        return X ^ Y;

    }

- Anonymous February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

2 Implementations in Java, one with O(nlogn) and one with O(n)

import java.util.Arrays;

public class FindTheMissingNumber {

	public static void main(String[] args) {
		int[] a = { 4, 2, 5, 1 };
		System.out.print(new FindTheMissingNumber().find(a, 5));
		System.out.print(new FindTheMissingNumber().find(5, a));
	}

	// O(nlogn)
	public int find(int[] numbers, int size) {

		Arrays.sort(numbers);

		for (int i = 0; i < size - 1; i++) {
			if (numbers[i + 1] != numbers[i] + 1) {
				return numbers[i] + 1;
			}
		}

		return 0;
	}

	// O(n)
	public int find(int size, int[] numbers) {
		int number = (size + 1) * size / 2;
		for (int i = 0; i < size - 1; i++) {
			number -= numbers[i];
		}

		return number;
	}

}

- Karthik August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ public int findMissing(int n, int[] arr) { int sum = (n * (n - 1)) / 2; for (int i : arr) sum -= i; return sum; } }} - Paras December 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java O(n) time, O(1) space

public int findMissing(int n, int[] arr) {
    int sum = (n * (n - 1)) / 2;
    for (int i : arr)
        sum -= i;
    return sum;
}

- Anonymous December 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Assuming n is integer and there is only 1 missing number
# Python 3.4
def find_missing_num(n, v):
     v = sorted(v)
     for number in range(1, n+1):
         if number == v[number - 1]:
             continue
         else:
             return number

#test
print(find_missing_num(5, [4,2,5,1]))
print(find_missing_num(10, [4,2,5,3,9,6,8,1]))

- jaycee.chou March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

hi sir am sashikumar ......am providing the sample of code here......
my code divided into two block.block one for sorting and another for finding missing ele....
int missele(int a[],int n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
}
}
}
/* now am finding missing ele*/
for(i=0;i<n;i++)
{

if((a[i]+1)==a[i+1])
{
pf("")
}
else
pf("%d",a[i]+1);

- sashikumar December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for sorting you are using two for loops. Which in worst case takes the time complexity O(N^2).

- deepak643 February 10, 2014 | Flag


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