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 previous runs may not be the most frequent characters in later runs because we already place some of them so the frequency decreased thus it may not be the most frequent one any more. We need a data structure that can reflect on that when frequency goes down and to…
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 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.
The naive way is to try all the subarrays in nested loops. That will take O(n³).
That is very inefficient. We can use additional data structure to reduce the time complexity. Mathematically, we have the following relation:
(a + n*k) % k == a % k
According to above relation, we can see that if two number have same remainder, their difference must be divisible by k…
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.
2. we want to find the permutation is as little lexicographically greater as possible than current one, thus the position changed should be as right-side as possible.
1. Find the first position, pos , that starts to increase from back of the array so that the subarray [pos+1: ] is a non-increasing sequence meaning that it does not have next…
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 as the height and find the max area.
The area of consecutive histograms can be expressed with following formula.
area = min(consecutive histograms) * distance between two ends.
The height of the area is determined by the shortest height among the consecutive histograms.
Maintain a non-decreasing stack and…
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. All the numbers that are less than [i] are irrelevant.
For naive solution, we just find the max value for each window size of k. It takes O(n*k), which is not good enough for this problem. We are aiming for linear solution for given input size (10⁵). Notice that…
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 difficult to do sliding window technique.
However, we know that prefix_sum[i] - prefix_sum[j] is a good choice of window representing sum of elements between [j]…[i-1].
2. Mono-Non-decreasing double-ended queue:
A mono increasing sequence have a trait that first and last elements has the longest distance and largest sum difference…
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 array with zeros.
2. Create the characters to count mapping using the array above.
3. Loop thru the string s.
if current char in the mapping is greater than 0 meaning that current char is needed, so decrement the need and the char count by 1, otherwise only decrement the char count by…