PYnative

Python Programming

Home » Java Exercises » Java Data Structures Exercises: 30 Coding Problems with Solutions

Java Data Structures Exercises: 30 Coding Problems with Solutions

Updated on:  | Leave a Comment

This collection of 30 Java exercises builds core data structures from the ground up, going well beyond using Java’s built-in collections to actually implementing the structures yourself.

What You’ll Practice

  • Arrays & Two-Pointers: Min/max search, in-place reversal, rotation, and pair-sum problems.
  • Linked Structures: A custom singly linked list, reversal, Floyd’s cycle detection, and merging sorted lists.
  • Stacks & Queues: A hand-built stack and circular queue, balanced-parentheses checking, and postfix expression evaluation.
  • Trees & Graphs: Binary tree traversals, BST validation, lowest common ancestor, BFS/DFS, and cycle detection in a directed graph.
  • Heaps & Tries: Finding the k-th largest element, merging k sorted arrays, and building a Trie for prefix search.

Each exercise includes a Problem Statement, Purpose, Hint, and a Solution with Explanation, so you understand the mechanics behind the structure, not just how to call a library method.

+ Table of Contents (30 Exercises)

Table of contents

Exercise 1: Find the Maximum and Minimum Element in an Array

Problem Statement: Write a Java program to find the maximum and minimum element in a one-dimensional array.

Purpose: This exercise helps you practice iterating over an array, comparing elements, and tracking running values, core skills used in data validation, statistics, and array processing tasks.

Given Input: int[] numbers = {12, 45, 2, 78, 34, 5};

Expected Output: Maximum = 78 and Minimum = 2

▼ Hint
  • Initialize max and min to the first element of the array.
  • Loop through the array starting from the second element.
  • Update max whenever you find a larger value, and min whenever you find a smaller value.
  • You can also sort the array and read the first and last elements as an alternative, though a single loop is more efficient.
▼ Solution & Explanation
class MinMaxFinder {
    public int[] findMaxMin(int[] numbers) {
        int max = numbers[0];
        int min = numbers[0];
        for (int num : numbers) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        return new int[]{max, min};
    }
}

public class Main {
    public static void main(String[] args) {
        MinMaxFinder minMaxFinder = new MinMaxFinder();
        int[] numbers = {12, 45, 2, 78, 34, 5};
        int[] result = minMaxFinder.findMaxMin(numbers);
        System.out.println("Maximum = " + result[0]);
        System.out.println("Minimum = " + result[1]);
        // Usage:
        // findMaxMin(new int[]{12, 45, 2, 78, 34, 5}) returns [78, 2]
    }
}Code language: Java (java)

Explanation:

  • int max = numbers[0];: Initializes both max and min to the first element so comparisons start from a valid baseline.
  • for (int num : numbers): Uses an enhanced for loop to iterate through each element without needing an index.
  • if (num > max) / if (num < min): Updates max and min whenever a new extreme value is found.
  • Alternative: You could sort the array with Arrays.sort() and read the first and last elements, but that costs O(n log n) time compared to O(n) for a single pass.

Exercise 2: Reverse an Array In-Place

Problem Statement: Write a Java program to reverse an array in-place without using extra memory, meaning without creating a second array.

Purpose: This exercise helps you practice the two-pointer swapping technique, a useful pattern for in-place array manipulation problems commonly seen in coding interviews.

Given Input: int[] numbers = {10, 20, 30, 40, 50};

Expected Output: [50, 40, 30, 20, 10]

▼ Hint
  • Use two index pointers, one starting at the beginning (left) and one at the end (right).
  • Swap the elements at left and right, then move left forward and right backward.
  • Continue until left is no longer less than right.
▼ Solution & Explanation
import java.util.Arrays;

class ArrayReverser {
    public void reverseArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
            left++;
            right--;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayReverser arrayReverser = new ArrayReverser();
        int[] numbers = {10, 20, 30, 40, 50};
        arrayReverser.reverseArray(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // reverseArray(new int[]{10, 20, 30, 40, 50}) modifies the array to [50, 40, 30, 20, 10]
    }
}Code language: Java (java)

Explanation:

  • int left = 0; int right = numbers.length - 1;: Sets up two pointers at opposite ends of the array.
  • while (left < right): Continues swapping until the pointers meet or cross in the middle.
  • temp / swap logic: Uses a temporary variable to exchange numbers[left] and numbers[right] without allocating a new array.
  • Alternative: You could convert the array to a list and call Collections.reverse(), but that adds overhead and does not work directly on primitive arrays.

Exercise 3: Rotate an Array to the Right by K Steps

Problem Statement: Write a Java program to rotate an array to the right by k steps, where k is a given non-negative integer.

Purpose: This exercise helps you practice the array reversal technique to solve rotation in-place, a pattern commonly used in scheduling, buffering, and circular data structures.

Given Input: int[] numbers = {1, 2, 3, 4, 5, 6, 7}; int k = 3;

Expected Output: [5, 6, 7, 1, 2, 3, 4]

▼ Hint
  • Normalize k using k % numbers.length to handle cases where k is larger than the array length.
  • Reverse the entire array first.
  • Reverse the first k elements, then reverse the remaining elements, this produces the rotated array.
▼ Solution & Explanation
import java.util.Arrays;

class ArrayRotator {
    public void rotateRight(int[] numbers, int k) {
        int n = numbers.length;
        k = k % n;
        reverse(numbers, 0, n - 1);
        reverse(numbers, 0, k - 1);
        reverse(numbers, k, n - 1);
    }

    private void reverse(int[] numbers, int start, int end) {
        while (start < end) {
            int temp = numbers[start];
            numbers[start] = numbers[end];
            numbers[end] = temp;
            start++;
            end--;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayRotator arrayRotator = new ArrayRotator();
        int[] numbers = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        arrayRotator.rotateRight(numbers, k);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // rotateRight(new int[]{1, 2, 3, 4, 5, 6, 7}, 3) modifies the array to [5, 6, 7, 1, 2, 3, 4]
    }
}Code language: Java (java)

Explanation:

  • k = k % n;: Normalizes k so rotating by a value larger than the array length still works correctly.
  • reverse(numbers, 0, n - 1);: Reverses the whole array first, placing elements roughly in rotated order but reversed within each segment.
  • reverse(numbers, 0, k - 1); / reverse(numbers, k, n - 1);: Reverses the first k elements and the remaining elements separately to restore the correct order within each segment.
  • Alternative: You could rotate one step at a time in a loop k times, but that costs O(n * k) time compared to O(n) for the reversal approach.

Exercise 4: Remove Duplicates from a Sorted ArrayList

Problem Statement: Write a Java program to remove duplicates from a sorted ArrayList without using standard Collection sets such as HashSet or TreeSet.

Purpose: This exercise helps you practice manual duplicate detection by comparing adjacent elements, useful for understanding how set-like behavior can be implemented without relying on built-in set classes.

Given Input: ArrayList numbers = new ArrayList<>(Arrays.asList(10, 10, 20, 30, 30, 30, 40));

Expected Output: [10, 20, 30, 40]

▼ Hint
  • Since the list is already sorted, duplicates will always sit next to each other.
  • Loop through the list using an index, comparing each element with the next one.
  • Remove the current element if it equals the next element, otherwise move to the next index.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Arrays;

class DuplicateRemover {
    public void removeDuplicates(ArrayList<Integer> numbers) {
        int index = 0;
        while (index < numbers.size() - 1) {
            if (numbers.get(index).equals(numbers.get(index + 1))) {
                numbers.remove(index + 1);
            } else {
                index++;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        DuplicateRemover duplicateRemover = new DuplicateRemover();
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(10, 10, 20, 30, 30, 30, 40));
        duplicateRemover.removeDuplicates(numbers);
        System.out.println(numbers);
        // Usage:
        // removeDuplicates(new ArrayList<>(Arrays.asList(10, 10, 20, 30, 30, 30, 40)))
        // modifies the list to [10, 20, 30, 40]
    }
}Code language: Java (java)

Explanation:

  • while (index < numbers.size() - 1): Loops through the list comparing the current element with its neighbor, stopping before the last index to avoid an out-of-bounds check.
  • numbers.get(index).equals(numbers.get(index + 1)): Compares adjacent elements since the list is sorted, so equal elements are always next to each other.
  • numbers.remove(index + 1);: Removes the duplicate without advancing the index, so the new neighbor is checked next.
  • Alternative: You could copy the elements into a LinkedHashSet to remove duplicates in one line, but that is excluded here since the exercise asks you to avoid standard Collection sets.

Exercise 5: Find All Pairs With a Given Sum

Problem Statement: Write a Java program to find all pairs of integers in an array whose sum is equal to a specified target number.

Purpose: This exercise helps you practice the two-pointer technique on a sorted array, a common pattern for efficiently solving pair-sum and subarray-sum problems.

Given Input: int[] numbers = {2, 4, 3, 7, 8, 1}; int target = 9;

Expected Output:

(1, 8)
(2, 7)
▼ Hint
  • Sort the array first so that a two-pointer approach can be used.
  • Place one pointer at the start and one at the end of the sorted array.
  • If the sum of the two pointed elements equals the target, record the pair and move both pointers inward. If the sum is smaller, move the left pointer forward; if larger, move the right pointer backward.
▼ Solution & Explanation
import java.util.Arrays;

class PairSumFinder {
    public void findPairsWithSum(int[] numbers, int target) {
        Arrays.sort(numbers);
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                System.out.println("(" + numbers[left] + ", " + numbers[right] + ")");
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        PairSumFinder pairSumFinder = new PairSumFinder();
        int[] numbers = {2, 4, 3, 7, 8, 1};
        int target = 9;
        pairSumFinder.findPairsWithSum(numbers, target);
        // Usage:
        // findPairsWithSum(new int[]{2, 4, 3, 7, 8, 1}, 9) prints (1, 8) and (2, 7)
    }
}Code language: Java (java)

Explanation:

  • Arrays.sort(numbers);: Sorts the array first, which is required for the two-pointer technique to work correctly.
  • int left = 0; int right = numbers.length - 1;: Sets up two pointers at opposite ends of the sorted array.
  • if (sum == target): Prints the pair and moves both pointers inward to look for the next unique pair.
  • else if (sum < target) / else: Moves the left pointer forward when the sum is too small, or the right pointer backward when the sum is too large.
  • Alternative: You could use a nested loop to check every pair in O(n^2) time, but the two-pointer approach on a sorted array runs faster overall.

Exercise 6: Implement a Custom Singly Linked List

Problem Statement: Implement a custom Singly Linked List from scratch in Java with insert, delete, and display methods.

Purpose: This exercise helps you practice building a fundamental data structure from the ground up and understanding node references and pointer manipulation, which forms the foundation for more advanced structures like stacks, queues, and trees.

Given Input: Insert 10, 20, 30, then delete 20, then display the list.

Expected Output: 10 -> 30 -> null

▼ Hint
  • Create a Node class with a data field and a reference to the next node.
  • Maintain a head reference pointing to the first node of the list.
  • To insert, create a new node and attach it at the end by traversing to the last node.
  • To delete, traverse the list while keeping track of the previous node, then re-link the previous node’s next pointer to skip the target node.
▼ Solution & Explanation
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;

    public void insert(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void delete(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node previous = head;
        Node current = head.next;

        while (current != null) {
            if (current.data == data) {
                previous.next = current.next;
                return;
            }
            previous = current;
            current = current.next;
        }
    }

    public void display() {
        Node current = head;
        StringBuilder result = new StringBuilder();

        while (current != null) {
            result.append(current.data).append(" -> ");
            current = current.next;
        }
        result.append("null");

        System.out.println(result);
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.delete(20);
        list.display();

        // Usage:
        // list.insert(10); list.insert(20); list.insert(30); list.delete(20); list.display();
        // prints 10 -> 30 -> null
    }
}Code language: Java (java)

Explanation:

  • static class Node: Represents a single element in the list, holding a data value and a reference to the next node.
  • insert(int data): Traverses to the last node and attaches a new node there, or sets it as the head if the list is empty.
  • delete(int data): Handles removing the head separately, then traverses the list keeping a previous reference so it can re-link around the node being removed.
  • display(): Walks through the list from head to tail, building a readable string ending in null to represent the end of the list.
  • Alternative: You could use Java’s built-in LinkedList class for most practical applications, but implementing one manually builds a deeper understanding of how references and traversal work internally.

Exercise 7: Reverse a Singly Linked List

Problem Statement: Write a Java program to reverse a singly linked list, implemented both iteratively and recursively.

Purpose: This exercise helps you practice pointer manipulation and recursion on linked structures, a common interview question that tests understanding of how references are rewired.

Given Input: A linked list containing 1 -> 2 -> 3 -> 4 -> 5 -> null

Expected Output: 5 -> 4 -> 3 -> 2 -> 1 -> null

▼ Hint
  • For the iterative approach, keep three references: previous, current, and next, and rewire current.next to point backward as you move forward.
  • For the recursive approach, recurse to the end of the list first, then reverse the link on the way back up the call stack.
  • In both approaches, the original head becomes the new tail, so remember to set its next reference to null.
▼ Solution & Explanation
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListReverser {
    public Node reverseIterative(Node head) {
        Node previous = null;
        Node current = head;

        while (current != null) {
            Node nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }
        return previous;
    }

    public Node reverseRecursive(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node newHead = reverseRecursive(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    public void display(Node head) {
        Node current = head;
        StringBuilder result = new StringBuilder();

        while (current != null) {
            result.append(current.data).append(" -> ");
            current = current.next;
        }
        result.append("null");

        System.out.println(result);
    }
}

public class Main {
    public static void main(String[] args) {
        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);

        LinkedListReverser linkedListReverser = new LinkedListReverser();
        Node reversedHead = linkedListReverser.reverseIterative(head);
        linkedListReverser.display(reversedHead);

        // Usage:
        // reverseIterative(head) on 1 -> 2 -> 3 -> 4 -> 5 -> null
        // returns a list printing 5 -> 4 -> 3 -> 2 -> 1 -> null
    }
}Code language: Java (java)

Explanation:

  • reverseIterative(Node head): Uses three pointers, previous, current, and nextNode, to reverse each link one step at a time while walking through the list.
  • current.next = previous;: Rewires the current node to point backward instead of forward, gradually reversing the whole chain.
  • reverseRecursive(Node head): Recurses all the way to the last node first, then reverses the link between each pair of nodes while unwinding the recursion.
  • head.next.next = head; head.next = null;: Makes the next node point back to the current node, then clears the current node’s forward reference to avoid a cycle.
  • Alternative: You could push all node values onto a stack and pop them into a new list, but that uses extra space compared to the in-place pointer approach shown here.

Exercise 8: Detect a Cycle in a Linked List (Floyd’s Cycle-Finding Algorithm)

Problem Statement: Write a Java program to detect whether a cycle (loop) exists in a linked list using Floyd’s Cycle-Finding Algorithm.

Purpose: This exercise helps you practice the fast and slow pointer technique, a widely used pattern for detecting cycles and finding midpoints in linked structures without extra memory.

Given Input: A linked list where the last node’s next reference is manually set to point back to an earlier node, creating a loop.

Expected Output: Cycle detected = true

▼ Hint
  • Use two pointers, a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time.
  • If the linked list has a cycle, the fast pointer will eventually meet the slow pointer inside the loop.
  • If the fast pointer reaches null, the list has no cycle.
▼ Solution & Explanation
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CycleDetector {
    public boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        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 = head.next;

        CycleDetector cycleDetector = new CycleDetector();
        System.out.println("Cycle detected = " + cycleDetector.hasCycle(head));

        // Usage:
        // hasCycle(head) where head.next.next.next.next points back to head.next
        // returns true
    }
}Code language: Java (java)

Explanation:

  • Node slow = head; Node fast = head;: Initializes both pointers at the head of the list before starting the traversal.
  • fast = fast.next.next;: Advances the fast pointer two steps at a time so it moves through the list faster than the slow pointer.
  • if (slow == fast): Checks whether the two pointers have met, which can only happen if the list contains a cycle.
  • while (fast != null && fast.next != null): Stops safely if the fast pointer reaches the end of the list, confirming there is no cycle.
  • Alternative: You could store visited nodes in a HashSet and check for repeats, but Floyd’s algorithm achieves the same result using O(1) extra space instead of O(n).

Exercise 9: Find the Middle Element of a Linked List

Problem Statement: Write a Java program to find the middle element of a linked list in a single pass.

Purpose: This exercise helps you practice the fast and slow pointer technique to solve positional problems on a linked list without knowing its length in advance.

Given Input: A linked list containing 10 -> 20 -> 30 -> 40 -> 50 -> null

Expected Output: Middle element = 30

▼ Hint
  • Use two pointers, slow and fast, both starting at the head.
  • Move slow one step at a time and fast two steps at a time.
  • When fast reaches the end of the list, slow will be positioned at the middle node.
▼ Solution & Explanation
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class MiddleElementFinder {
    public int findMiddle(Node head) {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.data;
    }
}

public class Main {
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        head.next.next.next = new Node(40);
        head.next.next.next.next = new Node(50);

        MiddleElementFinder middleElementFinder = new MiddleElementFinder();
        System.out.println("Middle element = " + middleElementFinder.findMiddle(head));

        // Usage:
        // findMiddle(head) on 10 -> 20 -> 30 -> 40 -> 50 -> null
        // returns 30
    }
}Code language: Java (java)

Explanation:

  • Node slow = head; Node fast = head;: Sets up both pointers at the start of the list.
  • fast = fast.next.next;: Moves the fast pointer twice as fast as the slow pointer, so slow lands on the middle node once fast reaches the end.
  • while (fast != null && fast.next != null): Handles both odd and even length lists correctly by stopping fast safely at or just before the end.
  • Alternative: You could count the total number of nodes first, then traverse to length divided by two, but that requires two passes instead of one.

Exercise 10: Merge Two Sorted Linked Lists

Problem Statement: Write a Java program to merge two already sorted linked lists into a single, sorted linked list.

Purpose: This exercise helps you practice comparing and re-linking nodes across two structures, a foundational technique used in merge sort and in combining ordered data streams.

Given Input: List A: 1 -> 3 -> 5 -> null and List B: 2 -> 4 -> 6 -> null

Expected Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

▼ Hint
  • Use a dummy node to simplify building the merged list, this avoids special-casing the head.
  • Compare the current nodes of both lists and attach the smaller one to the merged list, then advance that list’s pointer.
  • Once one list is exhausted, attach the remaining nodes of the other list directly, since they are already sorted.
▼ Solution & Explanation
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SortedListMerger {
    public Node mergeSortedLists(Node headA, Node headB) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (headA != null && headB != null) {
            if (headA.data <= headB.data) {
                tail.next = headA;
                headA = headA.next;
            } else {
                tail.next = headB;
                headB = headB.next;
            }
            tail = tail.next;
        }
        tail.next = (headA != null) ? headA : headB;
        return dummy.next;
    }

    public void display(Node head) {
        Node current = head;
        StringBuilder result = new StringBuilder();
        while (current != null) {
            result.append(current.data).append(" -> ");
            current = current.next;
        }
        result.append("null");
        System.out.println(result);
    }
}

public class Main {
    public static void main(String[] args) {
        Node headA = new Node(1);
        headA.next = new Node(3);
        headA.next.next = new Node(5);
        Node headB = new Node(2);
        headB.next = new Node(4);
        headB.next.next = new Node(6);

        SortedListMerger sortedListMerger = new SortedListMerger();
        Node mergedHead = sortedListMerger.mergeSortedLists(headA, headB);
        sortedListMerger.display(mergedHead);
        // Usage:
        // mergeSortedLists(headA, headB) on 1 -> 3 -> 5 -> null and 2 -> 4 -> 6 -> null
        // returns 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
    }
}Code language: Java (java)

Explanation:

  • Node dummy = new Node(0);: Creates a placeholder node so the merged list can be built without special-casing which list contributes the first node.
  • if (headA.data <= headB.data): Compares the current nodes from both lists and attaches the smaller value to the merged list.
  • tail.next = (headA != null) ? headA : headB;: Attaches whichever list still has remaining nodes once the other one is exhausted.
  • return dummy.next;: Skips the dummy placeholder and returns the actual head of the merged list.
  • Alternative: You could copy all values into an array, sort it, then rebuild a new linked list, but merging directly avoids the extra sorting and rebuilding overhead.

Exercise 11: Implement a Stack Using a Standard Java Array

Problem Statement: Implement a Stack data structure in Java using a standard array, supporting push, pop, and peek operations.

Purpose: This exercise helps you practice managing a fixed-size backing array with a top pointer, the foundational mechanism behind stack-based structures used in expression evaluation, undo systems, and function call tracking.

Given Input: Push 10, 20, 30 onto the stack, then pop once and peek at the new top.

Expected Output: Popped = 30 and Peek = 20

▼ Hint
  • Maintain a top index that starts at -1 to represent an empty stack.
  • To push, increment top first, then place the value at that index.
  • To pop, read the value at top, then decrement top.
  • Always check for an empty or full stack before popping or pushing to avoid errors.
▼ Solution & Explanation
class ArrayStack {
    private int[] data;
    private int top;

    public ArrayStack(int capacity) {
        data = new int[capacity];
        top = -1;
    }

