Facebook Interview Question for SDE1s


Country: United States




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

We divide the array into 2 equals parts and foreach subarray - we check if the number of elements that are actually in there (meaning the highest value minus the lowest value) matches the number of element of that sub array. If so (meaning the difference is zero) the function weill return from this subarray and do nothing. otherwise, we check if we got array that is actually a pair arr[i],arr[i+1] that has a difference bigger than 1. if so we add all the numbers from arr[i] to arr[i+1].
the complexity is m*log(n). I'm assuming that m is a constant value because if he isn't (say m==n/2) that it will take n/2 times to insert m elements into the set (and O(n/2)>O(log(n))) - so I don't see how to implement it without the assumption m is not a const.

public static Set<Integer> findMissingNumbers(int arr[], int m) {

		Set<Integer> set = new HashSet<Integer>();
		findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length - 1, m);
		return set;
	}

	public static void findMissingNumbersBetweenToIndexes(int[] arr,
			Set<Integer> set, int start, int finish, int m) {
		if (m == 0) {
			return;
		}
		if (start + 1 == finish) {
			for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
				m--;
			}
			return;
		}
		int middle = (start + finish) / 2;
		// right
		findMissingNumbersBetweenToIndexes(arr, set, start, middle,
				(arr[middle] - arr[start] + 1) - (middle - start));

		// left
		findMissingNumbersBetweenToIndexes(arr, set, middle, finish,
				(arr[finish] - arr[middle] + 1) - (finish - middle));
	}

- Matoy December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I liked your idea to check whether there are missing numbers in each half (by subtracting one end from another and comparing to the number of elements). Clever and simple.

- Victor December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also thought about this approach, but have problem. You have a pair. How can you be certain to get to the other pair? For instance:

1 3 5 7

Let's say you visit pair 1 3 and detect 2. How can you be certain you will also visit 3 5 and detect 4. Once you split, you cannot get element from the other half.

Also, you are missing the situation of missing at the beginning and the end. for instance, starting with 5. need to detect 1, 2, 3, 4. And also, ending with N-5. You need to detect N-4 and etc.

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, I see you are having middle in both sides, not bad. But what about edges?

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I thought you start with 1, and end with n - but if not, you can easily add 1 to the first position in the array and n the the last place of the array and gives m=m-2
shouldn't add time to the complexity :)

- Matoy December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well maybe adding to the array is not the right term :)
just make two while loops for the start and for the finish (in case we don't start with 1 or end with n)

- Matoy December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But very clever to include middle in both half so we can look at every pair of interest, I thought about pair solution but could not come up with this trick. And if no missing, discard the entire chunk so deepening only where missing. You could have also not pass m but detect that nothing is missing instead of m==0, would make it even simpler :)

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is good lesson for me because I got stock thinking edges have to be handled on every recursion. If you just take care of them once, the whole problem becomes easier. I had another solution that was not working because of that, where I could place missing into array instead of Set. It also was passing missing as param, only missing from-to indexes, so you could know exactly where to place each missing item. May be will post it later.

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I will up-vote if you handle edges. Because this way it will be a lesson to everyone that sometimes edges should be handled once instead of recursively.

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can't edit but I reposted the code with the correct modification.

- Patrick December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What happens if the input array is {5} ?

- zortlord December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

right... so lets make it:

public static void findMissingNumbersBetweenToIndexes(int[] arr,
			Set<Integer> set, int start, int finish) {
		if (arr.length == 1) {
			return;
		}
		if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
			return;
		}
		if (start + 1 == finish) {
			for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
			}
			return;
		}
		int middle = (start + finish) / 2;
		// right
		findMissingNumbersBetweenToIndexes(arr, set, start, middle);

		// left
		findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
	}

- Patrick December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think that's the mistake. The mistake is here:

