Tuesday, December 17, 2013

No. 52 - Maximal Product when Cutting Rope

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(n2) 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.

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

 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.

Thursday, December 5, 2013

No. 51 - Next Number with Same Set of Digits


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) {
List<Character> decreasingChars = new ArrayList();
int firstDecreasing = getDecreasingChars(number, decreasingChars);

if(isGreatestNumber(firstDecreasing)) {
return"";
}

String prefix = "";
if(firstDecreasing > 1) {
prefix = number.substring(0, firstDecreasing - 1);
}

StringBuilder resultBuilder = new StringBuilder(prefix);
char target = number.charAt(firstDecreasing - 1);
char leastGreater = swapLeastGreater(decreasingChars, target);
resultBuilder.append(leastGreater);

Collections.sort(decreasingChars);
appendList(resultBuilder, decreasingChars);

return resultBuilder.toString();
}

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) {
return firstDecreasing == 0;
}

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) {
int firstDecreasing = number.length() - 1;
for(; firstDecreasing > 0; --firstDecreasing) {
char curChar = number.charAt(firstDecreasing);
char preChar = number.charAt(firstDecreasing - 1);
decreasing.add(curChar);

if(curChar > preChar) {
break;
}
}

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) {
Iterator it=chars.iterator();
char finding = '9';
while(it.hasNext()) {
char value = ((Character)it.next()).charValue();
if(value > target && value < finding) {
finding = value;
}
}

chars.remove(new Character(finding));
chars.add(new Character(target));

return finding;
}

The following method appendList appends characters from a list into a string builder:
privatestaticvoid appendList(StringBuilder str, List<Character> chars) {
Iterator it=chars.iterator();
while(it.hasNext()) {
char value = ((Character)it.next()).charValue();
str.append(value);
}
}

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.

Tuesday, December 3, 2013

No. 50 - Numbers Appearing Once


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) {
int[] bitSum = newint[32];
for(int i = 0; i < 32; ++i) {
bitSum[i] = 0;
}

for(int i = 0; i < numbers.length; ++i) {
int bitMask = 1;
for(int j = 31; j >= 0; --j) {
int bit = numbers[i] & bitMask;
if(bit != 0) {
bitSum[j] += 1;
}

bitMask = bitMask << 1;
}
}

int result = 0;
for(int i = 0; i < 32; ++i) {
result = result << 1;
result += bitSum[i] % 3;
}

return result;
}

 The time efficiency of this solution is O(n), and space efficiency is O(1) because an array with 32 elements is created. It's more efficient than two straightforward solutions: (1) It's easy to find the unique number from a sorted array, but it costs O(nlogn) time to sort an array with n elements. (2) We may utilize a hash table to store the number of occurrences of each element in the array, but the cost for the hash table is O(n).

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

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.

Friday, November 29, 2013

No. 49 - Longest Substring without Duplication

Problem: Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’.

Analysis: It’s not difficult to get all substrings of a string, and to check whether a substring has duplicated characters. The only concern about this brute-force strategy is performance. A string with n characters has O(n2) substrings, and it costs O(n) time to check whether a substring has duplication. Therefore, the overall cost is O(n3).

We may improve the efficiency with dynamic programming. Let’s denote the length of longest substring ending with the ith character by L(i).

We scan the string one character after another. When the ith character is scanned, L(i-1) is already know. If the ith character has not appeared before, L(i) should be L(i-1)+1. It’s more complex when the ith character is duplicated. Firstly we get the distance between the ith character and its previous occurrence. If the distance is greater than L(i-1), the character is not in longest substring without duplication ending with the (i-1)th character, so L(i) should also be L(i-1)+1. If the distance is less than L(i-1), L(i) is the distance, and it means between the two occurrence of the ith character there are no other duplicated characters.

This solution can be implemented in Java as the following code:

publicstaticint longestSubstringWithoutDuplication(String str) {
int curLength = 0;
int maxLength = 0;

int position[] = newint[26];
for(int i = 0; i < 26; ++i) {
position[i] = -1;
}

for(int i = 0; i < str.length(); ++i) {
int prevIndex = position[str.charAt(i) - 'a'];
if(prevIndex < 0 || i - prevIndex > curLength) {
++curLength;
}
else {
if(curLength > maxLength) {
maxLength = curLength;
}

curLength = i - prevIndex;
}
position[str.charAt(i) - 'a'] = i;
}

if(curLength > maxLength) {
maxLength = curLength;
}

return maxLength;
}

L(i) is implemented as curLength in the code above. An integer array is used to store the positions of each character.

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

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.

Thursday, November 28, 2013

