Data Structures and Algorithms (DSA) in Java : Helpful Tips for Coding Interviews

DSA With Java

This roadmap provides a crash course in Data Structures and Algorithms (DSA) using Java, designed to help you master key concepts, implementations, and problem-solving skills for coding interviews and real-world applications. With 230 lessons, 22 quizzes, 65 challenges, and interview questions per topic, this structured 5-week plan (extendable with additional topics) equips you with the tools to excel. Each section includes detailed descriptions, key points, and Java code snippets to solidify your understanding.

Week 1: Complexity Measures and Arrays

1. Complexity Measures

Crash Course Description: Dive into algorithm efficiency by learning to measure time and space complexity using Big O notation. Understand asymptotic analysis to compare algorithms and tackle nested loop challenges to master complexity calculations.

Comparing Algorithms

• Description: Learn to evaluate algorithms based on time and space complexity to choose the most efficient one for a problem. Compare trade-offs in performance.

• Key Points: Use Big O to quantify runtime; consider best, average, and worst cases.

• Example: Linear search (O(n)) vs. binary search (O(log n)).

Example: Measuring Time Complexity of a Single Loop Algorithm

Analyze the time complexity of a single loop iterating n times, typically O(n).

for (int i = 0; i < n; i++) {
    System.out.println(i); // O(1) operation
} // Total: O(n)

Example: Time Complexity of an Algorithm With Nested Loops

Understand how nested loops multiply complexities, e.g., two loops result in O(n²).

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j); // O(1)
    }
} // Total: O(n²)

Introduction to Asymptotic Analysis and Big O

• Description: Learn asymptotic analysis to describe algorithm performance as input size grows, focusing on Big O notation.

• Key Points: Big O ignores constants and lower-order terms (e.g., O(3n² + 2n) = O(n²)).

Other Common Asymptotic Notations and Why Big O Trumps Them

• Description: Explore Big Theta (Θ) and Big Omega (Ω); Big O is preferred for worst-case analysis simplicity.

• Key Points: Big O is upper bound, Θ is tight bound, Ω is lower bound.

Useful Formulae

• Description: Master formulas for summing loops, e.g., arithmetic series sum = n(n+1)/2.

• Example: Sum of 1 to n is O(n²) for a nested loop.

Common Complexity Scenarios

• Description: Recognize patterns like O(1) for constant operations, O(log n) for divide-and-conquer, and O(n!) for permutations.

• Key Points: Logarithmic complexity often arises in binary search or balanced trees.

Challenge: Big O of Nested Loop with Addition

• Description: Calculate complexity for loops where the inner loop’s iterations depend on addition (e.g., j < i + k).

• Key Points: Often reduces to O(n²) if iterations scale linearly.

Solution: Big O of a Nested Loop with Addition

Analyze and derive O(n²) for nested loops with additive dependencies.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i + 5; j++) { // O(n) per i
        // O(1) operation
    }
} // Total: O(n²)

Challenge: Big O of Nested Loop with Subtraction

• Description: Evaluate complexity when inner loop iterations decrease (e.g., j < n - i).

• Key Points: Still often O(n²) due to total iterations.

Solution: Big O of a Nested Loop with Subtraction

Confirm O(n²) for nested loops with subtraction-based bounds.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i; j++) { // O(n) per i
        // O(1)
    }
} // Total: O(n²)

Challenge: Big O of Nested Loop with Multiplication

• Description: Analyze loops where inner iterations scale multiplicatively (e.g., j < i * k).

• Key Points: May lead to higher complexities like O(n² log n) in some cases.

Solution: Big O of a Nested Loop with Multiplication

• Description: Derive complexity, typically O(n²) or higher, based on multiplicative bound

for (int i = 1; i < n; i++) {
    for (int j = 1; j < i * 2; j++) { // O(i)
        // O(1)
    }
} // Total: O(n²)

Challenges and Solutions: Nested Loop with Multiplication (Basic, Intermediate, Advanced, Pro)

• Description: Solve increasingly complex multiplicative loop challenges to practice complexity analysis.

• Key Points: Focus on simplifying bounds and analyzing iteration patterns.

• Code: Varies based on specific loop structures, typically O(n²) to O(n^k).

Complexity Interview Questions

• Description: Practice common interview questions on time and space complexity analysis.

• Example: “What’s the complexity of quicksort’s average case?” (Answer: O(n log n)).

2. Arrays

Crash Course Description: Get hands-on with arrays and lists in Java. Learn to manipulate, traverse, and optimize arrays through challenges like merging sorted arrays, finding pairs summing to a target, and rearranging elements.

What is an Array?

Arrays are fixed-size, contiguous memory structures storing elements of the same type, accessed by index in O(1).

int[] arr = new int[5]; // Fixed size array
arr[0] = 1; // O(1) access

Two Dimensional Arrays

2D arrays store data in rows and columns, ideal for matrices. Accessed as arr[i][j].

int[][] matrix = new int[3][3];
matrix[1][2] = 5; // Set value at row 1, column 2

What Is a List?

Lists (e.g., ArrayList) are dynamic arrays in Java, resizing automatically.

import java.util.ArrayList;

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // Dynamic resizing

Challenge: Remove Even Integers From Array

• Description: Remove all even numbers from an array, returning only odd numbers.

• Key Points: Use two-pointer technique or ArrayList for dynamic resizing.

Solution: Remove Even Integers From Array

Implement removal using a new array or in-place modification.

int[] removeEvens(int[] arr) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int num : arr) {
        if (num % 2 != 0) result.add(num);
    }
    return result.stream().mapToInt(i -> i).toArray();
}

Challenge: Merge Two Sorted Arrays

• Description: Combine two sorted arrays into one sorted array.

• Key Points: Use two pointers to compare and merge in O(n + m).

Solution: Merge Two Sorted Arrays

Implement merging with a new array.

int[] mergeSorted(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, k = 0;
    while (i < arr1.length && j < arr2.length) {
        result[k++] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
    }
    while (i < arr1.length) result[k++] = arr1[i++];
    while (j < arr2.length) result[k++] = arr2[j++];
    return result;
}

Challenge: Find Two Numbers That Add Up to K

• Description: Find two numbers in an array that sum to a target value k.

• Key Points: Use HashMap for O(n) or sorting for O(n log n).

Solution: Find Two Numbers That Add Up to K

Use HashMap to store complements.

int[] twoSum(int[] arr, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        if (map.containsKey(k - arr[i])) return new int[]{map.get(k - arr[i]), i};
        map.put(arr[i], i);
    }
    return new int[]{};
}

