- How to solve?
- verify the constraints
- write out some test cases
- figure out a solution without code
- write out our solution in code
- double check for errors
- algorithmic approaches
- sorting
- divide and conquer
- greedy method: optimization problem (max or min)
- dynamic programming: optimization problem (max or min)
- backtracking
- recursion
- Arrays
- hash map
- two-pointer
- Strings
- sliding window
- Linked Lists
- singly vs doubly
- cycle detection
- Stacks vs Queues
- Recursion
- normal vs tail recursion
- divide & conquer
- multi-branched recursion
- breaks a problem into multiple smaller but same sub-problems
- combines the solutions of sub-problems into the solution for the original problem
- patterns: if, for ([] within []), check for relationship between is n and n-1
- sorting: quick sort, quick select
- search: binary search
- Binary Trees
- search
- breath first search
- iterative
- depth first search
- recursion
- determine traversal
- breath first search
- traversal
- pre-order traversal
- in-order traversal
- post-order traversal
- maximum depth
- number of nodes from root node to furthest leaf node
- full tree
- each node has either 0 or 2 children
- complete tree
- every level must be complete except last level is pushed as far left
- binary search tree
- all left nodes value < current node value
- all right nodes value > current node value
- no duplicate value
- heaps
- is a complete tree
- max/min heap
- use max heap to implement a priority queue
- priority queue
- holds a collection of elements, each with an associated priority
- allows access the element with the highest priority
- search
- 2D-Arrays
- traversal
- 4 directions: up, right, down, left
- sequential search: scan 2D array in a zigzag pattern
- breath first search: iterative
- depth first search: recursion
- values
- limited or unlimited
- traversal
- Graphs
- node(vertex) and connection(edge)
- connection
- cyclic vs acyclic
- unconnected
- undirected vs directed
- unweighted vs weighted
- examples: binary trees and 2D arrays
- representaion
- adjacency list
- adjacency matrix
- traversal
- breath first search: iterative
- depth first search: recursion
- topological sort
- indegree: how many connections are coming into a vertex
- topological ordering
- remove any vertex with indegree = 0 and push to array
- reduce indegree of attached vertices by 1
- continue until all vertices are removed
- topological order is possible for directed acyclic graph (DAG)
- dijkstra's algorithm
- a greedy method approach
- works for postive weight only
- cannot work for negative cycle
- bellman-ford algorithm
- dynamic programming approach
- state space tree
- cannot work for negative cycle
- can detect negative cycle
- Dynamic Programming
- recursive solution from recurrence relation
- memorize redundant recursive call (state-space tree)
- top down approach
- bottom up tabulation (convert recursion to iterative solution)
- remove the need for call stack that come with recursion
- bottom up optimization
- reduce size of dp array
- Dynamic Programming List
- Backtracking
- return all solutions (paths)
- backtrack when violate constraints
- return a valid solution amongst all solutions
- by brute force
- by recursive: add, decide, remove
chesterheng/big-tech-interviews
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|