## Riverbed Interview Question for Software Engineer / Developers

Country: United States

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

I'll solve a simplified version of the problem. You should be able to extend it to solve your problem.

You have a large number of integers between 1 to 100000 in a file. However, you can only store a single array of length. How do you find an integer on in that file.

``````1. Divide the range of integers to 10. Meaning 1 - 10000 maps to index 1 in the array, 10001 - 20000 maps to 2 etc
2. Read each integer from the file and find out its corresponding index in the array as described in 1. And increment the value at that array by 1.
3. After you are done reading. Find the index of the array that has the least value. There must be some element in the array, whose value is less that 10000. (If not, all possible integers are on the disk.)
4. Now you know the range where you can find a missing integer. Lets say, it is between 50001 to 60000.
5. Set all the array indices to 0. Now index 1 in the array corresponds to 50001 to 51000, index 2 maps to 51001 to 52000 and so on
6. read the file again and find out the array index with the smallest value
7.  ...
8. ...``````

Hope you get the idea. Sorry about the horrible pseudocode!

Comment hidden because of low score. Click to expand.
0

This is a very good approach.

Comment hidden because of low score. Click to expand.
0

I don't think this works, a negative test case for your code is :
1, 2 , 9997,9999, 9999
10000, 10001, 19997, 19999,19999
etc.
this means 9998 is always missing but 9999 always duplicated, so your algorithm doesn't work.

Unless the interviewer says the numbers are unique.

Comment hidden because of low score. Click to expand.
0

Numbers can't be unique, because we have only 4b unique integers.
Unless the interviewer says that number has type long :)

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

Sum the every thing and subtract it from the sum for first billion+1 integers , you have your missing number.

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

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

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

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

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

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Are those integers supposed to be continuous? If yes, you need only O(1) memory and O(N) complexcity. The algo is:

1. Sum all the integers from the given array and store it as A.
2. Calculate the expected number via this equation: B = (min + max) * number / 2;
3. The missing number is B - A

Comment hidden because of low score. Click to expand.
0

I doubt they're meant to be continuous. Why would you assume that?

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.

### 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.