Algorithms and Data Structure 2 Mins Review.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures And Algorithms 2 Mins Review\n",
    "\n",
    "by Stephen Gou\n",
    "\n",
    "Jan, 2019\n",
    "\n",
    "This notebook provides brief descriptions and runtimes for common data structures and algorithms. Use this as a quick review for technical interviews or as a checklist for knowledge. I wanted a **comprehensive, concise, and correct** cheat sheet but couldn't find a satisfactory one online, thus I created my own. Runtime refers to average runtime.\n",
    "\n",
    "## Data Structures\n",
    "\n",
    "### 1 Dynamic Array\n",
    "Sequentially stored data in a continuous chunk of memory. Double current capacity whenever capacity reached. When increasing capacity, it allocates new chunk of memory and copy over the previous values to new location.\n",
    "\n",
    "**Runtime**\n",
    "\n",
    "indexing: $O(1)$\n",
    "\n",
    "searching: $O(n)$\n",
    "\n",
    "insertion: $O(n)$ *Note: $O(1)$ Amortized*\n",
    "\n",
    "deletion: $O(n)$ \n",
    "\n",
    "### 2 Linked List\n",
    "Most commonly refers to singly linked list. Data stored in nodes where each node has a reference to the next node. There are doubly linked list and circular linked list as well.\n",
    "\n",
    "**Runtime**\n",
    "\n",
    "indexing: $O(n)$\n",
    "\n",
    "searching: $O(n)$\n",
    "\n",
    "insertion: $O(1)$\n",
    "\n",
    "deletion: $O(1)$ \n",
    "\n",
    "Stack and queue are often implemented with linked list because linked list are most performant for insertion/deletion, which are the most frequently used operations for stacks/queues.\n",
    "\n",
    "**Stack** Last in First Out (LIFO)\n",
    "\n",
    "**Queue** First in First Out (FIFO)\n",
    "\n",
    "### 3 Hash Table (Hash Map)\n",
    "An usually unordered data structure that maps keys to values. A hash (preferably unique) is computed for a given key and its value will be stored in the corresponding bins or index according to the hash. Internally the bins can be an array. Collision can happen when multiple keys are mapped to the same hash. Common resolution is to store a list/linked-list at each bin/index location (called chaining).\n",
    "\n",
    "**Runtime**\n",
    "\n",
    "value lookup: $O(1)$\n",
    "\n",
    "insertion: $O(1)$\n",
    "\n",
    "deletion: $O(1)$ \n",
    "\n",
    "### 4 Binary Search Tree (BST)\n",
    "A binary tree with extra condition that each node is greater than or equal to all nodes in left sub-tree, and smaller than or equal to all nodes in right sub-tree.\n",
    "\n",
    "**Runtime**\n",
    "\n",
    "searching: $O(log\\ n)$\n",
    "\n",
    "insertion: $O(log\\ n)$\n",
    "\n",
    "deletion: $O(log\\ n)$ \n",
    "### 5 Heap (Max Heap/Min Heap)\n",
    "A binary tree with the condition that parent node's value is bigger/smaller than its children. So root is the maximum in a max heap and minimum in min heap. Priority queue is also referred to as heap because it's usually implemented by a heap.\n",
    "\n",
    "**Runtime**\n",
    "\n",
    "min/max: $O(1)$\n",
    "\n",
    "insertion: $O(log\\ n)$\n",
    "\n",
    "deletion: $O(log\\ n)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms\n",
    "### 1 Sorting\n",
    "**Bubble Sort**\n",
    "\n",
    "Iterate through entire list while comparing pairs and swap positions based on their values until all elements sorted.\n",
    "\n",
    "$O(n^2)$ but fast if list is almost sorted.\n",
    "\n",
    "\n",
    "**Insertion Sort**\n",
    "\n",
    "Iterates through unsorted list while building a sorted list. For each value encountered in unsorted list, find appropriate place in sorted list and insert it.\n",
    "\n",
    "$O(n^2)$\n",
    "\n",
    "**Merge Sort**\n",
    "\n",
    "A type of divide and conquer algorithm: 1) divides the list into two equally sized sub lists 2) sort each sub list 3) merge two sorted lists into final list.\n",
    "\n",
    "$O(n\\ log\\ n)$ - needs to divide $log\\ n$ times, and for each divide, it needs to go through all $n$ items to merge, thus $ n\\ times\\ log\\ n$. \n",
    "\n",
    "**Heap Sort**\n",
    "\n",
    "1) Build a heap (min or max) from the unsorted list 2)repeatedly remove the root node from the heap and put into the sorted list.\n",
    "\n",
    "$O(n\\ log\\ n)$ - remove root node is $O(log \\ n)$, and has to be repeated for each node, thus  $ n\\ times\\ log\\ n$. \n",
    "\n",
    "**Quick Sort**\n",
    "\n",
    "A type of divide and conquer algorithm: 1) pick an item in the unsorted list as pivot 2) divided list into 2 sub lists, one contains elements smaller than pivot while the other contains elements greater than the pivot 3) sort the sub lists, and combine the results into final list.\n",
    "\n",
    "$O(n\\ log\\ n)$ - need to divide $O(log \\ n)$ times, and after each divide, the partioning has to go through all elements, thus overall runtime $ n\\ times\\ log\\ n$. \n",
    "\n",
    "\n",
    "## 2 Searching\n",
    "**Linear Search** $O(n)$\n",
    "\n",
    "**Binary Search** $O(log\\ n)$\n",
    "\n",
    "**Breadth-First-Search (BFS)** Siblings first then children. Use queue usually.\n",
    "\n",
    "**Depth-First-Search (DFS)** Children first then siblings. Use stack usually.\n",
    "\n",
    "**A\\* Search** Goal is to find the shortest path between 2 nodes in a graph. It's a best-first search. At each iteration it finds the next node to extend the path based on the criteria $g(next) + h(next)$ where g is the distance from next node to starting node and h is the heuristic (estimated) distance of next node to final node. use a heap usually.\n",
    "\n",
    "## 3 Tree Traversals\n",
    "**Inorder** (Left, Root, Right): useful for getting sorted list out of BST\n",
    "\n",
    "**Preorder** (Root, Left, Right) :useful for making copy of binary trees, or evaluate expression trees.\n",
    "\n",
    "**Postorder** (Left, Right, Root): useful for deleting trees (because need to delete children before deleting parent)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}