LC-Meta Flashcards
1
Q
Binary tree vertical order traversal
A
You know it
Add tuple to dictionary;
Pop left from queue
2
Q
Valid word abbreviation
A
- Make sure index2 is in range while getting the count
- Check if enough remaining chars in word and early return
3
Q
Nested list weight sum
A
Be careful about updating primitive variables with inner function.
4
Q
lowest common ancestor iii - with parent pointer
A
Two pointers that can merge, making sure they go through the same distance and eventually merge
5
Q
lowest common ancestor ii - nodes may or may not exist
A
Post order
Return (none, 0) as default after checking left and right
6
Q
Minimum remove to make valid parentheses - return just one valid string
A
Two pass; maintain balance.
T - N
S - N
7
Q
Valid Palindrome I
A
Get lower case of letter lower()
Check if letter is alphanumeric isalnum()
Reverse a string or list
8
Q
Valid palindrome II - remove at most one letter
A
Start from head and tail; whenever no match found, try remove either side
9
Q
Dot product of two sparse vectors
A
- Get both index and element by using enumerate func
- Get both key and value by items func
- Consider using array instead of hashmap!
10
Q
Validate palindrome - remove at most K letters
A
Think about base cases
Memorization
How to infer current from child cases
11
Q
Random pick with weight
A
Prefix sum the same length as array
Binary search - if low < target; else; then check both low and high
Random function - random.randint(start, stop) both inclusive
12
Q
Basic calculator II
A
- Track current operation
- How to truncate towards 0 when doing division for negative values
- isdigit()
- isspace()
13
Q
Basic calculator - with parentheses and only addition and subtraction
A
- In place update result, we still need a stack though - why?
- When operator found, finish previous calculation and reset the sign and operand
- When open parenthesis found, cache the current sign and result in stack. Reset the result and sign
- When closing parenthesis found, finish previous calculation first, pop from stack and complete the calculation outside of the parenthesis. Reset operator.
14
Q
Lowest common ancestor - two nodes must exist
A
Do preorder and early return
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
15
Q
Lowest common ancestor of binary search tree
A
Check the root value against p and a value and move to subproblem on either right or left subtree
What’s the stop case?
16
Q
Basic calculator III - with positive number s only, parentheses and all operators
A
- We anyway need to use a stack.
- Check if an variable is integer - isinstance(e, int)
- Use while loop instead of for loop
- How to truncate towards 0 when negative division
- What to do when open and closing parentheses encountered
- Reset current operation when dealing with open parentheses
17
Q
Building with ocean view
A
Monotonic stack.
18
Q
Kth largest element in an array
A
- initialize heap as list
- heapq.heappush
- heapq.heappop
- heap[0]
- Why do we use minimum heap here? Why do we pop when heap size is larger than k
19
Q
Range sum of BST
A
In order traversal - try recursion
20
Q
Moving average from data stream
A
Deque
Initialize sum as float(0)
21
Q
Simplify path
A
- For dots, check if dots are between slashes
- When dealing with current directly or previous directly, make exception for root directory
22
Q
Convert binary search tree to sorted doubly linked list
A
In order traversal
23
Q
Sum root to leaf numbers
A
DFS
24
Q
Simplify path
A
Remember to verify dots are only between slashes before moving on checking dots numbers
Remember to make exceptions for root directory slash
25
Insert into sorted circular linked list
1. No node
2. Single node
3. Use two pointers and while loop
4. Insert value between max and min
5. Find the tail, check if insert value is beyond and min and max range
4. When back to the head, just insert
26
Custom sort string
Frequency dictionary
27
3 sum closest
Sort.
Enumerate the start
Binary search and try to get closer and maintain the absolute diff.
Return target + diff
28
K closet points to origin
Heap
Tuple in heap
29
Interval list intersections
1. Two pointers
2. Get the start and end first
3. Check if the interval is valid
4. Move pointers by comparing end of the two intervals
https://leetcode.com/problems/interval-list-intersections/
30
Sticker to spell word
1. DFS on subsequence
2. For each subsequence, check which sticker to start with and exhaust the sticker by making a deep copy of it, then DFS on the remaining subsequence
4. When starting with different stickers, get what’s the minimum result
5. Eventually cache the minimum result for the subsequence
6. Apply the DFS on entire subsequence
31
Word break - check if break is true or false
Start with each word and DFS and see if possible
32
Word break II - return all sentences that can be formed
Start with word and do DFS, if a solution is found the append to global result;
Pop from current sentence after moving to next word
https://leetcode.com/problems/word-break-ii/description/
33
Pow(x, n)
Binary expression
34
Two sum - sorted array, avoid duplicates
Low and high pointers.
35
3 Sum; K Sum
Enumerate the start and skip duplicates.
Recursively call K-1 sum or 2 sum.
Iterate through the result from K - 1 sum or 2 sum and add to result.
36
Make a large island
Union find;
Get the maximum size during first pass for building the parent dictionary.
We can return early for some edge cases.
Remember to use a dictionary to record how many islands we can connect given a cell of water.
37
Number of islands
BSF from each island and add to visited set
Increment the result after BFS is done with the island.
Use set instead of list to store visited islands, because set provides constant search time
38
Word Ladder
1. Get all words combinations
2. BSF and maintain number of steps
https://leetcode.com/problems/word-ladder/description/
39
Min stack
Use one stack. Maintain the minimum value separately
40
Valid number
1. Three variables
2. enumerate the string
2. e should be after digits and not seen before; e can be right after dots! Reset digit seen because we expect integer after e
3. dots can no be seen twice or after e
41
Shortest path in binary matrix - 8 directional
1. BFS
2. Edge case
3. How to maintain distance for each node?
42
Subarray sum equals K - total number of subarrays;
Negative number in the array
Prefix sum + dictionary
Sum to to a set of indexes - why?
We actually don’t need to store the set of indexes, we can just have a frequency table.
43
Continuous subarray sum that is always a multiple of K
Dictionary of residue
44
Subarray product less than K - all positive numbers
Same direction two pointers;
Enumerate the start; end start from 0.
Remember to check the end - out of range or not, it impacts how we calculate the range.
https://leetcode.com/problems/subarray-product-less-than-k/description/
45
Group shifted strings
Do mod operation and take the residue and build hash key. In Python it’s guaranteed to return a nonnegative residue.
Python ord(c) to return a number representing the char.
46
Find Peak Item
Binary search
47
LRU cache
Double linked list to efficiently perform remove and insert.
1. Store the key with the node, so we can remove from the dictionary
2. del dictionary[key]
3. Define new node class and constructor. Val and key initialized as None
48
Maximum swap
Digit to highest index
49
Random pick index
Number to indexes dictionary
Random.randint(start, end) both inclusive
50
Toeplitz matrix
Optimize the space.
51
Diameter of binary tree
DFS
52
Closest binary search tree value
Recursion version, no need to return result from the DFS function. Update the result in place.
53
Binary tree right side view
https://leetcode.com/problems/binary-tree-right-side-view/description/
BFS by layer
54
Copy list with random pointer
Dictionary from old to new nodes;
Recursion;
If old in dictionary, directly return the new nodes
55
Clone graph
Old to new nodes dictionary at class level
Recursion
56
Product of two run-length encoded arrays
Two pointer
Remember to check if two intervals can be merged in result
Update original two inputs in place
57
Top K frequent elements
Frequency map and convert to tuple list
Heap sort on the tuple and keep heap size as K
58
Exclusive time of functions
https://leetcode.com/problems/exclusive-time-of-functions/description/
Maintain current running Id and current time.
Update the current time.
Pop from stack when a function ends
59
Missing ranges
Edge case when input is empty
60
Diagonal traversal
Maintain a flag of direction;
Change the head when reaching the boundary
Flip the head
If at the corner, just return
61
Merge intervals
1. Use just one pointer.
2. Maintain current start and end
3. Iterate through the input and compare with current start and end.
4. Pop from result if needed.
62
Check if an original string exists given two encoded string
1. Analysis first character of both strings and recursively solve the problem
2. how many possible number combinations? Enumerate them and solve iteratively
3. Use memo
https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/
63
Account merge
BFS
Email to name
Unique emails
64
Merge K sorted lists
1. Merge two sorted
2. Override original list1
65
Merge sorted array
Start from the end - m + n - 1
66
Meeting room II - how many meeting rooms needed
Maintain a heap of meeting room end time
Return the length of heap
67
Design tic tax toe
Maintain arrays of the marked blocks for each row and col and diagonal or anti-diagonal.
Set player to either 1 or -1
Each move should update all arrays
68
Remove invalid parentheses - return all unique valid strings with minimum number of removals
DFS, pass a new str into recursive call
69
Convert sorted linked into binary search tree 109
Converted linked list to array and the divide and conquer
70
Maximum consecutive ones
Two window
Be super careful with moving end
After while loop, check both cases - if end is out of bound or not
71
Kth missing positive number
Index to missing number? Binary search. Follow the standard binary search pattern.
72
Verifying an alien dictionary
1. Use zip
2. No need to compare more if first different char is sorted
3 check edge case - all letters the same
class Solution(object):
def isAlienSorted(self, words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
letter_order = {}
for index, letter in enumerate(order):
letter_order[letter] = index
# apple app
for word1, word2 in zip(words, words[1:]):
for letter1, letter2 in zip(word1, word2):
if letter1 != letter2:
if letter_order[letter1] > letter_order[letter2]:
return False
# if we find the first different character and they are sorted,
# then there's no need to check remaining letters
break
else:
if len(word1) > len(word2):
return False
return True
73
Populate next right pointer in each node
Make use of perfect binary to optimize the efficient, use while loop to check leftmost pointer at each letter
74
Add Strings
Pointers from last element and cache carry
75
All nodes distance K in binary tree
Two rounds of DFS
Build parent pointer
76
Unique path I and II
Memorization
77
Merge two BSTs
Use two stacks to do in-order traversal as the same time
https://favtutor.com/blogs/merge-binary-search-trees
78
Remove Nth node from end of list
Two pointers. Use dummy head!
79
Check completeness of binary tree
Get total nodes count.
DFS on indexes
80
Swapping nodes in a single linked list - kth from the beginning and kth from the end
3 pointers.
Front pointer
End pointer
Another current pointer that goes to end
81
Expression add operators
DFS and backtracking
Index, cur num, pre num, total, string
https://leetcode.com/problems/expression-add-operators/submissions/1285559171/
82
Next permutation
Find the first non-increasing digit from the last, swap it with the first digit larger than it to its right, and then reverse the sub list to its right
83
Validate IP address
Validate v4 and v6 separately by checking the number of dots
84
K smallest elements from n sorted array
Use heap, first push all first elements to heap.
85
Reverse integer
Keeping dividing and mod
Check against integer range
86
Minimum add to make parentheses valid
Maintain balance. One pass.