    public void push(int value) {
        if (top == data.length - 1) {
            throw new RuntimeException("Stack overflow");
        }
        data[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return data[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return data[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Popped = " + stack.pop());
        System.out.println("Peek = " + stack.peek());

        // Usage:
        // stack.push(10); stack.push(20); stack.push(30); stack.pop();
        // stack.peek() returns 20
    }
}Code language: Java (java)

Explanation:

  • private int top;: Tracks the index of the current top element, starting at -1 to represent an empty stack.
  • data[++top] = value;: Increments top before writing, so the value is placed at the next free slot.
  • data[top--];: Reads the value at the current top, then moves the top pointer down by one.
  • Alternative: You could use Java’s built-in java.util.Stack or an ArrayDeque for production code, but implementing one manually shows how the underlying array and pointer work together.

Exercise 12: Check if Parentheses Are Balanced Using a Stack

Problem Statement: Write a Java program to check if a string of parentheses, such as {[()]}, is balanced using a Stack.

Purpose: This exercise helps you practice using a stack to match opening and closing symbols, a technique used in compilers, code editors, and expression parsers.

Given Input: String expression = "{[()]}";

Expected Output: Balanced = true

▼ Hint
  • Push every opening bracket you encounter onto a stack.
  • When you encounter a closing bracket, pop from the stack and check whether it matches the corresponding opening bracket.
  • At the end, the string is balanced only if the stack is empty and every closing bracket found a match.
▼ Solution & Explanation
import java.util.Stack;

class BalancedParenthesesChecker {
    public boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }
                char open = stack.pop();
                if ((ch == ')' && open != '(') ||
                    (ch == '}' && open != '{') ||
                    (ch == ']' && open != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

public class Main {
    public static void main(String[] args) {
        BalancedParenthesesChecker balancedParenthesesChecker = new BalancedParenthesesChecker();
        String expression = "{[()]}";
        System.out.println("Balanced = " + balancedParenthesesChecker.isBalanced(expression));
        // Usage:
        // isBalanced("{[()]}") returns true
        // isBalanced("{[(])}") returns false
    }
}Code language: Java (java)

Explanation:

  • stack.push(ch);: Pushes every opening bracket onto the stack so it can be matched later.
  • char open = stack.pop();: Pops the most recent unmatched opening bracket when a closing bracket is found.
  • if (stack.isEmpty()) return false;: Catches the case where a closing bracket appears with no matching opening bracket on the stack.
  • return stack.isEmpty();: Confirms the string is balanced only if every opening bracket was eventually matched and closed.
  • Alternative: You could use a counter for a single bracket type, but a stack is required once multiple bracket types need to be matched in the correct order.

Exercise 13: Implement a Queue Using Two Stacks

Problem Statement: Implement a Queue data structure in Java using two Stacks, supporting enqueue and dequeue operations.

Purpose: This exercise helps you practice converting between LIFO and FIFO behavior, a common conceptual exercise for understanding how different data structures can simulate one another.

Given Input: Enqueue 1, 2, 3, then dequeue twice.

Expected Output:

Dequeued = 1
Dequeued = 2
▼ Hint
  • Use one stack (inStack) for enqueue operations, pushing new elements directly onto it.
  • Use a second stack (outStack) for dequeue operations.
  • When outStack is empty, pop everything from inStack and push it onto outStack to reverse the order, then pop from outStack.
▼ Solution & Explanation
import java.util.Stack;

class QueueUsingStacks {
    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();

    public void enqueue(int value) {
        inStack.push(value);
    }

    public int dequeue() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        if (outStack.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return outStack.pop();
    }
}

public class Main {
    public static void main(String[] args) {
        QueueUsingStacks queue = new QueueUsingStacks();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println("Dequeued = " + queue.dequeue());
        System.out.println("Dequeued = " + queue.dequeue());
        // Usage:
        // queue.enqueue(1); queue.enqueue(2); queue.enqueue(3);
        // queue.dequeue() returns 1, then 2, preserving FIFO order
    }
}Code language: Java (java)

Explanation:

  • inStack.push(value);: Adds every new element to inStack, which is simple and fast for enqueue.
  • while (!inStack.isEmpty()) outStack.push(inStack.pop());: Reverses the order of elements by moving them from inStack to outStack, which turns LIFO order back into FIFO order.
  • if (outStack.isEmpty()): Only triggers the transfer when outStack has run out of elements, keeping the operation efficient over many calls.
  • Alternative: You could use Java’s built-in LinkedList or ArrayDeque as a queue directly, but implementing it with two stacks demonstrates how FIFO behavior can emerge from LIFO structures.

Exercise 14: Evaluate a Postfix Expression

Problem Statement: Write a Java program to evaluate a given postfix expression, such as "2 3 1 * + 9 -".

Purpose: This exercise helps you practice using a stack to evaluate expressions without needing operator precedence rules or parentheses, the same principle used internally by many calculators and interpreters.

Given Input: String expression = "2 3 1 * + 9 -";

Expected Output: Result = -4

▼ Hint
  • Split the expression into tokens separated by spaces.
  • Push numbers onto a stack as you encounter them.
  • When you encounter an operator, pop the top two numbers, apply the operator, and push the result back onto the stack.
▼ Solution & Explanation
import java.util.Stack;

class PostfixEvaluator {
    public int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split(" ");
        for (String token : tokens) {
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a - b);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

public class Main {
    public static void main(String[] args) {
        PostfixEvaluator postfixEvaluator = new PostfixEvaluator();
        String expression = "2 3 1 * + 9 -";
        System.out.println("Result = " + postfixEvaluator.evaluatePostfix(expression));
        // Usage:
        // evaluatePostfix("2 3 1 * + 9 -") returns -4
    }
}Code language: Java (java)

Explanation:

  • expression.split(" ");: Breaks the postfix expression into individual number and operator tokens.
  • int b = stack.pop(); int a = stack.pop();: Pops the two most recent operands whenever an operator token is found, with b as the second operand and a as the first.
  • stack.push(a + b);: Applies the operator to the two popped operands and pushes the result back for use in later operations.
  • return stack.pop();: After processing every token, the single remaining value on the stack is the final result.
  • Alternative: You could convert the postfix expression to infix first and evaluate that, but postfix evaluation with a stack avoids handling operator precedence and parentheses entirely.

Exercise 15: Implement a Circular Queue Using an Array

Problem Statement: Implement a Circular Queue in Java using an array, supporting enqueue and dequeue operations that wrap around the array bounds.

Purpose: This exercise helps you practice using modular arithmetic to reuse array space efficiently, a pattern used in buffering systems, scheduling, and streaming data pipelines.

Given Input: A circular queue with capacity 5. Enqueue 10, 20, 30, dequeue once, then enqueue 40.

Expected Output: 20, 30, 40

▼ Hint
  • Track a front index, a rear index, and a size counter instead of relying on array length alone.
  • When enqueuing, advance rear using (rear + 1) % capacity so it wraps around to the start of the array.
  • When dequeuing, advance front the same way, and always update size to know when the queue is full or empty.
▼ Solution & Explanation
class CircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void enqueue(int value) {
        if (size == capacity) {
            throw new RuntimeException("Queue is full");
        }
        rear = (rear + 1) % capacity;
        data[rear] = value;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new RuntimeException("Queue is empty");
        }
        int value = data[front];
        front = (front + 1) % capacity;
        size--;
        return value;
    }

    public void display() {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int index = (front + i) % capacity;
            result.append(data[index]);
            if (i < size - 1) {
                result.append(", ");
            }
        }
        System.out.println(result);
    }
}

public class Main {
    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5);
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.dequeue();
        queue.enqueue(40);
        queue.display();
        // Usage:
        // queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.dequeue(); queue.enqueue(40);
        // queue.display() prints 20, 30, 40
    }
}Code language: Java (java)

Explanation:

  • rear = (rear + 1) % capacity;: Advances the rear pointer and wraps it back to index 0 once it reaches the end of the array.
  • front = (front + 1) % capacity;: Advances the front pointer the same way after a dequeue, allowing freed slots near the start of the array to be reused.
  • size: Tracks the current number of elements directly, which avoids the ambiguity of distinguishing a full queue from an empty one using front and rear alone.
  • Alternative: You could leave one slot permanently empty to distinguish full from empty without a size counter, but tracking size directly is more straightforward to reason about.

Exercise 16: Count the Frequency of Each Element or Word

Problem Statement: Write a Java program to count the frequency of each element in a given array, or each word in a given paragraph, using a HashMap.

Purpose: This exercise helps you practice using a HashMap to tally occurrences, a pattern widely used in word counting, analytics, and log analysis.

Given Input: String[] words = {"apple", "banana", "apple", "orange", "banana", "apple"};

Expected Output:

apple = 3
banana = 2
orange = 1
▼ Hint
  • Use a HashMap to store each word alongside its running count.
  • For each word, check whether it already exists in the map using getOrDefault.
  • Increment the stored count by one and put it back into the map.
▼ Solution & Explanation
import java.util.HashMap;
import java.util.Map;

class FrequencyCounter {
    public Map<String, Integer> countFrequency(String[] words) {
        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) {
            frequency.put(word, frequency.getOrDefault(word, 0) + 1);
        }
        return frequency;
    }
}

