Questions: All numbers in an array with length n+1 are in range from 1 to n, so there is at least one duplication in the array. How to find any a duplication? Please don't modify the input array.

Analysis: The simple solution is to utilize hash tables. When scanning the array, array elements are inserted into the hash table one by one. In this way, it's easy to find a duplication with the hash table, which costs O(n) space.

Let's try not to employ extra space. Why there are duplications in the array? If there are no duplications, the count of numbers ranging from 1 to n is n. Since the array contains more than n numbers, there should be duplications. It looks like it's important to count numbers in ranges.

Let's divide numbers from 1 to n into two ranges, split with the number in the middle (denoted as m), and then count the numbers of the two subranges. If the count of numbers from 1 to m is greater than m, the duplication is in the range from 1 to m. Otherwise, there should be at least one duplication in the range from m+1 to n. And then we continue the recursive process until we find the duplication.

The Java code is listed below:

static int countRange(int[] numbers, int start, int end)

{

int count = 0;

for(int i = 0; i < numbers.length; i++)

if(numbers[i] >= start && numbers[i] <= end)

++count;

return count;

}

static int getDuplication(int[] numbers)

{

intstart = 1;

int end = numbers.length;

while(end >= start)

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

Question: A board has n*m cells, and there is a gift with some value (value is greater than 0) in every cell. You can get gifts starting from the top-left cell, and move right or down in each step, and finally reach the cell at the bottom-right cell. What’s the maximal value of gifts you can get from the board?

For example, the maximal value of gift from the board above is 53, and the path is highlighted in red.

Analysis: It is a typical problem about dynamic programming. Firstly let’s analyze it with recursion. A function f(i, j) is defined for the maximal value of gifts when reaching the cell (i, j). There are two possible cells before the cell (i, j) is reached: One is (i - 1, j), and the other is the cell (i, j-1). Therefore, f(i, j)= max(f(i-1, j), f(i, j-1)) + gift[i, j].

Even though it’s a recursive equation, it’s not a good idea to write code in recursion, because there might be many over-lapping sub-problems. A better solution is to solve is with iteration. A 2-D matrix is utilized, and the value in each cell (i, j) is the maximal value of gift when reaching the cell (i, j) on the board.

The iterative solution can be implemented in the following Java code:

publicstaticint getMaxValue(int[][] values) {

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

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

Question: Given a number, please translate it to a string, following the rules: 1 is translated to 'a', 2 to 'b', …, 12 to 'l', …, 26 to 'z'. For example, the number 12258 can be translated to "abbeh", "aveh", "abyh", "lbeh" and "lyh", so there are 5 different ways to translate 12258. How to write a function/method to count the different ways to translate a number?

Analysis: Let's take the number 12258 as an example to analyze the steps to translate from the beginning character to the ending one. There are two possible first characters in the translated string. One way is to split the number 12258 into 1 and 2258 two parts, and 1 is translated into 'a'. The other way is to split the number 12258 into 12 and 258 two parts, and 12 is translated into 'l'.

When the first one or two digits are translated into the first character, we can continue to translate the remaining digits. Obviously, we could write a recursive function/method to translate.

Let's define a function f(i) as the count of different ways to translate a number starting from the ith digit, f(i)=g(i)*f(i+1)+h(i, i+1)*f(i+2). The function g(i) gets 1 when the ith digit is in the range 1 to 9 which can be converted to a character, otherwise it gets 0. The function h(i, i+1) gets 1 the ith and (i+1)th digits are in the range 10 to 26 which can also be converted to a character. A single digit 0 can't be converted to a character, and two digits starting with a 0, such as 01 and 02, can't be converted either.

Even though the problem is analyzed with recursion, recursion is not the best approach because of overlapping sub-problems. For example,The problem to translate 12258 is split into two sub-problems: one is to translate 1 and 2258, and the other is to translate 12 and 258. In the next step during recursion, the problem to translate 2258 can also split into two sub-problems: one is to translate 2 and 258, and the other is to translate 22 and 58. Notice the sub-problem to translate 258 reoccurs.

Recursion solves problem in the top-down order. We could solve this problem in the bottom-up order, in order to eliminate overlap sub-problems. That's to say, we start to translate the number from the ending digits, and then move from right to left during translation.

The following is the C# code to solve this problem:

publicstaticint GetTranslationCount(int number)

{

if (number <= 0)

{

return 0;

}

string numberInString = number.ToString();

return GetTranslationCount(numberInString);

}

privatestaticint GetTranslationCount(string number)

{

int length = number.Length;

int[] counts = newint[length];

for (int i = length - 1; i >= 0; --i)

{

int count = 0;

if (number[i] >= '1' && number[i] <= '9')

{

if (i < length - 1)

{

count += counts[i + 1];

}

else

{

count += 1;

}

}

if (i < length - 1)

{

int digit1 = number[i] - '0';

int digit2 = number[i + 1] - '0';

int converted = digit1 * 10 + digit2;

if (converted >= 10 && converted <= 26)

{

if (i < length - 2)

{

count += counts[i + 2];

}

else

{

count += 1;

}

}

}

counts[i] = count;

}

return counts[0];

}

In order to simply the code implementation, we first convert the number into a string, and then translate.

The code with unit tests is shared at http://ideone.com/7wihgj.

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

Questions: Given an array of ranges, please merge the overlapping ones. For example, four ranges [5, 13], [27, 39], [8, 19], [31, 37] (in blue in Figure1) are merged into two ranges, which are [5, 19] and [27, 39] (in green in Figure 1).

Analysis: Before we analyze how to merge an array of ranges, let’s discuss how to merge two ranges. When two ranges don’t overlap each other, they can’t merge. When two ranges overlap, the less starting value of two ranges becomes the starting value of the merged range, and the greater ending value of two ranges becomes the ending value of the merged range.

Therefore, two ranges [5, 13] and [8, 19] are merged into a new range [5, 19], and two ranges [27, 39] and [31, 37] are merged into a new range [27, 39]. The two merged ranges can’t be merged further because they don’t overlap.

The next question is: How to check whether two ranges overlap each other? When two ranges overlap, there is at least on node in a range is contained in the other range. For instance, the starting value 8 of the range [8, 19] is contained in the range [5, 13], therefore, the two ranges [5, 13] and [8, 19] overlap. No nodes in the range [8, 19] are contained in the range [31, 37], so the two ranges don’t overlap.

The following code shows how to merge two ranges, as well as to check whether two ranges overlap:

publicbool Contains(int value)

{

if (value >= this.Start && value <= this.End)

{

returntrue;

}

returnfalse;

}

publicbool Overlaps(Range other)

{

if (other == null)

{

returnfalse;

}

if (this.Contains(other.Start) || this.Contains(other.End)
|| other.Contains(this.Start) || other.Contains(this.End))

{

returntrue;

}

returnfalse;

}

publicRange Merge(Range other)

{

if (!this.Overlaps(other))

{

thrownewApplicationException("Can't merge two ranges.");

}

int newStart = (this.Start < other.Start) ? this.Start : other.Start;

int newEnd = (this.End > other.End) ? this.End : other.End;

returnnewRange(newStart, newEnd);

}

Now let’s move on to merge an array of ranges.The first step is to sort the ranges based on their start values. When the ranges [5, 13], [27, 39], [8, 19], and [31, 37] are sorted, they are in the order of [5, 13], [8, 19], [27, 39], and [31, 37].

The next steps are to merge the sorted ranges. The merged ranges are inserted into a data container. At each step, a range is retrieved from the sorted array, and merged with the existing ranges in the container.

At first the data container is empty, and the first range [5, 13] is inserted into the container directly, without merging. Now there is only one range [5, 13] in the container.

Then the next range [8, 19] is retrieved. Since it overlaps the range[5, 13], and they become [5, 19] when they merged. There is still only one range, which is [5, 19] in the container.

The next range [27, 39] is retrieved, which does not overlap the range [5, 19] in the container, so it is inserted into the range directly without merging. There are two ranges [5, 19] and [27, 39] in the container.

The last range in the sorted array is [31, 37]. It overlaps the last range [27, 39] in the container. Therefore, the last range [27, 39] is deleted from the container, and then the merged range is inserted into the container. At this step, the merged range is also [27, 39].

Ranges in the container are also sorted based on their starting values, and they don't overlap each other. Notice that it's only necessary to check whether the new range overlap the last range in the container. Why not the other ranges in the container? Let's analyze what would happen when a new range in the sorted array overlap two ranges in the container, with Figure 2:

In Figure 2, the container has two ranges A and B, and a new range C is retrieved from the sorted array, which overlaps the ranges A and B. Since C overlaps A, the starting value of C should be less than the ending value of A. On the other hand, C is retrieved from the sorted array later than B, the starting value of C is greater than starting value of B. Additionally, B is behind A and they don't overlap, so the starting value of B is greater than the ending value A. Therefore, the starting value of C is greater than the ending value of A. It contradicts.

Since it's only necessary to merge new ranges from the sorted array with the last range in the container. We implement the container as a stack, and the last range is on the top of the stack.

The following is the C# code to merge a sort an array of ranges:

publicstaticRange[] Merge(Range[] ranges)

{

Stack<Range> results = newStack<Range>();

if (ranges != null)

{

Array.Sort(ranges, CompareRangeByStart);

foreach (var range in ranges)

{

if (results.Count == 0)

{

results.Push(range);

}

else

{

var top = results.Peek();

if (top.Overlaps(range))

{

var union = top.Merge(range);

results.Pop();

results.Push(union);

}

else

{

results.Push(range);

}

}

}

}

return results.Reverse().ToArray();

}

The code with unit tests are shared at http://ideone.com/kg4TwM.

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