It is Friday and it has been a long week and I am feeling somewhat tired. My wife and I have been invited for dinner at one of her brother’s house. I am looking forward to decompress later today.
In this post I tackled problem 17.4 from the Cracking the Coding Interview book by Gayle Laakmann McDowell. As usual I read the problem a few times to get a good understanding of what is required. Given that I have to generate the test scaffolding I try to be even more careful not to waste time.
I then go to a different room where I have a white board. My office is full of stuff so I could not find a place for it. The good thing is that I walk back and forth until the problem is solved. I do not wish to take multiple pictures until I believe I have a workable solution that I can transfer to an IDE. In this case I am using the Eclipse IDE.
That said; I tend to use the Test Driven Approach (TDD) so I first implement the test scaffolding (which may be enhanced as development proceeds) and then move to solve the problem. Today it was not different.
I need to show you the text of the problem so you can follow. I strongly recommend the book. Solving different problems from the ones you encounter at work helps you learn and improve your work. You never know when something you learned outside work will help tackle a work issue.
The text for the problem 17.4 follows:
An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit from A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?
The simplest but not allowed way to find the missing value is to add all the values in the array. Then perform the sum of all values from 0 to n. Subtract the first result from the second and we got our answer. The problem with such approach is that, we cannot access an entire integer in A with a single operation. What we would need is to build a new array by pulling each of the 32 bits from each integer in the array, and then perform the sums. That would take O(32 * n) + O(n – 1) + O(n). If we ignore the constants we could get away with such solution, but I am sure that an interviewer would stop us from using such approach; at least I would.
I think I need to dump the marker I used. Will get more next time I stop by Costco.
I will now show the results of a few runs of my solution.
main <<< n: 6 main <<< m: 2 main <<< arr: [0, 1, 3, 4, 5, 6] arr.length: 6 main <<< missing: 2 == m: 2 main <<< n: 8 main <<< m: 0 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8] arr.length: 8 main <<< missing: 0 == m: 0 main <<< n: 19 main <<< m: 9 main <<< arr: [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] arr.length: 19 main <<< missing: 9 == m: 9
I started the test scaffolding by having to enter the two values, but before I completed getting and displaying them I switched to having the code specify the values and generate the array with the missing value. That way I can quickly run many tests with different missing values and different array sizes.
The program displays the number of elements in the array and the missing value. It then generates the actual array and to make sure all is well the size of the array is also displayed.
The program then display the missing value found by the method that I wrote and compares it to the actual missing value ‘m’. That way I do not have to do much to run a test and verify all is well or if something went wrong.
Let’s take a look at the test scaffolding.
/*
* Test scaffolding.
* random.nextInt(max - min + 1) + min
*/
public static void main(String[] args) {
// **** ****
final int MAX_LENGTH = 19;
final int MIN_LENGTH = 2;
// **** determine n ****
Random rand = new Random(System.currentTimeMillis());
int n = Math.abs(rand.nextInt(MAX_LENGTH - MIN_LENGTH + 1)) + MIN_LENGTH;
// ???? ????
System.out.println("main <<< n: " + n);
// **** array holding missing number ****
int[] arr = new int[n];
// **** determine missing value ****
int m = Math.abs(rand.nextInt((n - 1) - 0 + 1) + 0);
// ???? ????
System.out.println("main <<< m: " + m);
// **** populate array without the missing value ****
int j = 0;
for (int i = 0; i < arr.length; i++) {
// **** skip this value ****
if (i == m)
j++;
// **** populate array with this value ****
arr[i] = j++;
}
// ???? ????
System.out.print("main <<< arr: [");
for (int i = 0; i < arr.length; i++) {
if (i < arr.length - 1)
System.out.print(arr[i] + ", ");
else
System.out.print(arr[i]);
}
System.out.println("] arr.length: " + arr.length);
// **** find missing value ****
int missing = findMissing(arr);
// **** check if we found the proper missing value ****
System.out.println();
if (missing == m)
System.out.println("main <<< missing: " + missing + " == m: " + m);
else
System.err.println("main <<< missing: " + missing + " != m: " + m);
}
As we could deduct by the output the program chooses the size of the array. We then declare the array which I named arr instead of A. I tend to leave upper case characters to name constants. We then choose the missing value ‘m’.
Next we populate the array. As we can see in the console capture in the first array we should not have a 2; and we do not. The same follows on the other examples using the selected missing value.
We then invoke the findMissing() method which holds the solution for the problem.
To simplify checking when just clicking quickly the “Run Solution” button in Eclipse, we verify that the value returned by the method matches or not the value we skipped inserting into the array. Also note that if a failure is encountered it will be displayed using red text. I do like simplicity.
/*
* Find missing value in O(n).
* arr[i] & 0x01 is equivalent to fetch the 0th bit (LSB) from arr[i].
*/
static int findMissing(int[] arr) {
// **** ****
int missing = 0;
// **** traverse array looking for missing value ****
for (int i = 0; i < arr.length; i++) {
if ((i % 2) != fetchBit(arr, i, 0)) {
missing = i;
break;
}
}
// **** ****
return missing;
}
The findMissing() method traverse the specified array looking for the bit that does not match the index in the array. As the problem requires we traverse the array in O(n) and make a single call to return a single bit from the value stored in the array. If the calculation fails we encountered the missing value, save the value and return it to the caller.
Allow me to describe what I did using the following table which represents the array:
| Array
index |
Array
value |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
The first value in the array in location 0 is 0000 (o in binary). This is a requirement of the problem. Note the pattern on the values. The values end with 0 and 1 alternating. When we encounter the missing value a pattern repeats. In this case 0 followed by 0.
Initially I figured I would traverse the array looking for the duplicate pattern. Then I figured that I could use the index and determine when the last bits do not match.
When I completed the code I had the simple check inline, but after looking at the proposed solution, I decided to write a simple method that “…the only operation we can use to access them is fetch the jth bit from A[i]” which I encapsulated in the fetchBit() method.
/*
* Fetch jth bit from arr[i]
*/
static int fetchBit(int[] arr, int i, int j) {
// **** (we should really throw an exception) ****
if (i >= arr.length)
return 0;
// **** (we should really throw an exception) ****
if ((j < 0) || (j >= 32))
return 0;
// **** mask for jth bit ***
int mask = 1;
for (int k = 0; k < j; k++)
mask <<= 1;
// **** return the requested bit value ****
return arr[i] & mask;
}
The fetchBit() method performs a couple checks and uses a mask to find the bit in question. This was not required because we are only interested in the value of the LSB (Least Significant Bit). Once the mask is set, we return the value of the desired bit in the desired array location.
I am going to see if there is a way to send a message to Gayle and see what I get as a response. I believe I read and interpreted the requirement correctly. Will let you know my findings if and when I get a response.
he entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa