Given two sorted lists of intervals, List A and List B, the intervals in each list are not overlapped or disjoint. Find the overlapping intervals between A and B

When we see two sorted arrays/Lists, naturally we can think of anther problem that we know how to solve — merge two sorted arrays.
Thus, we can use two pointers to do this problem. We now how to move the pointers according to the ending time of each interval. If A[i].end < B[j].end, we move i because B[j] may have additional time period to overlap with different interval from A.
Secondly, we can easily get the overlapping interval by:

Interval a = [s1, e1], b = [s2, e2]
If s2 <= e1 and s1 <= e2 then,
overlap interval = [max(s1, s2), min(e1, e2)]


Instruction for a robot movement
L : turn left, R: turn right, G: go straight for 1 step
Given sequence of instruction will be repeated indefinitely.

Goal: given a sequence of instructions, check if robot forming a cycle.

if after one scan of execution, the robot faces different direction than starting direction(north), then won’t form a cycle.
or if the starting position and the ending position is the same, it forms a cycle

define four directions: [<(0, 1), north>, <(1, 0), east>, <(0, -1), south>, <(-1, 0), west>]
as we know the initial direction is always north, so use a variable to represent the direction, cur = 0, here 0 is the index in the direction array.
loop thru each instruction char, and change the cur accordingly
use (x, y) to represent position, and update the x, y when G is encountered.


Goal: Find the numbers of subarrays that sum up to k. Array is an int array and has duplicates and negative numbers.

when negative numbers are allowed, then we cannot use the sliding window method because we can’t decide the right boundary of the window. Thus, we need a way to guarantee the windows can be closed. So prefix sum is good approach since prefix[i] — prefix[j] == k is a fix window.

Maintaining a hashmap storing <prefix sum: count>, similar to two sum approach, to check complement.
if prefix_sum_so_far == k: cnt++
if prefix_sum_so_far — k in the hashmap: cnt += hashmap[prefix_sum_so_far — k]
insert prefix_sum_so_far into hashmap