O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

// O(1) Constant
array[index], map.get(key)

// O(log n) Logarithmic
binarySearch, balanced tree ops

// O(n) Linear
linear search, array traversal

// O(n log n) Linearithmic
mergeSort, quickSort average

// O(n²) Quadratic
nested loops, bubble sort

// O(2ⁿ) Exponential
recursive fibonacci, subset generation

Common Uses

• Algorithm analysis
• Performance comparison

Key Notes

• Describes worst-case unless specified
• Drop constants and lower-order terms

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

binarySearch([1, 3, 5, 7, 9, 11], 7) // Returns: 3
binarySearch([1, 3, 5, 7, 9, 11], 4) // Returns: -1

Common Uses

• Searching in sorted arrays
• Finding insertion points

Key Notes

• Array must be sorted
• Use safe mid calculation to avoid overflow

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

quickSort([64, 34, 25, 12, 22, 11, 90])
// Returns: [11, 12, 22, 25, 34, 64, 90]

Common Uses

• General purpose sorting
• When average case performance matters

Key Notes

• Not stable by default
• Performance depends on pivot selection

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

mergeSort([64, 34, 25, 12, 22, 11, 90])
// Returns: [11, 12, 22, 25, 34, 64, 90]

Common Uses

• When stability is required
• External sorting (large datasets)

Key Notes

• Stable sorting algorithm
• Consistent O(n log n) performance

// JavaScript Map
const map = new Map();
map.set(key, value);
const value = map.get(key);
map.has(key);
map.delete(key);
map.clear();

// JavaScript Object
const obj = {};
obj[key] = value;
const value = obj[key];
delete obj[key];

const userAges = new Map();
userAges.set('Alice', 25);
userAges.set('Bob', 30);
console.log(userAges.get('Alice')); // 25
console.log(userAges.has('Charlie')); // false

Common Uses

• Caching and memoization
• Counting frequencies

Key Notes

• Collision handling affects performance
• Load factor should be managed

// Pre-order (Root -> Left -> Right)
function preOrder(root) {
  if (!root) return [];
  return [root.val, ...preOrder(root.left), ...preOrder(root.right)];
}

// In-order (Left -> Root -> Right)
function inOrder(root) {
  if (!root) return [];
  return [...inOrder(root.left), root.val, ...inOrder(root.right)];
}

// Post-order (Left -> Right -> Root)
function postOrder(root) {
  if (!root) return [];
  return [...postOrder(root.left), ...postOrder(root.right), root.val];
}

// Level-order (BFS)
function levelOrder(root) {
  if (!root) return [];
  const queue = [root], result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

//     1
//    / \
//   2   3
//  / \
// 4   5

// Pre-order: [1, 2, 4, 5, 3]
// In-order: [4, 2, 5, 1, 3]
// Post-order: [4, 5, 2, 3, 1]
// Level-order: [1, 2, 3, 4, 5]

Common Uses

• Tree processing
• Expression evaluation

Key Notes

• In-order gives sorted sequence for BST
• Pre-order useful for tree copying

// Memoization (Top-down)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;
  memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  return memo[n];
}

// Tabulation (Bottom-up)
function fibTab(n) {
  if (n <= 2) return 1;
  const dp = [0, 1, 1];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

// Space-optimized
function fibOptimal(n) {
  if (n <= 2) return 1;
  let prev2 = 1, prev1 = 1;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

// Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21...
fibMemo(10);    // 55
fibTab(10);     // 55
fibOptimal(10); // 55

// Other DP problems:
// - Coin Change
// - Longest Common Subsequence
// - 0/1 Knapsack
// - Edit Distance

Common Uses

• Optimization problems
• Avoiding repeated calculations

Key Notes

• Requires overlapping subproblems
• Optimal substructure property needed

// Transform
arr.map(fn)           // Transform each element
arr.flatMap(fn)       // Map + flatten

// Filter
arr.filter(fn)        // Keep elements that pass test
arr.find(fn)          // First element that passes test
arr.findIndex(fn)     // Index of first match

// Test
arr.some(fn)          // True if any element passes test
arr.every(fn)         // True if all elements pass test
arr.includes(value)   // True if array contains value

// Aggregate
arr.reduce(fn, init)  // Reduce to single value
arr.reduceRight(fn)   // Reduce from right to left

// Modify
arr.sort(compareFn)   // Sort in place
arr.reverse()         // Reverse in place
arr.splice(start, deleteCount, ...items)

const nums = [1, 2, 3, 4, 5];

// Transform
nums.map(x => x * 2);              // [2, 4, 6, 8, 10]
[1, [2, 3], 4].flatMap(x => x);    // [1, 2, 3, 4]

// Filter
nums.filter(x => x > 3);           // [4, 5]
nums.find(x => x > 3);             // 4

// Test
nums.some(x => x > 3);             // true
nums.every(x => x > 0);            // true

// Aggregate
nums.reduce((sum, x) => sum + x);  // 15

Common Uses

• Data transformation
• Functional programming

Key Notes

• Most methods return new arrays (immutable)
• sort() and reverse() mutate original array

// Promise
const promise = new Promise((resolve, reject) => {
  // async operation
  if (success) resolve(result);
  else reject(error);
});

// Async/Await
async function fetchData() {
  try {
    const response = await fetch('/api/data');
    const data = await response.json();
    return data;
  } catch (error) {
    console.error('Error:', error);
  }
}

// Promise chaining
fetch('/api/data')
  .then(response => response.json())
  .then(data => console.log(data))
  .catch(error => console.error(error));

// Promise utilities
Promise.all([p1, p2, p3])      // Wait for all
Promise.allSettled([p1, p2])   // Wait for all (no fail-fast)
Promise.race([p1, p2])         // First to complete

// Sequential execution
async function sequential() {
  const result1 = await operation1();
  const result2 = await operation2();
  return [result1, result2];
}

// Parallel execution
async function parallel() {
  const [result1, result2] = await Promise.all([
    operation1(),
    operation2()
  ]);
  return [result1, result2];
}

Common Uses

• API calls
• File operations

Key Notes

• async/await is syntactic sugar over Promises
• Use Promise.all() for parallel execution

// List implementations
List<String> arrayList = new ArrayList<>();    // Resizable array
List<String> linkedList = new LinkedList<>();  // Doubly-linked list

// Set implementations
Set<String> hashSet = new HashSet<>();         // Hash table
Set<String> treeSet = new TreeSet<>();         // Red-black tree
Set<String> linkedHashSet = new LinkedHashSet<>(); // Hash + insertion order

// Map implementations
Map<String, Integer> hashMap = new HashMap<>();           // Hash table
Map<String, Integer> treeMap = new TreeMap<>();           // Red-black tree
Map<String, Integer> linkedHashMap = new LinkedHashMap<>(); // Hash + order

// Queue implementations
Queue<Integer> queue = new LinkedList<>();               // FIFO queue
PriorityQueue<Integer> pq = new PriorityQueue<>();       // Heap-based priority queue
Deque<Integer> deque = new ArrayDeque<>();               // Double-ended queue

// ArrayList operations
List<String> list = new ArrayList<>();
list.add("apple");           // O(1) amortized
list.get(0);                 // O(1)
list.remove(0);              // O(n)

// HashMap operations
Map<String, Integer> map = new HashMap<>();
map.put("key", 42);          // O(1) average
Integer value = map.get("key"); // O(1) average
map.containsKey("key");      // O(1) average

// TreeSet operations
Set<Integer> set = new TreeSet<>();
set.add(42);                 // O(log n)
boolean contains = set.contains(42); // O(log n)

Common Uses

• Data storage and retrieval
• Algorithm implementation

Key Notes

• ArrayList: Fast random access, slow insertion/deletion
• LinkedList: Fast insertion/deletion, slow random access

// Stream creation
Stream<String> stream = list.stream();
Stream<Integer> numbers = Stream.of(1, 2, 3, 4, 5);
Stream<Integer> range = IntStream.range(1, 10).boxed();

// Intermediate operations (lazy)
stream.filter(s -> s.length() > 3)
      .map(String::toUpperCase)
      .sorted()
      .distinct()
      .limit(10)
      .skip(2)

// Terminal operations (eager)
.collect(Collectors.toList())          // Collect to list
.forEach(System.out::println)          // Execute for each
.reduce(String::concat)                // Reduce to single value
.findFirst()                           // Get first element
.anyMatch(s -> s.startsWith("A"))     // Test if any match
.count()                               // Count elements

List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");

// Filter and transform
List<String> result = names.stream()
    .filter(name -> name.length() > 3)
    .map(String::toLowerCase)
    .sorted()
    .collect(Collectors.toList());
// Result: ["alice", "charlie", "david"]

// Group by length
Map<Integer, List<String>> grouped = names.stream()
    .collect(Collectors.groupingBy(String::length));
// Result: {3=["Bob"], 5=["Alice", "David"], 7=["Charlie"]}

// Find max by length
Optional<String> longest = names.stream()
    .max(Comparator.comparing(String::length));
// Result: Optional["Charlie"]

Common Uses

• Data processing pipelines
• Filtering and transforming collections

Key Notes

• Streams are lazy until terminal operation
• Intermediate operations return new streams

// Cache-Aside (Lazy Loading)
function getData(key) {
  let data = cache.get(key);
  if (!data) {
    data = database.get(key);
    cache.set(key, data, TTL);
  }
  return data;
}

// Write-Through
function setData(key, value) {
  database.set(key, value);
  cache.set(key, value, TTL);
}

// Write-Behind (Write-Back)
function setDataAsync(key, value) {
  cache.set(key, value, TTL);
  // Database write happens asynchronously
  writeQueue.push({key, value});
}

// Cache hierarchy example
// L1: Application cache (in-memory)
// L2: Distributed cache (Redis)
// L3: CDN (for static content)
// L4: Database query cache

// Cache eviction policies:
// - LRU (Least Recently Used)
// - LFU (Least Frequently Used)
// - FIFO (First In, First Out)
// - TTL (Time To Live)

// Cache warming
async function warmCache() {
  const popularItems = await getPopularItems();
  for (const item of popularItems) {
    cache.set(item.key, item.value, TTL);
  }
}

Common Uses

• Reducing database load
• Improving response times

Key Notes

• Choose appropriate cache size and TTL
• Consider cache coherence in distributed systems

// Round Robin
class RoundRobinBalancer {
  constructor(servers) {
    this.servers = servers;
    this.current = 0;
  }
  
  getServer() {
    const server = this.servers[this.current];
    this.current = (this.current + 1) % this.servers.length;
    return server;
  }
}

// Weighted Round Robin
class WeightedRoundRobin {
  constructor(servers) {
    this.servers = servers; // [{server, weight}, ...]
    this.currentWeights = servers.map(s => 0);
  }
  
  getServer() {
    let selected = 0;
    let total = 0;
    
    for (let i = 0; i < this.servers.length; i++) {
      this.currentWeights[i] += this.servers[i].weight;
      total += this.servers[i].weight;
      
      if (this.currentWeights[i] > this.currentWeights[selected]) {
        selected = i;
      }
    }
    
    this.currentWeights[selected] -= total;
    return this.servers[selected].server;
  }
}

// Load balancing algorithms:

// 1. Round Robin - Equal distribution
// Requests: A, B, C, A, B, C, ...

// 2. Weighted Round Robin - Based on capacity
// Server A (weight 3), Server B (weight 1)
// Requests: A, A, A, B, A, A, A, B, ...

// 3. Least Connections - Route to server with fewest active connections

// 4. IP Hash - Route based on client IP hash
// Ensures same client goes to same server

// 5. Health Check - Remove unhealthy servers
if (!server.isHealthy()) {
  removeFromPool(server);
}

Common Uses

• Distributing traffic across servers
• Preventing server overload

Key Notes

• Layer 4 (TCP) vs Layer 7 (HTTP) load balancing
• Health checks are crucial

-- INNER JOIN - Records that have matching values in both tables
SELECT columns
FROM table1
INNER JOIN table2 ON table1.key = table2.key;

-- LEFT JOIN - All records from left table + matching from right
SELECT columns
FROM table1
LEFT JOIN table2 ON table1.key = table2.key;

-- RIGHT JOIN - All records from right table + matching from left
SELECT columns
FROM table1
RIGHT JOIN table2 ON table1.key = table2.key;

-- FULL OUTER JOIN - All records when there's a match in either table
SELECT columns
FROM table1
FULL OUTER JOIN table2 ON table1.key = table2.key;

-- CROSS JOIN - Cartesian product of both tables
SELECT columns
FROM table1
CROSS JOIN table2;

-- Example tables:
-- Users: id, name
-- Orders: id, user_id, amount

-- Get users with their orders (only users who have orders)
SELECT u.name, o.amount
FROM users u
INNER JOIN orders o ON u.id = o.user_id;

-- Get all users, with their orders if they have any
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON u.id = o.user_id;

-- Get users who have never placed an order
SELECT u.name
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
WHERE o.user_id IS NULL;

Common Uses

• Combining data from multiple tables
• Data analysis and reporting

Key Notes

• Always consider performance implications
• Use proper indexes on join columns

// Resource-based URLs
GET    /api/users              // Get all users
GET    /api/users/123          // Get specific user
POST   /api/users              // Create new user
PUT    /api/users/123          // Update entire user
PATCH  /api/users/123          // Partial update
DELETE /api/users/123          // Delete user

// Nested resources
GET    /api/users/123/orders   // Get user's orders
POST   /api/users/123/orders   // Create order for user

// Query parameters for filtering/pagination
GET /api/users?page=1&limit=10&sort=name&filter=active

// Status codes
200 OK           // Success
201 Created      // Resource created
400 Bad Request  // Client error
401 Unauthorized // Authentication required
404 Not Found    // Resource not found
500 Server Error // Internal server error

// Good API design example

// Consistent naming (plural nouns)
GET /api/users
GET /api/products
GET /api/categories

// Nested resources
GET /api/users/123/orders/456
GET /api/categories/tech/products

// Filtering and sorting
GET /api/products?category=electronics&sort=price&order=desc

// Versioning
GET /api/v1/users
GET /api/v2/users

// Response format
{
  "data": [...],
  "meta": {
    "page": 1,
    "limit": 10,
    "total": 100
  },
  "links": {
    "next": "/api/users?page=2",
    "prev": null
  }
}

Common Uses

• Web and mobile applications
• Microservices communication

Key Notes

• Use HTTP methods semantically
• Keep URLs simple and predictable

// Repository setup
git init                    // Initialize new repo
git clone <url>            // Clone remote repo
git remote add origin <url> // Add remote

// Basic workflow
git status                 // Check status
git add <file>             // Stage changes
git add .                  // Stage all changes
git commit -m "message"    // Commit changes
git push origin main       // Push to remote
git pull origin main       // Pull from remote

// Branching
git branch                 // List branches
git branch <name>          // Create branch
git checkout <branch>      // Switch branch
git checkout -b <branch>   // Create and switch
git merge <branch>         // Merge branch
git branch -d <branch>     // Delete branch

// History and changes
git log                    // View commit history
git log --oneline          // Compact history
git diff                   // View changes
git diff --staged          // View staged changes
git show <commit>          // Show commit details

// Typical workflow
git checkout -b feature/new-feature
// Make changes
git add .
git commit -m "Add new feature"
git push origin feature/new-feature
// Create pull request
// After review and merge:
git checkout main
git pull origin main
git branch -d feature/new-feature

// Undo changes
git checkout -- <file>     // Discard unstaged changes
git reset HEAD <file>      // Unstage file
git reset --soft HEAD~1    // Undo last commit (keep changes)
git reset --hard HEAD~1    // Undo last commit (discard changes)

// Stashing
git stash                  // Temporarily save changes
git stash pop              // Apply and remove stash
git stash list             // List stashes

Common Uses

• Version control
• Collaboration

Key Notes

• Always commit with meaningful messages
• Use branches for features and fixes

import React, { useState, useEffect, useContext, useCallback, useMemo } from 'react';

// useState - State management
const [count, setCount] = useState(0);
const [user, setUser] = useState(null);

// useEffect - Side effects
useEffect(() => {
  // Effect logic
  return () => {
    // Cleanup logic
  };
}, [dependencies]);

// useCallback - Memoized function
const memoizedCallback = useCallback(() => {
  doSomething(a, b);
}, [a, b]);

// useMemo - Memoized value
const memoizedValue = useMemo(() => {
  return computeExpensiveValue(a, b);
}, [a, b]);

// useContext - Context consumption
const value = useContext(MyContext);

// Custom hook
function useCounter(initialValue = 0) {
  const [count, setCount] = useState(initialValue);
  const increment = () => setCount(c => c + 1);
  const decrement = () => setCount(c => c - 1);
  return { count, increment, decrement };
}

// Counter component with hooks
function Counter() {
  const [count, setCount] = useState(0);
  
  useEffect(() => {
    document.title = `Count: ${count}`;
  }, [count]);
  
  return (
    <div>
      <p>You clicked {count} times</p>
      <button onClick={() => setCount(count + 1)}>
        Click me
      </button>
    </div>
  );
}

// Data fetching with useEffect
function UserProfile({ userId }) {
  const [user, setUser] = useState(null);
  const [loading, setLoading] = useState(true);
  
  useEffect(() => {
    fetchUser(userId)
      .then(setUser)
      .finally(() => setLoading(false));
  }, [userId]);
  
  if (loading) return <div>Loading...</div>;
  return <div>{user?.name}</div>;
}

Common Uses

• State management in functional components
• Side effects and lifecycle

Key Notes

• Only call hooks at top level
• Don't call hooks inside loops or conditions

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
}

const list = new LinkedList();
// Insert: O(1) at head
// Search: O(n)
// Delete: O(1) with reference

Common Uses

• Dynamic memory allocation
• Implementing stacks/queues

Key Notes

• No random access
• Extra memory for pointers

// State hook
const [state, setState] = useState(initial);

// Effect hook
useEffect(() => {
  // side effect
  return () => cleanup();
}, [dependencies]);

function Counter() {
  const [count, setCount] = useState(0);
  
  useEffect(() => {
    document.title = `Count: ${count}`;
  }, [count]);
  
  return <button onClick={() => setCount(count + 1)}>
    {count}
  </button>;
}

Common Uses

• State management in functions
• Side effects and cleanup

Key Notes

• Only call at top level
• Don't call inside loops or conditions

GET    /users          # List users
GET    /users/:id      # Get specific user
POST   /users          # Create user
PUT    /users/:id      # Update user
DELETE /users/:id      # Delete user

// HTTP Status Codes
200 OK - Success
201 Created - Resource created
400 Bad Request - Client error
401 Unauthorized - Auth required
404 Not Found - Resource not found
500 Internal Server Error

Common Uses

• Web API development
• Microservices communication

Key Notes

• Use HTTP methods semantically
• Return appropriate status codes

// Inorder: Left -> Root -> Right
function inorder(node) {
  if (!node) return;
  inorder(node.left);
  visit(node);
  inorder(node.right);
}

// Preorder: Root -> Left -> Right
// Postorder: Left -> Right -> Root
// Level-order: BFS using queue

// Tree: [1,2,3]
// Inorder: [2,1,3]
// Preorder: [1,2,3]
// Postorder: [2,3,1]

Common Uses

• Tree processing
• Expression evaluation

Key Notes

• Inorder gives sorted sequence for BST
• Preorder useful for copying trees

-- INNER JOIN
SELECT * FROM users u
INNER JOIN orders o ON u.id = o.user_id;

-- LEFT JOIN
SELECT * FROM users u
LEFT JOIN orders o ON u.id = o.user_id;

-- Get users with their order count
SELECT u.name, COUNT(o.id) as order_count
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.id, u.name;

Common Uses

• Combining related data
• Data analysis and reporting

Key Notes

• INNER JOIN returns only matching rows
• LEFT JOIN includes all left table rows

// Basic types
string, number, boolean, array, object, null, undefined

// Array types
string[] or Array<string>

// Object types
interface User {
  id: number;
  name: string;
  email?: string; // optional
}

// Function types
type Handler = (event: Event) => void;

// Union types
type Status = 'loading' | 'success' | 'error';

// Generic types
interface Response<T> {
  data: T;
  status: number;
}

// Utility types
Partial<T>, Required<T>, Pick<T, K>, Omit<T, K>

// Interface vs Type
interface User {
  name: string;
}

type User = {
  name: string;
};

// Generic function
function identity<T>(arg: T): T {
  return arg;
}

// Utility type usage
type PartialUser = Partial<User>; // All properties optional
type UserName = Pick<User, 'name'>; // Only name property

Common Uses

• Type safety
• Better IDE support

Key Notes

• Interfaces are extendable, types are not
• Use strict mode for better type checking

// File operations
ls -la                 // List files with details
cp source dest         // Copy files
mv old new             // Move/rename files
rm -rf directory       // Remove directory recursively
find . -name "*.js"    // Find files by name

// Text processing
grep "pattern" file    // Search in files
sed 's/old/new/g' file // Replace text
awk '{print $1}' file  // Process columns
cat file               // Display file content
head -n 10 file        // First 10 lines
tail -f file           // Follow file changes

// Process management
ps aux                 // List processes
kill -9 PID            // Kill process
top                    // Monitor processes
jobs                   // List background jobs
nohup command &        // Run in background

// Common workflows

// Find and replace in multiple files
grep -r "oldText" . | xargs sed -i 's/oldText/newText/g'

// Monitor log files
tail -f /var/log/application.log

// Find large files
find . -type f -size +100M

// Check disk usage
du -sh * | sort -hr

// Network operations
curl -X GET https://api.example.com
wget https://example.com/file.zip

Common Uses

• System administration
• File management

Key Notes

• Be careful with rm -rf command
• Use man command for help

// Image operations
docker build -t myapp .           // Build image
docker pull nginx                 // Pull image
docker images                     // List images
docker rmi image_id               // Remove image

// Container operations
docker run -d -p 8080:80 nginx    // Run container
docker ps                         // List running containers
docker ps -a                      // List all containers
docker stop container_id          // Stop container
docker rm container_id            // Remove container
docker exec -it container_id bash // Execute command

// Docker Compose
docker-compose up -d              // Start services
docker-compose down               // Stop services
docker-compose logs               // View logs

// Dockerfile example
FROM node:16-alpine
WORKDIR /app
COPY package*.json ./
RUN npm install
COPY . .
EXPOSE 3000
CMD ["npm", "start"]

// Complete workflow

// 1. Create Dockerfile
FROM node:16-alpine
WORKDIR /app
COPY package*.json ./
RUN npm ci --only=production
COPY . .
EXPOSE 3000
USER node
CMD ["node", "server.js"]

// 2. Build and run
docker build -t myapp:latest .
docker run -d -p 3000:3000 --name myapp-container myapp:latest

// 3. Check logs
docker logs myapp-container

// 4. Clean up
docker stop myapp-container
docker rm myapp-container

Common Uses

• Application containerization
• Development environment consistency

Key Notes

• Use multi-stage builds for optimization
• Don't run as root in containers

// Compute
EC2         // Virtual servers
Lambda      // Serverless functions
ECS/EKS     // Container services

// Storage
S3          // Object storage
EBS         // Block storage
EFS         // File storage

// Database
RDS         // Relational databases
DynamoDB    // NoSQL database
ElastiCache // In-memory caching

// Networking
VPC         // Virtual private cloud
CloudFront  // CDN
Route 53    // DNS service
ELB         // Load balancing

// Monitoring & Security
CloudWatch  // Monitoring & logging
IAM         // Identity & access management
CloudTrail  // API logging

// Common architectures

// Web application stack:
// Route 53 -> CloudFront -> ALB -> EC2/ECS -> RDS
// 
// Serverless stack:
// API Gateway -> Lambda -> DynamoDB
//                     -> S3
//                     -> SQS

// Microservices pattern:
// Internet Gateway
//     |
// Application Load Balancer
//     |
// ECS Services (multiple)
//     |
// RDS + ElastiCache

// Cost optimization:
// - Use Reserved Instances for predictable workloads
// - Spot Instances for fault-tolerant workloads
// - S3 lifecycle policies for data archiving
// - CloudWatch for monitoring and alerting

Common Uses

• Scalable web applications
• Data processing pipelines

Key Notes

• Follow principle of least privilege
• Use CloudFormation for infrastructure as code

// Array/List
// Access: O(1), Search: O(n), Insert: O(n), Delete: O(n)

// Dynamic Array (ArrayList)
// Access: O(1), Search: O(n), Insert: O(1) amortized, Delete: O(n)

// Linked List
// Access: O(n), Search: O(n), Insert: O(1), Delete: O(1)

// Hash Table
// Access: N/A, Search: O(1), Insert: O(1), Delete: O(1)
// Worst case: O(n) for all operations

// Binary Search Tree
// Access: O(log n), Search: O(log n), Insert: O(log n), Delete: O(log n)
// Worst case: O(n) when unbalanced

// Heap (Binary)
// Access: O(n), Search: O(n), Insert: O(log n), Delete: O(log n)
// Find min/max: O(1)

// Trie
// Search: O(m), Insert: O(m), Delete: O(m)
// where m is the length of the key

// When to use each structure:

// Array: Fast random access, fixed size
const scores = [95, 87, 92, 78, 96];
console.log(scores[2]); // O(1) access

// Linked List: Frequent insertions/deletions
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Hash Table: Fast lookups
const userMap = new Map();
userMap.set('user123', userData); // O(1)

// BST: Ordered data with fast operations
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
  }
}

