commit 572deea60df2cd88ab7260b72bbdb9ed53899c0f
parent df6491e806461115e38795f271aa115dd36273f0
Author: Andrew Laack <andrew@laack.co>
Date: Thu, 10 Sep 2026 20:01:04 -0500
Did an assortment of problems and revised segment tree to have O(logn) updates
Diffstat:
6 files changed, 218 insertions(+), 1 deletion(-)
diff --git a/count-nodes-equal-to-average-of-subtree/count-nodes-equal-to-average-of-subtree.py b/count-nodes-equal-to-average-of-subtree/count-nodes-equal-to-average-of-subtree.py
@@ -0,0 +1,32 @@
+# Definition for a binary tree node.
+# class TreeNode:
+# def __init__(self, val=0, left=None, right=None):
+# self.val = val
+# self.left = left
+# self.right = right
+
+# idea
+ # backtracking
+ # average of this is sum of values / count of subtrees
+ # return this up the stack at each step
+ # have shared state that tracks count then return that
+
+
+class Solution:
+ def recurse(self, nd):
+ if nd is None:
+ return (0,0)
+ left = self.recurse(nd.left)
+ right = self.recurse(nd.right)
+
+ sum_val = (left[1] + right[1]) + nd.val
+ count = left[0] + right[0] + 1
+ avg = sum_val // count
+ if avg == nd.val:
+ self.count += 1
+ return (count, sum_val)
+
+ def averageOfSubtree(self, root: TreeNode) -> int:
+ self.count = 0
+ self.recurse(root)
+ return self.count
diff --git a/mice-and-cheese/mice-and-cheese.py b/mice-and-cheese/mice-and-cheese.py
@@ -0,0 +1,33 @@
+import heapq
+
+# two mice
+# n types of cheese
+# each type should be eaten by exactly one mouse
+# reward1[i] if first mouse eats it
+# reward2[i] if second mouse eats it
+# k is non-negative, reward lists are all positive
+# return max points if first mouse eats exactly k types of cheese
+
+# idea:
+ # seems greedy
+ # like what's the delta at each position
+ # then minimize this somehow
+
+ # yes. Since first mouse eats only k cheese we compute the deltas and then select
+ # the ones that are largest wrt value of first eating - second eating
+
+ # this'll be O(n + klogk) for time
+ # We could do O(logk) for space
+
+class Solution:
+ def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
+ best_k_heap = []
+ for i in range(len(reward1)):
+ delta = reward1[i] - reward2[i]
+ if len(best_k_heap) < k:
+ heapq.heappush(best_k_heap,delta)
+ else:
+ if k > 0 and best_k_heap[0] < delta:
+ heapq.heappop(best_k_heap)
+ heapq.heappush(best_k_heap,delta)
+ return sum(reward2) + sum(best_k_heap)
diff --git a/plan.txt b/plan.txt
@@ -5,4 +5,4 @@ these are the things I want to learn, ordered
x prim's algo (visualized in python)
x permutation problem (similar to interview where print all permutations of a string where only certain chars may be moved)
x union find
- - segment tree
+ x segment tree
diff --git a/range-sum-query-mutable/range-sum-query-mutable-v2.py b/range-sum-query-mutable/range-sum-query-mutable-v2.py
@@ -0,0 +1,97 @@
+class Node:
+ def __init__(self):
+ self.rng = [0, 0]
+ self.rv = 0
+ self.left = None
+ self.right = None
+
+def combine(a,b):
+ root = Node()
+ root.left = a
+ root.right = b
+ root.rv = a.rv + b.rv
+ root.rng[0] = min(a.rng[0], b.rng[0])
+ root.rng[1] = max(a.rng[1], b.rng[1])
+ return root
+
+
+# cases:
+ # if no overlap between rng and root return
+ # if same, return val
+ # if different return sum of left + right
+
+def find_sum(rng, root):
+ if root is None:
+ return 0
+ if rng[1] < root.rng[0] or rng[0] > root.rng[1]:
+ return 0
+
+ if root.rng[0] >= rng[0] and root.rng[1] <= rng[1]:
+ return root.rv
+
+ return find_sum(rng,root.left) + find_sum(rng,root.right)
+
+def update_val(root, idx, delta):
+ if root is None:
+ return
+ if idx < root.rng[0] or idx > root.rng[1]:
+ return
+
+ root.rv += delta
+ update_val(root.right, idx, delta)
+ update_val(root.left, idx, delta)
+
+
+
+
+def make_segment(nums):
+ forest = []
+
+ idx = 0
+ for num in nums:
+ current = Node()
+ current.rng = [idx,idx]
+ current.rv = num
+ forest.append(current)
+ idx += 1
+
+ while len(forest) > 1:
+ nf = []
+
+ for i in range(0, len(forest), 2):
+ if i + 1 < len(forest):
+ nf.append(combine(forest[i], forest[i + 1]))
+ else:
+ nf.append(forest[i])
+
+ forest = nf
+
+ return forest[0]
+
+class NumArray:
+
+ # len(nums) is at most 30_000
+ def __init__(self, nums: List[int]):
+ self.nums = nums
+ self.segment_tree = make_segment(nums)
+
+ # nums[index] = val
+ def update(self, index: int, val: int) -> None:
+ # could do away with this list if we accept log(n) cost for lookups here
+ # this would retain the same WCTC of log(n) for updating but increase the constant.
+ # this would decrease memory usage, but still in O(n) for that too.
+ prior = self.nums[index]
+ self.nums[index] = val
+ update_val(self.segment_tree,index,val - prior)
+ return
+
+ # range queries can be size of nums
+ # precondition: left <= right
+ # return: sum(nums[left,right]) - inclusive of left and right
+ def sumRange(self, left: int, right: int) -> int:
+ return find_sum([left,right], self.segment_tree)
+
+# Your NumArray object will be instantiated and called as such:
+# obj = NumArray(nums)
+# obj.update(index,val)
+# param_2 = obj.sumRange(left,right)
diff --git a/swap-nodes-in-pairs/swap.py b/swap-nodes-in-pairs/swap.py
@@ -0,0 +1,29 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+class Solution:
+ def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
+
+ ls = []
+ node1 = head
+
+ while node1 != None:
+ ls.append(node1)
+ print(node1.val)
+ node1 = node1.next
+
+ for i in range(0,len(ls) - 1, 2):
+ tmp = ls[i]
+ ls[i] = ls[i+1]
+ ls[i+1] = tmp
+
+ for i in range(0,len(ls) - 1):
+ ls[i].next = ls[i+1]
+
+ if len(ls) > 0:
+ ls[len(ls) - 1].next = None
+ head = ls[0]
+
+ return head
diff --git a/unique-three-digit-even-number/unique-three-digit-even-number.py b/unique-three-digit-even-number/unique-three-digit-even-number.py
@@ -0,0 +1,26 @@
+class Solution:
+ def recurse(self, num_dict, depth, even_sel, has_num):
+ if depth == 3:
+ if even_sel:
+ return 1
+ return 0
+ summed = 0
+ for num in num_dict:
+ count = num_dict[num]
+ if count == 0:
+ continue
+ if not has_num and num == 0:
+ continue
+ num_dict[num] -= 1
+ summed += self.recurse(num_dict, depth + 1, num%2==0, True)
+ num_dict[num] += 1
+ return summed
+
+ def totalNumbers(self, digits: List[int]) -> int:
+ num_dict = {}
+ for num in digits:
+ if num_dict.get(num) is None:
+ num_dict[num] = 1
+ else:
+ num_dict[num] += 1
+ return self.recurse(num_dict, 0, False, False)
