Crusoe Prep Flashcards
Max Depth of Tree
def max_depth(t):
if t is None:
return 0
left_depth = 0
right_depth = 0
if t.left:
left_depth = 1 + max_depth(t.left)
if t.right:
right_depth = 1+ max_depth(t.right)
return max(left_depth, right_depth)
Max Profit, Sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_elem = prices[0]
max_profit = 0
for i in range(1, len(prices)):
profit = prices[i] - min_elem
max_profit = max(max_profit, profit)
min_elem = min(min_elem, prices[i])
if max_profit > 0:
return max_profit
else:
return 0
Buy Sell Stock 2
Can only hold 1 share. Can buy or sell on any day. Looking for peaks and valleys
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxprofit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
maxprofit += prices[i] - prices[i - 1]
return maxprofit
Remove duplicates from sorted array
Have a write_index variable
~~~
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
num_elems = len(nums)
write_index = 1
for i in range(1, num_elems):
# Found unique element
if nums[i - 1] != nums[i]:
# Updating write_index in our main array
nums[write_index] = nums[i]
# Incrementing write_index count by 1
write_index += 1
return write_index ~~~
Remove duplicates, but allow at most 2 of the same element
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 1
write_index = 1
count = 1
while i < len(nums):
if nums[i] == nums[i - 1]:
count += 1
if count > 2:
i += 1
continue
else:
count = 1
nums[write_index] = nums[i]
write_index += 1
i += 1
del nums[j:]
return len(nums)Two Sum with Sorted Array
Have two pointers at opposite ends. Have while condition as “low < high”.
In the code below, they wanted the result
~~~
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low = 0
high = len(numbers) - 1
while low < high:
sum = numbers[low] + numbers[high]
if sum == target:
return [low + 1, high + 1]
elif sum < target:
low += 1
else:
high -= 1
# In case there is no solution, return [-1, -1].
return [-1, -1] ~~~
Heap - Kth largest
from heapq import heapify, heappop
class Solution:
def findKthLargest(self, nums, k) -> int:
nums = [-n for n in nums]
heapify(nums)
res = 0
for _ in range(k):
res = heappop(nums)
return -resTop K Elements - Heap
First have a counter hash
# Create heap with empty array.
# Iterate through keys, check size of heap. If == k, call heappushpop, otherwise call heappush
# To get the
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq_table = defaultdict(int)
for num in nums:
freq_table[num] += 1
heap = []
for key in freq_table.keys():
count = freq_table[key]
mytuple = (count, key)
if len(heap) == k: # If size is k then we dont want to increase the size further
heappushpop(heap, mytuple)
else: # Size is not k then freely push values
heappush(heap, mytuple)
# After this operation the heap contains only k largest values of all the values in nums
ans = []
while k > 0:
k -= 1
ans.append(heappop(heap)[1])
return ans
Currency Conversion
from collections import defaultdict
def calculate_conversion_rates(rates, queries):
# Build graph
graph = defaultdict(dict)
for rate in rates:
from_currency, to_currency, value = rate
graph[from_currency][to_currency] = value
graph[to_currency][from_currency] = 1/value
# Perform DFS for each query
result = []
for query in queries:
from_currency, to_currency = query
visited = set()
rate = dfs(graph, from_currency, to_currency, 1.0, visited)
result.append(rate)
return result
def dfs(graph, start, end, value, visited):
if start not in graph or start in visited:
return -1.0
if start == end:
return value
visited.add(start)
neighbors = graph[start]
for neighbor, neighbor_value in neighbors.items():
rate = dfs(graph, neighbor, end, value * neighbor_value, visited)
if rate != -1.0:
return rate
return -1.0
rates = [['USD', 'JPY', 100], ['JPY', 'CHN', 20], ['CHN', 'THAI', 200]]
queries = [['USD', 'CHN'], ['JPY', 'THAI'], ['USD', 'AUD']]
Run the function and print the result
print(calculate_conversion_rates(rates, queries))3Sum
2 pointers
~~~
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res, dups = set(), set()
seen = {}
for i, val1 in enumerate(nums):
if val1 not in dups:
dups.add(val1)
for j, val2 in enumerate(nums[i + 1 :]):
complement = -val1 - val2
if complement in seen and seen[complement] == i:
res.add(tuple(sorted((val1, val2, complement))))
seen[val2] = i
return res
~~~
- Longest Substring Without Repeating Characters
Sliding Window with a counter
~~~
def longestSubstr_2024_09_05(s):
max_len = 0
left = 0
right = 0
count_hash = defaultdict(int)
while right < len(s):
c = s[right]
count_hash[c] += 1
while count_hash[c] > 1:
c2 = s[left]
count_hash[c2] -= 1
left += 1
max_len = max(max_len, right - left + 1)
right += 1
return max_len ~~~
Merge Intervals
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
res = []
# sort, N log N
intervals.sort(key=lambda x: x[0])
for interval in intervals:
if not res or res[-1][1] < interval[0]:
res.append(interval)
else:
last = res.pop()
start = min(last[0], interval[0])
ending = max(last[1], interval[1])
res.append([start, ending])
return res
Sum of Root to Leaf
Do DFS
~~~
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
res: int = 0
stack = [(root, 0)]
while stack:
node, curr_number = stack.pop()
if node is not None:
# atoi calculation
curr_number = curr_number * 10 + node.val
# if it's a leaf, update node-to-leaf sum
if node.left is None and node.right is None:
res += curr_number
else:
stack.append((node.right, curr_number))
stack.append((node.left, curr_number))
return res ~~~
Phone number combinations
KEYBOARD = {
‘2’: ‘abc’,
‘3’: ‘def’,
‘4’: ‘ghi’,
‘5’: ‘jkl’,
‘6’: ‘mno’,
‘7’: ‘pqrs’,
‘8’: ‘tuv’,
‘9’: ‘wxyz’,
}
~~~
def letter_combinations_of_phone_number(digits: str) -> List[str]:
def dfs(start_index, path):
if start_index == len(digits):
res.append(‘‘.join(path))
return
next_number = digits[start_index]
for letter in KEYBOARD[next_number]:
path.append(letter)
dfs(start_index + 1, path)
path.pop()
res = []
dfs(0, [])
return res
```
Letter combinations
