Problem: Integers in an array are unique and increasingly sorted. Please write a function/method to find an integer from the array who equals to its index. For example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.

Analysis: If we scan all integers in the array from beginning to end, we may check whether every element equals its index. Obviously, this solution costs O(n) time.

Since numbers are sorted in the array, let's try to utilize the binary search algorithm to optimize. Supposing we reach the ith element in the array at some step. If the value of element is also i, it is a target integer and let's return it.

What would happen when the value m is greater than the index i? For any k (k>0), the value of element with index i+k should be greater than or equal to m+k, because integers are unique and increasingly sorted in the array. Additionally because m>i, m+k>i+k. Therefore, every element on the right side of index i should be greater than its index in such a case.

Similarly, when the value of element with index i is less than i, every integer on the left side should be less than its index. Please prove it if you are interested.

Therefore, we could reduce the search scope to half for the next step, and it is a typical process for binary search. The solution can be implemented with the following Java code:

publicstaticint getNumberSameAsIndex(int[] numbers) {

if(numbers == null || numbers.length == 0) {

return -1;

}

int left = 0;

int right = numbers.length - 1;

while(left <= right) {

int middle = left + ((right - left) >>> 1);

if(numbers[middle] == middle) {

return middle;

}

if(numbers[middle] > middle) {

right = middle - 1;

}

else {

left = middle + 1;

}

}

return -1;

}

The source code with unit test cases is shared at http://ideone.com/ZSd9kG.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this article in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Problem: Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ..., n[m-1], in order to get the maximal product of n[0]*n[1]* ... *n[m-1]? We have to cut once at least. Additionally, the length of the whole length of the rope, as well as the length of each part, are in integer value.

For example, if the length of the rope is 8, the maximal product of the part lengths is 18. In order to get the maximal product, the rope is cut into three parts with lengths 2, 3, and 3 respectively.

Analysis: There are two solutions to solve this problem. One is the traditional dynamic programming solution with O(n²) time and O(n) space, and the other is a quite creative and efficient solution with O(1) time and O(1) space.

Solution 1: Dynamic programming

Firstly let’s define a function f(n) for the maximal length product after cutting a rope with length n into parts. We have n-1 choice for the first cut on the rope, with the length of the first part 1, 2, … n-1 respectively. Therefore, f(n)=max(f(i)*f(n-i), where 0<i<n).

If the equation is resolved recursively in top-down order, there are lots of overlapping sub-problems and it’s a waste of recalculation. It’s much more efficient to calculate in bottom-up order. That is to say, we firstly get f(2), and then f(3), then f(4), f(5). We continue till we get f(n).

The following Java code solves the problem in bottom-up order:

publicstaticint maxProductAfterCutting_solution1(int length) {

if(length < 2) {

return 0;

}

if(length == 2) {

return 1;

}

if(length == 3) {

return 2;

}

int[] products = newint[length + 1];

products[0] = 0;

products[1] = 1;

products[2] = 2;

products[3] = 3;

for(int i = 4; i <= length; ++i) {

int max = 0;

for(int j = 1; j <= i / 2; ++j) {

int product = products[j] * products[i - j];

if(max < product) {

max = product;

}

products[i] = max;

}

}

return products[length];

}

An array products with length n+1 is created, in order to store the maximal product of for ropes with length 0, 1, 2, …, n.

Solution 2: Tricky cutting strategy

There is a strategy to cut the rope to get maximal product: We cut the parts with length either 3 or 2. Additionally, we try to keeping cut parts with length 3 as many as possible. Therefore, we could solve the problem with the following Java code:

publicstaticint maxProductAfterCutting_solution2(int length) {

if(length < 2) {

return 0;

}

if(length == 2) {

return 1;

}

if(length == 3) {

return 2;

}

int timesOf3 = length / 3;

if((length - timesOf3 * 3) % 2 == 1) {

timesOf3 -= 1;

}

int timesOf2 = (length - timesOf3 * 3) / 2;

return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));

}

This solution sounds a bit tricky, and it does not make sense if we can’t prove it mathematically. Let’s try to demonstrate its correctness.

