15 Java Algorithms Interview Questions and Answers

Java remains a cornerstone in the world of programming, known for its portability, robustness, and extensive use in enterprise environments. Mastery of Java algorithms is crucial for optimizing performance and solving complex problems efficiently. Understanding these algorithms not only enhances your coding skills but also prepares you for tackling real-world challenges in various domains such as web development, data processing, and system design.

This article offers a curated selection of Java algorithm questions designed to test and improve your problem-solving abilities. By working through these examples, you’ll gain a deeper understanding of algorithmic concepts and be better prepared to demonstrate your expertise in technical interviews.

Java Algorithms Interview Questions and Answers

1. Implement the QuickSort algorithm.

QuickSort is a divide-and-conquer algorithm that sorts an array by selecting a ‘pivot’ element and partitioning the other elements into two sub-arrays based on whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively until the base case of an empty or single-element array is reached.

public class QuickSort {

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;
        quickSort(array, 0, n - 1);
        System.out.println("Sorted array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

2. Write a function to perform binary search on a sorted array.

Binary search efficiently finds an item in a sorted array by repeatedly dividing the search interval in half. If the search key is less than the middle item, the interval is narrowed to the lower half; otherwise, it is narrowed to the upper half.

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;
        int result = binarySearch(sortedArray, target);
        System.out.println("Index of target: " + result);
    }
}

3. Implement a recursive solution to calculate the nth Fibonacci number.

The Fibonacci sequence is a series where each number is the sum of the two preceding ones. A recursive solution calculates the nth Fibonacci number by calling itself with the previous two numbers until reaching the base cases.

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 10; // Example input
        System.out.println(fibonacci(n)); // Output: 55
    }
}

4. Write a function to check if a given string is a palindrome.

A palindrome reads the same backward as forward. To check if a string is a palindrome, compare it with its reverse.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("racecar")); // true
        System.out.println(isPalindrome("hello"));   // false
    }
}

5. Implement the Knapsack problem using dynamic programming.

The Knapsack problem involves selecting items to maximize total value without exceeding a weight limit. Dynamic programming solves this by breaking it down into simpler subproblems and storing results to avoid redundant calculations.

public class Knapsack {
    public static int knapSack(int W, int[] wt, int[] val, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n)); // Output: 220
    }
}

6. Write a function to perform an in-order traversal of a binary tree.

In-order traversal of a binary tree visits nodes in the order: left subtree, root node, and right subtree. This is useful for binary search trees as it visits nodes in ascending order.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTree {
    public void inOrderTraversal(TreeNode root) {
        if (root != null) {
            inOrderTraversal(root.left);
            System.out.print(root.val + " ");
            inOrderTraversal(root.right);
        }
    }
}

7. Implement a function to find the first non-repeating character in a string using a hash table.

To find the first non-repeating character in a string, use a hash table to store the frequency of each character. Then iterate through the string to find the first character with a frequency of one.

import java.util.HashMap;

public class FirstNonRepeatingCharacter {
    public static char findFirstNonRepeatingChar(String str) {
        HashMap<Character, Integer> charCount = new HashMap<>();

        for (char c : str.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        for (char c : str.toCharArray()) {
            if (charCount.get(c) == 1) {
                return c;
            }
        }

        return '\0'; // Return null character if no non-repeating character is found
    }

    public static void main(String[] args) {
        String str = "swiss";
        System.out.println(findFirstNonRepeatingChar(str)); // Output: 'w'
    }
}

8. Implement a solution to the N-Queens problem using backtracking.

The N-Queens problem can be solved using backtracking by placing queens one by one in different columns, starting from the leftmost column. When placing a queen, check for conflicts with already placed queens. If a conflict is found, backtrack and try the next position.

public class NQueens {
    private int size;
    private int[] board;

    public NQueens(int size) {
        this.size = size;
        board = new int[size];
    }

    public boolean solve() {
        return placeQueen(0);
    }

