SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Trees
  2. --
  3. Binary tree: two nodes
  4. BST: Two nodes, s.t. left <= n < right for all nodes
  5. balanced: O(logn) insert/find, red-black, AVL
  6. Complete BST: All children filled, leaves filled left to right
  7. Full BST: All nodes have 2 or 0 children
  8. Perfect BST: All levels filled, all nodes have 2 children
  9. Ordering: Imagine a tree with nodes like 4 -> 2/6. Preorder (node first): "4 2 6", In order (node middle): "2 4 6", Post order is (node last) "2 6 4"
  10.  
  11. Heaps
  12. --
  13. Min-heap is asc, max-heap is desc
  14. Heaps are always complete binary trees (not BSTs)
  15. Always insert at right-most location, then swap up that element until it's parent is small (in min-heap) (O(logn))
  16. Re-heapify: Take bottom-right value, move it to the root, swap it down until it's parents are smaller
  17.  
  18. Tries
  19. --
  20. Full words end in a special node that denotes end-of-word.
  21. Each node stores a character and the child nodes.
  22.  
  23. Graphs
  24. --
  25. Adjacency list: obvious way to represent with nodes
  26. Adjacency matrix: NxN boolean matrix, true represents an edge (or weight)
  27. Find closest node: BFS it, since you're minimizing search space (DFS will generally take more iterations)
  28. DFS: Pre-order! Mark node as visited. Recursive.
  29. BFS: NOT RECURSIVE. Use a queue dawg. Still need to mark nodes. Add root to queue, then while queue not empty, dequeue node. For all adjacent nodes, enqueue. 4-> 2(-> 1/3) /6. Enqueue 4, Dequeue 4, enqueue 2 and 6. Dequeue 2, enqueue 1/3. Dequeue 6. Dequeue 1. Dequeue 3. Done.
  30.  
  31. Bidirectional Search (Path from node N to node M)
  32. --
  33. If you know both nodes to start, run two BFS's from each node. Check if they have a node in common. If they do, bam, done. Check after each level.
  34. Takes a factor of 2 less time.
  35.  
  36. Dynamic Programming
  37. --
  38. DRAW THE CALL TREE YOU DUMMY! It's your runtime for a given input size!
  39. DRAW THE CALL TREE WITH MEMOIZATION! It's STILL your runtime for a given input size!
  40. Consider having more than 1 base case and starting there, i.e. fib(0) / fib(1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top