{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4ceb4b19",
   "metadata": {},
   "source": [
    "# notebooks\n",
    "This directory contains my notes about various algorithms, data structures, and problem solving techniques. I use them as a personal reference and archive of things I've learned or tried. It is constantly under development and likely full of mistakes, so please consult a proper textbook where needed. I also pretty liberally plagiarize other resources; if you see something cool, assume I didn't come up with it (but assume any mistakes are original). \n",
    "\n",
    "Any notebooks in the `WIP/` folder are WIP; any not in that folder are not.\n",
    "\n",
    "Notation:\n",
    "- blank: generally useful for interviews or competitions\n",
    "- `i`: specifically useful in interviews\n",
    "- `c`: specifically useful in competition\n",
    "- `e`: esoteric, not something that comes up a lot in interviews or competitions\n",
    "\n",
    "\n",
    "# Part 1 - General\n",
    "\n",
    "## Arrays (and Strings)\n",
    "- Matrices\n",
    "    - Multiplication\n",
    "    - Transposition\n",
    "- Prefix Sum\n",
    "- Two pointers / sliding window\n",
    "- Knuth-Morris-Pratt\n",
    "\n",
    "### Problems\n",
    "- Reversal\n",
    "- Shift\n",
    "\n",
    "## Backtracking\n",
    "- N-Queens\n",
    "- [Algorithm X / Dancing Links](https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X)\n",
    "\n",
    "### Problems\n",
    "- Scrabble solver\n",
    "- Sudoku verifier / solver\n",
    "\n",
    "## Binary search\n",
    "- General implementation\n",
    "\n",
    "### Problems\n",
    "- Find insertion point for missing element (w/duplicates)\n",
    "- Search in rotated array (w/duplicates)\n",
    "\n",
    "## Bits and Binary\n",
    "- Powers of 2\n",
    "- Common data size conversions: bits, bytes, words (32/64bit), kilo/mega/giga/terabytes\n",
    "    - -bit vs -byte vs -bibyte\n",
    "\n",
    "## Bloom Filter\n",
    "\n",
    "## Complexity\n",
    "- Big-O, big-omega\n",
    "- P, NP, and NP-complete\n",
    "- [Karp's 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)\n",
    "    - Boolean Satisfiability (SAT)\n",
    "    - Vertex cover\n",
    "\n",
    "## Compression / Encoding\n",
    "- Gray code\n",
    "- Delta encoding\n",
    "\n",
    "## Divide and conquer\n",
    "### Problems\n",
    "- https://leetcode.com/problems/next-greater-element-i\n",
    "- https://leetcode.com/problems/beautiful-array/\n",
    "- https://leetcode.com/problems/median-of-two-sorted-arrays/\n",
    "- https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/\n",
    "- https://leetcode.com/problems/kth-largest-element-in-an-array/\n",
    "    - https://en.wikipedia.org/wiki/Quickselect\n",
    "    \n",
    "## Dynamic Programming\n",
    "- [Subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem)\n",
    "- [Bin packing](https://en.wikipedia.org/wiki/Bin_packing_problem)\n",
    "- [Knapsack problems](https://en.wikipedia.org/wiki/Knapsack_problem)\n",
    "    - [Coin change](https://en.wikipedia.org/wiki/Change-making_problem)\n",
    "    - Tiling path\n",
    "- Common subarray of two arrays\n",
    "    - [Longest common substring](https://en.wikipedia.org/wiki/Longest_common_substring_problem)\n",
    "- Common subsequence of two arrays\n",
    "    - Longest Increasing Subsequence\n",
    "    - [Longest Common Subsequence](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)\n",
    "- Subarray of one array\n",
    "     - [Longest palindromic substring](https://en.wikipedia.org/wiki/Longest_palindromic_substring)\n",
    "         - Manacher's algorithm\n",
    "     - [Maximum product subarray](https://leetcode.com/problems/maximum-product-subarray/)\n",
    "     - Maximum Subarray\n",
    "- Subsequence of one array\n",
    "     - [Longest increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)\n",
    "     - [Longest alternating subsequence](https://en.wikipedia.org/wiki/Longest_alternating_subsequence)\n",
    "\n",
    "## Edit Distance\n",
    "- Hamming distance \n",
    "- Levenshtein distance\n",
    "\n",
    "## Geometry\n",
    "- Convex hull / Graham scan\n",
    "- Painter's algorithm\n",
    "\n",
    "## Hashing\n",
    "- Collision resolution\n",
    "    - Nearest neighbor\n",
    "    - Linked list\n",
    "- Rolling Hash / Rabin Karp\n",
    "\n",
    "## Heaps / Priority Queue\n",
    "- Fibonacci Heap\n",
    "- Queap\n",
    "- Beaps\n",
    "- Find min element of max heap / max element of min heap\n",
    "- Percolating / heapify an array\n",
    "- Sort an array  using a heap\n",
    "\n",
    "## Math\n",
    "\n",
    "## Regular Expressions   \n",
    "\n",
    "## Recursion\n",
    "- Master theorem for recurrences\n",
    "\n",
    "### Problems\n",
    "- Tower of Hannoi\n",
    "- [Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)\n",
    "- Reconstruct IP addrs\n",
    "- house robber\n",
    "- stock prices\n",
    "\n",
    "## Parsing\n",
    "- Conversions from various date formats (including unix timestamps)\n",
    "- Finding the delta between dates\n",
    "- Regex\n",
    "- Shunting Yard / arithmetic expression calculator\n",
    "    - https://en.wikipedia.org/wiki/Shunting-yard_algorithm\n",
    "    - https://leetcode.com/problems/basic-calculator/\n",
    "    - https://leetcode.com/problems/basic-calculator-ii/\n",
    "    - https://leetcode.com/problems/basic-calculator-iii\n",
    "    - https://leetcode.com/problems/basic-calculator-iv/\n",
    "\n",
    "## Stack\n",
    "- Implement a queue using two stacks\n",
    "- Handle unsorted array\n",
    "    - https://leetcode.com/problems/daily-temperatures\n",
    "    - https://leetcode.com/problems/maximum-binary-tree/\n",
    "- Strings and text\n",
    "    - https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/\n",
    "    - https://leetcode.com/problems/valid-parentheses/\n",
    "    \n",
    "### Problems\n",
    "- https://leetcode.com/problems/merge-k-sorted-lists/\n",
    "- https://leetcode.com/problems/the-skyline-problem/\n",
    "\n",
    "\n",
    "## Sorting\n",
    "- Insertion, Selection, and Bubblesort\n",
    "- Quicksort\n",
    "- Mergesort\n",
    "- Partition sort (Dutch flag)\n",
    "- Heapsort\n",
    "\n",
    "## Union Find"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00d0df5c",
   "metadata": {},
   "source": [
    "# Part 2 - Graphs\n",
    "## Connected components\n",
    "### Problems\n",
    "- Find all in graph\n",
    "- Determine way to create entirely connected graph in fewest edges\n",
    "- Graph coloring\n",
    "\n",
    "## Linked Lists\n",
    "- Cycle detection\n",
    "- Reversal\n",
    "- Detect if two LLs are joined\n",
    "\n",
    "## Minimum Spanning Tree\n",
    "- Prim's algorithm\n",
    "- Kruskal's algorithm\n",
    "\n",
    "## Min flow, max cut\n",
    "- Ford-Fulkerson\n",
    "\n",
    "## Pathfinding / Search\n",
    "- A* \n",
    "- Beam search\n",
    "- BFS (iterative and recursive)\n",
    "- DFS (iterative and recursive)\n",
    "- Djikstra's Algorithm\n",
    "- Euler circuit (path using every edge exactly once)\n",
    "    - Hierholzer's algorithm\n",
    "- Hamiltonian circuit\n",
    "\n",
    "### Problems\n",
    "- Longest path\n",
    "- Shortest path\n",
    "- https://leetcode.com/problems/pacific-atlantic-water-flow/\n",
    "\n",
    "## Topological sorting\n",
    "- Kahn's algorithm\n",
    "- Using DFS\n",
    "\n",
    "### Problems\n",
    "- https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/\n",
    "- Course scheduler\n",
    "    - https://leetcode.com/problems/course-schedule\n",
    "    - https://leetcode.com/problems/course-schedule-iii/\n",
    "- Alien dictionary\n",
    "    - https://leetcode.com/problems/alien-dictionary/\n",
    "- https://leetcode.com/problems/longest-increasing-path-in-a-matrix/\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "448780e5",
   "metadata": {},
   "source": [
    "# Part 3 - Trees\n",
    "## B-Trees\n",
    "\n",
    "## Binary Search Tree\n",
    "- Insertion, Search, Deletion\n",
    "- Find minimal / maximal element \n",
    "- Find successor or predecessor for an element\n",
    "- Closest value to target\n",
    "    - https://leetcode.com/problems/closest-binary-search-tree-value-ii\n",
    "    - https://leetcode.com/problems/closest-binary-search-tree-value\n",
    "    \n",
    "## BSP Trees\n",
    "\n",
    "## General\n",
    "- [Determine if a graph is a valid tree](https://leetcode.com/problems/graph-valid-tree/)\n",
    "- [Find duplicate subtrees](https://leetcode.com/problems/find-duplicate-subtrees/)\n",
    "- [Find all minimum height trees](https://leetcode.com/problems/minimum-height-trees/)\n",
    "\n",
    "## Merkle tree\n",
    "\n",
    "## Red-Black tree\n",
    "\n",
    "## Segment tree\n",
    "\n",
    "## Suffix tree\n",
    "\n",
    "## Traversal\n",
    "- Preorder, In-order, Post-order\n",
    "    - Recursive implementation\n",
    "    - Iterative Implementation\n",
    "- Level-order\n",
    "- [Vertical order](https://leetcode.com/problems/binary-tree-vertical-order-traversal/)\n",
    "- Travelling Salesman Problem\n",
    "\n",
    "## Trie (Prefix tree)\n",
    "### Problems\n",
    "- [Word auto-completion](https://leetcode.com/problems/design-search-autocomplete-system/)\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddb575af",
   "metadata": {},
   "source": [
    "## Unsorted problems\n",
    "- [Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/)\n",
    "- https://leetcode.com/problems/zigzag-conversion\n",
    "- https://leetcode.com/problems/k-closest-points-to-origin\n",
    "- https://leetcode.com/problems/count-of-smaller-numbers-after-self\n",
    "- https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/\n",
    "- https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/\n",
    "- https://leetcode.com/problems/01-matrix/\n",
    "- https://leetcode.com/problems/top-k-frequent-elements/\n",
    "- https://leetcode.com/problems/word-search/\n",
    "- https://leetcode.com/problems/sequence-reconstruction/\n",
    "- https://leetcode.com/problems/k-th-symbol-in-grammar/\n",
    "- https://leetcode.com/problems/binary-tree-maximum-path-sum/\n",
    "- https://leetcode.com/problems/special-binary-string/\n",
    "- https://leetcode.com/problems/word-search-ii/\n",
    "- Knight's tour\n",
    "- Implementation\n",
    "- [LRU cache](https://leetcode.com/problems/lru-cache)\n",
    "- [In-memory filesystem](https://leetcode.com/problems/design-in-memory-file-system/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89976f8b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}