Showing posts sorted by relevance for query merge intervals. Sort by date Show all posts
Showing posts sorted by relevance for query merge intervals. Sort by date Show all posts

Thursday, January 20, 2022

Leetcode discuss: 56. Merge Intervals | C# Learning how to sort

Jan. 19, 2022


Introduction
It is the algorithm to sort intervals by start time first, and then end time next. The overlapped intervals should be considered carefully since I made a mistake and the failed test case reminded me the case, which is "the second interval is inside the first interval".

C# | SortedSet<int, int> | Sort the interval | How to merge
It is challenge for me to warmup the algorithm to prepare Microsoft onsite. I like to use SortedSet<Tuple<int,int>> to sort intervals, and also I like to write working code in less than 20 minutes.

I also like to see my growth in terms of problem solving, I like to write C# bug-free code without looking up how to define IComparer.

Failed test case | Learn a quick lesson
It is important for me to practice more algorithms in next month, so that I can perform better on onsite in Feb. 2022. Sometimes I should think about more carefully in terms of analysis.

[[1,4],[2,3]], output: [[1,3]], Expected: [[1,4]]
I changed the definition of end time for overlapped case using Math.Max(previous.Item2, current.Item2)))

The following code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_56_merge_intervals
{
    class Program
    {
        static void Main(string[] args)
        {
            // intervals = [[1,3],[2,6],[8,10],[15,18]]
            // output: [[1,6],[8,10],[15,18]]
            var intervals = new int[4][];
            intervals[0] = new int[] {1, 3};
            intervals[1] = new int[] { 2, 6 };
            intervals[2] = new int[] { 8, 10 };
            intervals[3] = new int[] { 15, 18 };

            var result = Merge(intervals);
        }

        /// <summary>
        /// 56 merge intervals
        /// Using C# SortedSet<Tuple<start, end>> to sort all intervals using start time first, and then end time
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public static int[][] Merge(int[][] intervals)
        {
            if (intervals == null || intervals[0] == null || intervals[0].Length == 0)
                return new int[0][];

            var sorted = new SortedSet<Tuple<int, int>>();
            var list2 = new List<Tuple<int, int>>();
        
            foreach (var interval in intervals)
            {
                list2.Add(new Tuple<int, int>(interval[0], interval[1]));
                //sorted.Add(new Tuple<int, int>(interval[0], interval[1]));
            }
            
            sorted = new SortedSet<Tuple<int, int>>(list2); // sort once is better than SortedSet.Add one by one

            var list = sorted.ToList();

            var merged = new List<int[]>();

            var previous = (Tuple<int, int>)list[0];

            for (int i = 1; i < list.Count; i++)
            {
                var current = list[i];

                var overlapped = previous.Item2 >= current.Item1;
                if (overlapped)
                {
                    previous = new Tuple<int, int>(previous.Item1, Math.Max(previous.Item2, current.Item2)); // caught by online judge:[[1,4],[2,3]], output: [[1,3]], Expected: [[1,4]]
                }
                else
                {
                    merged.Add(new int[] { previous.Item1, previous.Item2 });
                    previous = new Tuple<int, int>(current.Item1, current.Item2);
                }
            }

            merged.Add(new int[] { previous.Item1, previous.Item2 });

            return merged.ToArray();
        }
    }
}

Follow up | what to learn using C# API | Leetcode discuss C#
Jan. 20, 2022
There are so many ways to apply sorting using C#. I spent near 30 minutes to go over Leetcode discuss and see what to learn from other.

  1. Array.Sort | Apply rules of sorting, one or two levels;
  2. LYNQ: Order clause, OrderBy, ThenBy, CompareTo, OrderBy, Aggregate
  3. Comparer, or define a class to apply IComparer
  4. SortedSet<Tuple<int, int>>
  5. Others will be added later.
// 1. OrderBy clause
intervals = intervals.OrderBy(x => x[0]).ToArray();

