两个区间之间存在 6 种可能情况。取交集时，start = max(a.start, b.start); end = min(a.end, b.end)。

This pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.

Given two intervals (“a” and “b”), there will be six different ways the two intervals can relate to each other:

Understanding the above six cases will help us in solving all intervals related problems.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

n = len(intervals)
ans = []

i = 0
# case 1
while i < n and intervals[i][1] < newInterval[0]:
    ans.append(intervals[i])
    i += 1
# case 2-5
while i < n and intervals[i][0] <= newInterval[1]:
    newInterval[0] = min(newInterval[0], intervals[i][0])
    newInterval[1] = max(newInterval[1], intervals[i][1])
    i += 1
ans.append(newInterval)
# case 6
while i < n:
    ans.append(intervals[i])
    i += 1

return ans

LeetCode

56. Merge Intervals
57. Insert Interval
986. Interval List Intersections
435. Non-overlapping Intervals
253. Meeting Rooms II
1094. Car Pooling
759. Employee Free Time

掌握判环以及判环的变形。while 循环的条件往往是 r and r.next 存在，过程中可以顺便获取 middle pointer。

The Fast & Slow Pointers approach is a pointer algorithm that uses two pointers which move through the array (or linked list) at different speeds. This approach is quite useful when dealing with cyclic linked lists or arrays.

By moving at different speeds (say, in a cyclic linked list), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

l = r = head
while r and r.next:
    l = l.next
    r = r.next.next
    if l == r:
        break
else:
    return

l = head
while l != r:
    l = l.next
    r = r.next

return l

LeetCode

141. Linked List Cycle
142. Linked List Cycle II
202. Happy Number
876. Middle of the Linked List
234. Palindrome Linked List
143. Reorder List
457. Circular Array Loop

一个很灵活的模式，有序与否都有应用的场景。需要根据题意来决定，while 循环的条件是 l < r 还是 l <= r。

In problems where we deal with sorted arrays (or linked lists) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray. For example, take a look at the following problem:

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

To solve this problem, we can consider each element one by one (pointed out by the first pointer) and iterate through the remaining elements (pointed out by the second pointer) to find a pair with the given sum. The time complexity of this algorithm will be O(N^2) where “N” is the number of elements in the input array.

Given that the input array is sorted, an efficient way would be to start with one pointer in the beginning and another pointer at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do not, we will do one of two things:

• If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a less sum. So, to try more pairs, we can decrement the end-pointer;
• If the sum of the two numbers pointed by the two pointers is less than the target sum, this means that we need a pair with a greater sum. So, to try more pairs, we can increment the start-pointer;

难点大概是 shrink 的时机。窗口大小固定时，借助 end - start + 1；不固定时，借助基于 matched 的 while 循环。

In many problems dealing with an array (or a linked list), we are asked to find or calculate something among all the contiguous subarrays (or sublists) of a given size. For example, take a look at this problem:

Given an array, find the average of all contiguous subarrays of size “K” in it.

Let’s understand this problem with a real input:

1

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

Here, we are asked to find the average of all contiguous subarrays of size “5” in the given array. Let’s solve this:

1. For the first 5 numbers (subarray from index 0~4), the average is: (1+3+2+6-1)/5 = 2.2;
2. The average of next 5 numbers (subarray from index 1~5) is: (3+2+6-1+4)/5 = 2.8;
3. For the next 5 numbers (subarray from index 2~6), the average is: (2+6-1+4+1)/5 = 2.4;
4. …

Here is the final output containing the averages of all contiguous subarrays of size 5:

1

Output: [2.2, 2.8, 2.4, 3.6, 2.8]

Load Balancer (LB) is another critical component of any distributed system. It helps to spread the traffic across a cluster of servers to improve responsiveness and availability of applications, websites or databases. LB also keeps track of the status of all the resources while distributing requests. If a server is not available to take new requests or is not responding or has elevated error rate, LB will stop sending traffic to such a server.

Typically a load balancer sits between the client and the server accepting incoming network and application traffic and distributing the traffic across multiple backend servers using various algorithms. By balancing application requests across multiple servers, a load balancer reduces individual server load and prevents any one application server from becoming a single point of failure, thus improving overall application availability and responsiveness: