Idea: turn a TI-84/ Gameboy/DS into a meshtastic client

• DFS / BFS

  • BFS better for shortest path and level-order traversals
    • What the FUCK is a level-order
      • left to right, top to bottom

• k Smallest/largest use a heap/sorting?

• Can brute force of params are super small otherwise use DP

• if linked list or if multiple sequences, use two pointers

• if it’s a DAG, use a toposort

  • how to implement toposort

• if it involves summing a subset, prefix sum (constant time)

  • if not summing, then sliding window

• if searching min/max of monotonic, can just do binary search

• if not monotonic, but can split up use DP

• if can’t use DP, greedy search

• if counting, do backtracking or DP

• if multiple lists or pairs of indices/ use two pointer

• use two pointer for O(1) mem

Two pointer

• Fast/Slow can be used for stuff like cycle detection and dedup
• opposite directions can be used to find two elements that sum to target

Sliding Window

• can move end pointer to expand, start pointer to contract
  • longest non-repeating substring
  • good for continuous subsequences

• Graph is tree with cycles

  • if cycles, need a set of visited nodes

• BFS

  • search all neighbors
  • put nodes to visit into a queue
  • searches level by level?

1
2
3
4
5
6
7
8

queue = Queue(root)
while len(queue) > 0:
current = queue.pop()
for child in current.children:
  if condition(child):
    return
  queue.push(child)
return None

• DFS is just BFS with stack instead of queue

  • can just use Call stack for DFS (recursion)
  • Backtracking is DFS across solution space

• BFS finds shortest/ DFS finds all

• Max heap to find k smallest
• Min heap to find k biggest