Amazon Flashcards
(92 cards)
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)
Longest palindromic substring
Idea:
Start with individual letter, expand using l and r pointers continuously checking if the contained string is palindromic or not. Keep saving the max results
Algorithm:
1. For odd substrings
For each character, start with l and r at i
Bounds check and character equivalence check
Decrement l and increment r
- For even substrings
Same but start with l and r at i and i + 1 respectively
Roman to integer
Idea:
If the value of current character is less than the value of character after it, we have to subtract the current value from the result
Algorithm:
Define hashmap of (character, value)
Iterate through the string
If (i + 1) < len(s) and map(curr) < map(next)
answer -= curr
else
answer += curr
String to integer (atoi)
Idea:
We need to get to the point in the string where actual number (if it exists) starts
Algo:
First init result as 0 and sign as 1
First use strip to remove whitespace
Return 0 if no string at that point
Check the signage and assign the sign appropriately
Run the loop on remaining string
result = result * 10 + int(char)
break if the character is not digit
result = result * sign
Check bounds and return
Two Sum (Unsorted input)
NAME?
Integer to roman
NAME?
Valid paranthesis
- Create hashmap of (closing, opening)
- Iterate through string
- if bracket in map
- if stack and top of stack == map(bracket), then pop
- else return False
- else stack append
- Return true of stack empty else false
Valid sudoku
- Start outer loop till 9
- Define set for horizontal and vertical
- Start inner loop till 9
- Check for (i, j) in horizontal set and (j, i) in vertical set
- Return False if exists
- Add to set if not and the position is not ‘.’
-End both loops
For box check
Define a dictionary
- Start outer loop till 9
- a = i // 3
- Start inner loop till 9
- b = j // 3
- If (a, b) not in dictionary, define it as set
- If (i, j) in the dictionary of (a, b), return False
- Else add (i, j) to the (a, b) dictionary
return True
Combination sum
Idea:
- Draw the recursion tree
- We first need to make decision on first element, either include it or not
- And then based on the bounds and current total, make other decision
Algo:
- Define dfs function with current array and total as param
- If the target is achieved, add the current copy to the answer
- If outside bounds or target exceeded
- return
- Decision 1: add the current candidate, and call dfs on it with new total
- Decision 2: pop the element to remove the recently added candidate and call the dfs on i + 1 element
Call the dfs on zeroth element
Permutations
Recursive idea:
We start with the empty combination, add the last element, then add the other on either side of it. Then we add next element to all possible positions within the above result (i.e. at start, middle, end)
Recursive algo:
- Define base case of if len(array) is 0 then return [[]]
- Call the self function and pass the array without the first element. Retrieve the results in the variable (perm)
- Define result as []
- For each p in perm
- For i in len(p) + 1
- Make a copy of p and insert array[0] at i position
- add the updated copy to answer
- end for
- end for
Return answer
Iterative algo:
- answer = [[]]
- for each number
- new_perm = []
- for each answer
- for each position in answer
- make a copy of answer and insert into position the current number and append to new_perm
- end for
- end for
- answer = new_perm
- end for
return answer
Merge intervals
- Sort intervals by start time
- Iterate through the intervals
- Insert 1st interval in the answer
- For rest, if current interval start is less or equal to last interval end, change last interval time to max of either
- else append to answer
Rotate list
Idea:
We need to find the pivot point at length - k, and then reassign pointers, i.e. join end to the start and return new head
Algorithm
Base case: If not head, return head
Calculate length and tail simultaneously
length = 1, tail = head. Run loop till tail.next
k = k % length
if k is 0, return head
curr = head
loop till length-k-1, curr = curr.next
Reassign pointers:
new_head = curr.next
curr.next = None
tail.next = head
return new_head
Minimum path sum
Idea:
Calculate minimum path sum for all the positions in the grid one by one, and eventually, we will have the minimum path sum for bottom right
Algorithm:
- Define dp array
- dp[i, j] = min(dp[i - 1, j], dp[i, j - 1]) + gri[i, j]
(except if the cell is on boundary, in which case it will be directly sum with either the left one or above one)
- Return dp[m - 1, n - 1]
Word search
Idea:
Run the dfs from each position in the grid recursively and compare the letter in that cell
Algorithm:
Define m and n, define path as empty set
Define dfs function with row, col and index for params as follows:
- if out of bounds or board letter != word index or position already in path set, return False
- Add position to path set
- store OR of dfs in 4 directions in result
- remove position from path
- return result
- Brute force through the board and call dfs, if True, return True
return False
Validate binary search tree
Idea:
We need to check if each node is within the its bounds. The left child has to be within (-inf, parent), right child has to be within (parent, inf)
Algo:
define util function with root, left_bound, right_bound for params as follows
- If not root, return True
- If not within value bounds, return False
- Return OR of recursive call for left and right child, right_bound is parent for left subtree call, left_bound is parent for right subtree call
- call util function over root with bounds as (-inf, inf)
