notes

Topics

• Arrays, Strings
• Linked List
• Stack & Queue
• Trees (BST, AVL)
• Graphs (BFS, DFS)
• Heap / Priority Queue
• Dynamic Programming

Notes

• Time Complexity: Always optimize brute force → O(n log n) or O(n)
• Heap Usage: Use for Top K problems, priority-based selection
• Graph: BFS → shortest path, DFS → traversal
• DP: Identify overlapping subproblems + memoization

---

Important Problem: Top K Frequent Elements

Problem: Given an array of integers, return the k most frequent elements.

Key Points

• Order does not matter
• Focus on frequency, not value
• Works with duplicates and negative numbers

Approach 1: Sorting (O(n log n))

1. Count frequency using HashMap
2. Convert map → array
3. Sort by frequency (descending)
4. Return first k elements

function topKFrequent(nums, k) {
    const freqMap = new Map();

    for (let num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    const arr = Array.from(freqMap.entries());
    arr.sort((a, b) => b[1] - a[1]);

    return arr.slice(0, k).map(item => item[0]);
}
      

Time: O(n log n)

Approach 2: Min Heap (O(n log k))

• Use a min heap of size k
• Remove smallest frequency when size exceeds k
• Keeps only top k elements

Time: O(n log k)

Approach 3: Bucket Sort (O(n))

1. Build frequency map
2. Create buckets (index = frequency)
3. Store elements in buckets
4. Traverse from highest frequency

function topKFrequent(nums, k) {
    const freqMap = new Map();

    for (let num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    const buckets = Array(nums.length + 1).fill().map(() => []);

    for (let [num, freq] of freqMap.entries()) {
        buckets[freq].push(num);
    }

    const result = [];

    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }

    return result.slice(0, k);
}
      

Time: O(n)

Interview Tip

• Start with sorting (baseline)
• Optimize using heap
• Mention bucket sort for best answer

Topics

• Scalability (Horizontal vs Vertical)
• Load Balancers
• Caching (Redis, CDN)
• Database Scaling (Sharding, Replication)
• Microservices

Notes

• CAP Theorem: Choose between Consistency, Availability, Partition tolerance
• Caching: Reduces DB load, improves latency
• Rate Limiter: Token bucket / sliding window
• Design Tip: Always start with requirements → scale later

Topics

• Threads vs Processes
• Synchronization (Mutex, Semaphore)
• Deadlocks
• Race Conditions

Notes

• Race Condition: Multiple threads modifying shared data
• Deadlock: Circular wait → avoid using ordering
• Thread Pool: Improves performance

Topics

• SQL vs NoSQL
• Indexing
• Transactions (ACID)
• Normalization

Notes

• Index: Improves read performance but slows writes
• ACID: Atomicity, Consistency, Isolation, Durability
• NoSQL: Use for scalability and flexible schema

• Process Scheduling (FCFS, Round Robin)
• Memory Management
• Paging & Segmentation

Notes

• Context Switching: CPU switching between processes
• Virtual Memory: Uses disk as RAM

• HTTP / HTTPS
• TCP vs UDP
• DNS

Notes

• TCP: Reliable but slower
• UDP: Faster but unreliable
• HTTPS: Secure using SSL/TLS

• Ownership & Responsibility
• Handling Production Issues
• Mentoring Juniors
• Conflict Resolution

Notes

• Use STAR method (Situation, Task, Action, Result)
• Focus on real production experience