以下为个人准备amazon面试所用笔记原稿，每题记忆组成部分为 1) LC 题目 2)辅助记忆笔记
个人准备笔记，可能有点乱
祝你们也好运！
621. Task Scheduler,
math. max(res, len(tasks))
42. Trapping Rain Water,
log curmax and increment max(0,min(maxl,maxr)-height[p])
347. Top K Frequent Elements.
heap nlogk, stable. qs n, n2, faster for large k.
function partition(left, right):
for i from left to right-1:
if value_at(i) > pivot_value: # Modify comparison for min-k
swap(elements[store_index], elements[i])
store_index += 1
swap(elements[store_index], elements[pivot]) # Place pivot in correct position
return store_index # Final position of the pivot
function quickselect(left, right):
if left == right:
return
pivot_index = partition(left, right)
if pivot_index == k:
return # Found kth element
elif pivot_index < k:
quickselect(pivot_index + 1, right) # Search right partition
else:
quickselect(left, pivot_index - 1) # Search left partition
3. Longest Substring Without Repeat
while invlid, move left
move right. update res
138. Copy List with Random Pointer
! need to check if cur has random. (the end doesnt)
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
227. Basic Calculator II
stack = [] # return the sum of stack
num = 0
sign = '+' # need to use str.
when meet a ops, apply prev ops
+-, append the num to stack
*, times num to last in stack
then log the new ops
84. Largest Rectangle in Histogram
decreasing stack. if incoming smaller, process the stack
n = len(heights)
res = 0
stack = []
heights = heights +[-1]
for i,h in enumerate(heights):
while stack and h<heights[stack[-1]]:
minh=stack.pop()
if stack:
width=i-stack[-1]-1
else:
width=i
area=heights[minh]*width
res=max(res,area)
stack.append(i)
135. Candy
1. all 1
2. foward pass
3. backward. same. but only increase reward by max(cur, new)
295. Find Median from Data Stream
self.low = [] # max heap
self.high = [] # min heap
def addNum(self, num: int) -> None:
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.low) < len(self.high):
heapq.heappush(self.low, -heapq.heappop(self.high))
1152. Analyze User Website Visit Pattern
2: Organize visits by username. user: history
3: set(combinations(websites, 3))
4. Median of Two Sorted Arrays
bs.
mid1 = (low + high) // 2 # Calculate mid index for nums1
mid2 = leftnumbers a fixed value - mid1 # Calculate mid index for nums2
compute the smallest right, largest left.
ends when largest left < smallest right
224. Basic Calculator
curres = 0
ops = 1
stack = [] # Stack to save state before parentheses
n = 0 # Accumulate numbers
+-, finish cur ops and asign ops.
l, save curres ops to stack. reset
r, finish cur ops, pop the preres, add in.
297. Serialize and Deserialize Binary Tree
bfs
def deserialize(self, data):
ans = TreeNode(flat_bt[0])
queue = collections.deque([ans])
i = 1
# when you pop a node, its children will be at i and i+1
while queue:
node = queue.pop()
if i < len(flat_bt) and flat_bt[i]:
node.left = TreeNode(int(flat_bt[i]))
queue.appendleft(node.left)
i += 1
if i < len(flat_bt) and flat_bt[i]:
node.right = TreeNode(int(flat_bt[i]))
queue.appendleft(node.right)
i += 1
return ans
10. Regular Expression Matching
class Solution:
def backtrack(i, j):
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
# Handle '*'
if j + 1 < len(p) and p[j + 1] == '*':
# Match zero or more occurrences of p[j]
return (
backtrack(i, j + 2) or #0
(first_match and backtrack(i + 1, j)) #many
)
else:
# Match one character and move forward
return first_match and backtrack(i + 1, j + 1)
return backtrack(0, 0)
34. Find First and Last Position of Element in Sorted Array
def findLeft(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def findRight(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
53. Maximum Subarray
keep adding, when sum become negative, reset.
211. Design Add and Search Words Data Structure
self.trie = defaultdict(dict) # Root of the trie
def addWord(self, word: str) -> None:
node = self.trie
for char in word:
if char not in node:
node[char] = defaultdict(dict)
node = node[char]
node["#"] = True # Mark the end of a word
2275. Largest Combination With Bitwise AND Greater Than Zero
loop the 31 bits. then loopp for inputs
# Iterate over all 31 possible bit positions
for bit in range(31):
count = 0
for num in candidates
if num & (1 << bit): # if 1 is at bit location.
count += 1
max_count = max(max_count, count)
return max_count
33. Search in Rotated Sorted Array
Determine if the left half is sorted, then normal bs
if nums[left] <= nums[mid]:
72. Edit Distance
insert_op = 1 + dfs(i, j + 1) # Insert
delete_op = 1 + dfs(i + 1, j) # Delete
replace_op = 1 + dfs(i + 1, j + 1) # Replace
memo[(i, j)] = min(insert_op, delete_op, replace_op)
116. Populating Next Right Pointers in Each Node
bfs. but can use prev res instead of q.
123. Best Time to Buy and Sell Stock
lim 2.
log each time's maxprofit in forward pass, backward pass. uisng curmin seen.
res = max(forwardi+backi) for all is.
239. Sliding Window Maximum
increasing q.
remove out of bound
remove all smaller than cur. log res
243. Shortest Word Distance
1 pass. for ecah w, check if w1 w2. log the ind and update res
450. Delete Node in a BST
recursive when delete nonleaf. move rightmost value here, and delete rightmost
739. Daily Temperatures
stack
