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: 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

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

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

Question 1: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence should be same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7, whose elements have same order as they are in the array, and the length is 4.

Analysis: Every pair of two adjacent numbers in an arithmetic sequence has exactly same difference. For example, 1, 3, 5, and 7 is an arithmetic sequence, and the pairs (1, 3), (3, 5), and (5, 7) have the same difference 2.

There are n(n-1)/2 pairs out of an array with n elements. These pairs can be categorized into a set of groups, of which each group of pairs have the same difference. For example, the pairs of numbers in the array {1, 6, 3, 5, 9, 7} can be categorized into groups:

Difference -1: (6, 5)
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
…

Therefore, a hash table can be defined for the groups. The key in the hash table is the difference of pairs, and the value in the hash table is a list of pairs with same difference. The code to build the hash table can be implemented in C# as the following:

internalclassPair

{

publicint First { get; set; }

publicint Second { get; set; }

}

privatestaticDictionary<int, List<Pair>> BuildHashTable(int[] numbers)

{

var hashTable = newDictionary<int, List<Pair>>();

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

{

for(int j = i + 1; j < numbers.Length; ++j)

{

Pair pair = newPair

{

First = i,

Second = j

};

int diff = numbers[j] - numbers[i];

if(hashTable.Keys.Contains(diff))

{

hashTable[diff].Add(pair);

}

else

{

List<Pair> newValue = newList<Pair>();

newValue.Add(pair);

hashTable[diff] = newValue;

}

}

}

return hashTable;

}

In the code above, the values of the hash table is pairs of indexes, rather than elements themselves of the array. The pairs are sorted according to their first elements.

The next step is to get the length of pairs with each difference. A list of pairs with difference k is got given a key k in the hash table. If an element A[i] is m^th element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs, the element A[j] should be the m+1^thelemement in the arithmetic sequence.

Therefore, the code to get the max length of all arithmetic sequences can be implemented as:

privatestaticint Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)

{

int maxLength = 0;

foreach(var key in hashTable.Keys)

{

int[] lengths = newint[lengthOfNumbers];

for (int i = 0; i < lengthOfNumbers; ++i)

{

lengths[i] = 1;

}

foreach(Pair pair in hashTable[key])

{

lengths[pair.Second] = lengths[pair.First] + 1;

}

foreach(var length in lengths)

{

if(length > maxLength)

{

maxLength = length;

}

}

}

return maxLength;

}

publicstaticint GetMaxLengthOfArithmeticSequence(int[] numbers)

{

var hashTable = BuildHashTable(numbers);

return Analyze(hashTable, numbers.Length);

}

The source code with unit test cases are shared at: http://ideone.com/jxRDkd.

As mentioned above, there are O(n²) pairs in an array with n elements. Therefore, the time and space efficiencies of this solution is O(n²) given an array with n elements.

Question 2: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence is not necessarily same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, 7, and 9, and the length is 5.

Analysis: Different from the previous problem, there are no limitations on the order of arithmetic sequence. Consequently, we can sort the array before we try to get the maximal length of arithmetic sequences. The code is almost same as before, except for the revision that there is an additional line of code to sort the array, as listed below:

publicstaticint GetMaxLengthOfArithmeticSequence(int[] numbers)

{

Array.Sort(numbers);

var hashTable = BuildHashTable(numbers);

return Analyze(hashTable, numbers.Length);

}

The source code with unit test cases are shared at: http://ideone.com/lEqNm3.

Question 3: Given an array, please get the length of the longest consecutive sequence. A consecutive sequence is an arithmetic sequence with common difference 1. The element order in the consecutive sequence is not necessarily same as the element order in the array. The solution should not cost more than O(n) time and space if the length of the input array is n. For example, in the array {1, 6, 3, 5, 9, 7}, the longest consecutive sequence is 5, 6, and 7 whose length is 3.

Analysis: The solution to solve the above problems cost O(n²) time and space. Therefore, we need a new solution to solve this problem.

A consecutive can’t have duplicated elements. A hash set, of which every element is unique, can be built from the input array. When a number is located in the set, we try to locate its consecutive neighbors. For instance, when the number 6 is found in the set, we try to find the number 5 and 7 in the set, and then we get a consecutive sequence 5, 6, and 7.

This solution can be implemented in C# code as listed below:

publicstaticint GetMaxLengthConsecutiveSequence(int[] numbers)

{

HashSet<int> set = BuildHashSet(numbers);

return AnalyzeHashSet(set);

}

privatestaticHashSet<int> BuildHashSet(int[] numbers)

{

var set = newHashSet<int>();

foreach(int number in numbers)

{

set.Add(number);

}

return set;

}

privatestaticint AnalyzeHashSet(HashSet<int> set)

{

int maxCount = 0;

while(set.Count > 0)

{

int number = set.First();

int count = 0;

int toDelete = number;

while(set.Remove(toDelete))

{

count++;

toDelete++;

}

toDelete = number - 1;

while(set.Remove(toDelete))

{

count++;

toDelete--;

}

if(count > maxCount)

{

maxCount = count;

}

}

return maxCount;

}

Every number in the input array is added into and removed from the array only once, so the time and space efficiency is O(n) if there are n numbers in the array.

The source code with unit tests is shared at http://ideone.com/0oRqLq.

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