Challenge: Product of Array Except Self

• Description: Compute an array where each element is the product of all others.

• Key Points: Avoid division for O(n) solution using left and right products.

Solution: Product of Array Except Self

Use two-pass approach without division,

int[] productExceptSelf(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i-1] * arr[i-1]; // Left products
    }
    int right = 1;
    for (int i = n-1; i >= 0; i--) {
        result[i] *= right; // Multiply by right products
        right *= arr[i];
    }
    return result;
}

Challenge: Find Minimum Value in Array

• Description: Find the smallest element in an unsorted array.

• Key Points: Linear scan in O(n).

Solution: Find Minimum Value in Array

Iterate to find minimum.

int findMin(int[] arr) {
    int min = arr[0];
    for (int num : arr) {
        if (num < min) min = num;
    }
    return min;
}

Challenge: First Non-Repeating Integer in an Array

• Description: Find the first integer that appears only once.

• Key Points: Use HashMap to count frequencies.

Solution: First Non-Repeating Integer in an Array

Scan HashMap for first element with count 1.

int firstNonRepeating(int[] arr) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : arr) map.put(num, map.getOrDefault(num, 0) + 1);
    for (int num : arr) if (map.get(num) == 1) return num;
    return -1;
}

Challenge: Find Second Maximum Value in an Array

• Description: Find the second-largest element in an array.

• Key Points: Track max and second max in one pass.

Solution: Find Second Maximum Value in an Array

Update second max when a new max is found.

int secondMax(int[] arr) {
    int max = arr[0], second = Integer.MIN_VALUE;
    for (int num : arr) {
        if (num > max) {
            second = max;
            max = num;
        } else if (num > second && num < max) {
            second = num;
        }
    }
    return second;
}

Challenge: Rotate Array

• Description: Rotate array elements right by k steps.

• Key Points: Use reversal algorithm for O(n) solution.

Solution: Rotate Array

Reverse entire array, then first k and rest.

void rotate(int[] arr, int k) {
    k %= arr.length;
    reverse(arr, 0, arr.length - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, arr.length - 1);
}
void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start++] = arr[end];
        arr[end--] = temp;
    }
}

Challenge: Rearrange Positive & Negative Values

• Description: Rearrange array to alternate positive and negative numbers.

• Key Points: Partition positives and negatives, then interleave.

Solution: Rearrange Positive & Negative Values

• Description: Use two-pointer partitioning and merging.

• Code: Varies based on constraints (e.g., maintaining order).

Challenge: Rearrange Sorted Array in Max/Min Form

• Description: Rearrange sorted array to alternate max and min elements.

• Key Points: Use two pointers (start and end).

Solution: Rearrange Sorted Array in Max/Min Form

Fill result array alternating high and low values.

int[] maxMin(int[] arr) {
    int[] result = new int[arr.length];
    int left = 0, right = arr.length - 1, i = 0;
    while (left <= right) {
        if (i % 2 == 0) result[i++] = arr[right--];
        else result[i++] = arr[left++];
    }
    return result;
}

Challenge: Maximum Subarray

• Description: Find the contiguous subarray with the largest sum.

• Key Points: Use Kadane’s algorithm for O(n).

Solution: Maximum Subarray

Track current and global max sums.

