Medium Flashcards
How to solve problems of the form “Longest Substring with At Most x Distinct Characters”?
- Sliding window with hash map holding the right most position of each char. When we hit x+1 distinct chars remove the left most from the hash map and continue.
How to solve a problem where we are given two strings s and t, return true if they are both one edit distance apart, otherwise return false?
- One pass algorithm: find diff and check substring after it. Note to handle different string lengths.
- Dynamic programming (general edit distance ): It turns out that one could compute D[i][j], knowing D[i - 1][j], D[i][j - 1] and D[i - 1][j - 1]. Note, when w[i] != w2[j] we have to handle the replacement case by subtracting one D[i - 1][j - 1] - 1.
How to reverse a string of words in-place?
Reverse the whole string and then reverse each word.
How to create a data structure with words in order to compute the shortest distance between them in the original array?
- Using preprocessed sorted indices and two pointers progressing through the two arrays based on which index is higher until both arrays have been processed completely.
How to find all n strobogrammatic number? Numbers that are the same when rotated 180 degrees.
Use dfs search to build the strings. The base case is when ‘l’ and ‘r’ are the same. And the strings are build from both ends at the same time (left and right).
How to group strings based on their shifting sequence?
Encode the different between each char of the string as a list of differences (diff = 26 + str[i] - str[i - 1] % 26). Use this as the key to a hashmap.
How to find the distance between to chars in the alphabet?
Add the alphabet length to the int value of the char and subtract the other char’s int value. Then modulo the result by the alphabet length.
How can we call a position in an array a “good index” if starting at that position, we can reach the last index. Otherwise, that index is called a “bad index”.
- Dynamic programming: Define the end index as good and start from it moving backwards. At each index ask what is the furthest i can travel from this index and is there a good index on the way. As soon as we find a good index we stop and continue moving backwards. O(n^2)
- Greedy: Keep track of the left most good index then ask at each index if we can travel to it. O(n)
How can we calculate the minimum number of jumps required to reach an end index?
- Dynamic programming: Same as with finding a good index, instead we calculate the min jumps required at each index, and when we calculate if we can reach a good index, we look further to see if we can find a better index on the path.
- Greedy: Keeping taking the best jumps along the way.
How to calculate maximum subarrray of a circular array?
- Kadane’s algorithm with modifications:
- Use algorithm with n start and end points with modulo on each index. To find the max subarray from each start and end position (O(n^2)).
- Circular subarrays are either viewed as one-interval subarrays or two-interval subarrays depending on if we go past the end of the array to represent the subarray.
- We can also view the problem as Kadane’s algorithm on a fixed array but the original doubled to form A + A array.
- Find the minimum subarray sum and subtract it from the total array sum, then we have the max sub array sum with the circular array. (Note boundary case where are values a negative, here simply return the smallest negative value). (We can implement it by inverting each element).
What is a monotonic queue?
A data structure where the elements from the front to the end are strictly increasing or decreasing.
How to calculate the maximum product subarray?
Realize the we look for combos of numbers that give the max sub array. The only types of numbers that can break a combo are negative numbers and zeros. Zeros completly stop a combo, but negative numbers can potentially result in a positive number down the line, så we need to track both the current max and current min numbers and select the max of them as the overall result each time.
How to calculate the largest length subarray where the product is positive?
Reset the counts on zero. Keep track of positive and negative occurrences and swap the count of positive and negative on every negative number (simulating a sign shift). Note, also increment the opposing sign count if it is different from zero, in order for swapping to work.
How can we separate substrings of a given string with strings from a dictionary?
- Brute-force recursive backtracking: for every letter check both if the substring until now can be found in the dictionary or include it in the substring and recurse on the next letter.
- Use BFS: Builld a tree of prefixes. For each substring check if it is in the dictionary and build a tree with prefix of substring length.
- Dynamic programming: We can divide the problem into subproblems s1 and s2. If these subproblems dsatisfies the condition.
How to do we solve a problem when we have to consider the height of elements before and after our current element?
- Brute-force: Iterate entire array and find an element before our current element and find an element after our current element in (N^2) complexity.
- Use stack: We can use stack to keep track of the bars that are bounded by longer bars and hence, may store water.
- Use two pointers: We can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right).
- Use dynamic programming: Precompute and store the left and right maxes from the brute force apprach.