if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {

You should not have + 1 there

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not think this catches the situation where 1 is missing, but the question says 1...n so I guess it is ok. otherwise you would need an specific case for when one is not there.

- alonsomh December 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

void findMissingSortedArrNoRepetitions(int arr[], int start, int end, List<Integer> missing) {
		if(start < end) {
			if(arr[end] - arr[start] == end - start) {
				return ;
			} else { 
				if(end - start == 1) {
					int temp = arr[start] + 1;
					while(temp != arr[end]) {
						missing.add(temp);
						temp = temp+1;
					}
				} else {
					findMissingSortedArrNoRepetitions(arr, start, (start+end)/2, missing);
					findMissingSortedArrNoRepetitions(arr, (start+end)/2, end, missing);
				}
			}
		}
	}

- Rohan February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In Java:

public static Set<Integer> findMissingNumbers(int arr[], int m) {
	
		Set<Integer> set = new HashSet<Integer>();
		// dealing with array that does not start with 1
		for (int i = 1; i < arr[0]; i++) {
			set.add(i);
		}
		// dealing with the middle elements
		findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length - 1);
		// recalculate m for any extra tail's numbers
		m = m - (((arr[arr.length - 1] - arr[0] + 1) - arr.length))
				- (arr[0] - 1);
		// dealing with the any extra tail's numbers
		for (int i = 1; i <= m; i++) {
			set.add(arr[arr.length - 1] + i);
		}

		return set;
	}

	public static void findMissingNumbersBetweenToIndexes(int[] arr,
			Set<Integer> set, int start, int finish) {
		if (arr.length == 1) {
			return;
		}
		if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
			return;
		}
		if (start + 1 == finish) {
			for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
			}
			return;
		}
		int middle = (start + finish) / 2;
		// right
		findMissingNumbersBetweenToIndexes(arr, set, start, middle);

		// left
		findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
	}

- Patrick December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although, I would just do this for the last loop:

for (int i =  arr[arr.length - 1] + 1; i < arr.length + m; i ++) {
  set.add(i);
}

Without calculating how much is still missing

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I know, just added it to try to make it more readable to others...

- Patrick December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for now let us assume that the code

for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
			}

in the function "findMissingNumbersBetweenToIndexes" is O(1) (i.e m << n). Then the complexity of your function would be
T(n) = 2T(n/2) + O(1)
upon calculating, you'll get T(n) = O(n)
For O(logn), you should have T(n) = T(n/2) + O(1)
Correct me if I am wrong.