int maxSubArray(int[] arr) {
    int maxSoFar = arr[0], maxEndingHere = arr[0];
    for (int i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

Array Interview Questions

• Description: Practice problems like “Find missing number” or “Rotate matrix.”

• Example: “Find pair with sum k” (HashMap or two-pointer).

Week 2: Linked Lists and Stack/Queues

3. Linked Lists

Crash Course Description: Master linked lists (singly and doubly) by implementing insertion, deletion, and traversal. Compare with arrays and solve problems like reversing lists, detecting cycles, and checking palindromes.

What is the Singly Linked List (SLL)?

A singly linked list is a chain of nodes, each with data and a next pointer.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

Basic Linked List Operations

• Description: Learn traversal, insertion, and deletion basics.

• Key Points: Traversal is O(n), access by index is O(n).

Insertion in a Singly Linked List

Insert a node at the head or specific position.

ListNode insertHead(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    return newNode;
}

Insertion in Singly Linked List (Insert After)

Insert a node after a given node.

void insertAfter(ListNode node, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = node.next;
    node.next = newNode;
}

Singly Linked List Deletion (Implementation)

Delete a node by value or position.

ListNode deleteNode(ListNode head, int val) {
    if (head == null) return null;
    if (head.val == val) return head.next;
    ListNode curr = head;
    while (curr.next != null && curr.next.val != val) curr = curr.next;
    if (curr.next != null) curr.next = curr.next.next;
    return head;
}

Linked Lists vs. Arrays

• Description: Compare linked lists (dynamic, O(n) access) vs. arrays (static, O(1) access).

• Key Points: Lists excel in insertions/deletions; arrays in random access.

What is a Doubly Linked List (DLL)?

Nodes have prev and next pointers for bidirectional traversal.

class DLLNode {
    int val;
    DLLNode prev, next;
    DLLNode(int val) { this.val = val; }
}

Linked List with Tail

Maintain a tail pointer for O(1) tail insertion.

class LinkedList {
    ListNode head, tail;
    void insertTail(int val) {
        ListNode node = new ListNode(val);
        if (head == null) head = tail = node;
        else tail = tail.next = node;
    }
}

Challenge: Insertion at Tail

• Description: Insert a node at the list’s end.

• Key Points: O(n) without tail pointer, O(1) with it.

Solution: Insertion at Tail

• Description: Implement tail insertion using a tail pointer.

• Code: As above in “Linked List with Tail.”

Challenge: Search in a Singly Linked List

• Description: Find a node with a given value.

• Key Points: Linear search, O(n).

Solution: Search in a Singly Linked List

Traverse to find the value.

ListNode search(ListNode head, int val) {
    ListNode curr = head;
    while (curr != null && curr.val != val) curr = curr.next;
    return curr;
}

Challenge: Deletion by Value

• Description: Remove the first occurrence of a value.

• Key Points: Handle head and non-head cases.

Solution: Deletion by Value

• Description: Implement deletion as shown in “Singly Linked List Deletion.”

• Code: See above.

Challenge: Find the Length of a Linked List

• Description: Count the number of nodes.

• Key Points: Simple traversal, O(n).

Solution: Find the Length of a Linked List

Iterate and count nodes.

int length(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

Challenge: Reverse Linked List

• Description: Reverse the order of nodes.

• Key Points: Use three pointers (prev, curr, next).

Solution: Reverse Linked List

Implement iterative reversal.

ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Challenge: Linked List Cycle

• Description: Detect if a cycle exists using Floyd’s cycle detection.

• Key Points: Fast and slow pointers meet in O(n).

Solution: Linked List Cycle

Implement Floyd’s algorithm.

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Challenge: Middle of the Linked List

• Description: Find the middle node using slow and fast pointers.

• Key Points: Slow moves one step, fast moves two.

Solution: Middle of the Linked List

Return middle node in O(n).

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Challenge: Remove Duplicates from a Linked List

• Description: Remove duplicates from a sorted linked list.

• Key Points: Compare adjacent nodes in O(n).

Solution: Remove Duplicates from a Linked List

Skip nodes with duplicate values.

ListNode removeDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return head;
}

Challenge: Union and Intersection of Linked Lists

• Description: Find union and intersection of two lists.

• Key Points: Use HashSet for O(n + m).

Solution: Union and Intersection of Linked Lists

Use sets to track unique and common elements.

ListNode union(ListNode l1, ListNode l2) {
    HashSet<Integer> set = new HashSet<>();
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null) { set.add(l1.val); l1 = l1.next; }
    while (l2 != null) { set.add(l2.val); l2 = l2.next; }
    for (int val : set) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

Challenge: Return the Nth Node from End

• Description: Find the nth node from the list’s end.

• Key Points: Use two pointers with n-step gap.

Solution: Return the Nth Node from End

Fast pointer leads by n nodes.

ListNode nthFromEnd(ListNode head, int n) {
    ListNode fast = head, slow = head;
    while (n-- > 0) fast = fast.next;
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

Challenge: Find If a Doubly Linked List Is a Palindrome

• Description: Check if a doubly linked list reads the same forward and backward.

• Key Points: Use two pointers or reverse half.

Solution: Find If a Doubly Linked List Is a Palindrome

Compare from both ends using prev/next.

boolean isPalindrome(DLLNode head) {
    DLLNode tail = head;
    while (tail.next != null) tail = tail.next;
    while (head != tail && head.prev != tail) {
        if (head.val != tail.val) return false;
        head = head.next;
        tail = tail.prev;
    }
    return true;
}

Linked List Interview Questions

• Description: Practice problems like “Merge two sorted lists” or “Detect cycle start.”

• Example: “Reverse a linked list in groups of k.”

4. Stack/Queues

Crash Course Description: Grasp stacks and queues in Java, implementing them to solve problems like generating binary numbers, reversing queue elements, and evaluating postfix expressions using stacks.

What is a Stack?

A stack is a LIFO (Last In, First Out) data structure supporting push and pop in O(1).

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1); // Add to top
stack.pop(); // Remove from top

Stack (Implementation)

Implement a stack using an array or linked list.

class MyStack {
    int[] arr = new int[100];
    int top = -1;
    void push(int val) { arr[++top] = val; }
    int pop() { return arr[top--]; }
}

What is a Queue?

A queue is a FIFO (First In, First Out) structure supporting enqueue and dequeue.

import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.add(1); // Enqueue
queue.poll(); // Dequeue

Queue (Implementation)

Implement a queue using an array or linked list.

class MyQueue {
    LinkedList<Integer> list = new LinkedList<>();
    void enqueue(int val) { list.addLast(val); }
    int dequeue() { return list.removeFirst(); }
}

Challenge: Generate Binary Numbers From 1 to n Using a Queue

• Description: Generate binary numbers from 1 to n (e.g., “1”, “10”, “11”).

• Key Points: Use queue to build numbers incrementally.

Solution: Generate Binary Numbers From 1 to n Using a Queue

Enqueue “1”, dequeue, and append “0” and “1”.

String[] generateBinary(int n) {
    String[] result = new String[n];
    Queue<String> queue = new LinkedList<>();
    queue.add("1");
    for (int i = 0; i < n; i++) {
        result[i] = queue.poll();
        queue.add(result[i] + "0");
        queue.add(result[i] + "1");
    }
    return result;
}

Challenge: Implement Two Stacks Using One Array

• Description: Use one array to implement two stacks growing from opposite ends.

• Key Points: Manage array indices carefully.

Solution: Implement Two Stacks Using One Array

Divide array for two stacks.

class TwoStacks {
    int[] arr = new int[100];
    int top1 = -1, top2 = arr.length;
    void push1(int val) { arr[++top1] = val; }
    void push2(int val) { arr[--top2] = val; }
    int pop1() { return arr[top1--]; }
    int pop2() { return arr[top2++]; }
}

Challenge: Reverse First k Elements of Queue

• Description: Reverse the first k elements of a queue.

• Key Points: Use a stack to reverse k elements.

Solution: Reverse First k Elements of Queue

Dequeue k elements to stack, then enqueue back.

Queue<Integer> reverseK(Queue<Integer> queue, int k) {
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < k; i++) stack.push(queue.poll());
    Queue<Integer> temp = new LinkedList<>();
    while (!stack.isEmpty()) temp.add(stack.pop());
    while (!queue.isEmpty()) temp.add(queue.poll());
    return temp;
}

Challenge: Implement Queue Using Stacks

• Description: Simulate a queue using two stacks.

• Key Points: Use one stack for enqueue, another for dequeue.

Solution: Implement Queue Using Stacks

Push to one stack; pop and push to another for dequeue.

class MyQueue {
    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();
    void enqueue(int val) { s1.push(val); }
    int dequeue() {
        if (s2.isEmpty()) while (!s1.isEmpty()) s2.push(s1.pop());
        return s2.pop();
    }
}

Challenge: Sort Values in a Stack

• Description: Sort a stack in ascending order.

• Key Points: Use a temporary stack.

Solution: Sort Values in a Stack

Pop and insert into temp stack in sorted order.

Stack<Integer> sortStack(Stack<Integer> stack) {
    Stack<Integer> temp = new Stack<>();
    while (!stack.isEmpty()) {
        int val = stack.pop();
        while (!temp.isEmpty() && temp.peek() > val) stack.push(temp.pop());
        temp.push(val);
    }
    return temp;
}

Challenge: Evaluate Postfix Expression Using a Stack

• Description: Compute the result of a postfix expression (e.g., “2 3 +”).

• Key Points: Push operands, pop for operators.

Solution: Evaluate Postfix Expression Using a Stack

Use stack to evaluate operators.

int evaluatePostfix(String exp) {
    Stack<Integer> stack = new Stack<>();
    for (char c : exp.toCharArray()) {
        if (Character.isDigit(c)) stack.push(c - '0');
        else {
            int b = stack.pop(), a = stack.pop();
            if (c == '+') stack.push(a + b);
            else if (c == '-') stack.push(a - b);
            else if (c == '*') stack.push(a * b);
            else stack.push(a / b);
        }
    }
    return stack.pop();
}

Challenge: Next Greater Element Using a Stack

• Description: Find the next greater element for each array element.

• Key Points: Use stack to track elements awaiting larger values.

Solution: Next Greater Element Using a Stack

Push indices, pop when larger element found.

int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) result[stack.pop()] = -1;
    return result;
}

