As I am waiting for my work pass to be issued, I have some spare time to kill now. Therefore, I have been doing some Leetcode questions for fun and also encounter some interesting algo techniques such as Line Sweep Algorithm and Fenwick Tree. As I continue to solve them and encounter more interesting algos, I will update this page :)
Sliding Window
This technique is useful if you need to maintain a window (i.e. a contiguous sequence) with some conditions. Most questions that are related to substring, subarray, contiguous sequence of 1s usually can be solved using this technique (+ probably combination with other techniques such as 2 pointers).
Questions
Union Find Disjoint Set (UFDS)
UFDS is a data structure that models disjoint set. This data structure is very useful to solve questions that requires/enquires some connectivity. Usually, you need to model the problem as graph first before using UFDS to solve it.
Following is the implementation of UFDS with path-compression (there are more optimizations such as union by rank but this should be enough for most leetcode questions).
class UFDS:
def __init__(self, n: int):
self.parents = [i for i in range(n)]
def find(self, i: int) -> int:
if self.parents[i] != i:
self.parents[i] = self.find(self.parents[i])
return self.parents[i]
def union(self, i: int, j: int) -> None:
self.parents[self.find(i)] = self.find(j)
Questions
String Matching
String matching by itself is not a technique, but a category of questions. However, in string matching questions, there are several algorithms and data structures that are very useful.
Trie (Prefix Tree)
Trie is very efficient in performing certain operations over large amount of strings dictionary. Some important queries are prefix matching, word search, and autocomplete. Following is simple implementation of Trie on Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
current_node = self.root
for char in word:
if char not in current_node.children:
current_node.children[char] = TrieNode()
current_node = current_node.children[char]
current_node.is_word = True
# For additional functionalities such as word search and prefix matching, you need to traverse the trie similar to the insert routine above
Questions
Knuth-Morris-Pratt (KMP) string-searching algorithm
Traditionally, this algorithm is used to find occurrences of a “pattern” string of length M within a “text” string of
length N. But, it can be modified to return a list of integers representing the longest prefix matching length in the
pattern at index i. For example, if the pattern is “AAA” and the text is “ABBAAA” then it can
return [1, 0, 0, 1, 2, 3] whereas the conventional KMP will just return [5] This algorithm can run in O(N + M)
whereas naive string matching runs in O(N * M)
Useful resource: KMP Algorithm
Following is the implementation of modified KMP to return length of prefix matching
def kmp(pattern, text):
k = 0
lps = [0] # longest prefix suffix aux array
for i in range(1, len(pattern)):
while k and pattern[k] != pattern[i]:
k = lps[k - 1]
if pattern[i] == pattern[k]:
k += 1
lps.append(k)
k = 0
prefix_matching = []
for i, ch in enumerate(text):
while k and (k == len(pattern) or pattern[k] != ch):
k = lps[k - 1]
if pattern[k] == ch:
k += 1
# conventionally, if k == len(pattern), add them to the "matched" array
prefix_matching.append(k)
return prefix_matching
Questions
Interesting Questions and Methods
Printing a Singly Linked List in Reverse Order with Space Complexity < O(N)
I encounter this question during an interview and I thought it’s pretty unique. On the surface, it looks really trivial until you are asked to solve it with space complexity $< O(N)$. This question does not rely on any programming language features.
The idea is similar to sqrt decomposition. Suppose the length of the LL is $N$. If we divide the LL into $K$ parts,
the space complexity to print the entire LL in reverse order is $N/K + K$
- $N/K$ to print the LL using stack or recursion
- $K$ to save the head pointers to each sublist
The big brain part is, note that $N/K + K$ is a convex function where $K > 0$. To find the optimal $K$, do $d(N/K + K)/dK = 0$ and solving this equation will give $K = \sqrt{N}$. Therefore, the total space complexity now is $N/\sqrt{N} + \sqrt{N} = 2 * \sqrt{N} = O(\sqrt{N})$ !! Really amazing right!!
Find the Largest Palindrome Divisible by K
This question comes up in LC weekly contest 411, and I thought it’s fascinating. My first instinct to solve this problem is to employ divisibility rule and try to pattern for each $k$. However, upon reading the hints, they mentioned that we can use string dp.
Let’s define $dp(i, mod)$ as whether starting from digit $i$ (and hence also digit $n - i - 1$ by definition of palindrome) with some remainder $mod$ is able to form palindrome number that is divisible by $k$. The interesting trick that I found from other people here, to get the biggest palindrome, we check the number recursively by iterating the number in strictly decreasing order. The core of the solution code can be seen below :)
...
choice = [None] * n
@cache
def dp(i, mod):
if i == half_length:
if mod == 0:
return True
return False
digit_pos = set([i, n - 1 - i])
for d in range(9, -1, -1):
cur_mod = 0
for pos in digit_pos:
choice[pos] = d
cur_mod += pos_mod[d][pos]
if dp(i + 1, (cur_mod + mod) % k):
return True
return False
...
Fascinating!! To combine dp technique with some external state!!
Advanced Algorithms
I personally never encounter these algorithms in any software engineering interviews. But I thought it’s quite interesting, so I will publish it here too :)
Finding Articulation Point
Tarjan’s algo to find articulation points (a node where if it’s deleted from the graph $G$, will increase the connected components in $G$).
Questions
Sieve of Eratosthenes
Conventionally, sieve of Erathosthenes is an algorithm to find all prime numbers from 1 to $N$. However, it can be modified to find many numbers does each number in the given array can divide. To solve this question, traditionally you can use $O(N^2)$ double for-loop but using sieve of Erathosthenes, the runtime is cut down to $O(N log log N)$.
Questions
The important trick in this question is to find how many pairs that have a GCD of $N$. Using Sieve of Erathosthenes and dynamic programming, this problem can be solved in $O(N log log N)$. The snippet for the important trick can be found below :)
def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
max_number = max(nums)
counter = [0] * (max_number + 1)
for el in nums:
counter[el] += 1
# divisor_counter[i] represents how many numbers can i divides in all of nums
divisor_counter = [0] * (max_number + 1)
for i in range(1, max_number + 1):
mul = 1
# Note: this is the Sieve of Erathosthenes
while i * mul <= max_number:
divisor_counter[i] += counter[i * mul]
mul += 1
# dp[i] represents how many pairs that have gcd of i
dp = [0] * (max_number + 1)
for i in range(max_number, 0, -1):
# initially, total pairs is (N * (N - 1)) / 2
# For example, in 2 4 4 => there are 3 * 2 / 2 = 3 pairs
dp[i] = divisor_counter[i] * (divisor_counter[i] - 1) // 2
mul = 2
# Note: this is the Sieve of Erathosthenes
while i * mul <= max_number:
# Reduce the current pairs by pairs with larger gcds
dp[i] -= dp[i * mul]
mul += 1
...
Reflection
To be honest, I used to be afraid to face technical interviews that involve leetcode questions. I used to believe that my algo is not as strong as the others. But most of the time, I just give up too easily and do not want to think. Whenever I encounter really hard questions, I just look at the editorial or answer key. I regret it and that’s why now I am determined to really practise my algos, while it is true that most of these algos won’t be useful at work, I believe that practising algo allows me think really systematically and to be a problem solver.