// 2. List.Sort API
var input = new List<Interval>(intervals);
    if(isFirst){
        input.Sort((a, b) => ((Interval)a).start >= ((Interval)b).start ? 1 : -1);
    }
//3. Array.Sort 	
Array.Sort(intervals, (arr1, arr2) => arr1[0].CompareTo(arr2[0]));

// 4. OrderBy
intervals = intervals.OrderBy(x=> x[0]).ToArray();

// 5. Array.Sort
Array.Sort(intervals, (op1, op2) => op1[0].CompareTo(op2[0]));

// 6. Array.Sort
Array.Sort(intervals, (a,b) => a[0] - b[0]);

// 7. LYNQ OrderBy 
var sortedIntervals=intervals.ToList().OrderBy(x=>x[0]).ToList();

// 8. LYNQ OrderBy, Aggregate
return intervals.OrderBy(x => x.start).Aggregate(new List<Interval>(),

// 9. Array.Sort
Array.Sort(intervals,(x,y)=>{
            if(x[0]==y[0])
                return x[1].CompareTo(y[1]);
            else
                return x[0].CompareTo(y[0]);
        });
		
// 10. Array.Sort API and also Comparer class
Array.Sort(intervals, (x, y) => Comparer<int>.Default.Compare(x[0], y[0]));

// 11. Define class Comparer to implement IComparer interface
Array.Sort(intervals, new Comparer());
public class Comparer : IComparer  {
  int IComparer.Compare( object x, object y )  {
      return( ((int[])x)[0] - ((int[])y)[0]);
  }
}
// 12. Define class Interval, order by Start first, next order by End if needed
intervals = intervals.OrderBy(x => x.Start).ThenBy(x => x.End).ToList();
class Interval
{
    public readonly int Start;
    public readonly int End;
    
    public Interval(int start, int end)
    {
        Start = start;
        End = end;
    }
}

I will look into more carefully about C# sorting techniques in short future. I choose to use C# SortedSet<Tuple<int, int>> instead of using IComparer. C# System.Lynq is very good choice to write working code if I have time to learn more and practice more.

Tuesday, December 8, 2020

Leetcode discuss: 715. Range Module

 Here is the link. 

First practice - C# - study and learn - copy ideas

Dec. 7, 2020
Introduction
It is hard for me to find time to work on my own practice. I have to go over 30 hard level algorithms based on Leetcode premium.

Learn from a competitive player
It is easy for me to practice the algorithm by rewriting a C# solution to fit my own need. I chose to study the code here.

Time complexity
Let K be the number of elements in ranges.
addRange and removeRange operations have O(K) complexity. queryRange has O(logK) complexity, if using binary search. But my approach is O(K).

Because addRange, removeRange adds at most 1 interval at a time, you can bound these further. For example, if there are A addRange, R removeRange, and Q queryRange number of operations respectively, we can express our complexity as O((A+R)^2 Q log(A+R)).

Space Complexity: O(A+R), the space used by ranges.

public class RangeModule {

    private List<int[]> intervals;
    
    public RangeModule() 
    {
        intervals = new List<int[]>();
    }
    
    /// AddRange - 
    /// first just add interval to the list;
    /// next sort the range by  start value. 
    /// merge intervals - overlap / non-overlap 
    public void AddRange(int left, int right)
    {
        intervals.Add(new int[] {left, right});
        
        // sort by start value - O(nlogn) - time complexity        
        intervals.Sort((x, y) => x[0].CompareTo(y[0]));
        
        int start = intervals[0][0];
        int end   = intervals[0][1];
        
        var temp = new List<int[]>();
        for(int i = 1; i < intervals.Count; i++)
        {
            int nextStart = intervals[i][0];
            int nextEnd   = intervals[i][1];
            
            // no overlap 
            if(nextStart > end)
            {
                temp.Add(new int[] {start, end});
                
                // next iteration
                start = nextStart; 
                end = nextEnd;
            }
            else
            {   // update first interval end value - leave merge for future
                end = Math.Max(end, nextEnd);
            }
        }
        
        temp.Add(new int[] {start, end});
        intervals = temp;
    }
    
    /// make sure that [left, right] is inside one of the intervals
    public bool QueryRange(int left, int right) 
    {
        for(int i = 0; i < intervals.Count; i++)
        {
            var start = intervals[i][0];
            var end   = intervals[i][1];
            
            if(IsOverlap(start, end, left, right))
            {
                int l = Math.Max(start, left);
                int r = Math.Min(end, right);
                
                if(l == left && r == right)
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    public void RemoveRange(int left, int right) 
    {
        var temp = new List<int[]>();
        for(int i = 0; i < intervals.Count; i++)
        {
            int start = intervals[i][0];
            var end   = intervals[i][1];
            
            if(IsOverlap(start, end, left, right))
            {
                int l = Math.Max(start, left);
                int r = Math.Min(end, right);
                
                // 0, 1, 2 intervals three choices 
                if(l > start)
                {
                    temp.Add(new int[] {start, l});
                }
                
                if(r < end)
                {
                    temp.Add(new int[] {r, end});
                }
            }
            else 
            {
                temp.Add(new int[] {start, end});
            }
        }
        
        intervals = temp;
    }
    
    /// checking is to check if it is not overlapped
    /// either [start1, end1] is left side of [start2, end2], or right side of [start2, end2]
    private bool IsOverlap(int start1, int end1, int start2, int end2)
    {
        return !(start2 >= end1 || start1 >= end2);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.AddRange(left,right);
 * bool param_2 = obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */

Sunday, July 10, 2016

Leetcode 56: Merge Intervals

July 10, 2016

Leetcode 56: Merge Intervals

study the code:
http://xiaoyaoworm.com/blog/2016/06/27/%E6%96%B0leetcode56-merge-intervals/
https://gist.github.com/jianminchen/a75a3ff78dbb863774b3b97da0d150f8

Write down C# code - 20 minutes workout later.

Sept. 24, 2016

The idea is the following:
1. Sort the list of intervals by start value;
2. Do iteration in the following
base = first.interval
foreach(interval in list)
{
    if base.end < interval.start
   {
      result.add(base);
      base = current;
      base
      ___________
                                current
                                _____________
    }
    else
    {
        (1)   base
              ------------------------
                          current
                      ---------------------
        (2) base
            ____________________
                     current
                  _________
          _____________________
             new base
     }
}

Have some drawing to analyze the problem.

blog reading:

http://www.canadianbusiness.com/leadership/office-space/microsoft-canada-vancouver/

http://www.canadianbusiness.com/leadership/office-space/jordan-banks-facebook-canada/image/2/

Editorial Notes:
1. Julia, could you write down your experience about this problem solving?
Answer: Julia spent 8+ hours to work on the HackerRank world code sprint #7 problem solving.

The idea is to find most simple task you can complete:

Two intervals are not overlapped, so left one should be added to result collections, and move to next one. In order to find the first one, sort the intervals using start time.


Sunday, January 22, 2017

Code Review: Leetcode 56: Merge Intervals (II)

January 22, 2017

Introduction
Julia chose to study 13 questions posted by Gilad, reputation over 700. (the link is here), she came cross the code review: Finding overlapping time intervals. So, she likes to relate to her own practice. She did some work on Leetcode 56: Merge Interval, so she investigated how her practice was. One fact is that she had not made any submission through leetcode online judge on the algorithm. Her practice was too closed and had zero impact, and she decided to make changes this time.  

Workout

Julia's C# practice, code is  here.

Highlights of practice:

1. Julia studied the Java code, and then tried to figure out how to write a C# comparator. She figure out that it is better to use LINQ instead of comparator. She studies the post on stackoverflow.com.

2. Julia tried Leetcode online judge, first test case failed, when the intervals has only one interval. And then, Julia added edge case. line 92 - 93.

3. Julia submitted Leetcode online judge again, failed test case: two intervals, [1,4], [0,4], the merged interval should [0,4], not [1,4]. Forgot to use sortedIntervals, instead of using intervals. How to avoid this kind of writing issue.

Code review on stackexchange.com, link is here.

January 23, 2017

Code review is here; and C# code is here. She got 7 up-votes and 3 answers in less than 24 hours.

A new study

1. Study C# code review completed by Nick Udell, review link is here.

2. Study tag - inteval questions, review link is here.


Sunday, January 31, 2016

Sunday - Algorithm day (4) - 25 algorithms study

Feb. 13, 2016

  Algorithm Sunday, work on it, not just Google. Think by yourself first, work hard on it first.

1. Maximum number of overlapping intervals

For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5).
Recall Leetcode merge interval

Good solutions maybe: Using two arrays, one is to sort interval by start, another is by end.

2. Merge two sorted linked lists





Julia's practice:


3. LRU Cache Miss

Read blogs about LRU first:


This blog is excellent. Julia will write the implementation in C#.



4. Leetcode 64: Minimum Path Sum


5. Disk scheduling algorithm: Round Robin


6. K closest point


Read blogs on this website:
blog 

Julia could not believe that she always reads excellent code, and then, also great stories how technologies are different.



7. Rearrange array - 区分正负数


 8. Window sum 



9. Rearrange array in alternating positive negative items with O(1) extra space



idea: 如果用O(1)的话那需要有一个pointer指向第一个错误的数字,比如偶数index的正数和奇数index的负数。然后碰到当前的数如果符号和错误的那个数不一样,那就rotate那段sub array。

10. Iterative binary tree traversal


12. Trie - Java Implementation




O(n)的解法,很巧妙,利用数组的特性,暂且称之为“派送法”哈哈,派送A[i]到A[A[i]-1]。




16. HeapSort


Read 10 minutes lecture notes. 



about partition, quick sorting:
Julia'sblog and her quick sorting partition explanation with a test case.


18. Merge Intervals

上来给一串start time - end time,格式是Apr 2010 - Mar 2011这种,要求计算出这些时间的总跨度,重叠的跨度不重复计算。举例:["Apr 2010 - Dec 2010", "Aug 2010 - Dec 2010", "Jan 2011 - Mar 2011"]这一个string数组,结果为(12-4+3-1)=10个月。一出这题有点蒙,感觉代码量很大,时间又不多了,只能硬着头皮上。写完string->time的解析函数之后,发现其实就是一道mergeinterval的题.

19. 
写一个函数,给一个node,代表一个人,返回他linkedin 或者facebook network

BFS - graph traversal 
如果一个用户 用这个api,那个node 的朋友很多,million to billion 级别,那么response感觉很慢怎么办? 

20. validBST

如果有duplicate 而且 duplicate return false 的时候会 failed 一个corner case

21. Given a tree, find the smallest subtree that contains all of the tree's deepest nodes.
                  a
               /  |  \
             b   c   d
           /   \       |
         e      f      g
       /       /  \
      h      i     j

depth of tree: 4
deepest nodes:[h,i,j]
least common ancestor of [h,i,j]:

return: b

leetcode
上面哪个lowest common ancestor of binary tree

22. insert node in circular list
, 

23. LRU miss count

输入 maxSize, input int array 
输出是miss cout

example:   size = 4, input array   【1,2,3,4,5,4,1】
1 miss
2 miss
3 miss
4 miss
5 miss  替换 1
4 hit    把4提前到第一位
1 miss  替换 2
大概就是这样。。。

February 2, 2016
Read blogs:


February 2, 2016




24.
8 个 cell  
example:【0,1,1,1,1,1,1,0】
规律每天变化:两边相同--》0, 两边不同--》1
输入:8个cell,  天数n

问n天后cell长啥样

ps:两端cell两边假设const = 0;

小example:
day0:  (0)0,1,1,1(0)
day1:  (0)1,1,0,1(0)
day2:  (0)1,1,0,0(0)

25. Longest path from root to leaf in binary tree


Feb. 17, 2016
Check out topcoder training about testing cases, maybe, use it for a while for practice.