Question: Given an array where two neighboring elements are adjacent (in absolute difference 1), can you write an algorithm to search an element in the array and return its position? If the element appears multiple times, please return the first occurrence.

For example, if given the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9} and an element 9, the element appears twice in the array, and the first occurrence is at position 7.

Analysis: The most simple and straightforward solution is to traverse the array and compare elements one by one. This strategy works for every array, and it does not utilize the property of the array where two neighboring elements are in absolute difference 1.

Let's try to search the first 9 from the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9}. Firstly we are at position 0 where the element 4 is. The difference between 9 and 4 is 5, so we move to the position 5. Why? Because the absolute difference between two neighboring elements is 1. If the numbers in the array is increasingly sorted, the element at position 5 is 9. If some elements decrease, 9 should sit on the right of position 5. Therefore, 5 is the leftmost possible position of the element 9.

It's 7 at position 5. The difference between 7 and 9 is 2, so we move to right by distance 2 to the position 7, where the first occurrence of 9 has been found.

We can summarize the solution: We begin from the first element of the element, and compare it with the given number. If the absolute difference is n, move to the right by distance n. Then we compare the current visited element. Repeat until the given element is found, or the position is beyond the length of the array when the given element is not available.

The solution can be implemented in C/C++ as below:

int findFirst(int* nums, intlength, inttarget)
{
if (nums == nullptr || length <= 0)
return -1;

intindex = 0;
while (index < length && nums[index] != target)
{
int delta = target - nums[index];
index += abs(delta);
}

if(index < length)
return index;

return -1;
}

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

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

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

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

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(n²) substrings, and it costs O(n) time to check whether a substring has duplication. Therefore, the overall cost is O(n³).

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

We scan the string one character after another. When the i^th character is scanned, L(i-1) is already know. If the i^th character has not appeared before, L(i) should be L(i-1)+1. It’s more complex when the i^th character is duplicated. Firstly we get the distance between the i^th 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 i^th 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.

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

For instance, in the binary search tree in Figure 1, the node closest to 29 is the node with value 28.

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

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

Analysis: A function f(i) is defined to denote the maximal stolen value from the first house to the i^th house, and the value contained in the i^th house is denoted as v_i. When the thief reaches the i^th house, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:

It would be much more efficient to calculate in bottom-up order than to calculate recursively. It looks like a 1D array with size n is needed, but actually it is only necessary to cache two values for f(i-1) and f(i-2) to calculate f(i).

This algorithm can be implemented with the following C++ code:

int maxStolenValue(const vector<int>& values)

{

int length = values.size();

if(length == 0)

return 0;

int value1 = values[0];

if(length == 1)

return value1;

int value2 = max<int>(values[0], values[1]);

if(length == 2)

return value2;

int value;

for(int i = 2; i < length; ++i)

{

value = max<int>(value2, value1 + values[i]);

value1 = value2;

value2 = value;

}

return value;

}

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