// Heap: Priority queue operations
class MinHeap {
  // Insert: O(log n), extractMin: O(log n)
}

Common Uses

• Algorithm optimization
• System design decisions

Key Notes

• Choose structure based on operation frequency
• Consider space-time tradeoffs

// Two Pointers
// Use for: sorted arrays, palindromes, pair finding
function twoSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
}

// Sliding Window
// Use for: subarray problems, max/min in windows
function maxSumSubarray(arr, k) {
  let maxSum = 0, windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  maxSum = windowSum;
  
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Fast & Slow Pointers
// Use for: cycle detection, middle element
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Pattern selection guide:

// Two Pointers: Valid Palindrome, Container With Most Water
// Sliding Window: Longest Substring Without Repeating Characters
// Fast & Slow: Linked List Cycle, Finding Middle of Linked List
// Merge Intervals: Meeting Rooms, Insert Interval
// Cyclic Sort: Find Missing Number, Find Duplicate Number
// Tree DFS: Path Sum, Maximum Depth of Binary Tree
// Tree BFS: Level Order Traversal, Minimum Depth
// Topological Sort: Course Schedule, Alien Dictionary
// Binary Search: Search in Rotated Array, Find Peak Element
// Backtracking: N-Queens, Sudoku Solver, Permutations
// Dynamic Programming: Coin Change, Longest Common Subsequence

Common Uses

• Coding interviews
• Algorithm optimization

Key Notes

• Learn to recognize problem patterns
• Practice implementation variations

// Service Discovery
// Services register themselves and discover others
// Tools: Consul, Eureka, Zookeeper

// API Gateway
// Single entry point for client requests
// Handles: routing, authentication, rate limiting

// Circuit Breaker
// Prevents cascade failures
class CircuitBreaker {
  constructor(threshold, timeout) {
    this.threshold = threshold;
    this.timeout = timeout;
    this.failureCount = 0;
    this.state = 'CLOSED'; // CLOSED, OPEN, HALF_OPEN
  }
  
  async call(operation) {
    if (this.state === 'OPEN') {
      throw new Error('Circuit breaker is OPEN');
    }
    
    try {
      const result = await operation();
      this.onSuccess();
      return result;
    } catch (error) {
      this.onFailure();
      throw error;
    }
  }
}

// Event Sourcing
// Store events instead of current state
// Enables: audit trail, replay, temporal queries

// CQRS (Command Query Responsibility Segregation)
// Separate read and write models

// Microservices communication patterns:

// 1. Synchronous (HTTP/REST)
const userService = {
  async getUser(id) {
    return await fetch(`/user-service/users/${id}`);
  }
};

// 2. Asynchronous (Message Queues)
const eventBus = {
  publish(event, data) {
    // Publish to message queue (RabbitMQ, Apache Kafka)
  },
  subscribe(event, handler) {
    // Subscribe to events
  }
};

// 3. Database per Service
// Each service has its own database
// Challenges: transactions, data consistency

// 4. Saga Pattern (Distributed Transactions)
class OrderSaga {
  async processOrder(order) {
    try {
      await this.reserveInventory(order);
      await this.processPayment(order);
      await this.shipOrder(order);
    } catch (error) {
      await this.compensate(order, error);
    }
  }
}

Common Uses

• Large scale applications
• Team autonomy

Key Notes

• Start with monolith, evolve to microservices
• Network latency becomes significant

enum Color { RED, BLACK }
class RBNode {
  constructor(data, color = Color.RED) {
    this.data = data;
    this.color = color;
    this.left = this.right = this.parent = null;
  }
}

// All operations guaranteed O(log n)
// Used in: Java TreeMap, C++ std::map
// Better insert/delete than AVL
// Slightly slower search than AVL

Common Uses

• Language libraries (TreeMap)
• Operating system schedulers

Key Notes

• Root is always black
• Red nodes can't have red children

class SkipListNode {
  constructor(data, level) {
    this.data = data;
    this.forward = new Array(level + 1).fill(null);
  }
}

// Probabilistic O(log n) operations
// Level 0: [1, 3, 6, 9, 12]
// Level 1: [1, 6, 12]
// Level 2: [6]
// Express lanes for faster traversal

Common Uses

• Redis sorted sets
• Concurrent data structures

Key Notes

• Simpler than balanced trees
• Good for concurrent access

class SplayTree {
  search(data) {
    const node = this.searchNode(data);
    if (node) this.splay(node); // Move to root
    return node;
  }
}

// Recently accessed elements move to root
// Excellent for temporal locality
// Zig, Zig-Zig, Zig-Zag rotations
// Adaptive to access patterns

Common Uses

• Caches with locality
• Compiler symbol tables

Key Notes

• Self-optimizing structure
• No balance guarantees per operation

class BTreeNode {
  constructor(minDegree, isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
    this.minDegree = minDegree;
  }
}

// High branching factor reduces height
// All leaves at same level
// 2t-1 max keys per node (t = min degree)
// Minimizes disk I/O operations

Common Uses

• Database indexes (MySQL, PostgreSQL)
• File systems (NTFS, ext4)

Key Notes

• Optimized for block storage
• High branching factor

class RopeLeaf {
  constructor(data) {
    this.data = data;
    this.length = data.length;
  }
}

class RopeInternal {
  constructor(left, right) {
    this.left = left;
    this.right = right;
    this.length = left.length + right.length;
  }
}

// O(1) concatenation vs O(n+m) for strings
// O(log n) insert/delete vs O(n)
// Excellent for large text documents
// Used in text editors and version control

Common Uses

• Text editors (large documents)
• Version control systems

Key Notes

• Trade random access for edit speed
• Immutable operations create new ropes

// Persistent List (functional)
class ConsList {
  constructor(head, tail) {
    this.head = head;
    this.tail = tail;
  }
  push(value) {
    return new ConsList(value, this);
  }
}

const list1 = persistentList(1, 2, 3);
const list2 = list1.push(4); // New version
const list3 = list1.set(1, 99); // Another version
// All versions coexist and share memory

Common Uses

• Version control systems
• Undo/redo functionality

Key Notes

• Immutable by design
• Structural sharing saves memory