Crusoe Prep

Question 1

Max Depth of Tree

Answer 1

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)

Question 2

Max Profit, Sell Stock

Answer 2

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

Question 3

Buy Sell Stock 2

Answer 3

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

Question 4

Remove duplicates from sorted array

Answer 4

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

Question 5

Remove duplicates, but allow at most 2 of the same element

Answer 5

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)

Question 6

Two Sum with Sorted Array

Answer 6

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]

Question 7

Heap - Kth largest

Answer 7

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 -res

Question 8

Top K Elements - Heap

Answer 8

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

Question 9

Currency Conversion

Answer 9

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))

Question 10

3Sum

Answer 10

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

Question 11

3. Longest Substring Without Repeating Characters

Answer 11

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

Question 12

Merge Intervals

Answer 12

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

Question 13

Sum of Root to Leaf

Answer 13

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

Question 14

Phone number combinations

Answer 14

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
	```

Question 15

Letter combinations