Table of Contents
- Why These Programs Matter
- Program #1: Binary Search Implementation (Medium)
- Program #2: Merge Two Sorted Arrays (Medium)
- Program #3: Linked List Reversal (Medium-Hard)
- Program #4: Find All Permutations of a String (Hard)
- Program #5: Implement a Min Heap (Hard)
- Program #6: Detect Cycle in a Directed Graph (Hard)
- Program #7: Longest Common Subsequence (Hard)
- Program #8: N-Queens Problem (Very Hard)
- Program #9: Implement LRU Cache (Very Hard)
- Program #10: Serialize and Deserialize Binary Tree (Extremely Hard)
- How to Practice These Programs Effectively
- Common Mistakes to Avoid
- Resources for Further Learning
- Why These Programs Matter for Your Career
- Frequently Asked Questions
- Conclusion
If you're a college student studying Java, you've probably realized that knowing syntax isn't enough. Employers, interviewers, and professors expect you to solve real problems—the kind that test your logic, algorithms, and understanding of data structures.
This article covers 10 essential Java programs every college student should master. We're not talking about 'Hello World' or simple loops. These are medium to extremely hard problems that will challenge you, teach you, and prepare you for technical interviews and real-world development.
Each program includes complete working code, detailed explanations, time/space complexity analysis, and practical applications. Let's dive in.
Difficulty Progression
Programs are arranged from medium difficulty to extremely hard. Start with the earlier ones to build confidence, then tackle the advanced challenges. Each solution is production-quality code you can learn from.
Why These Programs Matter
Before we jump into code, let's understand why these specific programs are crucial:
- Interview Preparation: These patterns appear frequently in technical interviews at top companies
- Algorithm Mastery: Each program teaches fundamental algorithmic thinking
- Data Structure Practice: You'll work with arrays, lists, trees, graphs, and more
- Problem-Solving Skills: These aren't just coding exercises—they're logic puzzles that sharpen your mind
- Real-World Applications: Every program has practical use cases in actual software development
Master these, and you'll be ahead of 90% of your peers. Let's begin.
Program #1: Binary Search Implementation (Medium)
Binary search is a fundamental algorithm that every programmer must know. It searches for an element in a sorted array in O(log n) time—much faster than linear search.
Problem Statement
Given a sorted array of integers and a target value, return the index of the target if found, otherwise return -1. Implement both iterative and recursive approaches.
Solution
public class BinarySearch {
// Iterative approach
public static int binarySearchIterative(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Recursive approach
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};
int target = 23;
int resultIterative = binarySearchIterative(arr, target);
System.out.println("Iterative: Element found at index " + resultIterative);
int resultRecursive = binarySearchRecursive(arr, target, 0, arr.length - 1);
System.out.println("Recursive: Element found at index " + resultRecursive);
}
}Explanation & Key Points
- Time Complexity: O(log n) - divides search space in half each iteration
- Space Complexity: O(1) for iterative, O(log n) for recursive (call stack)
- Key Insight: Use 'left + (right - left) / 2' instead of '(left + right) / 2' to prevent integer overflow
- Prerequisite: Array must be sorted
- Real-World Use: Database indexing, searching in large datasets, autocomplete features
Program #2: Merge Two Sorted Arrays (Medium)
This program tests your understanding of the two-pointer technique and is commonly asked in interviews.
Problem Statement
Given two sorted arrays, merge them into a single sorted array without using any built-in sorting functions.
Solution
public class MergeSortedArrays {
public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
int n1 = arr1.length;
int n2 = arr2.length;
int[] merged = new int[n1 + n2];
int i = 0, j = 0, k = 0;
// Compare elements from both arrays and add smaller one
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
// Copy remaining elements from arr1
while (i < n1) {
merged[k++] = arr1[i++];
}
// Copy remaining elements from arr2
while (j < n2) {
merged[k++] = arr2[j++];
}
return merged;
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5, 7, 9};
int[] arr2 = {2, 4, 6, 8, 10, 12};
int[] result = mergeSortedArrays(arr1, arr2);
System.out.print("Merged Array: ");
for (int num : result) {
System.out.print(num + " ");
}
}
}Explanation & Key Points
- Time Complexity: O(n + m) where n and m are array lengths
- Space Complexity: O(n + m) for the merged array
- Technique: Two-pointer approach - fundamental for many array problems
- Edge Cases: Handle arrays of different lengths, empty arrays
- Real-World Use: Merge sort algorithm, combining sorted data streams, database operations
Program #3: Linked List Reversal (Medium-Hard)
Reversing a linked list is a classic problem that tests your understanding of pointers and data structures.
Problem Statement
Given the head of a singly linked list, reverse the list and return the new head. Implement both iterative and recursive solutions.
Solution
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListReversal {
// Iterative approach
public static Node reverseIterative(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next; // Store next node
current.next = prev; // Reverse the link
prev = current; // Move prev forward
current = next; // Move current forward
}
return prev; // New head
}
// Recursive approach
public static Node reverseRecursive(Node head) {
// Base case: empty list or single node
if (head == null || head.next == null) {
return head;
}
// Recursively reverse the rest of the list
Node newHead = reverseRecursive(head.next);
// Reverse the link
head.next.next = head;
head.next = null;
return newHead;
}
// Helper method to print list
public static void printList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// Create list: 1 -> 2 -> 3 -> 4 -> 5
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
System.out.println("Original List:");
printList(head);
Node reversedHead = reverseIterative(head);
System.out.println("\nReversed List (Iterative):");
printList(reversedHead);
}
}Explanation & Key Points
- Time Complexity: O(n) for both approaches
- Space Complexity: O(1) for iterative, O(n) for recursive (call stack)
- Key Concept: Three-pointer technique (prev, current, next)
- Common Mistake: Losing reference to the rest of the list
- Real-World Use: Undo functionality, browser history, implementing stacks
Pro Tip
Draw the linked list on paper and trace through the algorithm step by step. Visualizing pointer movements is crucial for understanding linked list problems.
Program #4: Find All Permutations of a String (Hard)
This problem tests your understanding of recursion and backtracking—essential techniques for solving complex problems.
Problem Statement
Given a string, generate all possible permutations of its characters. For example, 'ABC' should generate: ABC, ACB, BAC, BCA, CAB, CBA.
Solution
import java.util.*;
public class StringPermutations {
public static List<String> findPermutations(String str) {
List<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
return result;
}
boolean[] used = new boolean[str.length()];
StringBuilder current = new StringBuilder();
backtrack(str, used, current, result);
return result;
}
private static void backtrack(String str, boolean[] used,
StringBuilder current, List<String> result) {
// Base case: we've used all characters
if (current.length() == str.length()) {
result.add(current.toString());
return;
}
// Try adding each unused character
for (int i = 0; i < str.length(); i++) {
if (used[i]) continue; // Skip if already used
// Choose
current.append(str.charAt(i));
used[i] = true;
// Explore
backtrack(str, used, current, result);
// Unchoose (backtrack)
current.deleteCharAt(current.length() - 1);
used[i] = false;
}
}
// Alternative approach using swapping
public static void permuteSwap(String str, int left, int right, List<String> result) {
if (left == right) {
result.add(str);
return;
}
for (int i = left; i <= right; i++) {
str = swap(str, left, i);
permuteSwap(str, left + 1, right, result);
str = swap(str, left, i); // Backtrack
}
}
private static String swap(String str, int i, int j) {
char[] chars = str.toCharArray();
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
public static void main(String[] args) {
String str = "ABC";
List<String> permutations = findPermutations(str);
System.out.println("All permutations of '" + str + "':");
for (String perm : permutations) {
System.out.println(perm);
}
System.out.println("\nTotal permutations: " + permutations.size());
}
}Explanation & Key Points
- Time Complexity: O(n! × n) - n! permutations, each taking O(n) to build
- Space Complexity: O(n) for recursion depth
- Technique: Backtracking - choose, explore, unchoose pattern
- Key Insight: Track which characters are used to avoid duplicates
- Real-World Use: Password generation, combinatorial optimization, puzzle solving
Program #5: Implement a Min Heap (Hard)
Understanding heaps is crucial for priority queues, sorting algorithms, and many graph algorithms.
Problem Statement
Implement a Min Heap data structure with insert, extractMin, and heapify operations. The heap should maintain the property that parent nodes are always smaller than their children.
Solution
import java.util.*;
public class MinHeap {
private List<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
// Get parent index
private int parent(int i) {
return (i - 1) / 2;
}
// Get left child index
private int leftChild(int i) {
return 2 * i + 1;
}
// Get right child index
private int rightChild(int i) {
return 2 * i + 2;
}
// Swap two elements
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
// Insert element into heap
public void insert(int value) {
heap.add(value);
int current = heap.size() - 1;
// Bubble up to maintain heap property
while (current > 0 && heap.get(current) < heap.get(parent(current))) {
swap(current, parent(current));
current = parent(current);
}
}
// Extract minimum element
public int extractMin() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
int min = heap.get(0);
int lastElement = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, lastElement);
heapifyDown(0);
}
return min;
}
// Heapify down from given index
private void heapifyDown(int i) {
int minIndex = i;
int left = leftChild(i);
int right = rightChild(i);
// Find smallest among node and its children
if (left < heap.size() && heap.get(left) < heap.get(minIndex)) {
minIndex = left;
}
if (right < heap.size() && heap.get(right) < heap.get(minIndex)) {
minIndex = right;
}
// If smallest is not the current node, swap and continue
if (minIndex != i) {
swap(i, minIndex);
heapifyDown(minIndex);
}
}
// Get minimum without removing
public int peek() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
return heap.get(0);
}
// Get heap size
public int size() {
return heap.size();
}
// Check if heap is empty
public boolean isEmpty() {
return heap.isEmpty();
}
// Print heap
public void printHeap() {
System.out.println(heap);
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
// Insert elements
int[] elements = {5, 3, 8, 1, 9, 2, 7};
System.out.println("Inserting elements:");
for (int element : elements) {
minHeap.insert(element);
System.out.println("Inserted " + element + ": ");
minHeap.printHeap();
}
// Extract minimum elements
System.out.println("\nExtracting minimum elements:");
while (!minHeap.isEmpty()) {
System.out.println("Extracted: " + minHeap.extractMin());
if (!minHeap.isEmpty()) {
minHeap.printHeap();
}
}
}
}Explanation & Key Points
- Time Complexity: O(log n) for insert and extractMin, O(1) for peek
- Space Complexity: O(n) for storing elements
- Key Operations: Bubble up (insert), bubble down (extract)
- Heap Property: Parent is always smaller than children
- Real-World Use: Priority queues, Dijkstra's algorithm, heap sort, task scheduling
Program #6: Detect Cycle in a Directed Graph (Hard)
Graph algorithms are essential for technical interviews. This problem uses Depth-First Search (DFS) with color coding.
Problem Statement
Given a directed graph, detect if it contains a cycle. Use DFS with three states: unvisited (white), visiting (gray), and visited (black).
Solution
import java.util.*;
public class CycleDetectionDirectedGraph {
enum Color {
WHITE, // Unvisited
GRAY, // Currently visiting (in recursion stack)
BLACK // Completely visited
}
static class Graph {
private int vertices;
private List<List<Integer>> adjList;
public Graph(int vertices) {
this.vertices = vertices;
adjList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination);
}
public boolean hasCycle() {
Color[] colors = new Color[vertices];
Arrays.fill(colors, Color.WHITE);
// Check for cycle starting from each unvisited vertex
for (int i = 0; i < vertices; i++) {
if (colors[i] == Color.WHITE) {
if (hasCycleDFS(i, colors)) {
return true;
}
}
}
return false;
}
private boolean hasCycleDFS(int vertex, Color[] colors) {
// Mark current vertex as being visited
colors[vertex] = Color.GRAY;
// Visit all adjacent vertices
for (int neighbor : adjList.get(vertex)) {
// If neighbor is gray, we found a back edge (cycle)
if (colors[neighbor] == Color.GRAY) {
return true;
}
// If neighbor is white, recursively visit it
if (colors[neighbor] == Color.WHITE) {
if (hasCycleDFS(neighbor, colors)) {
return true;
}
}
}
// Mark vertex as completely visited
colors[vertex] = Color.BLACK;
return false;
}
// Alternative: Using recursion stack tracking
public boolean hasCycleAlternative() {
boolean[] visited = new boolean[vertices];
boolean[] recStack = new boolean[vertices];
for (int i = 0; i < vertices; i++) {
if (hasCycleUtil(i, visited, recStack)) {
return true;
}
}
return false;
}
private boolean hasCycleUtil(int vertex, boolean[] visited, boolean[] recStack) {
if (recStack[vertex]) {
return true; // Found cycle
}
if (visited[vertex]) {
return false; // Already processed
}
visited[vertex] = true;
recStack[vertex] = true;
for (int neighbor : adjList.get(vertex)) {
if (hasCycleUtil(neighbor, visited, recStack)) {
return true;
}
}
recStack[vertex] = false; // Remove from recursion stack
return false;
}
}
public static void main(String[] args) {
// Create a graph with cycle
Graph graph1 = new Graph(4);
graph1.addEdge(0, 1);
graph1.addEdge(1, 2);
graph1.addEdge(2, 3);
graph1.addEdge(3, 1); // Creates cycle: 1 -> 2 -> 3 -> 1
System.out.println("Graph 1 has cycle: " + graph1.hasCycle());
// Create a graph without cycle
Graph graph2 = new Graph(4);
graph2.addEdge(0, 1);
graph2.addEdge(1, 2);
graph2.addEdge(2, 3);
System.out.println("Graph 2 has cycle: " + graph2.hasCycle());
}
}Explanation & Key Points
- Time Complexity: O(V + E) where V is vertices and E is edges
- Space Complexity: O(V) for color/visited arrays and recursion stack
- Key Concept: Gray nodes indicate vertices in current DFS path
- Back Edge: Edge to a gray node indicates a cycle
- Real-World Use: Deadlock detection, dependency resolution, build systems
Important Distinction
This algorithm is for directed graphs. For undirected graphs, you'd use a different approach (checking if you revisit a node that's not the parent).
Program #7: Longest Common Subsequence (Hard)
This classic dynamic programming problem appears frequently in interviews and has many practical applications.
Problem Statement
Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous. For example, 'ACE' is a subsequence of 'ABCDE'.
Solution
public class LongestCommonSubsequence {
// Dynamic Programming approach (Bottom-up)
public static int lcsDP(String text1, String text2) {
int m = text1.length();
int n = text2.length();
// Create DP table
int[][] dp = new int[m + 1][n + 1];
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// Characters match: add 1 to diagonal value
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// Characters don't match: take max of left or top
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Recursive approach with memoization (Top-down)
public static int lcsMemo(String text1, String text2) {
int[][] memo = new int[text1.length()][text2.length()];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return lcsMemoHelper(text1, text2, 0, 0, memo);
}
private static int lcsMemoHelper(String text1, String text2, int i, int j, int[][] memo) {
// Base case: reached end of either string
if (i == text1.length() || j == text2.length()) {
return 0;
}
// Check memo
if (memo[i][j] != -1) {
return memo[i][j];
}
int result;
if (text1.charAt(i) == text2.charAt(j)) {
// Characters match: include and move both pointers
result = 1 + lcsMemoHelper(text1, text2, i + 1, j + 1, memo);
} else {
// Characters don't match: try both options
int option1 = lcsMemoHelper(text1, text2, i + 1, j, memo);
int option2 = lcsMemoHelper(text1, text2, i, j + 1, memo);
result = Math.max(option1, option2);
}
memo[i][j] = result;
return result;
}
// Method to reconstruct the actual LCS string
public static String getLCSString(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// Fill DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Backtrack to find the actual subsequence
StringBuilder lcs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
lcs.insert(0, text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs.toString();
}
public static void main(String[] args) {
String text1 = "ABCDGH";
String text2 = "AEDFHR";
System.out.println("String 1: " + text1);
System.out.println("String 2: " + text2);
int lengthDP = lcsDP(text1, text2);
System.out.println("\nLCS Length (DP): " + lengthDP);
int lengthMemo = lcsMemo(text1, text2);
System.out.println("LCS Length (Memoization): " + lengthMemo);
String lcsString = getLCSString(text1, text2);
System.out.println("Actual LCS: " + lcsString);
}
}Explanation & Key Points
- Time Complexity: O(m × n) where m and n are string lengths
- Space Complexity: O(m × n) for DP table
- DP Recurrence: If chars match: dp[i][j] = dp[i-1][j-1] + 1, else: max(dp[i-1][j], dp[i][j-1])
- Key Insight: Build solution from smaller subproblems
- Real-World Use: Diff tools (git diff), DNA sequence analysis, plagiarism detection, file comparison
Program #8: N-Queens Problem (Very Hard)
The N-Queens problem is a classic backtracking challenge that tests your ability to handle complex constraints.
Problem Statement
Place N chess queens on an N×N chessboard so that no two queens threaten each other. Find all possible solutions.
Solution
import java.util.*;
public class NQueens {
public static List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
char[][] board = new char[n][n];
// Initialize board with empty cells
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
// Sets to track attacked positions
Set<Integer> cols = new HashSet<>();
Set<Integer> diag1 = new HashSet<>(); // row - col
Set<Integer> diag2 = new HashSet<>(); // row + col
backtrack(0, n, board, solutions, cols, diag1, diag2);
return solutions;
}
private static void backtrack(int row, int n, char[][] board,
List<List<String>> solutions,
Set<Integer> cols,
Set<Integer> diag1,
Set<Integer> diag2) {
// Base case: all queens placed successfully
if (row == n) {
solutions.add(constructSolution(board));
return;
}
// Try placing queen in each column of current row
for (int col = 0; col < n; col++) {
// Check if position is safe
if (cols.contains(col) ||
diag1.contains(row - col) ||
diag2.contains(row + col)) {
continue;
}
// Place queen
board[row][col] = 'Q';
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
// Recurse to next row
backtrack(row + 1, n, board, solutions, cols, diag1, diag2);
// Remove queen (backtrack)
board[row][col] = '.';
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
}
private static List<String> constructSolution(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(new String(row));
}
return solution;
}
// Helper method to print a solution
private static void printSolution(List<String> solution, int solutionNumber) {
System.out.println("\nSolution " + solutionNumber + ":");
for (String row : solution) {
System.out.println(row);
}
}
// Alternative: Check if position is safe (without sets)
private static boolean isSafe(char[][] board, int row, int col, int n) {
// Check column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check upper-left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check upper-right diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
public static void main(String[] args) {
int n = 4;
System.out.println("Solving " + n + "-Queens Problem:");
List<List<String>> solutions = solveNQueens(n);
System.out.println("\nTotal solutions found: " + solutions.size());
// Print all solutions
for (int i = 0; i < solutions.size(); i++) {
printSolution(solutions.get(i), i + 1);
}
}
}Explanation & Key Points
- Time Complexity: O(N!) - trying all possible placements
- Space Complexity: O(N²) for board + O(N) for recursion
- Optimization: Using sets to track attacked positions in O(1) time
- Diagonal Formula: row - col for one diagonal, row + col for the other
- Real-World Use: Constraint satisfaction problems, scheduling, resource allocation
Challenge Yourself
Try solving for N=8 (standard chessboard). There are 92 distinct solutions! Can you optimize the algorithm further?
Program #9: Implement LRU Cache (Very Hard)
LRU (Least Recently Used) Cache is a common interview question that tests your understanding of data structures and design.
Problem Statement
Design and implement a data structure for Least Recently Used (LRU) cache. It should support get and put operations in O(1) time complexity.
Solution
import java.util.*;
public class LRUCache {
// Doubly linked list node
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, Node> cache;
private int capacity;
private Node head; // Most recently used
private Node tail; // Least recently used
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
// Initialize dummy head and tail
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
// Move accessed node to front (most recently used)
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
// Update existing key
Node node = cache.get(key);
node.value = value;
moveToHead(node);
} else {
// Add new key
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
// Check capacity
if (cache.size() > capacity) {
// Remove least recently used (tail)
Node lru = removeTail();
cache.remove(lru.key);
}
}
}
// Helper method: Add node right after head
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// Helper method: Remove node from list
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// Helper method: Move node to head
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
// Helper method: Remove and return tail node
private Node removeTail() {
Node lru = tail.prev;
removeNode(lru);
return lru;
}
// Helper method to display cache state
public void displayCache() {
System.out.print("Cache (MRU -> LRU): ");
Node current = head.next;
while (current != tail) {
System.out.print("[" + current.key + ":" + current.value + "] ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
System.out.println("LRU Cache with capacity 3\n");
cache.put(1, 10);
System.out.println("Put (1, 10)");
cache.displayCache();
cache.put(2, 20);
System.out.println("\nPut (2, 20)");
cache.displayCache();
cache.put(3, 30);
System.out.println("\nPut (3, 30)");
cache.displayCache();
System.out.println("\nGet key 1: " + cache.get(1));
cache.displayCache();
cache.put(4, 40);
System.out.println("\nPut (4, 40) - Should evict key 2");
cache.displayCache();
System.out.println("\nGet key 2: " + cache.get(2) + " (should be -1)");
cache.put(5, 50);
System.out.println("\nPut (5, 50) - Should evict key 3");
cache.displayCache();
}
}Explanation & Key Points
- Time Complexity: O(1) for both get and put operations
- Space Complexity: O(capacity) for storing cache entries
- Data Structures: HashMap for O(1) lookup + Doubly Linked List for O(1) removal/insertion
- Key Design: HashMap stores key-node pairs, list maintains access order
- Real-World Use: Browser cache, database query cache, CDN caching, memory management
Program #10: Serialize and Deserialize Binary Tree (Extremely Hard)
This is one of the most challenging tree problems. It tests your understanding of tree traversal, recursion, and string manipulation.
Problem Statement
Design an algorithm to serialize a binary tree to a string and deserialize the string back to the original tree structure. The serialization should preserve the tree structure completely.
Solution
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class SerializeDeserializeBinaryTree {
private static final String NULL_MARKER = "null";
private static final String DELIMITER = ",";
// Serialize using preorder traversal
public static String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private static void serializeHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NULL_MARKER).append(DELIMITER);
return;
}
// Preorder: root -> left -> right
sb.append(node.val).append(DELIMITER);
serializeHelper(node.left, sb);
serializeHelper(node.right, sb);
}
// Deserialize from string
public static TreeNode deserialize(String data) {
Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
return deserializeHelper(nodes);
}
private static TreeNode deserializeHelper(Queue<String> nodes) {
String val = nodes.poll();
if (val.equals(NULL_MARKER)) {
return null;
}
// Create node and recursively build left and right subtrees
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = deserializeHelper(nodes);
node.right = deserializeHelper(nodes);
return node;
}
// Alternative: Level-order (BFS) serialization
public static String serializeLevelOrder(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append(NULL_MARKER).append(DELIMITER);
} else {
sb.append(node.val).append(DELIMITER);
queue.offer(node.left);
queue.offer(node.right);
}
}
return sb.toString();
}
public static TreeNode deserializeLevelOrder(String data) {
if (data.isEmpty()) {
return null;
}
String[] values = data.split(DELIMITER);
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < values.length) {
TreeNode node = queue.poll();
// Process left child
if (!values[i].equals(NULL_MARKER)) {
node.left = new TreeNode(Integer.parseInt(values[i]));
queue.offer(node.left);
}
i++;
// Process right child
if (i < values.length && !values[i].equals(NULL_MARKER)) {
node.right = new TreeNode(Integer.parseInt(values[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
// Helper method to print tree (inorder)
private static void printInorder(TreeNode node) {
if (node == null) {
return;
}
printInorder(node.left);
System.out.print(node.val + " ");
printInorder(node.right);
}
// Helper method to print tree structure
private static void printTree(TreeNode node, String prefix, boolean isLeft) {
if (node == null) {
return;
}
System.out.println(prefix + (isLeft ? "├── " : "└── ") + node.val);
if (node.left != null || node.right != null) {
if (node.left != null) {
printTree(node.left, prefix + (isLeft ? "│ " : " "), true);
}
if (node.right != null) {
printTree(node.right, prefix + (isLeft ? "│ " : " "), false);
}
}
}
public static void main(String[] args) {
// Create a sample tree:
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Original Tree:");
printTree(root, "", false);
// Serialize
String serialized = serialize(root);
System.out.println("\nSerialized (Preorder): " + serialized);
// Deserialize
TreeNode deserialized = deserialize(serialized);
System.out.println("\nDeserialized Tree:");
printTree(deserialized, "", false);
// Verify with inorder traversal
System.out.println("\nInorder traversal of original: ");
printInorder(root);
System.out.println("\nInorder traversal of deserialized: ");
printInorder(deserialized);
// Test level-order approach
System.out.println("\n\nLevel-order serialization: " + serializeLevelOrder(root));
}
}Explanation & Key Points
- Time Complexity: O(n) for both serialization and deserialization
- Space Complexity: O(n) for storing the tree structure
- Two Approaches: Preorder (DFS) and Level-order (BFS) - both work
- Key Challenge: Handling null nodes to preserve structure
- Real-World Use: Saving/loading data structures, network transmission, database storage, caching
Master Achievement
If you can implement this from scratch without looking at the solution, you're ready for senior-level interviews. This problem combines multiple advanced concepts.
How to Practice These Programs Effectively
Knowing the solutions isn't enough. Here's how to actually master these programs:
1. Code Without Looking
After understanding a solution, close this article and try implementing it from scratch. Struggle is where learning happens.
2. Explain Out Loud
Pretend you're teaching the algorithm to someone else. If you can't explain it clearly, you don't understand it well enough.
3. Modify and Extend
Change the problem slightly. What if the input is different? What if you need to optimize for space instead of time? Variations deepen understanding.
4. Time Yourself
In interviews, you'll have limited time. Practice implementing these programs within 30-45 minutes to build speed and confidence.
5. Review Regularly
Revisit these programs every few weeks. Spaced repetition is key to long-term retention.
- Week 1: Learn and implement all 10 programs
- Week 2: Implement from memory without looking
- Week 3: Solve variations and similar problems
- Week 4: Teach these concepts to a peer or study group
- Monthly: Review and optimize your solutions
Interview Preparation
These 10 programs cover 80% of common interview patterns. Master them, and you'll recognize similar problems instantly during interviews.
Common Mistakes to Avoid
- Just Reading Solutions: You must code them yourself. Reading ≠ Understanding
- Ignoring Edge Cases: Always test with empty inputs, single elements, and large datasets
- Not Analyzing Complexity: Always think about time and space complexity
- Memorizing Instead of Understanding: Focus on the 'why' behind each approach
- Skipping the 'Easy' Ones: Even medium problems teach fundamental patterns
- Not Testing Thoroughly: Write test cases before claiming your code works
Resources for Further Learning
Want to go deeper? Here are recommended resources:
- Books: 'Cracking the Coding Interview' by Gayle Laakmann McDowell, 'Introduction to Algorithms' (CLRS)
- Online Platforms: LeetCode, HackerRank, CodeForces for practice problems
- Courses: Our Full-Stack Development course covers advanced Java concepts
- YouTube Channels: Abdul Bari for algorithms, Tech Dose for problem-solving
- Practice: Solve at least 2-3 problems daily on coding platforms
Why These Programs Matter for Your Career
Let's be real about why you should invest time mastering these programs:
- Technical Interviews: 90% of coding interviews test these exact patterns
- Problem-Solving Skills: These algorithms teach you to think systematically
- Code Quality: You'll write cleaner, more efficient code in real projects
- Confidence: Knowing you can solve hard problems builds genuine confidence
- Career Growth: Senior developers are expected to know these fundamentals cold
Companies like Google, Amazon, Microsoft, and top startups ask variations of these problems. Master them, and you'll stand out.
Frequently Asked Questions
With consistent practice (1-2 hours daily), you can understand and implement all 10 in 2-3 weeks. True mastery—being able to code them from memory and explain them clearly—takes 1-2 months of regular practice.
No! Memorization is useless. Focus on understanding the patterns, techniques, and reasoning. Once you understand the approach, you can recreate the solution even if you forget the exact code.
These 10 programs cover fundamental patterns, but you should solve 100-150 problems total for solid interview prep. Use these as your foundation, then practice variations on LeetCode or similar platforms.
That's normal! Struggle for 30-45 minutes first. If stuck, look at hints (not full solutions). If still stuck, study the solution, understand it completely, then implement it from scratch without looking.
Java is excellent for interviews—it's widely accepted, has good library support, and forces you to think about data structures explicitly. Python is also popular for its conciseness. Choose what you're most comfortable with.
Analyze time and space complexity. Compare with the solutions here. Ask yourself: Can I do better? Research the problem online to see if there are more efficient approaches. Discuss with peers or mentors.
You need basic data structures knowledge first (arrays, linked lists, trees, graphs, hash maps). If you're weak on fundamentals, study data structures first, then tackle these programs.
Use them to learn, not to copy. Understand the logic, then write your own implementation. Submitting copied code is plagiarism and defeats the purpose of learning.
Conclusion
These 10 Java programs represent the core of what every college student should master. They're not just coding exercises—they're fundamental patterns that appear repeatedly in real software development and technical interviews.
From binary search to LRU cache, from linked list reversal to tree serialization—each program teaches you something essential about algorithms, data structures, and problem-solving.
The difference between students who succeed in technical interviews and those who struggle often comes down to this: did they practice hard problems, or did they stick to easy ones? Did they understand the patterns, or did they just memorize solutions?
You now have complete, working solutions with explanations. The question is: what will you do with them?
- Start with Program #1 and work your way up
- Code each solution from scratch without looking
- Test with multiple inputs and edge cases
- Analyze time and space complexity
- Solve variations to deepen understanding
- Review regularly to maintain mastery
Remember: every expert programmer once struggled with these exact problems. The difference is they kept going. They debugged, they learned, they practiced—and eventually, they mastered them.
You can do the same. Start today. Pick one program. Understand it. Code it. Master it. Then move to the next. In a few months, you'll look back and be amazed at how far you've come.
Need more guidance? Check out our advanced Java courses where we dive deeper into algorithms, data structures, and interview preparation. Or reach out to us with questions—we're here to help you succeed.
Your Journey Starts Now
These 10 programs are your roadmap to coding mastery. Don't just read them—code them, break them, fix them, and make them yours. That's how you become the developer companies fight to hire.
