Facebook Interview Question for Software Engineer Interns


Country: United States




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

You have to clarify if the integer is 32 bit or 64 bit. For 64 bit case, it is actually easier to generate an integer randomly. Since you have 4 billion = 2^32 integer, if you generate a random 64 bit integer, the chance that it is unique is (2^64 - 2^32) / 2^64 = 1.0 (with good precision)

So the question should be, having 4 billion 32 bit integers, how do you know if one of them is repeated?

This is what came to my mind.

Let's assume you have 4 MB = 2^20 integer words. Define an array of length 2^20 of integers. Each value (unsigned) can hold up to 2^32

Round A)
Now read the stream of numbers (4 billion):
For number X Let Y = X % 2^20. and array[Y] = array[Y] + 1

After reading all, go through the array and find a "Y"with array[Y] < 2^12

Round B)
We know something about the missing number. The 20 LSB are same as Y.
Clear memory except for "Y" and make another array of length 2^12.
Read all X again. For each X, if X%2^20 == Y, increase the memory location at array[Z].

Round C)
For through array Z and find the location where "array[Z] = 0". Report Z * 2^20 + Y as the missing number.

- Ehsan February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

If you are only restricted to sort in memory then bit arrays would be the way to go (4MB = ~32 million bits), do multiple passes for range 0-32, 32-64 etc...

Otherwise, use external sort.

- Anonymous February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

how about the use of a bitset?

#include <iostream>
#include <bitset>
#include <list>
using namespace std;

int is_duplicate(bitset<32000000> &bs, int number) {
	if(bs.test(number)) {
		return true;
	}	
	else {
		bs.set(number);
	}
	
	return false;
}

int main() {
	// your code goes here
	
	bitset<32000000> bs;
	list<int> l = {1, 2, 4, 1, 12};
	
	for(auto it = l.begin(); it != l.end(); it++) {
		cout << is_duplicate(bs, *it) << ' ';
	}
	
	return 0;
}

- Gerald February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

Its simple case of using bloom filter . And bloom filter are designed for this purpose only check wiki for details
Many url shorting websites such as bitly use this technique .

- Pragti February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

If there are no duplicates, then we can create array of buckets. The array size is 1M, and each element is a 12-bit integer count. Then scan the numbers, for each number N, increase the count in the (N>>12)'th bucket. At the end if the count in the bucket is less than 2^12-1, then the missing number is in this bucket. The rest is easy - scan the numbers again, discard the numbers not in the bucket, for the number is this bucket, use bitmap to indicate if the number is visited.

- Westlake February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can split maximum integer into ranges and sum integers in every range, in order to avoid overflow we have to subtract from every number the range start value. At the end all buckets must contain the same value. If value in bucket is different that is our searched range. Then we have to add all possible numbers of that range to bucket again and if total amount matches total amount of other buckets that is our missing number. But it works only if all integers are unique.

- Andrey Yeliseyev March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the constraints are that all the numbers are unique and because there is only 1 integer missing.

Step 1. Take an integer -> temp1=0.
Step 2. Iterate through the array and then keep xor-ing each item with temp1.
Step 3. Take another integer -> temp2=0;
Step 4. Iterate till 4 billion / limit and keep xor-ing each item with temp2.
Step 5 . Xor temp1 and temp2 to get the missing element.

If however, unique elements aren't guaranteed or there are more than 1 elements missing then, we can use a bit vector. In the absence of STLs ,we can use an array of integers as a bit stream and set the bit appropriately and scan through this array to find the missing elements.

- capt_caveman March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

errr... find the max and add 1 ??
seems to solve the problem as stated

- trepper March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is no duplication, this works well:
1) calculate the sum of all N up to the MAX, java Biginteger will keep that
2) calculate the sum off all N in the list
3) subtract and we have the number!

- andmed March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is no duplication, this works well:
1) calculate the sum of all N up to the MAX, java Biginteger will be good to keep that
2) calculate the sum off all N in the list
3) subtract and we have the number!

- andmed March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Code based on above discussion

import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

// Given a list of 4 billion integers, 
// find an integer not in the list using 4MB of memory. (interview was in Java)
public class MissingIntFinder {
	
	// 4 MB can accommodate -> 4*8*1024*1024 = 32*(2^20) = 2^25
	// 32 bit integer can have possible -> 2 ^ 32 numbers
	
	// so if we assume the Integer range is 32 bit and we'll do the scan in 2 stages
	// (0 -> 16bit) -> (16 -> 32bit)
	
	// Following is a result of 1 stage scan

	public static void main(String[] args) {
	
		List<Integer> data = Arrays.asList(0,1,5,3,4,5,12,2,16,21);
		
		BitSet bitSet = new BitSet(2^16);
		for (Integer val : data) {
			bitSet.set(val);
		}
		
		// nextClearBit : Returns the index of the first bit that is set to false that occurs 
		//                on or after the specified starting index.
		int nextClearBit = bitSet.nextClearBit(0);
		System.out.println(nextClearBit);
	}
}

- dee707 October 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

so insert all elements into the bitset after that iterate through the bitset until you find a bit which is set to 0...that means the number was not int the list...

- Gerald February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort in place, iterate and find.

- memo March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.


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