Challenge: Find the Celebrity

• Description: Find a celebrity (known by all, knows none) in a party.

• Key Points: Use stack to eliminate non-celebrities.

Solution: Find the Celebrity

Narrow down to candidate, verify with matrix.

int findCelebrity(int n, int[][] knows) {
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) stack.push(i);
    while (stack.size() > 1) {
        int a = stack.pop(), b = stack.pop();
        if (knows[a][b] == 1) stack.push(b);
        else stack.push(a);
    }
    int candidate = stack.pop();
    for (int i = 0; i < n; i++) {
        if (i != candidate && (knows[candidate][i] == 1 || knows[i][candidate] == 0)) return -1;
    }
    return candidate;
}

Challenge: Valid Parentheses

• Description: Check if a string of parentheses is valid.

• Key Points: Use stack to match opening/closing brackets.

Solution: Valid Parentheses

Push opening, pop on matching closing.

boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') stack.push(c);
        else if (stack.isEmpty() || 
                 (c == ')' && stack.pop() != '(') ||
                 (c == '}' && stack.pop() != '{') ||
                 (c == ']' && stack.pop() != '[')) return false;
    }
    return stack.isEmpty();
}

Challenge: Min Stack

• Description: Design a stack with O(1) min element access.

• Key Points: Use two stacks: one for values, one for mins.

Solution: Min Stack

Push/pop min with each operation.

class MinStack {
    Stack<Integer> stack = new Stack<>(), minStack = new Stack<>();
    void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }
    int pop() {
        int val = stack.pop();
        if (val == minStack.peek()) minStack.pop();
        return val;
    }
    int getMin() { return minStack.peek(); }
}

Stack/Queue Interview Questions

• Description: Practice problems like “Implement stack using queues” or “LRU cache.”

• Example: “Validate parentheses string.”

Week 3: Graphs and Trees

5. Graphs

Crash Course Description: Learn graph theory, including representations (adjacency lists/matrices) and traversal algorithms (BFS, DFS). Solve challenges like cycle detection and finding shortest paths in Java.

What is a Graph?

• Description: A graph is a set of nodes (vertices) connected by edges, representing relationships.

• Key Points: Directed/undirected, weighted/unweighted.

Representation of Graphs

Represent graphs using adjacency lists (space-efficient) or matrices (fast edge lookup).

ArrayList<Integer>[] adjList = new ArrayList[n]; // Adjacency list
int[][] adjMatrix = new int[n][n]; // Adjacency matrix

Graph Implementation

Implement a graph using adjacency list for flexibility.

class Graph {
    ArrayList<Integer>[] adj;
    Graph(int n) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    }
    void addEdge(int u, int v) { adj[u].add(v); }
}

Complexities of Graph Operations

• Description: Analyze time complexities: O(V + E) for BFS/DFS with adjacency list, O(V²) with matrix.

• Key Points: Adjacency list better for sparse graphs.

What is a Bipartite Graph?

• Description: A graph whose vertices can be split into two sets with no edges within sets.

• Key Points: Check using BFS/DFS coloring.

Graph Traversal Algorithms

• Description: Learn BFS (level-order) and DFS (depth-first) for graph exploration.

• Key Points: BFS for shortest path, DFS for cycle detection.

Challenge: Implement Breadth-First Search

• Description: Implement BFS to traverse or find shortest paths in unweighted graphs.

• Key Points: Use queue for level-order traversal.

Solution: Implement Breadth-First Search

BFS implementation with queue.

void bfs(int start, ArrayList<Integer>[] adj) {
    boolean[] visited = new boolean[adj.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                queue.add(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

Challenge: Implement Depth-First Search

• Description: Implement DFS to explore all paths or detect cycles.

• Key Points: Use recursion or stack.

Solution: Implement Depth-First Search

Recursive DFS implementation.

void dfs(int node, boolean[] visited, ArrayList<Integer>[] adj) {
    visited[node] = true;
    System.out.print(node + " ");
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) dfs(neighbor, visited, adj);
    }
}

Challenge: Detect Cycle in a Directed Graph

• Description: Check if a directed graph has a cycle using DFS.

• Key Points: Use recursion stack to detect back edges.

Solution: Detect Cycle in a Directed Graph

DFS with recursion stack.

boolean hasCycle(ArrayList<Integer>[] adj) {
    boolean[] visited = new boolean[adj.length], recStack = new boolean[adj.length];
    for (int i = 0; i < adj.length; i++) {
        if (!visited[i] && dfsCycle(i, visited, recStack, adj)) return true;
    }
    return false;
}

boolean dfsCycle(int node, boolean[] visited, boolean[] recStack, ArrayList<Integer>[] adj) {
    visited[node] = recStack[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor] && dfsCycle(neighbor, visited, recStack, adj)) return true;
        else if (recStack[neighbor]) return true;
    }
    recStack[node] = false;
    return false;
}

Challenge: Find a Mother Vertex in a Directed Graph

• Description: Find a vertex from which all others are reachable.

• Key Points: Use DFS; check if one vertex reaches all.

Solution: Find a Mother Vertex in a Directed Graph

Run DFS from each vertex or use Kosaraju’s algorithm.

int findMotherVertex(ArrayList<Integer>[] adj) {
    boolean[] visited = new boolean[adj.length];
    int last = 0;
    for (int i = 0; i < adj.length; i++) {
        if (!visited[i]) {
            dfs(i, visited, adj);
            last = i;
        }
    }
    Arrays.fill(visited, false);
    dfs(last, visited, adj);
    for (boolean v : visited) if (!v) return -1;
    return last;
}

Challenge: Count the Number of Edges in an Undirected Graph

• Description: Count edges in an undirected graph.

• Key Points: Sum degrees and divide by 2.

Solution: Count the Number of Edges in an Undirected Graph

Iterate adjacency list to count edges.

