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)]
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.
Use least frequent characters to fill the gap between most frequent characters.
The most frequent characters in the…
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
Given an array of non-negative integers, find the lexicographically next permutation. If no such permutation, return the ascending order permutation.
1. Notice that non-increasing sequence does not have next greater permutation, and non-decreasing sequence is the smallest permutation.
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.
Max area must use one of the histogram as the height, thus we can calculate areas formed with every histogram…
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…
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
negative: extra or not needed
1. Use an array/list of size 128 to represent all types of characters and initialize the…