    private boolean placeQueen(int row) {
        if (row == size) {
            return true;
        }
        for (int col = 0; col < size; col++) {
            if (isSafe(row, col)) {
                board[row] = col;
                if (placeQueen(row + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    public void printSolution() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 8;
        NQueens queens = new NQueens(n);
        if (queens.solve()) {
            queens.printSolution();
        } else {
            System.out.println("No solution exists");
        }
    }
}

9. Write a function to find the longest increasing subsequence in an array using dynamic programming.

Dynamic programming helps find the longest increasing subsequence (LIS) in an array by storing results of subproblems to avoid redundant calculations. Maintain an array dp where dp[i] represents the length of the LIS ending with the element at index i.

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int[] dp = new int[nums.length];
    int maxLength = 1;

    for (int i = 0; i < nums.length; i++) {
        dp[i] = 1; // Each element is an increasing subsequence of length 1
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }

    return maxLength;
}

10. Implement a function to find the lowest common ancestor in a binary search tree.

In a binary search tree (BST), the lowest common ancestor (LCA) of two nodes p and q is the lowest node that has both p and q as descendants. Use the properties of BSTs to find the LCA efficiently.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}

11. Write a function to find the maximum flow in a flow network using the Ford-Fulkerson method.

The Ford-Fulkerson method computes the maximum flow in a flow network by finding augmenting paths in the residual graph and increasing the flow along these paths until no more augmenting paths can be found.

import java.util.LinkedList;
import java.util.Queue;

public class FordFulkerson {
    private int V; // Number of vertices in the graph

    public FordFulkerson(int V) {
        this.V = V;
    }

    private boolean bfs(int[][] residualGraph, int s, int t, int[] parent) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        parent[s] = -1;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v = 0; v < V; v++) {
                if (!visited[v] && residualGraph[u][v] > 0) {
                    if (v == t) {
                        parent[v] = u;
                        return true;
                    }
                    queue.add(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }
        return false;
    }

    public int fordFulkerson(int[][] graph, int s, int t) {
        int u, v;
        int[][] residualGraph = new int[V][V];

        for (u = 0; u < V; u++) {
            for (v = 0; v < V; v++) {
                residualGraph[u][v] = graph[u][v];
            }
        }

        int[] parent = new int[V];
        int maxFlow = 0;

        while (bfs(residualGraph, s, t, parent)) {
            int pathFlow = Integer.MAX_VALUE;
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                pathFlow = Math.min(pathFlow, residualGraph[u][v]);
            }

            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                residualGraph[u][v] -= pathFlow;
                residualGraph[v][u] += pathFlow;
            }

            maxFlow += pathFlow;
        }

        return maxFlow;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 16, 13, 0, 0, 0},
            {0, 0, 10, 12, 0, 0},
            {0, 4, 0, 0, 14, 0},
            {0, 0, 9, 0, 0, 20},
            {0, 0, 0, 7, 0, 4},
            {0, 0, 0, 0, 0, 0}
        };
        FordFulkerson ff = new FordFulkerson(6);
        System.out.println("The maximum possible flow is " + ff.fordFulkerson(graph, 0, 5));
    }
}

12. Implement the KMP (Knuth-Morris-Pratt) algorithm for pattern matching in strings.

The Knuth-Morris-Pratt (KMP) algorithm efficiently matches patterns in strings by preprocessing the pattern to create an “lps” (longest prefix which is also suffix) array. This array is used to skip characters in the text while matching, avoiding redundant comparisons.

public class KMPAlgorithm {
    public static void KMPSearch(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        int[] lps = new int[M];
        int j = 0; // index for pat[]

        computeLPSArray(pat, M, lps);

        int i = 0; // index for txt[]
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
                i++;
            }
            if (j == M) {
                System.out.println("Found pattern at index " + (i - j));
                j = lps[j - 1];
            } else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
    }

    public static void computeLPSArray(String pat, int M, int[] lps) {
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String txt = "ABABDABACDABABCABAB";
        String pat = "ABABCABAB";
        KMPSearch(pat, txt);
    }
}

13. Write a function to perform parallel merge sort using Java’s ForkJoin framework.

Parallel merge sort extends traditional merge sort by leveraging multiple processors for efficiency. Java’s ForkJoin framework breaks down tasks into smaller subtasks, which can be executed in parallel.

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelMergeSort extends RecursiveAction {
    private int[] array;
    private int left;
    private int right;

    public ParallelMergeSort(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
        if (right - left < 2) {
            if (array[left] > array[right]) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
            return;
        }

        int mid = (left + right) / 2;
        ParallelMergeSort leftTask = new ParallelMergeSort(array, left, mid);
        ParallelMergeSort rightTask = new ParallelMergeSort(array, mid + 1, right);
        invokeAll(leftTask, rightTask);
        merge(array, left, mid, right);
    }

    private void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        System.arraycopy(temp, 0, array, left, temp.length);
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new ParallelMergeSort(array, 0, array.length - 1));

        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

14. Explain and implement Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal.

Breadth-First Search (BFS) and Depth-First Search (DFS) are algorithms for traversing graph data structures. BFS explores all vertices at the present depth level before moving to the next, using a queue. DFS explores as far as possible along each branch before backtracking, using a stack or recursion.

import java.util.*;

public class GraphTraversal {
    private int V; // Number of vertices
    private LinkedList<Integer> adj[]; // Adjacency List

    GraphTraversal(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }

    public static void main(String args[]) {
        GraphTraversal g = new GraphTraversal(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Breadth First Traversal starting from vertex 2:");
        g.BFS(2);

        System.out.println("\nDepth First Traversal starting from vertex 2:");
        g.DFS(2);
    }
}

15. Implement a dynamic programming solution for sequence alignment problems.

Dynamic programming is used for sequence alignment to find the optimal alignment between two sequences, such as DNA or protein sequences. The Needleman-Wunsch algorithm uses a scoring system to find the optimal alignment by filling in a matrix based on match, mismatch, and gap penalties.

public class SequenceAlignment {
    public static int[][] needlemanWunsch(String seq1, String seq2, int match, int mismatch, int gap) {
        int len1 = seq1.length();
        int len2 = seq2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i * gap;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j * gap;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int scoreDiag = dp[i - 1][j - 1] + (seq1.charAt(i - 1) == seq2.charAt(j - 1) ? match : mismatch);
                int scoreUp = dp[i - 1][j] + gap;
                int scoreLeft = dp[i][j - 1] + gap;
                dp[i][j] = Math.max(scoreDiag, Math.max(scoreUp, scoreLeft));
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        String seq1 = "GATTACA";
        String seq2 = "GCATGCU";
        int match = 1;
        int mismatch = -1;
        int gap = -2;

        int[][] result = needlemanWunsch(seq1, seq2, match, mismatch, gap);
        System.out.println("Optimal alignment score: " + result[seq1.length()][seq2.length()]);
    }
}