• Big O Cheat Sheet
• Know Thy Complexities!

1. Understand the Problem

2. Explore Concrete Examples

3. Break It down

4. Solve/ Simplify

5. Look Back and Refactor

• Related to hash table
• Using objects, sets to collect value/frequencies of values
• Can often avoid nested loop or O(n^2) operations with arrays/strings

• Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on certain condition
• Very efficient for solving problems with minimal space complexity as well

• Create a window: can either be an array or number from one position to another
• Depending on certain condition, the window either increases or closes (and a new window is created)
• Useful for keeping track of a subset of data in an array/string

• dividing a data set into smaller chunks then repeating a process with a subset of data
• Can extremely decrease time complexity

• Call stack

• Base case: condition to end the recursion
• Different input

• No base case
• Forget to return or returning the wrong thing
• stack overflow

• create a recursion method inside function to do recursion tasks

• Best: O(1)
• Worst: O(n)
• Average: O(n)

• much faster form of search
• rather than eliminating one element at a time, we eliminating half of the remaining elements at a time
• only works on sorted array
• idea: divide and conquer

• input: sorted array, a value
• output: index of value in sorted array
• create left pointer at start
• create right pointer at end
• while left pointer right pointer
  • create middle pointer
  • if value > middle => move the left up
  • if value < middle => move the right down
  • if value = middle return index
• If never find the value, return -1

• visual algo

• idea: largest values bubbles up to the top

• start loop: i = arr.length => > 0
  • nested loop: j = 0; j < i -1; j++
  • if arr[j] > arr[j+1] => swap

1. Idea

• function merging two sorted arrays
• this function should run in O(n+m) time and O(n+m) space and should not modify the parameters passes to it

2. Pseudocode

• create empty array, take a look at smallest values in each input array
• While loop through all element of two array
  • If value in first array < value in second array, push it to the results then move on to next value in first array
  • If value in second array < value in first array....

1. Idea

• Exploit the fact that array of 0 or 1 element always sorted
• Using recursion, mid, left, right pointers and slice to break down the input array into array with empty or one element
• Using merged sorted array function to merge

2. Pseudocode

3. Big O

   • best: O(nlogn)
   • average: O(nlogn)
   • worst: O(nlogn)
   • space complexity: O(n)

• data structure contains a head, tail and length property
• Linked lists consists of nodes, and each nodes has a value, a pointer to another node or null

• Data Structures in JavaScript: Singly Linked Lists

• all concept where LIFO
• add and remove at O(1)

• Managing function invocation
• undo/ redo
• routing (history object)

• using arrays
• using linked list

• insertion O(1)
• removal O(1)
• accession O(n)
• search O(n)

• Data structure FIFO
• use in: background tasks, uploading resources, printing, task processing

• insertion O(1)
• removal O(1)
• accession O(n)
• search O(n)

• a data structure that consists of nodes in a parent/ child relationship
• Lists: linear
• Trees: nonlinear

• Root
• Child
• Parent
• Sibling
• Leaf
• Edge: the arrow

• HTML DOM
• Network routing
• Abstract syntax tree
• AI
• Folder in OS

• parent have max 2 nodes
• every left children < parent
• every right children > parent

• take advantage of Queue - FIFO
• visit the list and keep track of what visited

1. InOrder

• visit the most left first, then parent node, then right, then root and to most right

2. PostOrder Idea

• visit all children before visit the parent nodes and the root
• this mean we will push the cur node to store after recursively loop through the tree

3. PreOrder Idea

• visit the root first

• then left

• then right

  Steps - Recursively

• Create a var to store the values of nodes visited

• Store the root node of the BST in a variable called current

• Write a helper function which accepted a node

  • push the value of the node to the var that stores the values
  • if the node has left property, call the helper with the left property on the node
  • if the node has right property, call the helper with the right property on the node

  When to use DFS - BFS

  DFS and BFS time complexity are same, we need to visit all nodes once. The different is space complexity when we need to store visited node to the Queue

  1. DFS
  • goal is depp => dfs reach deep more faster
  2. BFS
  • goal is shallow => bfs
  3. In reality
  • BFS take a lot of memory make it impractical even in case DFS is not optimal
  4. DFS types
  • When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

• Similar BST with some different rules:

  • MaxBinaryHeap Parent nodes are > children nodes
  • MinBinaryHeap parent < children
  • for any parent index n (index start at 0)
    • left child is stored at 2n + 1
    • right child is at 2n + 2
  • for child index n
    • parent (n-1)/2
  1. Max Binary Heap
  • Each parent has at most two children
  • parent > children
  • siblings can > or <, =
  • as compact as possible: all children node are as full as they can be and left children are filled out first
  2. Min Binary Heap
  • Parent < children

-   Priority Queue
-   Graph Traversal

1. Definition
- a data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities
2. Implement Priority Queue base on binary heap

• useful for sorting, and implement other data structures like priority queue
• time complexity insert and extract: O(logn)

• What a hash table is
• Define what a hashing algorithm
• what make good a good hashing algorithm
• how collision occur in a hash table

• store in key-value pairs
• like array but not store in ordered
• unlike array, hash table fast for: finding, adding, removing
• hash table is commonly used

What make a good hash

• fast (like constant time)
• doesn't cluster outputs at specific indices, but distributed uniformly
• deterministic (same input yields same output)

1. Separate Chaining

• at each index in our array we store values using a more sophisticated data structure (eg. an array or linked list)

• this allow us to store multiple key-value pairs at the same index => store more than size

• Pseudocode - set

  • accept key, value
  • hashed the key
  • store the key-value pair in the hash table array via separate chaining

• Pseudocode - get

  • accept key
  • hashed the key
  • receive the key-value pair in hash table
    • if the key-value pair is array - loop through the array and check for the right key
  • if the key isn't found, return undefined

• keys/ values methods: each value in values array should be unique

2. Linear Probing

• when we find a collision, we search through the array to find the next empty slot
• this allow us to store single key-value at each index => store as size

Average case

• Insert: O(1)
• Deletion: O(1)
• Access: O(1)

• hash table 1

• hash table 2

• Cấu trúc dữ liệu & giải thuật
• Blind 75