When n≥5, we could prove that 2(n-2)>n and 3(n-3)>n.Therefore, we continue to cut rope into parts with length 3 or 2 when the length is greater than 5. Additionally, 3(n-3) ≥ 2(n-2) when n≥5, so we cut parts with length 3 as many as possible.

The prerequisite of the proof above is n≥5. How about n is 4? There are only two approaches to cut when the length of the rope is 4: Cut into two parts with lengths 1 and 3, or with lengths 2 and 2. In our strategy, the rope will be cut into two parts with length 2 and 2. The other approach is discarded because a part with length 1 is not allowed. Notice that 4=2*2, and 2*2>1*3. That’s to say, it’s no harm to cut a rope with length 4 into two parts with same length 2.

Therefore, our strategy to cut ropes is correct.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Problem: Reorder the digits of a number, in order to get the next number which is the least one that is greater than the input number. For example, the number 34724126 is the next number of 34722641 when reordering digits.

Analysis: When a digit in a number is swapped with a greater digit on its right side, the number becomes greater. For example, if the digit 3 in the number 34722641 is swapped with digit 7, the result is 74322641 which is greater than the original number. The remaining issue how to get least number which is greater than the original one.

Since we are going to get the least number after reordering digits, let’s find digits to be swapped on the right side. The first three digits on the right side of 34722641 are 641 which are decreasingly sorted. The two digits among them are swapped, the whole number will become less.

Let’s move on to the left digits. The next digit on the right side is 2, which is less than 6 and 4 on its right side. If the digit 2 is swapped with 6 or 4, the whole number will be become greater. Since we are going to keep the swapped number as less as possible, the digit 2 is swapped with 4, which is less one between 4 and 6. The number becomes 34724621.

Now 34724621 is greater than the original number 34722641, but it’s not the least one which is greater than 34722641. The three digits on the right side, 6, 2 and 1, should be increasingly sorted, in order to form the least number 34724126 among numbers which are greater than of 34722641.

The solution can be implemented with the following JAVA code:

publicstatic String getLeastGreaterNumber(String number) {

if(isGreatestNumber(firstDecreasing)) {

String prefix = "";

StringBuilder resultBuilder = new StringBuilder(prefix);

Collections.sort(decreasingChars);

When all digits are already increasingly sorted in the input number, the number itself is the greatest number with given digits. We should discuss with our interviewers what to return for this case during interviewers. Here we just return an empty string for this case.

When firstDecreasing is 0, it means all digits are increasingly sorted, and the input number is the greatest number with given digits, as listed in the following method isGreatestNumber.

privatestatic Boolean isGreatestNumber(int firstDecreasing) {

The following method getDecreasingChars gets the longest sequence of decreasing digits on the right side of a number:

privatestaticint getDecreasingChars(String number, List<Character> decreasing) {

return firstDecreasing;

The following method swapLeastGreater swaps the digit before the decreasing digits on the right side (target) and the least digit which is greater than target:

privatestaticchar swapLeastGreater(List<Character> chars, char target) {

return finding;

The following method appendList appends characters from a list into a string builder:

privatestaticvoid appendList(StringBuilder str, List<Character> chars) {

Code with unit tests is shared at http://ideone.com/czs13W .

Extended Problem 1: Given a set of digits, please output all numbers permutated by the digits in increasing order. For example, if the input are five digits 1, 2, 3, 4, 5, the output are numbers from 12345, 12354, ..., to 54321 in increasing order.

Extended Problem 2: Given a number n, please out put all numbers with n bits of 1 in increasing order. For example, if the input is 3, the output are numbers 7, 11, 13, …

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com , or Apress .

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/ . If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Problem: In an array, all numbers appear three times except one which only appears only once. Please find the unique number.

Analysis: It is simpler if we modify the problem a little bit: Please find a unique number from an array where other numbers appear twice. We could solve this simplified problem with the XOR bitwise operation. If all numbers in the array are XORed, the result is the number appearing only once, since pairs of numbers get 0 when they are XORed.

The strategy with XOR does not work since all numbers except one appear three times, since the XOR result of a triple of numbers is the number itself.

Even though we could not solve the problem with XOR, we may still stick on the bitwise operations. A number appears three times, each bit (either 0 or 1) also appears three times. If every bit of numbers appearing three time is added, the sum of every bit should be multiple of 3.

Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.

The solution can be implemented in Java as the code listed below:

publicstaticint FindNumberAppearingOnce(int[] numbers) {

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com , or Apress .

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/ . If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Question: When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.

For example, array {3, 4, 5, 1, 2} is a rotation of array {1, 2, 3, 4, 5}. If the target number to be searched is 4, the index of the number 4 in the rotation 1 should be returned. If the target number to be searched is 6, -1 should be returned because the number does not exist in the rotated array.

Analysis: Binary search is suitable for sorted arrays. Let us try to utilize it on a rotation of a sorted array. Notice that a rotation of a sorted array can be partitioned into two sorted sub-arrays, and numbers in the first sub-array are greater than numbers in the second one.

Two pointers P1 and P2 are utilized. P1 references to the first element in the array, and P2 references to the last element. According to the rotation rule, the first element should be greater than the last one.

The algorithm always compares the number in middle with numbers pointed by P1 and P2 during binary search. If the middle number is in the first increasingly sorted sub-array, it is greater than the number pointed by P1.

If the value of target number to be search is between the number pointed by P1 and the middle number, we then search the target number in the first half sub-array. In such a case the first half sub-array is in the first increasing sub-array, we could utilize the binary search algorithm. For example, if we search the number 4 in a rotation {3, 4, 5, 1, 2}, we could search the target number 4 in the sub-array {3, 4, 5} because 4 is between the first number 3 and the middle number 5.

If the value of target number is not between the number pointed by P1 and the middle number, we search the target in the second half sub-array. Notice that the second half sub-array also contains two increasing sub-array and itself is also a rotation, so we could search recursively with the same strategy. For example, if we search the number 1 in a rotation {3, 4, 5, 1, 2}, we could search the target number 1 in the sub-array {5, 1, 2} recursively.

The analysis above is for two cases when the middle number is in the first increasing sub-array. Please analyze the other two cases when the middle number is in the second increasing sub-array yourself, when the middle number is less than the number pointed by P2.

The code implementing this algorithm is listed below, in C/C++:

int searchInRotation(int numbers[], int length, int k)

{

if(numbers == NULL || length <= 0)

return -1;

return searchInRotation(numbers, k, 0, length - 1);

}

int searchInRotation(int numbers[], int k, int start, int end)

{

if(start > end)

return -1;

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

if(numbers[middle] == k)

return middle;

// the middle number is in the first increasing sub-array

if(numbers[middle] >= numbers[start])

{

if(k >= numbers[start] && k < numbers[middle])

return binarySearch(numbers, k, start, middle - 1);

return searchInRotation(numbers, k, middle + 1, end);

}

// the middle number is in the second increasing sub-array

else if(numbers[middle] <= numbers[end])

{

if(k > numbers[middle] && k <= numbers[end])

return binarySearch(numbers, k, middle + 1, end);

return searchInRotation(numbers, k, start, middle - 1);

}

// It should never reach here if the input is valid

assert(false);

}

Since the function binarySearch is for the classic binary search algorithm, it is not listed here. You might implement your own binary search code if you are interested.

In each round of search, half of the array is excluded for the next round, so the time complexity is O(logn).

You may wonder why we assume there are no duplications in the input array. We determine whether the middle number is in the first or second sub-array by comparing the middle number and the numbers pointed by P1 or P2. When the middle number, the number pointed by P1 and P2 are identical, we don’t know whether the middle number is in the first or second increasing sub-array.

Let’s look at some examples. Two arrays {1, 0, 1, 1, 1} and {1, 1, 1, 0, 1} are both rotations of an increasingly sorted array {0, 1, 1, 1, 1}, which are visualized in Figure 1.

Figure 1: Two rotations of an increasingly sorted array {0, 1, 1, 1, 1}: {1, 0, 1, 1, 1} and {1, 1, 1, 0, 1}. Elements with gray background are in the second increasing sub-array.

In Figure 1, the elements pointed by P1 and P2, as well as the middle element are all 1. The middle element with index 2 is in the second sub-array in Figure 1 (a), while the middle element is in the first sub-array in Figure 1 (b).

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com , or Apress .

Email This BlogThis! Share to X Share to Facebook Share to Pinterest