Hard deck Flashcards
Merge k sorted lists
Idea:
Instead of iterating over each of k lists one by one, we can try merging a set of 2 lists and then merge these merged lists and so on
Algorithm:
-define mergeList function with two lists l1 and l2 params as follws
-declare a new empty dummy node and assign it to tail
-while l1 and l2
-if l1.val<l2.val, then tail.next = l1, l1 = l1.next
-else tail.next = l2, l2 = l2.next
-end if else
-tail = tail.next
-end while
-if l1, tail.next = l1
-if l2, tail.next = l2
-return dummy.next
-if not lists or len(lists) is 0, return None
-while len(lists) > 1
-mergedLists = []
-for i from 0 to len(lists) with step of 2
-l1 = lists[i]
-l2 = lists[i + 1] only if i + 1 < len(lists) else None
-add mergeList(l1, l2) to mergedLists array
-end for
-lists = mergedLists
-end while
-return lists[0]
Median of two sorted arrays
Idea:
Aim is to find the left partition without merging two arrays. We find the partition in one array using binary search, and then the other based on length. Then we change binary search conditions based on the whether the partition has been correct or not
Algorithm:
-Assign both the arrays to A and B
-keep smaller one in B
-calculate total and half length
-initialize l and r to binary search on A
-while True
-i = (l + r) // 2
-j = half - i - 2 (i.e. the remaining partition in the B)
-Aleft = A[i] if i >= 0 else float(‘-inf’)
-Aright = A[i + 1] if (i + 1) < len(A) else float(‘inf’)
-Bleft = B[j] if j >= 0 else float(‘-inf’)
-Bright = B[j + 1] if (j + 1) < len(B) else float(‘inf’)
-if Aleft <= Bright and Bleft <= Aright, (partitions are correct)
-if total is odd, return min(Aright, Bright)
-else, return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
-end if else
-elif Aleft > Bright, r = i + 1 (A partition is bigger than needed)
-else l = i + 1 (A partition is smaller than required)
Word search 2
Idea:
Using original word search for each is inefficient. Use trie to first store the words given, and then run dfs on each cell and evaluate whether the word is formerd or not
Algorithm:
-Define TrieNode class
-constructor, define children as set and isWord boolean
-define the addWord function
-Initialize root TrieNode and run addWord on each provided word
-Get rows and cols, and define answer and visited as set
-Define dfs function with params r, c, word and node as follows
-if not in bounds or (r, c) in visited or current position not in node.children, return
-add (r, c) to visited
-node = node.children[board[r][c]]
-word += board[r][c]
-if node.isWord, add word to answer
-call dfs in four directions
-remove (r, c) from visited (Backtracking)
-Double loop for through rows and columns
-call dfs on each with root and “” as other params
-return list(answer)
Find median from data stream
Idea:
Data is not ordered, so instead of using an array. We will use two heaps
Small heap will be a max heap
Large heap will be a min heap
Each element in small heap will be less than the smallest in large heap
Solution:
1. INIT
-just initialize two heaps, small and large
- ADD NUM
-push -1*num to small heap
-if small and large exists and (largest in small ) > (smallest in large), then pop from small and insert into large
-if small heap longer than large heap + 1, pop from small and insert to large
-if large heap longer than small heap + 1, pop from large and insert into small - FIND MEDIAN
-if small heap longer, return largest in small
-if large heap longer, return smallest in large
-else, return (largest in small + smallest in large) / 2
Word ladder
Idea:
We need to find the words which differ from each other by only one letter, so e.g. hit and hot, follow the pattern h*t.
So we will build an adjacency list of such patterns and then use bfs to tranverse the graph and find the shortest path
Algorithm:
-if endword not in wordList, return 0
-declare nei as default dict
-append beginning word to wordList
-for every word in wordList
-for j at every position in the current word
-pattern = word[:j] + ‘*’ + word[j + 1:]
-nei[pattern].append(word)
-end for
-end for
-declare visited set and a queue and add beginword to it, declare answer as 1
-while queue
-for i in range(len(q))
-word = popleft()
-if word is endword, return answer
-for j at every position in current word
-create patttern
-for every neighbor in nei[pattern]
-if neighbor not visited, add neighbour to visited and queue
-end if
-end for
-end for
-increment answer
-end while
-return 0
Integer to english words
Idea:
We need to do some repeated work every three digits
So we first extract the last 3 digits, construct a string and then repeat
Algorithm:
-if num is 0, return “Zero”
-define ones_map as {number: string} for numbers 1 to 20
-define tens_map as {number: string} for numbers 20, 30, …., 90
-define get_string function with number for param as follows
-res = []
-hundreds = n // 100
-if hundreds, res.append(ones_map[hundreds] + “ Hundred”)
-end if
-last_2 = n % 100
-if last_2 >= 20
-tens, ones = last_2 // 10, last_2 % 10
-res.append(tens_map[tens * 10])
-if ones, then res.append(ones_map[ones])
-elif last_2, res.append(ones_map[last_2])
-end if else
-return “ “.join(res)
-define postfix as [””, “ Thousand”, “ Million”, “ Billion”]
-i = 0
-answer = []
-while num
-digits = num % 1000
-s = get_string(digits)
-if s, answer.append(s + postfix[i])
num = num // 1000
i += 1
-end while
-answer.reverse()
-return “ “.join(answer)
Minimum window substring
Idea:
We use two pointer approach along with the hashmaps. Build map of string t and keep changing window simultaneously. Move right till be have all we need. Then we move left until we are missing something. This way, we get minimum
Algorithm:
-if t empty, return “”
-define hashmaps for count_t and window
-construct count_t hashmap
-declare have and need as 0 and len(count_t)
-declare answer and answer_len as [-1, -1] and float(“inf”) respectively
-l = 0
-for r in range of length s
-c is character at r
-window[c] += 1
-if c in t hashmap and count_t[c] equals window[c], have += 1
-while have == need
-if (r - l + 1) < answer_len, reassign answer and answer_len
-window[s[l]] -= 1
-if s[l] in t hashmap and window[s[l]] < count_t[s[l]], have -= 1
-l += 1
-end while
-end for
-l, r = answer
-if answer is float(“inf”), return “” or return s[l : r + 1]
Binary tree maximum path sum
Idea:
Do a dfs to return the maximum sum without the split. Calculate the maximum sum with the split every time and change the global variable if needed
Algorithm:
-answer = root.val
-define dfs function with root for param as follows
-nonlocal answer
-if not root, return 0
-recursively calculate left_max and right_max
-reassign left_max to max of itself or 0, and same for right_max
-answer = max(answer, root.val + left_max + right_max)
-return root.val + max(left_max, right_max)
-dfs(root)
-return answer
Serialize and deserialize binary tree
Idea:
Use preorder traversal to recursively construct the array and then the string. Replace the None with N. Do the same backwards
Solution:
1. Serialize
-res = []
-define dfs with node for param as follows
-if not node, res.append(“N”), return
-res.append(str(node.val))
-dfs(node.left)
-dfs(node.right)
-dfs(root)
-return “,”.join(res)
- Deserialize
-values = data.split(‘,’)
-self.i = 0
-define dfs function as follows
-if values at self.i is “N”, inc self.i, return None
-node = TreeNode(int(values[self.i]))
-inc self.i
-node.left = dfs()
-node.right = dfs()
-return node
-return dfs()
Alien dictionary
Idea:
Build an adjacency list based on the words provided. Then perform topological sort and post order DFS
Algorithm:
-construct adjacency list for all the letters as follows adj = {c: set() for w in words for c in w}
-for i in range(len(words) - 1)
-w1, w2 = words[i], words[i + 1]
-minLen = min(len(w1), len(w2))
-if len(w1) > len(w2) and w1[:minLen] == w2[:minLen], return””
-for j in range(minLen)
-if w1[j] != w2[j]
-adj[w1[j]].add(w2[j])
-break
-end if
-end for
-end for
-declare visited and answer as empty dictionary and array respectively
-define dfs function with c for param as follows
-if c in visited, return visited[c] (False if just visited, True if in current path, thus cycle)
-visited[c] = True
-for nei in adj[c]:
-if dfs(nei), return “”
-end for
-visited[c] = False
-answer.append(c)
-end func
-for c in adj:
-if dfs(c), return “”
-end for
-answer.reverse()
-return ““.join(answer)