int countEdges(ArrayList<Integer>[] adj) {
    int edges = 0;
    for (ArrayList<Integer> list : adj) edges += list.size();
    return edges / 2; // Undirected: each edge counted twice
}

Challenge: Check If a Path Exists between Two Vertices

• Description: Determine if a path exists between two nodes.

• Key Points: Use BFS or DFS.

Solution: Check If a Path Exists between Two Vertices

BFS to find path.

boolean hasPath(int start, int end, ArrayList<Integer>[] adj) {
    boolean[] visited = new boolean[adj.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == end) return true;
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                queue.add(neighbor);
                visited[neighbor] = true;
            }
        }
    }
    return false;
}

Challenge: Graph Valid Tree

• Description: Check if a graph is a valid tree (connected, no cycles).

• Key Points: Use DFS/BFS, ensure n-1 edges.

Solution: Graph Valid Tree

Use BFS and check for cycles.

boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    ArrayList<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(e[1]);
        adj[e[1]].add(e[0]);
    }
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);
    visited[0] = true;
    int count = 1;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                queue.add(neighbor);
                visited[neighbor] = true;
                count++;
            }
        }
    }
    return count == n;
}

Challenge: Find the Shortest Path between Two Vertices

• Description: Find the shortest path in an unweighted graph.

• Key Points: Use BFS for shortest path.

Solution: Find the Shortest Path between Two Vertices

BFS with parent tracking.

List<Integer> shortestPath(int start, int end, ArrayList<Integer>[] adj) {
    int[] parent = new int[adj.length];
    Arrays.fill(parent, -1);
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    parent[start] = start;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == end) break;
        for (int neighbor : adj[node]) {
            if (parent[neighbor] == -1) {
                queue.add(neighbor);
                parent[neighbor] = node;
            }
        }
    }
    List<Integer> path = new ArrayList<>();
    if (parent[end] == -1) return path;
    for (int v = end; v != start; v = parent[v]) path.add(v);
    path.add(start);
    Collections.reverse(path);
    return path;
}

Challenge: Remove Edge from a Directed Graph

• Description: Remove a specific edge from a directed graph.

• Key Points: Update adjacency list.

Solution: Remove Edge from a Directed Graph

Remove edge from adjacency list.

void removeEdge(int u, int v, ArrayList<Integer>[] adj) {
    adj[u].remove(Integer.valueOf(v));
}

Graph Interview Questions

• Description: Practice problems like “Clone graph” or “Topological sort.”

• Example: “Find shortest path in weighted graph” (Dijkstra’s).

6. Trees

Crash Course Description: Explore tree structures like binary trees, BSTs, AVL, and red-black trees. Implement traversals and solve problems like finding tree height or kth maximum value in Java.

What is a Tree?

• Description: A tree is a hierarchical structure with a root and child nodes, no cycles.

• Key Points: Used in file systems, DOM, etc.

Types of Trees

• Description: Learn binary trees, BSTs, AVL, red-black, and n-ary trees.

• Key Points: Each type serves specific use cases (e.g., BST for searching).

What Makes a Tree Balanced?

• Description: A tree is balanced if left and right subtree heights differ by at most 1.

• Key Points: Balanced trees ensure O(log n) operations.

What is a Binary Tree?

A tree where each node has at most two children (left, right).

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

More on Complete Binary Trees

• Description: All levels except possibly the last are fully filled, left to right.

• Key Points: Used in heaps.

Skewed Binary Tree

• Description: A tree with only left or right children, resembling a linked list.

• Key Points: Worst case O(n) for operations.

What is a Binary Search Tree (BST)?

• Description: A binary tree where left subtree < node < right subtree.

• Key Points: Enables O(log n) search in balanced cases.

Insertion in Binary Search Trees

Insert a value maintaining BST property.

TreeNode insertBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insertBST(root.left, val);
    else root.right = insertBST(root.right, val);
    return root;
}

Insertion in BST (Complete Implementation)

• Description: Full recursive or iterative BST insertion.

• Code: See above (recursive version).

Search in Binary Search Trees (Implementation)

• Description: Search for a value in a BST.

• Code:

TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

Deletion in Binary Search Trees

• Description: Delete a node while maintaining BST property.

• Key Points: Handle cases: leaf, one child, two children.

Deletion in Binary Search Trees (Implementation)

• Description: Implement deletion with successor replacement.

• Code:

TreeNode deleteBST(TreeNode root, int val) {
    if (root == null) return null;
    if (val < root.val) root.left = deleteBST(root.left, val);
    else if (val > root.val) root.right = deleteBST(root.right, val);
    else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode min = findMin(root.right);
        root.val = min.val;
        root.right = deleteBST(root.right, min.val);
    }
    return root;
}
TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

Pre-Order Traversal in Binary Search Trees

• Description: Traverse root, left, right.

• Code:

void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

In-Order Traversal in Binary Search Trees

• Description: Traverse left, root, right (sorted order for BST).

• Code:

void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

Post-Order Traversal in Binary Search Tree

• Description: Traverse left, right, root.

• Code:

void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + " ");
}

What is an AVL Tree?

• Description: A self-balancing BST where height difference (balance factor) is at most 1.

• Key Points: Ensures O(log n) operations.

AVL Insertion

• Description: Insert and rebalance using rotations.

• Key Points: Left-left, right-right, left-right, right-left cases.

AVL Deletion

• Description: Delete and rebalance to maintain AVL property.

• Key Points: Similar rotations as insertion.

What is a Red-Black Tree?

• Description: A self-balancing BST with color properties to ensure O(log n) operations.

• Key Points: Red/black nodes, no two red nodes adjacent.

Red-Black Tree Insertion

• Description: Insert and fix violations using rotations and recoloring.

• Key Points: Complex but maintains balance.

Red-Black Tree Deletion

• Description: Delete and rebalance with color adjustments.

• Key Points: More complex than insertion.

What is a 2-3 Tree?

• Description: A balanced tree where nodes have 2 or 3 children, ensuring O(log n) operations.

• Key Points: Precursor to red-black trees.

2-3 Insertion

• Description: Insert into 2-3 tree, splitting nodes as needed.

• Key Points: Maintains balance through splits.

2-3 Deletion of Element at Leaf Node

• Description: Delete leaf node, borrowing or merging if needed.

• Key Points: Ensures tree remains balanced.

2-3 Deletion of Element at Internal Node

• Description: Replace internal node with successor, then delete.

• Key Points: Similar to BST deletion.

2-3-4 Trees

