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.



34 comments:

  1. The current method returns incorrect range after merging [5,13] , [27,39] giving [5,39]

    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);
    }

    the correct statement for the new end code statement is

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

    let me know if i am wrong in understanding problem..

    ReplyDelete
    Replies
    1. The two ranges [5, 13] and [27, 39] don't overlap, and they will not merge.

      The results of my code to merge [5, 13] and [27, 39] contains the same two ranges. A new test cases Test6 is added, please refer to the source code unit test at http://ideone.com/kg4TwM. Thanks.

      Delete
    2. Ohayo,


      Brilliant article, glad I slogged through the it seems that a whole lot of the details really come back to from my past project.

      Currently retrieving account attributes
      We are currently in the process of retrieving your account attributes. Please try again in a few minutes.

      I am getting this error message for the last couple of days. According to it is about my account not AWS Training been activated. But according to am email from Amazon, my account is fully activated.



      Anyways great write up, your efforts are much appreciated.


      Ganesh,

      Delete
  2. you can take more help and challenge from quiz questions at:- http://www.fixoncloud.com/Home/Quiz/
    It will prepare you for many languages.

    ReplyDelete
  3. Nice blog...providing lot of information about Jobs and Results

    ReplyDelete
  4. Thanks for your sharing. I also discuss this problem here http://www.capacode.com/array/merge-ranges/ :)

    ReplyDelete
  5. Good questions for practicing and preparing for an interview, thanks! They're unlikely to be used in a actual interview though, considering they've become too common and are easily available online. Companies now either create their own questions or use an online platform that does the same, for example: https://www.testdome.com/

    ReplyDelete
  6. Nice Blog, I really wonder to visit your blog, Thanks a lot! for sharing the useful Information.
    iphone job Oriented course
    apple ios training institutes Hyderabad

    ReplyDelete
  7. Hello Mate,


    I’ve often thought about this No. 54 - Merge Ranges . Nice to have it laid out so clearly. Great eye opener.

    I am using an EC2 instance, my application on the instance is working fine I mean the website hosted on EC2 instance but when I expose it to the general users it gets hacked. The hacking team is from Indonesia and I am unable to identify what type of hacking technique is it. I cannot find their ip in the log file of SSH and a new file is uploaded to the EC2 Instance. AWS Training






    Very useful article, if I run into challenges along the way, I will share them here.


    Thanks,
    Ajeeth

    ReplyDelete
  8. Aloha,


    Zoooooooom! That’s how speedy and easy this read was! Looking forward to more of such powerful content on No. 54 - Merge Ranges


    I'm currently having a small problem with my ECS setup, and I've posted about it here in the ECS forum but still waiting for a response. As I would like to get this issue resolved quickly (and I suspect it's an AWS bug) I would have preferred to open a support case to have someone look at it and quickly tell me either what I did wrong or that the bug is being fixed. AWS Training USA





    Thank you very much and will look for more postings from you.


    Ciao,
    Ajeeth

    ReplyDelete

  9. Hi Your Blog is very nice!!

    Get All Top Interview Questions and answers PHP, Magento, laravel,Java, Dot Net, Database, Sql, Mysql, Oracle, Angularjs, Vue Js, Express js, React Js,
    Hadoop, Apache spark, Apache Scala, Tensorflow.

    Mysql Interview Questions for Experienced

    php interview questions for freshers


    php interview questions for experienced


    python interview questions for freshers


    tally interview questions and answers

    ReplyDelete
  10. Thanks for the information.I really need that information.It's helps me to learn new things. I want to be like you. keep posting new article . I'm your fan. I love to read your article .
    http://www.tutorialabc.com/2018/04/c-interview-questions.html

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. I’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
    AWS Training in Marathahalli | AWS Training in Marathahalli
    AWS Amazon Web Services Training in Chennai | Best AWS Training and Certification for Solution Architect in Chennai
    Amazon Web Services Training in Chennai |Best AWS Training in Chennai

    ReplyDelete
  13. I’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
    AWS Training in Marathahalli | AWS Training in Marathahalli
    AWS Amazon Web Services Training in Chennai | Best AWS Training and Certification for Solution Architect in Chennai
    Amazon Web Services Training in Chennai |Best AWS Training in Chennai

    ReplyDelete
  14. thanks for sharing amazing one keep posting
    services
    world news

    ReplyDelete
  15. I think Navigation is a great Career option. Unfortunately, it is very difficult to find information about What Navigation actually is. Most pages on the internet just talk about How to get into Navigation. While I was searching for reliable information about a Career in Navigation, I came across this amazing page: https://www.lifepage.in/career/20181117-0002/Science/Merchant Navy/Career-in-Navigation/hindi

    ReplyDelete
  16. Sora paper premium blogger template jiska price 10 $ hai lekin mein aap sabhi ko free mein de raha hu kyuki mein nhi chahta newbie blogger ko koi pareshani ho jo mujhe huyi thi or crack theme apne blogger se hata do warna rank karne mein bohot mushkil hoga maine bhi hata diya hai ye wala theme use karo AMP version hai or bohot Fast hai

    Sorapaperpremiumbloggertemplate and please put my premium template links in your article

    ReplyDelete
  17. خدمة كتابة السيرة الذاتية الإحترافية says
    Where to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast

    ReplyDelete




  18. Coding


    Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!



    https://www.bricks4kidz.com.sg/about-us/

    ReplyDelete
  19. This comment has been removed by the author.

    ReplyDelete
  20. How old can the knowledge be?
    Answer: 10 years is typically enough. If the knowledge is older, you risk using information that's not eligible. There are cases when experience older than 10 years represents a plus and has got to be mentioned.

    ReplyDelete
  21. I have been given a Dell computer from my sister. However, her former husband set up his account on this computer (says he cannot remember the password), making himself the only administrator. Now, I cannot add any programs ( like iTunes), nor can I delete anything. How can I clear his passwords from this computer, and make myself the administrator? I am afraid that I shall have to delete everything, then begin again (ugh!) That would mean buying new programs, installing them and so on. Any ideas?.

    ReplyDelete
  22. Very Interested reading. If you have packaging requirements, Just visit our website. Flat Fold Boxes

    Flat Fold Boxes

    Flat Fold Boxes

    ReplyDelete
  23. Amazing blog post with indepth knowledge of Arrays. Thanks for sharing. Interviewhabit

    ReplyDelete