How to solve: Given three arrays sorted in increasing order, return a sorted array of only the integers that appeared in all three arrays.
Create three pointers one for each array, thereby exploiting that the three arrays are sorted in increasing order.
We have two cases:
1. All three pointers are the same, then add to result array.
2. Increment the pointer pointing to the lowest value.
How to solve: Given a string s, return the number of substrings that only have one distinct letter.
Two approaches:
1. The number of substrings of s is 1 + 2 + …. + (len(s) - 1) + len(s). This is an Arithmetic sequence (Sum Equation of Arithmetic Sequence) (1 + len(s)) * len(s) / 2.
If a string contains only one distinct letter, all of its substrings are formed by one distinct letter as well. Therefore, to find the number of substrings that contain only one distinct letter, we can first find the longest continuous segments with only one distinct letter; then we can apply Sum Equation of Arithmetic Sequence to to calculate the number of substrings of each segment.
- We can use dynamic programming. Given a string s, we may define an integer array substrings[] with a length of len(s), such that substrings[i] is the number of substrings ending with S[i] which contains only one distinct letter S[i]. Therefore, if S[i] == S[i - 1], substrings[i] would be substrings[i - 1] + 1 else substrings[i] is 1. Total is the sub of all numbers in substrings.
How to get the digits of a number?
- Modulo 10 gives us the last digit. Apply in while loop until N /= 10 is 0.
- Log can be used to get the number of digits in a number. log_10(1) = 0, log_10(10) = 1, log_10(100) = 2, log_10(1000) = 3. Floor(log10N)+1.
How to solve problems where we only need top x of an array list?
- Sorting.
- Max heap.
- Min heap when the heap is full (x items) we simply remove the min value and insert the larger value, thereby we have the top x elements in the end.
How to calculate the moving average of a data stream?
- Add values to a queue and retrieve the window size from the queue adding values together.
- Double-ended queue (dequeue) remove last item as a new item is inserted. Do not iterate the values each time, simply maintain a total and subtract the last value and add the new value.
- Circular queue with array, same principal as double-ended queue, just a fixed size array instead.
How to implement a timestamp rate limiter (only print at most every 10 secs).
- Use a queue and set. The queue represents a sliding window, the first step when a new item arrives is to invalidate the messages that have expired. Next the new item is placed in the queue if it is not already in it. We check if it is a duplicate using the set to accelerate this check.
- Hashtable. Simply store items in a hashtable and query it. This approach does not have proactive cleaning and simply accumulate all items until the end of time.
How to solve a problem of finding the maximum number of items to put into a container weighing less than some value x?
- Sort and greedy.
- Min-heap.
- Bucket sort. O(N) but does not scale since we need a bucket for each distinct value in the array.
How to find the intersection of x number of sorted arrays?
- Brute force with hashmap. Count each item and run through map values including items occurring x times.
- x number of points. Always increment the pointer pointing at the smallest value and if all pointers point at the same value then include and increment all pointers.
How to find missing number in arithmetic progression?
- Linear search. Find expected difference and search array for a pair of numbers not matching this expected difference.
- Binary search. At any position i we can find if the value is correct by taking the first value and adding i times the expected difference. Given this we can perform a binary search for the value.
How to perform a list of operations on a data type that is expensive to naively perform each operations on in succession?
- Compute a list of actions and combine them into a single modification.
How to perform a binary search on a sorted list?
(Most important what is the loop termination condition and how to calculate “mid” from left and right.)
int search(vector& nums, int target) {
int left = 0; int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int curr = nums[mid];
if (curr == target) return mid;
if (curr > target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
What is Kadane’s Algorithm?
(Most important how is the current value and the max values calculated given a new number from the array.)
Solves the maximum continuous sub-array problem.
int c = nums[0];
int m = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int n = nums[i];
c = max(n, c + n);
m = max(m, c);
}
return m;
How to find the maximum sub array using divide and conquer?
(Most important what is the recursive base case, how are best left and right sums calculated, how is the middle part included in the calculation.)
int m(int l, int r, vector& nums) {
if (l > r) return INT_MIN;
int mid = (l + r) / 2;
int curr = 0;
int bestLeft = 0;
int bestRight = 0;
for (int i = mid - 1; i >= l; –i) {
curr += nums[i];
bestLeft = max(bestLeft, curr);
}
curr = 0;
for (int i = mid + 1; i <= r; ++i) {
curr += nums[i];
bestRight = max(bestRight, curr);
}
int bestWithMid = bestLeft + bestRight + nums[mid];
int daL = m(l, mid - 1, nums);
int daR = m(mid + 1, r, nums);
return max(bestWithMid, max(daL, daR));
}
How to rotate an array by k steps?
(Important realize that rotating n steps results in the starting array. Hence only k mod n steps are important)
- Brute force 2 loops
- Use another array to hold the result.
- Use Cyclic Replacements. We can directly place every number of the array at its required correct position.
- Reverse the array, reverse the first k steps, then reverse the remaining array.
How to find numbers adding up to a target number from a list of sorted numbers?
(Best solution is to exploit that the numbers are sorted)
Use two pointers and start the search from both ends.
int idxs = 0;
int idxl = numbers.size() - 1;
while (idxs < idxl) {
int sum = numbers[idxs] + numbers[idxl];
if (sum == target) return {idxs + 1, idxl + 1;
else if (sum < target) idxs++;
else idxl–;
}
How to find the intersection between two lists of numbers?
1.
How to find the middle of a linked list?
- Added to list and get the middle of the list.
- One pointer moves one each iteration and one fast pointer moving two steps each iteration. At the end of the fast pointer the slow pointer will be in the middle of the linked list.
How to handle a bi-directional graph with only edges as input?
Convert edges to a adjacency list for each vertex.