• Description: Extension of 2-3 trees with up to 4 children per node.

• Key Points: Simplifies red-black tree operations.

Overview of Trees

• Description: Recap tree types, their properties, and use cases.

• Key Points: BSTs for searching, AVL/red-black for guaranteed balance.

Challenge: Find Minimum Value in Binary Search Tree

• Description: Find the smallest value in a BST.

• Key Points: Leftmost node is minimum.

Solution: Find Minimum Value in Binary Search Tree

• Description: Traverse left until null.

• Code:

int findMin(TreeNode root) {
    while (root.left != null) root = root.left;
    return root.val;
}

Challenge: Find kth Maximum Value in Binary Search Tree

• Description: Find the kth largest value using reverse in-order.

• Key Points: Right, root, left traversal.

Solution: Find kth Maximum Value in Binary Search Tree

• Description: Use in-order traversal with counter.

• Code:

int kthMax(TreeNode root, int k) {
    int[] count = {0};
    TreeNode[] result = {null};
    kthMaxHelper(root, k, count, result);
    return result[0].val;
}
void kthMaxHelper(TreeNode root, int k, int[] count, TreeNode[] result) {
    if (root == null) return;
    kthMaxHelper(root.right, k, count, result);
    if (++count[0] == k) result[0] = root;
    kthMaxHelper(root.left, k, count, result);
}

Challenge: Find Ancestors of a Given Node in a BST

• Description: List all ancestors of a node.

• Key Points: Traverse from root to node.

Solution: Find Ancestors of a Given Node in a BST

• Description: Track path during search.

• Code:

List<Integer> findAncestors(TreeNode root, int val) {
    List<Integer> ancestors = new ArrayList<>();
    while (root != null && root.val != val) {
        ancestors.add(root.val);
        root = val < root.val ? root.left : root.right;
    }
    return root == null ? new ArrayList<>() : ancestors;
}

Challenge: Find the Height of Binary Search Tree

• Description: Compute the height of a BST.

• Key Points: Max depth of left and right subtrees.

Solution: Find the Height of Binary Search Tree

• Description: Recursive height calculation.

• Code:

int height(TreeNode root) {
    if (root == null) return -1;
    return 1 + Math.max(height(root.left), height(root.right));
}

Challenge: Find Nodes at k Distance from the Root

• Description: List nodes at depth k from root.

• Key Points: Use recursion or BFS.

Solution: Find Nodes at k Distance from the Root

• Description: Recursive traversal at depth k.

• Code:

List<Integer> nodesAtK(TreeNode root, int k) {
    List<Integer> result = new ArrayList<>();
    nodesAtKHelper(root, k, result);
    return result;
}
void nodesAtKHelper(TreeNode root, int k, List<Integer> result) {
    if (root == null) return;
    if (k == 0) result.add(root.val);
    nodesAtKHelper(root.left, k - 1, result);
    nodesAtKHelper(root.right, k - 1, result);
}

Tree Interview Questions

• Description: Practice problems like “Lowest common ancestor” or “Invert binary tree.”

• Example: “Check if two trees are identical.”

Week 4: Trie and Heaps

7. Trie (Advanced Trees)

Crash Course Description: Master Tries for efficient string operations. Learn to implement insertion, search, and deletion, and solve challenges like word counting and array sorting using Tries in Java.

What is a Trie?

• Description: A Trie (prefix tree) is a tree for storing strings, with nodes representing characters.

• Key Points: Ideal for prefix-based searches.

The Structure of a Trie

• Description: Each node has children (array or map) and a flag for word end.

• Code:

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

Insertion in a Trie

• Description: Insert a word by creating nodes for each character.

• Code:

class Trie {
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new TrieNode();
            node = node.children[i];
        }
        node.isEndOfWord = true;
    }
}

Search in a Trie

• Description: Check if a word exists in the Trie.

• Code:

boolean search(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int i = c - 'a';
        if (node.children[i] == null) return false;
        node = node.children[i];
    }
    return node.isEndOfWord;
}

Deletion in a Trie

• Description: Delete a word by clearing isEndOfWord or removing nodes.

• Key Points: Handle node reuse carefully.

Challenge: Total Number of Words in a Trie

• Description: Count all words stored in the Trie.

• Key Points: DFS to count isEndOfWord nodes.

Solution: Total Number of Words in a Trie

• Description: Recursively count end-of-word nodes.

• Code:

int countWords(TrieNode root) {
    if (root == null) return 0;
    int count = root.isEndOfWord ? 1 : 0;
    for (TrieNode child : root.children) count += countWords(child);
    return count;
}

Challenge: Find All Words Stored in Trie

• Description: List all words in the Trie.

• Key Points: Use DFS with string builder.

Solution: Find All Words Stored in Trie

• Description: Collect words via DFS.

• Code:

List<String> findAllWords(TrieNode root) {
    List<String> result = new ArrayList<>();
    findAllWordsHelper(root, "", result);
    return result;
}
void findAllWordsHelper(TrieNode node, String prefix, List<String> result) {
    if (node == null) return;
    if (node.isEndOfWord) result.add(prefix);
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            findAllWordsHelper(node.children[i], prefix + (char)(i + 'a'), result);
        }
    }
}

Challenge: Array Sort Using Trie

• Description: Sort an array of strings using a Trie.

• Key Points: Insert strings, use in-order traversal.

Solution: Array Sort Using Trie

• Description: Collect strings in lexicographical order.

• Code: Use findAllWords from above.

Challenge: Word Formation From a Dictionary Using Trie

• Description: Check if a string can be formed from dictionary words.

• Key Points: Use Trie for prefix matching.

Solution: Word Formation From a Dictionary Using Trie

• Description: DFS with backtracking on Trie.

• Code:

boolean wordBreak(String s, List<String> dict) {
    Trie trie = new Trie();
    for (String word : dict) trie.insert(word);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && trie.search(s.substring(j, i))) dp[i] = true;
        }
    }
    return dp[s.length()];
}

Trie Interview Questions

• Description: Practice problems like “Implement autocomplete” or “Longest common prefix.”

• Example: “Design a dictionary with search.”

8. Heaps

Crash Course Description: Understand heaps (max and min) and their array-based implementations. Solve problems like converting heaps or finding k smallest/largest elements to leverage heaps in Java.

What is a Heap?

• Description: A heap is a complete binary tree where parent nodes are greater (max heap) or smaller (min heap) than children.

• Key Points: O(log n) insert/delete, O(1) peek.

Why Use Heaps?