public class Main {
    public static void main(String[] args) {
        FrequencyCounter frequencyCounter = new FrequencyCounter();
        String[] words = {"apple", "banana", "apple", "orange", "banana", "apple"};
        Map<String, Integer> frequency = frequencyCounter.countFrequency(words);
        for (Map.Entry<String, Integer> entry : frequency.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
        // Usage:
        // countFrequency(new String[]{"apple", "banana", "apple", "orange", "banana", "apple"})
        // returns a map with apple=3, banana=2, orange=1
    }
}Code language: Java (java)

Explanation:

  • Map frequency = new HashMap<>();: Creates a map to associate each unique word with how many times it has appeared.
  • frequency.getOrDefault(word, 0): Returns the current count for the word, or 0 if the word has not been seen yet, avoiding a manual null check.
  • frequency.put(word, ... + 1);: Stores the updated count back into the map for that word.
  • Alternative: You could sort the array first and count consecutive equal elements without a map, but a HashMap handles unsorted input directly in a single pass.

Exercise 17: Find the First Non-Repeating Character in a String

Problem Statement: Write a Java program to find the first non-repeating character in a string using a HashMap.

Purpose: This exercise helps you practice combining a frequency map with an ordered scan, a pattern used in text processing tasks like deduplication and character analysis.

Given Input: String str = "swiss";

Expected Output: First non-repeating character = w

▼ Hint
  • First pass: build a HashMap counting how many times each character appears.
  • Second pass: scan the string in its original order and return the first character whose count in the map is exactly 1.
▼ Solution & Explanation
import java.util.HashMap;
import java.util.Map;

class FirstNonRepeatingCharacterFinder {
    public Character firstNonRepeating(String str) {
        Map<Character, Integer> frequency = new HashMap<>();
        for (char ch : str.toCharArray()) {
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (char ch : str.toCharArray()) {
            if (frequency.get(ch) == 1) {
                return ch;
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        FirstNonRepeatingCharacterFinder firstNonRepeatingCharacterFinder = new FirstNonRepeatingCharacterFinder();
        String str = "swiss";
        System.out.println("First non-repeating character = " + firstNonRepeatingCharacterFinder.firstNonRepeating(str));
        // Usage:
        // firstNonRepeating("swiss") returns 'w'
    }
}Code language: Java (java)

Explanation:

  • First loop: Builds a frequency map of every character in the string in a single pass.
  • Second loop: Re-scans the string in its original order so the first character with a count of 1 is returned, preserving the correct position.
  • frequency.get(ch) == 1: Confirms the character appears exactly once in the entire string.
  • Alternative: You could use a LinkedHashMap to preserve insertion order and avoid the second pass entirely, but two passes over a small string is simple and easy to follow.

Exercise 18: Implement a Basic Custom HashMap from Scratch

Problem Statement: Implement a basic custom HashMap from scratch in Java, supporting put and get operations and handling collisions with chaining.

Purpose: This exercise helps you understand how hash-based lookup structures work internally, including hashing, bucket placement, and collision resolution, which underpins Java’s own HashMap implementation.

Given Input: Put the pairs "one" -> 1, "two" -> 2, and "three" -> 3, then get the value for "two".

Expected Output: Value for 'two' = 2

▼ Hint
  • Use an array of linked lists (buckets) as the underlying storage.
  • Compute a bucket index from the key’s hashCode() using the modulo operator against the array length.
  • When two keys hash to the same bucket, chain them together as a small linked list of entries within that bucket, this is how collisions are handled.
▼ Solution & Explanation
import java.util.LinkedList;

class Entry {
    String key;
    int value;

    Entry(String key, int value) {
        this.key = key;
        this.value = value;
    }
}

class CustomHashMap {
    private LinkedList<Entry>[] buckets;
    private int capacity;

    @SuppressWarnings("unchecked")
    public CustomHashMap(int capacity) {
        this.capacity = capacity;
        buckets = new LinkedList[capacity];
    }

    private int getBucketIndex(String key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(String key, int value) {
        int index = getBucketIndex(key);
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }
        for (Entry entry : buckets[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        buckets[index].add(new Entry(key, value));
    }

    public Integer get(String key) {
        int index = getBucketIndex(key);
        if (buckets[index] == null) {
            return null;
        }
        for (Entry entry : buckets[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        CustomHashMap map = new CustomHashMap(16);
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
        System.out.println("Value for 'two' = " + map.get("two"));
        // Usage:
        // map.put("one", 1); map.put("two", 2); map.put("three", 3);
        // map.get("two") returns 2
    }
}Code language: Java (java)

Explanation:

  • LinkedList[] buckets;: Stores each bucket as a linked list of entries, allowing multiple keys to share the same bucket safely.
  • Math.abs(key.hashCode()) % capacity;: Converts the key’s hash code into a valid bucket index within the array bounds.
  • for (Entry entry : buckets[index]): Walks through the chain in a bucket to check for an existing key before inserting or to find a matching key during lookup.
  • Alternative: You could resolve collisions with open addressing (probing for the next free slot) instead of chaining, but chaining is simpler to implement and reason about for a basic version.

Exercise 19: Intersection of Two Arrays Using a HashSet

Problem Statement: Write a Java program to find the common elements between two arrays using a HashSet.

Purpose: This exercise helps you practice using a HashSet for fast membership checks, a pattern commonly used to compare datasets and filter overlapping values efficiently.

Given Input: int[] arr1 = {1, 2, 3, 4, 5}; int[] arr2 = {3, 4, 5, 6, 7};

Expected Output: [3, 4, 5]

▼ Hint
  • Add all elements of the first array into a HashSet.
  • Loop through the second array and check whether each element already exists in that set.
  • Collect matching elements into a result set to automatically avoid duplicates in the output.
▼ Solution & Explanation
import java.util.HashSet;
import java.util.Set;

class ArrayIntersectionFinder {
    public Set<Integer> findIntersection(int[] arr1, int[] arr2) {
        Set<Integer> firstSet = new HashSet<>();
        for (int num : arr1) {
            firstSet.add(num);
        }
        Set<Integer> result = new HashSet<>();
        for (int num : arr2) {
            if (firstSet.contains(num)) {
                result.add(num);
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayIntersectionFinder arrayIntersectionFinder = new ArrayIntersectionFinder();
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {3, 4, 5, 6, 7};
        System.out.println(arrayIntersectionFinder.findIntersection(arr1, arr2));
        // Usage:
        // findIntersection(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 6, 7})
        // returns a set containing 3, 4, 5
    }
}Code language: Java (java)

Explanation:

  • firstSet.add(num);: Loads every element of the first array into a set, which allows O(1) average-time lookups.
  • firstSet.contains(num): Checks each element of the second array against the set built from the first array to detect common values.
  • result.add(num);: Adds a matching value to the result set, and duplicates are handled automatically since sets do not store repeated values.
  • Alternative: You could sort both arrays and use a two-pointer approach to find the intersection, but a HashSet is simpler to write and works regardless of input order.

Exercise 20: Group Anagrams Together

Problem Statement: Write a Java program to group anagrams together from an array of strings.

Purpose: This exercise helps you practice using a sorted string as a normalized key in a HashMap, a pattern useful whenever items need to be grouped by a shared characteristic rather than an exact value.

Given Input: String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};

Expected Output:

[eat, tea, ate]
[tan, nat]
[bat]
▼ Hint
  • Two words are anagrams of each other only if their letters, when sorted, produce the same string.
  • Sort the characters of each word to create a normalized key.
  • Use a HashMap> to group original words under their shared sorted key.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class AnagramGrouper {
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

public class Main {
    public static void main(String[] args) {
        AnagramGrouper anagramGrouper = new AnagramGrouper();
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> grouped = anagramGrouper.groupAnagrams(words);
        for (List<String> group : grouped) {
            System.out.println(group);
        }
        // Usage:
        // groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"})
        // returns [[eat, tea, ate], [tan, nat], [bat]]
    }
}Code language: Java (java)

Explanation:

  • Arrays.sort(chars);: Sorts the letters of each word so that anagrams produce an identical character sequence.
  • String key = new String(chars);: Converts the sorted characters back into a string to use as the grouping key in the map.
  • groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);: Creates a new list for a key the first time it is seen, then adds the original word to whichever list matches its sorted key.
  • Alternative: You could use a character frequency count as the key instead of a sorted string, which avoids sorting but requires building a consistent string representation of the counts.

Exercise 21: In-order, Pre-order, and Post-order Tree Traversals

Problem Statement: Implement In-order, Pre-order, and Post-order tree traversals recursively for a Binary Tree in Java.

Purpose: This exercise helps you practice recursive traversal patterns on tree structures, the foundation for tasks like expression tree evaluation, tree serialization, and syntax tree processing.

Given Input: A binary tree with root 4, left subtree 2 (children 1 and 3), and right subtree 6 (children 5 and 7).

Expected Output:

In-order = 1 2 3 4 5 6 7
Pre-order = 4 2 1 3 6 5 7
Post-order = 1 3 2 5 7 6 4
▼ Hint
  • In-order visits left, then the node, then right, which produces sorted output for a Binary Search Tree.
  • Pre-order visits the node, then left, then right, which is useful for copying a tree.
  • Post-order visits left, then right, then the node, which is useful for deleting a tree safely.
▼ Solution & Explanation
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class TreeTraverser {
    public void inOrder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        inOrder(node.left, result);
        result.append(node.data).append(" ");
        inOrder(node.right, result);
    }

    public void preOrder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        result.append(node.data).append(" ");
        preOrder(node.left, result);
        preOrder(node.right, result);
    }

    public void postOrder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        postOrder(node.left, result);
        postOrder(node.right, result);
        result.append(node.data).append(" ");
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);

        TreeTraverser treeTraverser = new TreeTraverser();

        StringBuilder inOrderResult = new StringBuilder();
        treeTraverser.inOrder(root, inOrderResult);

        StringBuilder preOrderResult = new StringBuilder();
        treeTraverser.preOrder(root, preOrderResult);

        StringBuilder postOrderResult = new StringBuilder();
        treeTraverser.postOrder(root, postOrderResult);

        System.out.println("In-order = " + inOrderResult.toString().trim());
        System.out.println("Pre-order = " + preOrderResult.toString().trim());
        System.out.println("Post-order = " + postOrderResult.toString().trim());

        // Usage:
        // inOrder(root, new StringBuilder()) visits nodes in the order 1 2 3 4 5 6 7
    }
}Code language: Java (java)

Explanation:

  • inOrder(node.left, ...): Recurses into the left subtree first, so smaller values in a BST are visited before the current node.
  • preOrder: Appends the current node’s value before recursing into either subtree, visiting the node itself first.
  • postOrder: Appends the current node’s value only after both subtrees have been fully visited.
  • Alternative: You could implement each traversal iteratively using an explicit stack, but the recursive versions mirror the tree’s structure directly and are easier to follow.

Exercise 22: Level-order Traversal (Breadth-First Search) Using a Queue

Problem Statement: Implement Level-order traversal of a Binary Tree in Java using a Queue.

Purpose: This exercise helps you practice using a queue to process a tree level by level, the same underlying technique used in shortest-path searches and tree-printing utilities.

Given Input: A binary tree with root 4, left subtree 2 (children 1 and 3), and right subtree 6 (children 5 and 7).

Expected Output: 4 2 6 1 3 5 7

▼ Hint
  • Start by adding the root node to a queue.
  • While the queue is not empty, remove a node, process it, then add its left and right children to the queue if they exist.
  • This naturally processes the tree one level at a time, since children are always added after their parent.
▼ Solution & Explanation
import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class LevelOrderTraverser {
    public void levelOrder(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            System.out.print(current.data + " ");
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);
        LevelOrderTraverser levelOrderTraverser = new LevelOrderTraverser();
        levelOrderTraverser.levelOrder(root);
        // Usage:
        // levelOrder(root) prints 4 2 6 1 3 5 7
    }
}Code language: Java (java)

Explanation:

  • queue.add(root);: Seeds the queue with the root node so the traversal has a starting point.
  • Node current = queue.poll();: Removes and processes the next node in FIFO order, which is what keeps the traversal level by level.
  • queue.add(current.left); queue.add(current.right);: Adds the children of the current node to the back of the queue so they are processed only after the rest of the current level.
  • Alternative: You could track level boundaries by recording the queue size before processing each level, which is useful if you need to group the output by level rather than print it as one flat sequence.

Exercise 23: Find the Maximum Depth of a Binary Tree

Problem Statement: Write a Java program to find the maximum depth, or height, of a Binary Tree.

Purpose: This exercise helps you practice recursive tree measurement, a building block for balancing checks, tree visualization, and complexity analysis of tree-based algorithms.

Given Input: A binary tree with root 4, left subtree 2 (children 1 and 3), and right subtree 6 (children 5 and 7).

Expected Output: Maximum depth = 3

▼ Hint
  • The depth of an empty tree is 0.
  • The depth of any other node is 1 plus the greater of the depths of its left and right subtrees.
  • Solve this recursively by computing the depth of each subtree before combining the results.
▼ Solution & Explanation
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class MaxDepthFinder {
    public int maxDepth(Node node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);

        MaxDepthFinder maxDepthFinder = new MaxDepthFinder();
        System.out.println("Maximum depth = " + maxDepthFinder.maxDepth(root));

        // Usage:
        // maxDepth(root) returns 3
    }
}Code language: Java (java)

Explanation:

  • if (node == null) return 0;: Defines the base case where an empty subtree contributes zero depth.
  • maxDepth(node.left) / maxDepth(node.right): Recursively computes the depth of each subtree independently.
  • Math.max(leftDepth, rightDepth) + 1;: Takes the deeper of the two subtrees and adds one to account for the current node.
  • Alternative: You could compute the depth iteratively using level-order traversal and counting levels, but the recursive version is more concise for this problem.

Exercise 24: Validate a Binary Search Tree

Problem Statement: Write a Java program to validate whether a given Binary Tree is a true Binary Search Tree (BST).

Purpose: This exercise helps you practice enforcing ordering constraints across an entire subtree rather than just between immediate parent and child, a subtlety that is easy to get wrong.

Given Input: A binary tree with root 4, left subtree 2 (children 1 and 3), and right subtree 6 (children 5 and 7).

Expected Output: Is valid BST = true

▼ Hint
  • Checking only that a node’s value is greater than its left child and less than its right child is not enough, since a violation can occur several levels down.
  • Pass down a valid range (a minimum and maximum bound) as you recurse, tightening the range for each subtree.
  • A node is valid only if its value falls strictly within the current allowed range.
▼ Solution & Explanation
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class BSTValidator {
    public boolean isValidBST(Node node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        if ((min != null && node.data <= min) || (max != null && node.data >= max)) {
            return false;
        }
        return isValidBST(node.left, min, node.data) && isValidBST(node.right, node.data, max);
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);
        BSTValidator bstValidator = new BSTValidator();
        System.out.println("Is valid BST = " + bstValidator.isValidBST(root, null, null));
        // Usage:
        // isValidBST(root, null, null) returns true
    }
}Code language: Java (java)

Explanation:

  • Integer min, Integer max: Represents the valid range a node’s value must fall within, starting as unbounded at the root.
  • if ((min != null && node.data <= min) || (max != null && node.data >= max)): Rejects the tree as soon as a node’s value falls outside the range established by its ancestors.
  • isValidBST(node.left, min, node.data): Recurses into the left subtree, tightening the upper bound to the current node’s value.
  • Alternative: You could perform an in-order traversal and check that the resulting sequence is strictly increasing, since a valid BST always produces sorted output that way.

Exercise 25: Find the Lowest Common Ancestor (LCA) of Two Nodes in a BST

Problem Statement: Write a Java program to find the Lowest Common Ancestor of two given nodes in a Binary Search Tree.

Purpose: This exercise helps you practice using the ordering property of a BST to navigate directly toward the answer, instead of searching the whole tree as you would with a general binary tree.

Given Input: A BST with root 4, left subtree 2 (children 1 and 3), and right subtree 6 (children 5 and 7). Find the LCA of 1 and 3.

Expected Output: LCA of 1 and 3 = 2

▼ Hint
  • If both target values are smaller than the current node, the LCA must be in the left subtree.
  • If both target values are larger than the current node, the LCA must be in the right subtree.
  • If neither of the above is true, the current node is the point where the paths to both targets diverge, making it the LCA.
▼ Solution & Explanation
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class LowestCommonAncestorFinder {
    public Node findLCA(Node node, int a, int b) {
        if (node == null) {
            return null;
        }
        if (a < node.data && b < node.data) {
            return findLCA(node.left, a, b);
        }
        if (a > node.data && b > node.data) {
            return findLCA(node.right, a, b);
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);
        LowestCommonAncestorFinder lowestCommonAncestorFinder = new LowestCommonAncestorFinder();
        Node lca = lowestCommonAncestorFinder.findLCA(root, 1, 3);
        System.out.println("LCA of 1 and 3 = " + lca.data);
        // Usage:
        // findLCA(root, 1, 3) returns the node holding value 2
    }
}Code language: Java (java)

Explanation:

  • if (a < node.data && b < node.data): Moves the search into the left subtree only when both targets are smaller than the current node’s value.
  • if (a > node.data && b > node.data): Moves the search into the right subtree only when both targets are larger than the current node’s value.
  • return node;: Returns the current node once the two targets fall on different sides, or one of them equals the current node, marking the split point as the LCA.
  • Alternative: You could store the full path from the root to each target node and compare the paths to find the last common node, but that approach uses extra space compared to navigating directly using BST ordering.

Exercise 26: Find the K-th Largest Element Using a Min-Heap

Problem Statement: Write a Java program to find the K-th largest element in an unsorted array using a Min-Heap (PriorityQueue).

Purpose: This exercise helps you practice using a heap to track the top K elements efficiently without fully sorting the array, a pattern widely used in ranking and top-N problems.

Given Input: int[] numbers = {7, 10, 4, 3, 20, 15}; int k = 3;

Expected Output: 3rd largest element = 10

▼ Hint
  • Use a PriorityQueue, which is a min-heap by default in Java, to hold at most k elements at a time.
  • Add each number to the heap, and if the heap size exceeds k, remove the smallest element.
  • After processing every number, the smallest element remaining in the heap is the k-th largest overall.
▼ Solution & Explanation
import java.util.PriorityQueue;

class KthLargestFinder {
    public int findKthLargest(int[] numbers, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : numbers) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

public class Main {
    public static void main(String[] args) {
        KthLargestFinder kthLargestFinder = new KthLargestFinder();
        int[] numbers = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println("3rd largest element = " + kthLargestFinder.findKthLargest(numbers, k));
        // Usage:
        // findKthLargest(new int[]{7, 10, 4, 3, 20, 15}, 3) returns 10
    }
}Code language: Java (java)

Explanation:

  • PriorityQueue minHeap = new PriorityQueue<>();: Creates a heap that always keeps the smallest element accessible at the top.
  • if (minHeap.size() > k) minHeap.poll();: Removes the smallest element whenever the heap grows past k, ensuring the heap only ever holds the k largest values seen so far.
  • return minHeap.peek();: Returns the smallest of the k largest values, which is exactly the k-th largest element overall.
  • Alternative: You could sort the entire array and read the element at the appropriate index, but that costs O(n log n) time compared to O(n log k) with a bounded heap.

Exercise 27: Merge K Sorted Arrays into One Sorted List Using a Heap

Problem Statement: Write a Java program to merge K sorted arrays into a single sorted list using a Heap.

Purpose: This exercise helps you practice using a heap to always pick the smallest available candidate across multiple sorted sources, the same principle used in external sorting and merging log files from multiple servers.

Given Input: int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};

Expected Output: [1, 1, 2, 3, 4, 4, 5, 6]

▼ Hint
  • Start by placing the first element of every array into a min-heap, along with which array and index it came from.
  • Repeatedly remove the smallest element from the heap, add it to the result, then push the next element from that same array into the heap.
  • Continue until the heap is empty, meaning every array has been fully consumed.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class ArrayEntry {
    int value;
    int arrayIndex;
    int elementIndex;

    ArrayEntry(int value, int arrayIndex, int elementIndex) {
        this.value = value;
        this.arrayIndex = arrayIndex;
        this.elementIndex = elementIndex;
    }
}

class KSortedArraysMerger {
    public List<Integer> mergeKSortedArrays(int[][] arrays) {
        PriorityQueue<ArrayEntry> minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                minHeap.add(new ArrayEntry(arrays[i][0], i, 0));
            }
        }
        while (!minHeap.isEmpty()) {
            ArrayEntry entry = minHeap.poll();
            result.add(entry.value);
            int nextIndex = entry.elementIndex + 1;
            if (nextIndex < arrays[entry.arrayIndex].length) {
                minHeap.add(new ArrayEntry(arrays[entry.arrayIndex][nextIndex], entry.arrayIndex, nextIndex));
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        KSortedArraysMerger kSortedArraysMerger = new KSortedArraysMerger();
        int[][] arrays = {
            {1, 4, 5},
            {1, 3, 4},
            {2, 6}
        };
        System.out.println(kSortedArraysMerger.mergeKSortedArrays(arrays));
        // Usage:
        // mergeKSortedArrays(new int[][]{{1, 4, 5}, {1, 3, 4}, {2, 6}})
        // returns [1, 1, 2, 3, 4, 4, 5, 6]
    }
}Code language: Java (java)

Explanation:

  • ArrayEntry: Wraps a value together with which array it came from and its position within that array, so the correct next element can be pushed later.
  • minHeap.add(new ArrayEntry(arrays[i][0], i, 0));: Seeds the heap with the first element of every array so all sources start competing for the smallest value.
  • minHeap.add(new ArrayEntry(...nextIndex));: After removing the smallest value, pushes the next element from the same array back into the heap to keep that source in the running.
  • Alternative: You could concatenate all arrays into one list and sort it directly, but that costs O(n log n) over all elements combined, while the heap approach costs O(n log k) where k is the number of arrays.

Exercise 28: BFS and DFS for a Graph Using an Adjacency List

Problem Statement: Implement Breadth-First Search (BFS) and Depth-First Search (DFS) in Java for a Graph represented via an Adjacency List.

Purpose: This exercise helps you practice the two fundamental graph traversal strategies, which form the basis for shortest-path algorithms, connectivity checks, and cycle detection.

Given Input: An undirected graph with 5 vertices (0 to 4) and edges 0-1, 0-2, 1-3, 2-3, 3-4. Traverse starting from vertex 0.

Expected Output:

BFS = 0 1 2 3 4
DFS = 0 1 3 2 4
▼ Hint
  • For BFS, use a queue and a visited array, marking a vertex as visited the moment it is added to the queue to avoid processing it twice.
  • For DFS, use recursion (or an explicit stack) and a visited array, exploring as deep as possible along one path before backtracking.
  • Both approaches rely on the adjacency list to look up a vertex’s neighbors quickly.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Graph {
    private int vertices;
    private List<List<Integer>> adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int a, int b) {
        adjacencyList.get(a).add(b);
        adjacencyList.get(b).add(a);
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");
            for (int neighbor : adjacencyList.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        System.out.println();
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        dfsHelper(start, visited);
        System.out.println();
    }

    private void dfsHelper(int current, boolean[] visited) {
        visited[current] = true;
        System.out.print(current + " ");
        for (int neighbor : adjacencyList.get(current)) {
            if (!visited[neighbor]) {
                dfsHelper(neighbor, visited);
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        System.out.print("BFS = ");
        graph.bfs(0);
        System.out.print("DFS = ");
        graph.dfs(0);
        // Usage:
        // graph.bfs(0) prints 0 1 2 3 4
        // graph.dfs(0) prints 0 1 3 2 4
    }
}Code language: Java (java)

Explanation:

  • visited[start] = true; queue.add(start);: Marks the starting vertex as visited immediately so it is never added to the queue a second time.
  • bfs(int start): Processes vertices in the order they were added to the queue, which naturally expands outward one layer at a time.
  • dfsHelper(int current, ...): Recurses into an unvisited neighbor immediately, going as deep as possible before returning to try the next neighbor.
  • Alternative: You could implement DFS iteratively using an explicit Stack instead of recursion, which avoids the risk of a stack overflow on very deep graphs.

Exercise 29: Detect a Cycle in a Directed Graph

Problem Statement: Write a Java program to detect a cycle in a Directed Graph.

Purpose: This exercise helps you practice tracking the current recursion path during a DFS traversal, a technique used in deadlock detection, build dependency validation, and topological sorting.

Given Input: A directed graph with 4 vertices (0 to 3) and edges 0 -> 1, 1 -> 2, 2 -> 0, 2 -> 3.

Expected Output: Cycle detected = true

▼ Hint
  • A plain visited array is not enough for directed graphs, since revisiting an already-finished vertex through a different path is not necessarily a cycle.
  • Keep a second array marking which vertices are in the current recursion stack.
  • If a DFS traversal reaches a vertex that is already in the current recursion stack, a cycle exists.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.List;

class Graph {
    private int vertices;
    private List<List<Integer>> adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int from, int to) {
        adjacencyList.get(from).add(to);
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[vertices];
        boolean[] inRecursionStack = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && hasCycleHelper(i, visited, inRecursionStack)) {
                return true;
            }
        }
        return false;
    }

    private boolean hasCycleHelper(int current, boolean[] visited, boolean[] inRecursionStack) {
        visited[current] = true;
        inRecursionStack[current] = true;
        for (int neighbor : adjacencyList.get(current)) {
            if (!visited[neighbor]) {
                if (hasCycleHelper(neighbor, visited, inRecursionStack)) {
                    return true;
                }
            } else if (inRecursionStack[neighbor]) {
                return true;
            }
        }
        inRecursionStack[current] = false;
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        System.out.println("Cycle detected = " + graph.hasCycle());
        // Usage:
        // graph.addEdge(0, 1); graph.addEdge(1, 2); graph.addEdge(2, 0); graph.addEdge(2, 3);
        // graph.hasCycle() returns true
    }
}Code language: Java (java)

Explanation:

  • boolean[] inRecursionStack: Tracks which vertices are part of the current DFS path, separately from vertices that have simply been visited at some point.
  • else if (inRecursionStack[neighbor]): Detects a cycle when a neighbor is already on the current path, meaning there is a way back to an ancestor of the current vertex.
  • inRecursionStack[current] = false;: Removes the current vertex from the recursion stack once all of its neighbors have been explored, since it is no longer part of the active path.
  • Alternative: You could use Kahn’s algorithm for topological sorting and check whether all vertices can be ordered, since a directed graph with a cycle cannot be fully topologically sorted.

Exercise 30: Implement a Trie (Prefix Tree)

Problem Statement: Implement a Trie (Prefix Tree) in Java with insert, search, and startsWith methods.

Purpose: This exercise helps you practice building a character-based tree structure optimized for prefix lookups, the same structure used in autocomplete systems, spell checkers, and IP routing tables.

Given Input: Insert the words "apple", "app", and "application", then check search("app"), search("appl"), and startsWith("appl").

Expected Output:

search("app") = true
search("appl") = false
startsWith("appl") = true
▼ Hint
  • Each Trie node should hold a map of characters to child nodes, plus a flag marking whether a complete word ends at that node.
  • To insert a word, walk character by character, creating a new child node whenever one does not already exist.
  • search requires the end-of-word flag to be true at the final node, while startsWith only requires that the path exists, regardless of the flag.
▼ Solution & Explanation
import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.children.computeIfAbsent(ch, c -> new TrieNode());
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String str) {
        TrieNode current = root;
        for (char ch : str.toCharArray()) {
            current = current.children.get(ch);
            if (current == null) {
                return null;
            }
        }
        return current;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        System.out.println("search(\"app\") = " + trie.search("app"));
        System.out.println("search(\"appl\") = " + trie.search("appl"));
        System.out.println("startsWith(\"appl\") = " + trie.startsWith("appl"));
        // Usage:
        // trie.insert("apple"); trie.insert("app"); trie.insert("application");
        // trie.search("app") returns true, trie.startsWith("appl") returns true
    }
}Code language: Java (java)

Explanation:

  • children.computeIfAbsent(ch, c -> new TrieNode());: Reuses an existing child node for a character if one is already there, or creates a new one if this is the first word to use that path.
  • current.isEndOfWord = true;: Marks the final node of an inserted word so it can be distinguished from a node that is only a prefix of a longer word.
  • findNode(String str): Shared helper that walks the Trie character by character and returns the node reached, or null if the path breaks early.
  • Alternative: You could use a fixed-size array of 26 children instead of a HashMap when working only with lowercase English letters, which is faster but less flexible for other character sets.

TweetF  sharein  shareP  Pin

About Vishal

I’m Vishal Hule, the Founder of PYnative.com. As a Python developer, I enjoy assisting students, developers, and learners. Follow me on Twitter.

Related Tutorial Topics:

Java Exercises

All Coding Exercises:

C Exercises
C++ Exercises
Python Exercises
Java Exercises

Python Exercises and Quizzes

Free coding exercises and quizzes cover Python basics, data structure, data analytics, and more.

  • 15+ Topic-specific Exercises and Quizzes
  • Each Exercise contains 25+ questions
  • Each Quiz contains 25 MCQ
Exercises
Quizzes

Leave a Reply

your email address will NOT be published. all comments are moderated according to our comment policy.

Use <pre> tag for posting code. E.g. <pre> Your entire code </pre>

About PYnative

PYnative.com is for Python lovers. Here, You can get Tutorials, Exercises, and Quizzes to practice and improve your Python skills.

Follow Us

To get New Python Tutorials, Exercises, and Quizzes

Explore Python

Coding Exercises

Legal Stuff

We use cookies to improve your experience. While using PYnative, you agree to have read and accepted our:

Copyright © 2018–2026 pynative.com