Problem: 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
Intuition: When we see two sorted arrays/Lists, naturally we can think of anther problem that we know how to solve —…
Problem: 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.
Intuition: 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
Algorithm: 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.
Intuition: 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.
Algorithm: 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