Java Coding Interview Questions and Answers

11 questions

How do you reverse a string in Java without using `StringBuilder.reverse()`?

Swap characters of a char[] from both ends toward the middle: O(n) time, and O(n) space for the copy.

Java

public class Main {
    static String reverse(String s) {
        char[] c = s.toCharArray();
        for (int i = 0, j = c.length - 1; i < j; i++, j--) {
            char tmp = c[i];
            c[i] = c[j];
            c[j] = tmp;
        }
        return new String(c);
    }

    public static void main(String[] args) {
        System.out.println(reverse("interview"));
        System.out.println(reverse("a"));
        System.out.println("[" + reverse("") + "]");
    }
}

It prints weivretni, a and []. new StringBuilder(s).reverse() is shorter and also keeps emoji (surrogate pairs) intact.

Practice it: Reverse a String

Write a Java program to check whether a string is a palindrome, ignoring case and non-letters.

Use two pointers: skip characters that are not letters or digits, compare the rest case-insensitively, and stop when the pointers meet. O(n) time, O(1) space.

Java

public class Main {
    static boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (!Character.isLetterOrDigit(s.charAt(i))) { i++; continue; }
            if (!Character.isLetterOrDigit(s.charAt(j))) { j--; continue; }
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
        System.out.println(isPalindrome("race a car"));
    }
}

It prints true then false.

Practice it: Valid Palindrome

How do you count the occurrences of each character in a string in Java?

Count with merge into a LinkedHashMap<Character, Integer>, which keeps first-seen order.

Java

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String s = "programming";
        Map<Character, Integer> counts = new LinkedHashMap<>();
        for (char c : s.toCharArray()) {
            counts.merge(c, 1, Integer::sum);
        }
        System.out.println(counts);

        for (char c : s.toCharArray()) {
            if (counts.get(c) == 1) {
                System.out.println("first non-repeated: " + c);
                break;
            }
        }
    }
}

It prints {p=1, r=2, o=1, g=2, a=1, m=2, i=1, n=1} and first non-repeated: p. For lowercase letters only, an int[26] is faster.

Practice it: Count a Character, First Unique Character in a String

Write a Java program to check if two strings are anagrams.

Anagrams have the same characters with the same counts. For lowercase letters, count up for one string and down for the other in an int[26], then check for zeros: O(n).

Java

public class Main {
    static boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < a.length(); i++) {
            count[a.charAt(i) - 'a']++;
            count[b.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));
        System.out.println(isAnagram("rat", "car"));
    }
}

It prints true then false. Sorting both is O(n log n); Unicode input needs a HashMap.

Practice it: Valid Anagram, Group Anagrams

Solve Two Sum in Java: find two indices whose values add up to a target.

One pass with a HashMap from value to index: if target - num was already seen, return both indices. O(n) time and space.

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]);
            if (j != null) return new int[] {j, i};
            seen.put(nums[i], i);
        }
        return new int[0];
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[] {2, 7, 11, 15}, 9)));
        System.out.println(Arrays.toString(twoSum(new int[] {3, 2, 4}, 6)));
    }
}

It prints [0, 1] and [1, 2]. Checking before inserting stops an element pairing with itself.

Practice it: Two Sum, Two Sum II: Sorted Input

Find the second largest number in an array in Java.

One O(n) pass tracking the largest and second largest, ignoring repeats of the largest, so [5, 5, 3] gives 3.

Java

public class Main {
    static Integer secondLargest(int[] a) {
        Integer first = null, second = null;
        for (int x : a) {
            if (first == null || x > first) {
                second = first;
                first = x;
            } else if (x < first && (second == null || x > second)) {
                second = x;
            }
        }
        return second;   // null if there is no second distinct value
    }

    public static void main(String[] args) {
        System.out.println(secondLargest(new int[] {12, 35, 1, 10, 34, 1}));
        System.out.println(secondLargest(new int[] {5, 5, 3}));
        System.out.println(secondLargest(new int[] {7, 7}));
    }
}

It prints 34, 3 and null. Starting from Integer.MIN_VALUE instead of null fails when the array contains that value.

Practice it: Second Largest Number

Reverse a singly linked list in Java.

Walk the list once and point each next back at the previous node, keeping prev, curr and the saved next. O(n) time, O(1) space.

Java

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    static Node reverse(Node head) {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;   // save the rest
            curr.next = prev;        // flip the pointer
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        Node head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
        StringBuilder out = new StringBuilder();
        for (Node n = reverse(head); n != null; n = n.next) out.append(n.val).append(' ');
        System.out.println(out.toString().trim());
    }
}

It prints 4 3 2 1. See the linked list visualization.

Practice it: Reverse Linked List

Check whether a string of brackets is balanced in Java.

Push each opener's matching closer on an ArrayDeque; every closing bracket must equal the popped top, and the stack must end empty. O(n) time.

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> stack.push(')');
                case '[' -> stack.push(']');
                case '{' -> stack.push('}');
                default -> {
                    if (stack.isEmpty() || stack.pop() != c) return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("{[()]}") + " " + isValid("([)]") + " " + isValid("(("));
    }
}

It prints true false false.

Practice it: Valid Parentheses

Implement binary search in Java.

Compare the middle of the sorted range with the target and drop the half that cannot hold it: O(log n).

Java

public class Main {
    static int binarySearch(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // avoids int overflow of lo + hi
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};
        System.out.println(binarySearch(a, 23) + " " + binarySearch(a, 7));
    }
}

It prints 5 -1. Use lo + (hi - lo) / 2, because (lo + hi) / 2 can overflow, a bug the JDK's own Arrays.binarySearch had for years. See the binary search visualization.

Practice it: Binary Search, Search in Rotated Sorted Array

Write a Java program to print the Fibonacci series. Why is the naive recursive version slow?

Loop with two variables: O(n) time, O(1) space. Naive recursion recomputes the same values and takes exponential time.

Java

public class Main {
    static long fib(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        return a;
    }

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) sb.append(fib(i)).append(' ');
        System.out.println(sb.toString().trim());
        System.out.println("fib(90) = " + fib(90));
    }
}

It prints 0 1 1 2 3 5 8 13 21 34 and fib(90) = 2880067194370816120. Use long: int overflows after fib(46).

Practice it: Fibonacci Number, Climbing Stairs

Write a Java program to check whether a number is prime.

A number n > 1 is prime if nothing from 2 to √n divides it, because a larger factor pairs with a smaller one. O(√n).

Java

public class Main {
    static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        for (int i = 3; (long) i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        StringBuilder primes = new StringBuilder();
        for (int i = 0; i <= 30; i++) if (isPrime(i)) primes.append(i).append(' ');
        System.out.println(primes.toString().trim());
        System.out.println(isPrime(2147483647));
    }
}

It prints 2 3 5 7 11 13 17 19 23 29 and true; (long) i * i avoids overflow. For all primes up to a limit, use the Sieve of Eratosthenes.

Practice it: Check Prime Number

How do you reverse a string in Java without using StringBuilder.reverse()?

Write a Java program to check whether a string is a palindrome, ignoring case and non-letters.

How do you count the occurrences of each character in a string in Java?

Write a Java program to check if two strings are anagrams.

Solve Two Sum in Java: find two indices whose values add up to a target.

Find the second largest number in an array in Java.

Reverse a singly linked list in Java.

Check whether a string of brackets is balanced in Java.

Implement binary search in Java.

Write a Java program to print the Fibonacci series. Why is the naive recursive version slow?

Write a Java program to check whether a number is prime.

Learn to code with Coddy

How do you reverse a string in Java without using `StringBuilder.reverse()`?