**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 —

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)]**

**Algorithm**

**Problem**:

Given a string `s`

, rearrange the characters of `s`

so that any two adjacent characters are not the same.Return *any possible rearrangement of* `s`

*or return* `""`

*if not possible*.

**Intuition**:

Use least frequent characters to fill the gap between most frequent characters.

**Discussion:**The most frequent characters in the…

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.

Code:

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

Code:

**Goal:**

Given an array of integers, count number of subarrays that have sums that are divisible by K, where 2 ≤ K ≤ 10000. The subarray size should be at least 1.

**Intuition: **The naive way is to try all the subarrays in nested loops. That will take O(n³).

That is…

**Goal:**Given an array of non-negative integers, find the lexicographically next permutation. If no such permutation, return the ascending order permutation.

**Intuition:**1.

2. …

**Goal: **Given an array of non-negative integers which represent histograms with width of 1 and height of the integer value. Find the largest area of any consecutive histograms can form.

**Intuition:**Max area must use one of the histogram as the height, thus we can calculate areas formed with every histogram…

**Goal: **Given an integer array and window side of K, find the max values for every window in the array. Return the max values array.

**Intuition: **For window of size k ending with [i], the max of this window must ≥ [i] and must be within the window borders. …

**Goal: **find the size of shortest subarray in given array that sum up to at least K, where negative integer is allowed.**Reasoning for techniques used: 1. Prefix sum: **Because negative number is allowed. This causes a problem that you don’t know when to stop expanding or shrinking the window. It’s…

**Goal**:

Find the minimum length substring in s that will cover all the characters in t.

Represent three states of the problem: **zero**: just meet the needs**positive**: needs**negative**: extra or not needed

**Algorithm**:

1. Use an array/list of size 128 to represent all types of characters and initialize the…