No. 48 - Least Number after Deleting Digits

Problem: Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.

Analysis: Let’s delete a digit from the number at each step. What’s the first digit to be deleted from the number 24635, in order to get the least number with the remaining digits? We may list all the remaining numbers after deleting a digit, in the following table:

Deleted Digit
Remaining Number
2
4635
4
2635
6
2435
3
2465
5
2463

The number 2435 is the least one in all remaining numbers, by deleting the digit 6. Notice that the digit 6 is the first digit in the number 24635 which is greater than the next digit.

Let’s delete another digit from the number 2435, the remaining least number after the first step. We may summarize the remaining numbers after delete every digit from it in the following table:

Deleted Digit
Remaining Number
2
435
4
235
3
245
5
243

The number 235 is the least one in all remaining numbers, by deleting the digit 4. Notice that the digit 4 is the first digit in the number 2435 which is greater than the next digit.

The remaining three digits in the number 235 are increasingly sorted. What is the next digit to be deleted to get the least remaining number? Again, we may list the remaining numbers after deleting each digit in a table:

Deleted Digit
Remaining Number
2
35
3
25
5
23

The number 23 is the least one in all remaining numbers, by deleting the last digit 5.

If we are going to deleting more digits from a number whose digits are increasingly sorted to get the least number, the last digit is deleted at each step.

Now we get the rules to delete digits to get the least remaining number: If there are digits who are greater than the next one, delete the first digit. If all digits in the number are increasingly sorted, delete the last digit gets deleted. The process repeats until the required k digits are deleted.

The code can be implemented in Java as the following:

publicstatic String getLeastNumberDeletingDigits_1(String number, int k) {
String leastNumber = number;
while(k > 0 && leastNumber.length() > 0) {
int firstDecreasingDigit = getFirstDecreasing(leastNumber);
if(firstDecreasingDigit >= 0) {
leastNumber = removeDigit(leastNumber, firstDecreasingDigit);
}
else {
leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
}

--k;
}

return leastNumber;
}

privatestaticint getFirstDecreasing(String number) {
for(int i = 0; i < number.length() - 1; ++i) {
int curDigit = number.charAt(i) - '0';
int nextDigit = number.charAt(i + 1) - '0';
if(curDigit > nextDigit) {
return i;
}
}

return -1;
}

privatestatic String removeDigit(String number, int digitIndex) {
String result = "";
if(digitIndex > 0) {
result = number.substring(0, digitIndex);
}
if(digitIndex < number.length() - 1) {
result += number.substring(digitIndex + 1);
}

return result;
}

Optimization: Save the start index for the next round of search for the first decreasing digit

In the method getFirstDecreasing above to get the first digit which is greater than the next one, we always start from the first digit. Is it necessary to start over in every round of search?

The answer is no. If the ith digit is the first digit which is greater than the next one, all digits before the ith digit are increasingly sorted. The (i-1)th digit might be less than the (i+1)th digit, the next digit of the (i-1)th digit after the ith digit is deleted. Therefore, it is safe to start from the (i-1)th digit in the next round of search.

With this optimization strategy, the efficiency gets improved from O(n*k) to O(n), if the length of the input number has n digits and k digits are deleted.

The optimized solution can be implemented as:

classDecreasingResult {
publicint firstDecreasing;
publicint nextStart;
}

publicstatic String getLeastNumberDeletingDigits_2(String number, int k) {
String leastNumber = number;
int start = 0;
while(k > 0 && leastNumber.length() > 0) {
DecreasingResult result = getNextDecreasing(leastNumber, start);
if(result.firstDecreasing >= 0) {
leastNumber = removeDigit(leastNumber, result.firstDecreasing);
}
else {
leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
}

start = result.nextStart;
--k;
}

return leastNumber;
}

privatestatic DecreasingResult getNextDecreasing(String number, int start) {
int firstDecreasing = -1;
int nextStart;

for(int i = start; i < number.length() - 1; ++i) {
int curDigit = number.charAt(i) - '0';
int nextDigit = number.charAt(i + 1) - '0';
if(curDigit > nextDigit) {
firstDecreasing = i;
break;
}
}

if(firstDecreasing == 0) {
nextStart = 0;
}
elseif (firstDecreasing > 0) {
nextStart = firstDecreasing - 1;
}
else {
nextStart = number.length();
}

DecreasingResult result = new DecreasingResult();
result.firstDecreasing = firstDecreasing;
result.nextStart = nextStart;

return result;
}

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

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.
Subscribe to: Posts (Atom)

AltStyle によって変換されたページ (->オリジナル) /