- Harsha December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lets take the worths case where there are m elements and each one of the m number is seprated between two numbers
i.e (1,3,5,7) and not (1,6).
then we will do binary search (O(log(n)) for each missing number (m) which will give us: m*log(n) which in case m is constat will give O(log(n))

- Patrick December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

public static List<int> FindMissing(int[] arr, int left, int right)
        {
            List<int> result = new List<int>();
            if ((right - left) == 1)
            {
                if (Math.Abs(arr[right] - arr[left]) > 1)
                {

                    int step =  Math.Sign(arr[right] - arr[left]);//left>right returns -1  left<right returns 1 
                    int missingNum = arr[left] + step;
                    do
                    {                       
                        result.Add(missingNum);
                        
                    }
                    while ((missingNum+=step) != arr[right]);
                }

                return result;
            }

            int middle = (left + right) / 2;
            result.AddRange(FindMissing(arr, left, middle));
            result.AddRange(FindMissing(arr, middle, right));
            return result;
        }

- yair.cohen1 December 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cleanest so far

- CT December 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although, just please handle not starting from 1 and not ending with N

- CT December 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(log). You are blindly dividing an array until you get to the difference one ... thus checking every possible i,j (where i-j =1) ... Asymptotically it is O(n)

I think interviewer is looking for O(m*log n) answer i.e. for every missing number it should be log(n) operations.

- Sandesh December 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Code in c:

#define SIZE(x) sizeof(x)/sizeof(x[0])
int result[100] = {0};
int result_size;

void find_missing(int a[], int start, int end)
{
        if (start >= end)
                return;
        if (end-start == 1) {
                if ((a[end] - a[start]) > 1) {
                        int step = a[end] - a[start];
                        int missingNum = a[start] + 1;
                        result[result_size++] = missingNum;
                }
                return;
        }
        int mid = (start + end)/2;
        find_missing(a, start, mid);
        find_missing(a, mid, end);
}

int main()
{
        int a[] = {1, 2, 3, 4, 5, 6, 8};
        find_missing(a, 0, SIZE(a)-1);
        while(result_size)
                printf("%d\n", result[--result_size]);
        return 0;
}

- aka January 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Python 3

def answer(n, m, arr):
    return set(range(1, n + 1)).difference(set(arr))

# or... 

def answer(n, m, arr):
    if m == 0:
        return {}
    current, cnt = 1, 0
    s = set()
    for x in arr:
        if not current == x:
            s.add(current)
            if cnt == m:
                return s
            current = x
            cnt += 1
        current += 1
    return s

print(answer(8, 2, [1, 2, 4, 5, 6, 8]))  # {3, 7}
print(answer(2, 0, [1, 2]))              # {}

- A. December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is O(nlogn) and isn't correct if there are consecutive missing number. For instance:

[1, 3, 5, 6, 8, 9]

- Victor December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Solution

public static void bsearch( int[] num, int start, int end)
    {
        int mid  = (start+end)/2;
        if(start == end )
            return;
        if( (mid+1) < num.length && num[mid]+1 < num[mid+1])
        {
            System.out.println(num[mid]+1);
        }
        else if( (mid) > 0 && num[mid-1]+1 < num[mid])
        {
            System.out.println(num[mid]-1);
        }
        else if(num[mid] == mid+1)
        {
            // right
            bsearch(num, mid+1, end);
        }
        else
        {
            //left
            bsearch(num, start, mid-1);
        }
    }

- Stuart December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution only recurses into one half of the array. There may be missing numbers in both halves at the same time, though.

- Victor December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I ran this and this will find only one missing number

- ibit December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is m log (n-m) solution. Provided that m is within constant (find very few missing numbers out of very many), this would be close to log n solution.

The idea is divide and conquer. Think about missing numbers as making indexes of array delay from value. If delay is the same within entire partition, there are no missing here and we are not computing this region. We are deepening only in partitions where there is missing, and for one missing this would be log (n-m).

static Set<Integer> findMissing(int[] input, int N) {
	Set<Integer> result = new HashSet<Integer>(N-input.length);
	findMissing(input,result,0,input.length-1, 0, N+1);
	return result;
}
	
static void findMissing(
		int[] input, Set<Integer> result,
		int start, int end,
		int valBefore, int valAfter) {
		
	int delayAtBegin = input[start] - start;
	int delayAtEnd = input[end] - end;
		
	if ( delayAtBegin == delayAtEnd ) {
		for (int i = valBefore+1; i < input[start]; i ++) result.add(i);
		for (int i = input[end]+1; i < valAfter; i ++) result.add(i);
		return;
	}
		
	int endM = (start+end)/2;
	int startM = endM+1;
		
	findMissing(input,result,start,endM,valBefore,input[startM]);
	findMissing(input,result,startM,end,input[endM],valAfter);
}

Test with:

System.out.println(findMissing(new int[]{1,2,4,5,6,8},8));

- CT December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can't achieve O(log n) anyway, since constructing a result of size m must take at least O(m) anyway.

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

Try this out...

function returnMissingDetails(int []a, start, end)
{
	int temp = a[0] ;
	for(int i=0; i<(start - end) ; i++)
	{	
		if (a[i] != temp)
		{
			CWL("Missing number is {0}", (temp)) ; 
			i--; 
		}
		temp  ++;
	}
}

- Jai December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works, but it's not O(logn)

- Victor December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Another Java solution. Function takes the # of missing elements as the parameter
	private static	void findMissingElements(int [] array, int lo, int hi,int missingElements,List<Integer> missingList) {
		//boundary condition
		if(missingList.size() == missingElements) return;
		if(lo>=hi) return;
		int mid = lo +(hi-lo)/2;
		//search for neighborhood of lo,hi and mid and see if there are missing elements
		if(array[lo+1] - array[lo]!=1) {
			missingList.add(array[lo]+1);
			if(missingList.size() == missingElements) return;
		}
		if(array[mid+1] - array[mid]!=1) {
			missingList.add(array[mid]+1);
			if(missingList.size() == missingElements) return;
		}
		if(array[mid] - array[mid-1]!=1) {
			missingList.add(array[mid-1]+1);
			if(missingList.size() == missingElements) return;
		}
		if(array[hi] - array[hi-1]!=1) {
			missingList.add(array[hi-1]+1);
			if(missingList.size() == missingElements) return;
		}
		//search both in halves
		findMissingElements(array,lo,mid,missingElements,missingList);
		findMissingElements(array,mid+1,hi,missingElements,missingList);
	
	}
	public static void main(String[] args) {
		//arr = [1,2,4,5,6,8] 
		int [] array = new int [] {1,2,4,5,6,8};
		List<Integer> missingList = new ArrayList<Integer>();
		findMissingElements(array, 0,array.length-1, 2, missingList);
		System.out.println(missingList);
	}

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

def driver(arr, n, m):
    if len(arr) == 0:
        return set(range(1, n + 1))
    s = set()
    for i in range(1, arr[0]):
        s.add(i)
    bst(arr, 0, n - m - 1, 0, s)
    for i in range(arr[n - m - 1] + 1, n + 1):
        s.add(i)
    return s

def bst(arr, left, right, miss, s):
    if right - left <= 1:
        for i in range(arr[left] + 1, arr[right]):
            s.add(i)
        return
    mid = (left + right) / 2
    diff = arr[mid] - mid - 1
    if diff > miss:
        bst(arr, left, mid, miss, s)
        miss = diff
    bst(arr, mid, right, miss, s)

n = 8
arr = [1, 2, 4, 5, 6, 8]
m = n - len(arr)
s = driver(arr, n, m)
print s #set([3, 7])

Driver prints out the numbers between 1 and the smallest number in list, process the list, and prints out the numbers between the largest number in list and n.
In function bst, variable "miss" stands for number of founded missing numbers on the left of arr[mid], variable "diff" means the number of missing numbers on the left of arr[mid].
Therefore, if diff > miss, it means there are some missing numbers we didn't found on the left of arr[mid], thus we need to search the left part of the list. Otherwise, we can proceed to the right part.

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

Solution in C++. It's O(logn) by performing binary search. It always controls how many missing numbers there are in each half in order to avoid unnecessary searches.

void missingNumbers(const IntVector &V, int s, int e, int m, int offset, IntVector *missing)
{
	if (m == 0) return;
	if (s > e) return;

	int mid_idx = (s+e)/2;
	int mid_element = V[mid_idx];

	int new_offset = mid_element - (mid_idx+1);
	int delta_offset = new_offset - offset;

	int new_m = m;
	int delta_m = 0;
	int delta_deltas = delta_offset - delta_m;

	if (delta_offset > 0) {
		int j = (mid_idx > 0) ? V[mid_idx-1]+1 : 1;

		for (; j < mid_element; ++j) {
			missing->push_back(j);
			--new_m;
		}

		delta_m = m - new_m;
		delta_deltas = delta_offset - delta_m;

		if (delta_deltas > 0) {
			missingNumbers(V, s, mid_idx-1, delta_deltas, offset, missing);
		}
	}

	missingNumbers(V, mid_idx+1, e, new_m - delta_deltas, new_offset, missing);
}

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

public class MissN{
    static int l=0;
    public static void main(String [] args){
	    int [] arr={1,2,4,5,6,8};
		int n=8;
		int m=2;
		findM(arr,0,5);
	}
	public static void findM(int [] arr,int i,int k){
	   int x=i+1;
		if((arr[x]-arr[i])==1){
		   if(k!=x){
		      int j=(i+k)/2;
			  if(x!=j)
			     findM(arr,x,j);
			  findM(arr,j,j+1);
			  int s=j+1;
			  if(s!=k)
			      findM(arr,s,k);
		   }
		   else
		      return;
		}
		else{
		    int p=arr[i]+1;
			System.out.print(" "+p);
			l=l+1;
			
		}
		if(l==2)
		   return;
		if(x==k)
		   return;
	}
}

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

This code is good for only this array. It's not working for other

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

Basically I kind of do a binary search. I look at the middle of the array, and calculate the expected value if the array wasn't missing numbers from start to index, and end to index. If the values are what I expected for the left, then I don't check the left half. I do the same for the right. If it isn''t the expected value, I check the adjacent numbers to see if there is a gap and print out those numbers.

public static void main(String [ ] args)
{
		Set<Integer> set = new HashSet<Integer>();
		printMissingNumbers(8, 8, new int[] {1,3,5,9,10,11,15}, set);
		Set<Integer> set2 = new HashSet<Integer>();
		printMissingNumbers(8, 1, new int[] {1,2,3,4,5,6,7,8,9,11}, set2);
}
static public void printMissingNumbers(int n, int m, int[] arr,
			Set<Integer> set) {
		int start = arr[0];
		int end = arr[arr.length - 1];
		printMissingUtil(start, end, m, arr, set);
	}
	static public void printMissing(int startNum, int endNum,
			Set<Integer> set) {
		for(int i = startNum + 1; i < endNum; i++) {
			System.out.println(i);
			set.add(i);
		}
	}
	static int num = 0;
	static public int printMissingUtil(int start, int end,
			int m, int[] arr , Set<Integer> set)
	{
		num++;
		System.out.println("iteration: " + num);
		int index = arr.length/2;
		int expectedLeft = index + start;
		int expectedRight = end - (arr.length - (index + 1));
		int currentVal = arr[index];
		
		if(expectedLeft < currentVal) {
			if(currentVal - arr[index - 1] != 1) {
				printMissing(arr[index - 1], currentVal, set);
				m -= (currentVal - arr[index - 1] - 1);
			}
			if (m == 0) {
				return 0;
			}
			int newend = arr[index - 1];
		    m = printMissingUtil(start, newend, m, 
		    		Arrays.copyOfRange(arr, 0,index ), set);
		}
		if(expectedRight > currentVal) {
			if(arr[index + 1] - currentVal != 1) {
				printMissing(currentVal, arr[index + 1] ,set);
				m -= (arr[index + 1] - currentVal - 1);
			}
			if(m == 0)
				return 0;
			int newstart = arr[index + 1];
			m = printMissingUtil(newstart, end, m, 
					Arrays.copyOfRange(arr, index + 1, arr.length  ), set);
		}
		return m;
	}

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

def find(a, left, right, result):
    if left == right:
        return

    if left == right - 1:
        if a[left] < a[right] - 1:
            for i in range(a[left] + 1, a[right]):
                result.append(i)
    else:
        mid = (left + right) / 2

        if a[mid] - a[left] > mid - left:
            find(a, left, mid, result)

        if a[right] - a[mid] > right - mid:
            find(a, mid, right, result)

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

Before this method, take care of appending to a if first element is lesser / last element is greater

static Run findMissing(int a[], int start, int end) {
        // only one element
        if (start == end) {
            return new Run(a[start], a[end]);
        }

        // this subarray is already sorted
        if (a[start] == start && a[end] == end) {
            return new Run(a[start], a[end]);
        }

        int mid = start + (end - start) / 2;

        Run leftSide = findMissing(a, start, mid);
        Run rightSide = findMissing(a, mid + 1, end);

        // FInd missing numbers from leftSide.right -> mid
        for (int i = leftSide.right + 1; i<a[mid]; i++) {
            System.out.print(i + " ");
        }

        // Find missing numbers from mid+1 -> rightSide.left
        for (int i=a[mid]+1; i<rightSide.left; i++) {
            System.out.print(i + " ");
        }

        return new Run(leftSide.left, rightSide.right);

}

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

using System;
using System.Collections.Generic;

namespace TestRun
{
    class Program
    {
        int[] Arr = new int[] {0,1,4,5,6,8 };
        List<int> missing = new List<int>();
        int amc = 0;

        public void FindMissing(int start, int end)
        {
            
            if ((Arr[start] == Arr[1] + start - 1 + amc) && (Arr[end] == Arr[1] + end - 1 + amc))
                return;
            else
            {
                if (start == end)
                {
                    if(Arr[start]!=Arr[1]+start-1+amc)
                    {
                        for(int i=start+amc;i<Arr[start];i++)
                        {
                            missing.Add(i);
                            amc++;
                        }
                        return;
                    }
                }

                int mid = (start + end) / 2;
                FindMissing(start, mid);
                FindMissing(mid + 1, end);
            }

        }


        //Main Program to Call the Function 
        static void Main(string[] args)
        {
            Program p = new Program();
            
            int totalElement = 8;
            int endIndex = p.Arr.Length - 1;
            
            p.FindMissing(1,endIndex);

            if(p.Arr[endIndex]!=totalElement)
            {
                for (int i = p.Arr[endIndex] + 1; i <=totalElement; i++)
                    p.missing.Add(i);
            }
            
            foreach (int i in p.missing)
                Console.WriteLine(i);
            
            Console.ReadLine();
        }
    }
}

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

set<int> getMissing(int* input, int low, int high, int missing)
{
	static set<int> result;
	static int calls = 0;
	calls++;

	if (low > high || low < 0 || high < 0 || result.size() == missing)
		return result;

	if (low + 1 == high || low == high )
	{
		int temp = input[low] + 1;
		while (temp < input[high])
		{
			result.insert(temp);
			temp++;
		}
		//check lower boundary
		if (low > 0)
		{
			int temp1 = input[low - 1];
			while (temp1 + 1  < input[low])
			{
				result.insert(temp1 + 1);
				temp1++;
			}
		}
		

		//check upper boundary
		int temp2 = input[high];
		while (temp2 + 1 < input[high+1])
		{
			result.insert(temp2 + 1);
			temp2++;
		}
	}

	unsigned int  mid = (low + high) / 2;

	//both half sets missing a number
	if (input[mid] != mid && mid >= 2)
	{
		getMissing(input, low, mid-1, missing);
		getMissing(input, mid+1, high, missing);
	}
	 
	return result;
}

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

List<int> FindMissingNumbers(int[] array, int missing)
	{
		return CoreFindMissingNumbers(array, 0, array.Length);
	}


	List<int> CoreFindMissingNumbers(int start, int end)
	{
		List<int> result = new List<int>();

		if(end-start) == (A[end] - A[start]); // Do nothing as there is no missing numbers here
                else if(end-start == 2)
                {
              		for(int i = A[start] + 1; i < A[end]; i++)
			{
				result.Add(i);
			}
                }
		else
		{
			int pivot = (end+start)/2;

			result.AddRange(CoreFindMissingNumbers(pivot, end);
			result.AddRange(CoreFindMissingNumber(start, pivot + 1);
		}
		
		return result;
	}

- Nelson Perez January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code:

#include <vector>
using namespace std;

void findmissing(vector<int> data, int start, int end, vector<int> &result)
{
	int expected = start + result.size() + 1;
	if (start == end)
	{
		if (data[start] != expected)
		{
			result.push_back(expected);
		}
		return;
	}
	if (data[start] == expected && end - start == data[end] - data[start])
	{
		return;
	}
	int mid = start + (end - start) / 2;
	findmissing(data, start, mid, result);
	findmissing(data, mid + 1, end, result);
}

Explanation:

In the base case, we have a single integer. If that integer does not match what is expected at that index (accounting for missing integers already in the result set), we know that we are missing the number that *is* expected at that index.

In the next case, we can ignore this entire set of numbers if we know the first number is correct, and the difference between the first number and the last number is the same as the difference between the first index and the last index. If the initial data set is complete, this will keep us from ever having to iterate over the data.

Finally, we split the data in half, and recurse on each half. Note: It's very important that we recurse on the left half first, as the two cases above depend on all missing numbers to the left of our current starting index to already exist in the result set.

- Nick January 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't know why u require m in all of the above solution. 

my solution is: -

public static void findMissingNumber(Set<Integer> values,int[] arr,int low, int high){
		
		if(low>=high||arr==null) {
			return;
		}
		int mid = (low+high)/2;
		if(mid<high&& (arr[high]-arr[mid])!=high-mid){
			if(high==mid+1){
				//there is a missing number here 
				values.add(arr[mid]+1);
			}
			else{
				findMissingNumber(values,arr,mid,high);
			}
		}
		if(low<mid&&(arr[mid]-arr[low])!=mid-low){
			if(mid==low+1){
				//there is a missing number here 
				values.add(arr[low]+1);
			}
			else{
				findMissingNumber(values,arr,low,mid);
			}
		}
		
	}
	
	
	public static void main(String[] args) {
		int[] arr = {1,2,4,5,6,8};
		Set<Integer> sets = new HashSet<Integer>();
		findMissingNumber(sets, arr, 0, arr.length-1);
		System.out.print("{");
		for(Integer i:sets){
			System.out.print(i+",");
		}
		System.out.println("}");
		
		//second set of integers
		//int[] arr1 = {8,10,12,15};
		int[] arr1 = {1,3,5,7};
		sets.clear();
		findMissingNumber(sets, arr1, 0, arr1.length-1);
		System.out.print("{");
		for(Integer i:sets){
			System.out.print(i+",");
		}
		System.out.println("}");
		
		
		
		
	}

- Resh January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about a solution like this : just iterate once over array and grab two neightbors, if difference between them is greater than 1, than we can iterate over their difference and find missing numbers

O(n)
NSArray *missingNumbers(NSArray *a){
if(a.count < 2){
return [NSArray new];
}

NSMutableArray *array = [NSMutableArray new];
for (NSInteger i = 0; i < a.count - 1; i ++) {
NSNumber *x = a[i];
NSNumber *y = a[i+1];

NSInteger xInt = [x integerValue];
NSInteger yInt = [y integerValue];

NSInteger diff = yInt - xInt;

if(diff > 1){
for (NSInteger i = xInt + 1; i < yInt; i++) {
[array addObject:@(i)];
}
}
}
return array;
}

- Tomek February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSArray *missingNumbers(NSArray *a){
if(a.count < 2){
return [NSArray new];
}

NSMutableArray *array = [NSMutableArray new];
for (NSInteger i = 0; i < a.count - 1; i ++) {
NSNumber *x = a[i];
NSNumber *y = a[i+1];

NSInteger xInt = [x integerValue];
NSInteger yInt = [y integerValue];

NSInteger diff = yInt - xInt;

if(diff > 1){
for (NSInteger i = xInt + 1; i < yInt; i++) {
[array addObject:@(i)];
}
}
}
return array;
}

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

Something like binary search. If some part of array doesn't contain skipped element it wouldn't process that part.

import java.util.*;
public class Middle {
        public static void middle(int[] data, int b, int e, int bI, int eI, List<Integer> result) {
                if(bI < eI) {
                        int mid = (bI + eI) / 2;
                        if(data[mid] - b > mid - bI) {
                                middle(data, b, data[mid], bI, mid, result);
                        }
                        if(e - data[mid] > eI - mid) {
                                middle(data, data[mid] + 1, e, mid + 1, eI, result);
                        }
                } else if(bI == eI) {
                        for(int i = b; i <= e; i++) {
                                if(data[bI] != i) {
                                        result.add(i);
                                }
                        }
                }
        }
        public static List<Integer> middle(int[] data, int n) {
                List<Integer> result = new ArrayList<>();
                middle(data, 1, n, 0, data.length - 1, result);
                return result;
        }


        public static void main(String... args) {
                int[] data = new int[] {1,2,4,5,6,8};
                System.out.println(middle(data, 8));
        }
}

- anonymous April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution using modified binary search.

Running time is roughly O( log N), except for the corner case where missing numbers are on both end of array. (e.g. {2,3,4,5,6,7}). In that case, Running time is O(N).

#include<list>
#include<iostream>

using namespace std;

void find_missing(int* input, int s, int e, int m, int n, list<int>& result)
{
	if (s>e || result.size() == m)
		return;

	int half = s + (e-s)/2;
	if (half == 0)
	{
		for (int i = 1; i < input[half]; i++)
			result.push_back(i);
		result;
	}

	if (half == n-m-1)
	{
		for (int i = n; i > input[half]; i--)
			result.push_back(i);
		return;
	}

	if (half > s && input[half]-input[half-1] > 1)
	{
		for (int i = input[half-1]+1; i< input[half]; i++)
			result.push_back(i);
	}
	if (half < e && input[half+1] - input[half] > 1)
	{
		for (int i = input[half]+1; i<input[half+1]; i++)
			result.push_back(i);
	}

	if (s< half &&  (input[half-1]- input[s] > (half-1)-s || input[half-1]-1 > half-1))
		find_missing(input, s, half-1, m,n, result);

	if (e> half && (input[e] -input[half+1] > e - (half+1) || n - input[half+1] > (n-m -1) - (half+1)))
		find_missing(input, half+1, e, m, n, result);	
}

- hankm2004 August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can this handle the input as blow:

n = 8
m = 2
input = {2,3,4,5,6,7}

- hankm2004 August 25, 2015 | 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