Java Data Structures and Algorithms

Use List (ArrayList, LinkedList), Set (HashSet, TreeSet), and Map (HashMap, TreeMap) from the Java Collections Framework, explaining their performance trade-offs.

Implement the Comparable interface and custom Comparators for sorting objects in Java.

Handle fast input/output in Java using BufferedReader and StringBuilder for competitive programming scenarios.

Analyze the time complexity of iterative and recursive algorithms (Big O notation).

Analyze the space complexity of algorithms, including auxiliary space and the recursion stack.

Apply the two-pointer technique to solve problems on sorted arrays and strings (e.g., pair sum, palindrome check).

Implement and apply the sliding window technique for fixed and variable size window problems on arrays.

Use built-in Java methods for sorting (Arrays.sort, Collections.sort) and understand when to use them.

Implement linear search and binary search on sorted arrays.

Apply binary search on the answer space for optimization problems.

Solve problems on rotated sorted arrays using a modified binary search.

Apply prefix/suffix sum techniques to solve range query problems.

Apply Kadane's algorithm to find the maximum subarray sum.

Apply the Dutch National Flag algorithm for three-way partitioning.

Apply the Boyer-Moore Voting Algorithm to find majority elements in an array.

Implement and analyze bubble sort, selection sort, and insertion sort.

Implement merge sort and analyze its time/space complexity.

Solve the 'count inversions' problem by modifying the merge sort algorithm.

Implement quick sort using both Lomuto and Hoare partition schemes, and analyze its performance.

Apply counting sort for problems where the input is in a limited integer range.

Apply string hashing techniques (rolling hash) for fast string comparison.

Implement the Rabin-Karp algorithm for pattern matching.

Construct the Longest Proper Prefix which is also a Suffix (LPS) array for the KMP algorithm.

Implement the KMP pattern matching algorithm using a precomputed LPS array.

Implement a singly linked list with insertion, deletion, and traversal operations.

Implement a doubly linked list with insertion, deletion, and traversal operations.

Reverse a linked list both iteratively and recursively.

Detect and find the starting node of a cycle in a linked list using Floyd's algorithm.

Find the middle element of a linked list using the slow and fast pointer technique.

Find the intersection point of two linked lists.

Merge two sorted linked lists iteratively.

Apply the dummy node technique to simplify linked list manipulation problems (e.g., removing nodes).

Implement a stack using both an array and a linked list.

Solve the balanced parentheses problem using a stack.

Solve the 'next greater element' problem using a monotonic stack.

Implement a queue using both a circular array and a linked list.

Implement a queue using two stacks and analyze its amortized time complexity.

Implement a deque using a doubly linked list.

Solve the 'sliding window maximum' problem efficiently using a deque.

Convert an infix expression to postfix and evaluate it using a stack.

Implement preorder, inorder, and postorder traversals, both recursively and iteratively.

Implement level-order traversal of a binary tree using a queue.

Calculate the height, diameter, and size of a binary tree.

Solve problems to find the left and right view of a binary tree.

Solve the 'top view' and 'bottom view' of a binary tree problem.

Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.

Construct a binary tree from its preorder and inorder traversals.

Construct a binary tree from its postorder and inorder traversals.

Implement a Binary Search Tree (BST) with search, insertion, and deletion operations.

Validate if a given binary tree is a BST.

Explain the need for self-balancing trees and perform AVL tree rotations.

Implement insertion into an AVL tree with automatic rebalancing.

Implement a binary heap (max-heap and min-heap) using an array.

Build a heap from an unordered array in linear time using the heapify-down operation.

Implement heap sort.

Implement a priority queue using a binary heap and solve top-K element problems.

Explain hashing, hash functions, and collision resolution strategies (chaining, open addressing).

Implement a hash table using chaining (array of linked lists).

Apply hash maps to solve frequency counting and lookup problems (e.g., Two Sum, Subarray Sum Equals K).

Apply hashing to find the longest consecutive subsequence in an array.

Implement a trie (prefix tree) with insert and search operations.

Implement word search and autocomplete features using a trie.

Solve problems involving finding all words from a dictionary on a 2D grid of characters using a trie and backtracking.

Generate all subsets of a set using a recursive approach.

Generate all permutations of a set using backtracking with a swap-based approach.

Generate all combinations of a given size from a set using backtracking.

Implement a backtracking solution to find all valid configurations for the N-Queens problem.

Implement a backtracking algorithm to solve a Sudoku puzzle.

Apply backtracking to solve maze-solving problems (e.g., Rat in a Maze).

Represent graphs using an adjacency matrix and an adjacency list.

Implement Breadth-First Search (BFS) on a graph to find the shortest path in an unweighted graph.

Implement Depth-First Search (DFS) on a graph, both recursively and iteratively.

Detect a cycle in an undirected graph using BFS or DFS.

Detect a cycle in a directed graph using DFS.

Perform topological sorting on a Directed Acyclic Graph (DAG) using both DFS and Kahn's algorithm (BFS).

Solve problems related to connected components and finding the number of islands.

Implement the Disjoint Set Union (DSU) data structure with path compression and union by rank/size.

Find the Minimum Spanning Tree (MST) of a graph using Kruskal's algorithm with DSU.

Find the Minimum Spanning Tree (MST) of a graph using Prim's algorithm with a priority queue.

Implement Dijkstra's algorithm to find the single-source shortest path in a weighted graph with non-negative edges.

Implement the Bellman-Ford algorithm to find single-source shortest paths and detect negative cycles.

Implement the Floyd-Warshall algorithm to find all-pairs shortest paths.

Optimize a recursive solution with memoization (top-down DP).

Convert a memoized solution to a tabulated one (bottom-up DP), demonstrated on the Fibonacci problem.

Solve the 0/1 Knapsack problem using dynamic programming.

Find the length of the Longest Common Subsequence (LCS) and reconstruct it.

Solve the Longest Increasing Subsequence (LIS) problem using both O(n^2) DP and an optimized O(n log n) approach.

Solve the Matrix Chain Multiplication problem using dynamic programming.

Apply the greedy approach to solve the Activity Selection and Fractional Knapsack problems.

Solve problems involving merging overlapping intervals.