General
Algorithm
- Ask clarifying questions
- Come up with an approach, without writing any code yet
- Validate the approach with the recruiter
- Implement the solution with code
- Demonstrate correctness by running through test cases
Data Structure
- String
- represents characters in aother data scture, e.g. hashtable, bit map
- sliding window
- Linked List
- fast-slow pointers
- dummy nodes
- doubly linked list (LRU, LFU)
- Queue (FIFO)
- ArrayDequeue, LinkedList
- methods:
offer(),poll(),peek()
- Stack (FILO)
- methods:
push(),pop(),peek() - monotonic stack
- methods:
- Heap
- compelete binary tree in array (i -> 2i, 2i+1)
- heapify: Log(n)
- topK problem
- Tree
- binary search tree
- inorder (stack / recursion), preorder, postorder
- Hash Tables
- open address: liner probing, rehash
- close address: chain
- Graph
- dfs: recurision
- bfs: queue
- toplogical sort
- Searching
- binary search: log(n)
- Sorting
- Recursion
- back tracking: condition to add result, move back
Videos
Data Structure (C++)- mycodeschool
MIT6.006 Introduction to Algorithm, Spring 2020
MIT6.006 Introduction to Algorith, Fall 2011
System Design
- Not Dos (Restriction & Assumption)
- Functional Spec
- Technical Spec
- Related Problems
Data Volumn Estimations
bit, byte, kb, mb, gb, tb
My SQL
| Type | Size |
|---|---|
| INT | 4 Byte |
| BIGINT | 8 Byte |
| FLOAT | 4 Byte |
| DOUBLE | 8 Byte |
| DATE | 3 Byte |
| DATETIME | 8 Byte |
| TEXT | string length + 2 Bytes |
Java
| Type | Size |
|---|---|
| int | 4 Byte |
| long | 8 Byte |
| fload | 4 Byte |
| double | 8 Byte |
| char | 2 Byte |
Scalability Web Development
Components
- DNS
- Load Balancer
- Distributed Cache:
- Write around, Write back, Write through
- LRU (HashMap + Doubly Linked List), LFU (3 HashMaps w Doubly Linked List)
- Consistent Hashing
- Distributed DB:
- Relational: B tree
- None Relational: LSM (log structured merge tree)
- Sharding
- Replication
- CDN
- Multi AZ
Offers
- L5 AWS Route53
- L5 AWS OpenSearch