• Description: Heaps enable efficient priority queues, sorting (heapsort), and kth element queries.

• Key Points: Used in scheduling, graph algorithms.

Heap Representation in Arrays

• Description: Store heap in an array; for node i, children at 2i+1, 2i+2.

• Code:

int[] heap = new int[100];
int size = 0;

Max Heap: Introduction

• Description: Parent > children; root is maximum.

• Key Points: Used for max priority queue.

Max Heap (Implementation)

• Description: Implement max heap with insert and delete-max.

• Code:

class MaxHeap {
    int[] heap = new int[100];
    int size = 0;
    void insert(int val) {
        heap[size++] = val;
        int i = size - 1;
        while (i > 0 && heap[(i-1)/2] < heap[i]) {
            swap(heap, i, (i-1)/2);
            i = (i-1)/2;
        }
    }
    void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Min Heap: An Introduction

• Description: Parent < children; root is minimum.

• Key Points: Used for min priority queue.

Min Heap (Implementation)

• Description: Implement min heap with insert and delete-min.

• Code: Similar to max heap, reverse comparisons.

Challenge: Convert Max Heap to Min Heap

• Description: Transform a max heap array into a min heap.

• Key Points: Heapify in O(n).

Solution: Convert Max Heap to Min Heap

• Description: Heapify array for min heap property.

• Code:

void convertMaxToMin(int[] heap) {
    for (int i = heap.length / 2 - 1; i >= 0; i--) {
        minHeapify(heap, i, heap.length);
    }
}
void minHeapify(int[] heap, int i, int size) {
    int smallest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < size && heap[left] < heap[smallest]) smallest = left;
    if (right < size && heap[right] < heap[smallest]) smallest = right;
    if (smallest != i) {
        swap(heap, i, smallest);
        minHeapify(heap, smallest, size);
    }
}

Challenge: Find k Smallest Elements in an Array

• Description: Return the k smallest elements using a max heap.

• Key Points: Maintain k elements in heap.

Solution: Find k Smallest Elements in an Array

• Description: Use max heap of size k.

• Code:

int[] kSmallest(int[] arr, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    for (int num : arr) {
        maxHeap.offer(num);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = maxHeap.poll();
    return result;
}

Challenge: Find K Largest Elements in an Array

• Description: Return the k largest elements using a min heap.

• Key Points: Maintain k elements in heap.

Solution: Find K Largest Elements in an Array

• Description: Use min heap of size k.

• Code:

int[] kLargest(int[] arr, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : arr) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll();
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll();
    return result;
}

Heap Interview Questions

• Description: Practice problems like “Merge k sorted lists” or “Top k frequent elements.”

• Example: “Implement heapsort.”

Week 5: Hash Tables and Additional Topics

9. Hash Tables

Crash Course Description: Learn hash tables, hash functions, and collision handling in Java (HashMap, HashSet). Solve problems like finding symmetric pairs or subarrays with zero sum using hashing techniques.

What is a Hash Table?

• Description: A hash table stores key-value pairs with O(1) average-case operations using a hash function.

• Code:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // O(1)
map.get("key"); // O(1)

Hash Functions

• Description: Convert keys to array indices using hashCode() and modulo.

• Key Points: Good hash functions minimize collisions.

Collisions in Hash Tables

• Description: Handle multiple keys mapping to the same index using chaining or open addressing.

• Key Points: Java uses chaining (linked lists/trees).

Building a Hash Table from Scratch

• Description: Implement a basic hash table with array and linked lists.

• Code:

class MyHashTable {
    class Node {
        String key; int value; Node next;
        Node(String key, int value) { this.key = key; this.value = value; }
    }
    Node[] table = new Node[16];
    void put(String key, int value) {
        int index = key.hashCode() % table.length;
        if (table[index] == null) table[index] = new Node(key, value);
        else {
            Node curr = table[index];
            while (curr.next != null && !curr.key.equals(key)) curr = curr.next;
            if (curr.key.equals(key)) curr.value = value;
            else curr.next = new Node(key, value);
        }
    }
}

Add/Remove & Search in a Hash Table (Implementation)

• Description: Implement put, get, and remove operations.

• Code: See above for put; similar for get/remove.

Complete Implementation of Hash Tables

• Description: Full hash table with resizing and collision handling.

• Key Points: Use load factor (0.75 in Java).

Trie vs Hash Table

• Description: Compare Tries (prefix-based, O(m)) vs. hash tables (O(1) for exact matches).

• Key Points: Tries for strings, hash tables for general keys.

HashMap vs HashSet

• Description: HashMap stores key-value pairs; HashSet stores unique keys.

• Code:

HashSet<String> set = new HashSet<>();
set.add("key"); // O(1)

Challenge: An Array as a Subset of Another Array

• Description: Check if one array is a subset of another.

• Key Points: Use HashSet for O(n) check.

Solution: An Array as a Subset of Another Array

• Description: Hash larger array, check smaller.

• Code:

boolean isSubset(int[] arr1, int[] arr2) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : arr1) set.add(num);
    for (int num : arr2) if (!set.contains(num)) return false;
    return true;
}

Challenge: Check if Arrays are Disjoint

• Description: Check if two arrays have no common elements.

• Key Points: Use HashSet for O(n) check.

Solution: Check if Arrays are Disjoint

• Description: Hash one array, check other for overlaps.

• Code:

boolean areDisjoint(int[] arr1, int[] arr2) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : arr1) set.add(num);
    for (int num : arr2) if (set.contains(num)) return false;
    return true;
}

Challenge: Find Symmetric Pairs in an Array

• Description: Find pairs (a, b) and (b, a) in an array of pairs.

• Key Points: Use HashMap to track pairs.

Solution: Find Symmetric Pairs in an Array

• Description: Map (a, b) to check for (b, a).

• Code:

List<int[]> findSymmetric(int[][] pairs) {
    HashMap<Integer, Integer> map = new HashMap<>();
    List<int[]> result = new ArrayList<>();
    for (int[] pair : pairs) {
        if (map.containsKey(pair[1]) && map.get(pair[1]) == pair[0]) {
            result.add(new int[]{pair[1], pair[0]});
        }
        map.put(pair[0], pair[1]);
    }
    return result;
}

Challenge: Trace the Complete Path of a Journey

• Description: Given source-destination pairs, reconstruct the path.

• Key Points: Use HashMap to build graph.

Solution: Trace the Complete Path of a Journey

• Description: Map sources to destinations, follow path.

• Code:

List<String> tracePath(Map<String, String> tickets) {
    HashSet<String> destinations = new HashSet<>(tickets.values());
    String start = null;
    for (String src : tickets.keySet()) {
        if (!destinations.contains(src)) {
            start = src;
            break;
        }
    }
    List<String> path = new ArrayList<>();
    while (start != null) {
        path.add(start);
        start = tickets.get(start);
    }
    return path;
}

Challenge: Find Two Pairs in an Array Such That a+b = c+d

• Description: Find two pairs with equal sums.

• Key Points: Use HashMap to store sums.

Solution: Find Two Pairs in an Array Such That a+b = c+d

• Description: Map sums to pairs, check for matches.

• Code:

int[][] findPairs(int[] arr) {
    HashMap<Integer, int[]> map = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int sum = arr[i] + arr[j];
            if (map.containsKey(sum)) return new int[][]{map.get(sum), {arr[i], arr[j]}};
            map.put(sum, new int[]{arr[i], arr[j]});
        }
    }
    return new int[][]{};
}

Challenge: A Subarray with a Sum of 0

• Description: Find a subarray with sum zero.

• Key Points: Use cumulative sum with HashMap.

Solution: A Subarray with a Sum of 0

• Description: Track cumulative sums, check for repeats.

• Code:

boolean hasZeroSumSubarray(int[] arr) {
    HashSet<Integer> set = new HashSet<>();
    int sum = 0;
    set.add(0);
    for (int num : arr) {
        sum += num;
        if (set.contains(sum)) return true;
        set.add(sum);
    }
    return false;
}

Challenge: Word Formation Using a Hash Table

• Description: Check if a string can be formed from dictionary words.

• Key Points: Use HashMap for word frequency.

Solution: Word Formation Using a Hash Table

• Description: Dynamic programming with HashMap.

• Code:

boolean wordBreak(String s, List<String> dict) {
    HashSet<String> set = new HashSet<>(dict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && set.contains(s.substring(j, i))) dp[i] = true;
        }
    }
    return dp[s.length()];
}

Challenge: Find Two Numbers That Add Up to k—Hashing

• Description: Find two numbers summing to k using a hash table.

• Key Points: HashMap for O(n) solution.

Solution: Find Two Numbers That Add Up to k—Hashing

• Description: Store complements in HashMap.

• Code: See “Find Two Numbers That Add Up to K” above.

Challenge: First Non-Repeating Integer in an Array—Hashing

• Description: Find first non-repeating integer using hashing.

• Key Points: Use HashMap for frequency counting.

Solution: First Non-Repeating Integer in an Array—Hashing

• Description: Scan HashMap for count 1.

• Code: See “First Non-Repeating Integer in an Array” above.

Challenge: Linked List Cycle—Hashing

• Description: Detect cycle in linked list using hashing.

• Key Points: Store nodes in HashSet.

Solution: Linked List Cycle—Hashing

• Description: Check for repeated nodes.

• Code:

boolean hasCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
    while (head != null) {
        if (set.contains(head)) return true;
        set.add(head);
        head = head.next;
    }
    return false;
}

Challenge: Remove Duplicates from Linked List - Hashing

• Description: Remove duplicates using HashSet.

• Key Points: Track seen values.

Solution: Remove Duplicates from Linked List - Hashing

• Description: Skip nodes with seen values.

• Code:

ListNode removeDuplicates(ListNode head) {
    HashSet<Integer> set = new HashSet<>();
    ListNode dummy = new ListNode(0), curr = dummy;
    dummy.next = head;
    while (head != null) {
        if (!set.contains(head.val)) {
            set.add(head.val);
            curr.next = head;
            curr = curr.next;
        }
        head = head.next;
    }
    curr.next = null;
    return dummy.next;
}

Challenge: Union and Intersection of Linked Lists — Hashing

• Description: Find union and intersection using HashSet.

• Key Points: Store values for O(n + m).

Solution: Union and Intersection of Linked Lists — Hashing

• Description: Use sets for unique and common elements.

• Code: See “Union and Intersection of Linked Lists” above.

Hashing Interview Questions

• Description: Practice problems like “Group anagrams” or “LRU cache.”

• Example: “Find first unique character in a string.”

Additional Topics

10. Hash Maps

Crash Course Description: Discover the logic behind designing hash maps, solving data structure challenges, and optimal algorithms in Java.

Introduction to Hash Maps

• Description: HashMaps store key-value pairs with O(1) average-case operations, ideal for fast lookups and updates.

• Key Points: Use hashCode() for indexing, handle collisions via chaining.

Design HashMap

• Description: Build a custom HashMap with put, get, and remove operations.

• Key Points: Implement array-based storage with linked lists for collisions.

Solution: Design HashMap

• Description: Complete HashMap implementation with resizing.

• Code:

class MyHashMap {
    class Node {
        int key, value; Node next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }
    Node[] table = new Node[10000];
    void put(int key, int value) {
        int index = key % table.length;
        if (table[index] == null) table[index] = new Node(key, value);
        else {
            Node curr = table[index];
            while (curr.next != null && curr.key != key) curr = curr.next;
            if (curr.key == key) curr.value = value;
            else curr.next = new Node(key, value);
        }
    }
    int get(int key) {
        int index = key % table.length;
        Node curr = table[index];
        while (curr != null && curr.key != key) curr = curr.next;
        return curr == null ? -1 : curr.value;
    }
    void remove(int key) {
        int index = key % table.length;
        Node curr = table[index];
        if (curr == null) return;
        if (curr.key == key) table[index] = curr.next;
        else {
            while (curr.next != null && curr.next.key != key) curr = curr.next;
            if (curr.next != null) curr.next = curr.next.next;
        }
    }
}

Fraction to Recurring Decimal

• Description: Convert a fraction to decimal, handling recurring decimals.

• Key Points: Use HashMap to detect repeating remainders.

Solution: Fraction to Recurring Decimal

• Description: Track remainders to format decimal output.

• Code:

String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";
    StringBuilder result = new StringBuilder();
    result.append((numerator < 0 ^ denominator < 0) ? "-" : "");
    long num = Math.abs((long)numerator), den = Math.abs((long)denominator);
    result.append(num / den);
    long rem = num % den;
    if (rem == 0) return result.toString();
    result.append(".");
    HashMap<Long, Integer> map = new HashMap<>();
    while (rem != 0) {
        if (map.containsKey(rem)) {
            result.insert(map.get(rem), "(").append(")");
            break;
        }
        map.put(rem, result.length());
        rem *= 10;
        result.append(rem / den);
        rem