Saturday, August 9, 2014

No. 54 - Merge Ranges


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).
Figure 1: Merge four ranges [5, 13], [27, 39], [8, 19] and [31, 37] (in blue), and get [5, 19], and [27, 39] (in green)
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:
public bool Contains(int value)
{
    if (value >= this.Start && value <= this.End)
    {
        return true;
    }
 
    return false;
}
 
public bool Overlaps(Range other)
{
    if (other == null)
    {
        return false;
    }
 
    if (this.Contains(other.Start) || this.Contains(other.End)
        || other.Contains(this.Start) || other.Contains(this.End))
    {
        return true;
    }
 
    return false;
}
 
public Range Merge(Range other)
{
    if (!this.Overlaps(other))
    {
        throw new ApplicationException("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;
 
    return new Range(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:
Figure 2: It causes problems when a new range overlaps two ranges in the merged container
 
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:

public static Range[] Merge(Range[] ranges)
{
    Stack<Range> results = new Stack<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.



Sunday, March 23, 2014

No. 53 - Longest Arithmetic Sequence

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:

internal class Pair
{
    public int First { get; set; }
    public int Second { get; set; }
}

private static Dictionary<int, List<Pair>> BuildHashTable(int[] numbers)
{
    var hashTable = new Dictionary<int, List<Pair>>();
    for(int i = 0; i < numbers.Length; ++i)
    {
        for(int j = i + 1; j < numbers.Length; ++j)
        {
            Pair pair = new Pair
            {
                First = i,
                Second = j
            };

            int diff = numbers[j] - numbers[i];
            if(hashTable.Keys.Contains(diff))
            {
                hashTable[diff].Add(pair);
            }
            else
            {
                List<Pair> newValue = new List<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 mth 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+1thelemement in the arithmetic sequence.

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

private static int Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)
{
    int maxLength = 0;
    foreach(var key in hashTable.Keys)
    {
        int[] lengths = new int[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;
}

public static int 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(n2) pairs in an array with n elements. Therefore, the time and space efficiencies of this solution is O(n2) 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:

public static int 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(n2) 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:

public static int GetMaxLengthConsecutiveSequence(int[] numbers)
{
    HashSet<int> set = BuildHashSet(numbers);
    return AnalyzeHashSet(set);
}

private static HashSet<int> BuildHashSet(int[] numbers)
{
    var set = new HashSet<int>();
    foreach(int number in numbers)
    {
        set.Add(number);
    }

    return set;
}

private static int 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.