35 Java Coding Interview Problems for Freshers with Tested Solutions

import java.util.*;

public class ArrayProblems {
    // 8. Largest and second largest distinct values in a single pass
    static int[] twoLargest(int[] a) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
        for (int n : a) {
            if (n > first) {
                second = first;
                first = n;
            } else if (n > second && n != first) {
                second = n;
            }
        }
        return new int[]{first, second};
    }

    // 9. Two sum: indexes of the two numbers that add up to the target
    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];
    }

    // 10. Remove duplicates from a sorted array in place; returns the new length
    static int removeDuplicatesSorted(int[] a) {
        if (a.length == 0) return 0;
        int write = 1;
        for (int read = 1; read < a.length; read++) {
            if (a[read] != a[write - 1]) a[write++] = a[read];
        }
        return write;
    }

    // 11. Move zeros to the end, keeping the order of the other values
    static void moveZeros(int[] a) {
        int write = 0;
        for (int n : a) {
            if (n != 0) a[write++] = n;
        }
        while (write < a.length) a[write++] = 0;
    }

    // 12. Rotate right by k using three reversals
    static void rotate(int[] a, int k) {
        k %= a.length;
        reverse(a, 0, a.length - 1);
        reverse(a, 0, k - 1);
        reverse(a, k, a.length - 1);
    }

    private static void reverse(int[] a, int from, int to) {
        while (from < to) {
            int temp = a[from];
            a[from++] = a[to];
            a[to--] = temp;
        }
    }

    // 13. The array holds 1..n with one number missing
    static int missingNumber(int[] a) {
        int n = a.length + 1;
        int expected = n * (n + 1) / 2;
        int actual = 0;
        for (int v : a) actual += v;
        return expected - actual;
    }

    // 14. Maximum sum of a contiguous subarray (Kadane's algorithm)
    static int maxSubarraySum(int[] a) {
        int best = a[0], current = a[0];
        for (int i = 1; i < a.length; i++) {
            current = Math.max(a[i], current + a[i]);
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoLargest(new int[]{12, 35, 1, 10, 34, 35})));   // [35, 34]
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));             // [0, 1]

        int[] sorted = {1, 1, 2, 2, 3, 4, 4};
        int length = removeDuplicatesSorted(sorted);
        System.out.println(length + " " + Arrays.toString(Arrays.copyOf(sorted, length)));   // 4 [1, 2, 3, 4]

        int[] zeros = {0, 1, 0, 3, 12};
        moveZeros(zeros);
        System.out.println(Arrays.toString(zeros));                                          // [1, 3, 12, 0, 0]

        int[] rotated = {1, 2, 3, 4, 5, 6, 7};
        rotate(rotated, 3);
        System.out.println(Arrays.toString(rotated));                                        // [5, 6, 7, 1, 2, 3, 4]

        System.out.println(missingNumber(new int[]{1, 2, 4, 5, 6}));                         // 3
        System.out.println(maxSubarraySum(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));        // 6
    }
}

import java.math.BigInteger;

public class NumberProblems {
    // 15. Prime check: only divisors up to the square root matter
    static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 16. Factorial without overflow
    static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) result = result.multiply(BigInteger.valueOf(i));
        return result;
    }

    // 17. The nth Fibonacci number (0, 1, 1, 2, 3, 5, ...)
    static long fibonacci(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        return a;
    }

    // 18. Greatest common divisor and least common multiple
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    // 19. Armstrong number: 153 = 1^3 + 5^3 + 3^3
    static boolean isArmstrong(int n) {
        int digits = String.valueOf(n).length();
        int sum = 0;
        for (int t = n; t > 0; t /= 10) sum += (int) Math.pow(t % 10, digits);
        return sum == n;
    }

    // 20. Reverse the digits of a number, and add them up
    static int reverseNumber(int n) {
        int reversed = 0;
        while (n != 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }

    static int digitSum(int n) {
        int sum = 0;
        for (n = Math.abs(n); n > 0; n /= 10) sum += n % 10;
        return sum;
    }

    // 21. FizzBuzz as one line of text
    static String fizzBuzz(int n) {
        StringBuilder out = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.append(' ');
            out.append(i % 15 == 0 ? "FizzBuzz" : i % 3 == 0 ? "Fizz" : i % 5 == 0 ? "Buzz" : String.valueOf(i));
        }
        return out.toString();
    }

    public static void main(String[] args) {
        System.out.println(isPrime(97));                   // true
        System.out.println(isPrime(100));                  // false
        System.out.println(factorial(20));                 // 2432902008176640000
        System.out.println(factorial(25));                 // 15511210043330985984000000
        System.out.println(fibonacci(10));                 // 55
        System.out.println(fibonacci(90));                 // 2880067194370816120
        System.out.println(gcd(48, 18) + " " + lcm(4, 6)); // 6 12
        System.out.println(isArmstrong(153));              // true
        System.out.println(isArmstrong(154));              // false
        System.out.println(reverseNumber(12345));          // 54321
        System.out.println(digitSum(-9875));               // 29
        System.out.println(fizzBuzz(15));                  // 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz
    }
}

import java.util.*;
import java.util.stream.*;

public class CollectionProblems {
    // 22. Values that appear more than once, in first-seen order
    static List<Integer> findDuplicates(List<Integer> numbers) {
        Set<Integer> seen = new HashSet<>();
        Set<Integer> duplicates = new LinkedHashSet<>();
        for (int n : numbers) {
            if (!seen.add(n)) duplicates.add(n);
        }
        return new ArrayList<>(duplicates);
    }

    // 23. Word frequency, ignoring case, sorted by word
    static Map<String, Integer> wordFrequency(String text) {
        Map<String, Integer> frequency = new TreeMap<>();
        for (String word : text.toLowerCase().split("\\W+")) {
            if (!word.isEmpty()) frequency.merge(word, 1, Integer::sum);
        }
        return frequency;
    }

    // 24. Entries sorted by value (highest first), ties broken by key
    static List<Map.Entry<String, Integer>> sortByValueDesc(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(map.entrySet());
        entries.sort(Map.Entry.<String, Integer>comparingByValue().reversed()
                .thenComparing(Map.Entry.comparingByKey()));
        return entries;
    }

    // 25. Merge two sorted lists into one sorted list
    static List<Integer> mergeSorted(List<Integer> a, List<Integer> b) {
        List<Integer> merged = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            merged.add(a.get(i) <= b.get(j) ? a.get(i++) : b.get(j++));
        }
        while (i < a.size()) merged.add(a.get(i++));
        while (j < b.size()) merged.add(b.get(j++));
        return merged;
    }

    // 26. Distinct values present in both arrays, sorted
    static List<Integer> intersection(int[] a, int[] b) {
        Set<Integer> inA = Arrays.stream(a).boxed().collect(Collectors.toSet());
        return Arrays.stream(b).boxed().filter(inA::contains).distinct().sorted().toList();
    }

    public static void main(String[] args) {
        System.out.println(findDuplicates(List.of(4, 2, 4, 7, 2, 9, 4)));                       // [4, 2]

        Map<String, Integer> frequency = wordFrequency("the cat and The dog and THE bird");
        System.out.println(frequency);                                                          // {and=2, bird=1, cat=1, dog=1, the=3}
        System.out.println(sortByValueDesc(frequency));                                         // [the=3, and=2, bird=1, cat=1, dog=1]

        System.out.println(mergeSorted(List.of(1, 4, 9), List.of(2, 3, 10, 11)));               // [1, 2, 3, 4, 9, 10, 11]
        System.out.println(intersection(new int[]{4, 9, 5, 9}, new int[]{9, 4, 9, 8, 4}));      // [4, 9]
    }
}

import java.util.*;

public class RecursionProblems {
    // 27. Binary search on a sorted array: index of the target, or -1
    static int binarySearch(int[] sorted, int target) {
        int low = 0, high = sorted.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;               // avoids overflow of (low + high)
            if (sorted[mid] == target) return mid;
            if (sorted[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    // 28. x to the power n by repeated squaring (n may be negative)
    static double power(double x, long n) {
        if (n < 0) return 1 / power(x, -n);
        if (n == 0) return 1;
        double half = power(x, n / 2);
        return n % 2 == 0 ? half * half : half * half * x;
    }

    // 29. All permutations of a string
    static List<String> permutations(String s) {
        if (s.length() <= 1) return List.of(s);
        List<String> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            String rest = s.substring(0, i) + s.substring(i + 1);
            for (String p : permutations(rest)) result.add(s.charAt(i) + p);
        }
        return result;
    }

    // 30. Tower of Hanoi: record each move
    static void hanoi(int disks, char from, char to, char via, List<String> moves) {
        if (disks == 0) return;
        hanoi(disks - 1, from, via, to, moves);
        moves.add(from + "->" + to);
        hanoi(disks - 1, via, to, from, moves);
    }

    public static void main(String[] args) {
        int[] sorted = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println(binarySearch(sorted, 23));                 // 5
        System.out.println(binarySearch(sorted, 7));                  // -1
        System.out.println(power(2, 10));                             // 1024.0
        System.out.println(power(2, -2));                             // 0.25
        System.out.println(permutations("abc"));                      // [abc, acb, bac, bca, cab, cba]

        List<String> moves = new ArrayList<>();
        hanoi(3, 'A', 'C', 'B', moves);
        System.out.println(moves.size() + " " + moves);               // 7 [A->C, A->B, C->B, A->C, B->A, B->C, A->C]
    }
}

import java.util.*;

public class StructureProblems {
    static class Node {
        int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    // 31. Reverse a singly linked list
    static Node reverse(Node head) {
        Node previous = null;
        while (head != null) {
            Node next = head.next;
            head.next = previous;
            previous = head;
            head = next;
        }
        return previous;
    }

    static String show(Node head) {
        StringJoiner joiner = new StringJoiner(" -> ");
        for (Node n = head; n != null; n = n.next) joiner.add(String.valueOf(n.value));
        return joiner.toString();
    }

    // 32. Cycle detection (Floyd)
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    // 33. Balanced brackets
    static boolean isBalanced(String s) {
        Map<Character, Character> openerOf = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (openerOf.containsValue(c)) {
                stack.push(c);
            } else if (openerOf.containsKey(c)) {
                char expected = openerOf.get(c);
                if (stack.isEmpty() || stack.pop() != expected) return false;
            }
        }
        return stack.isEmpty();
    }

    // 34. A queue built from two stacks
    static class QueueWithStacks<T> {
        private final Deque<T> in = new ArrayDeque<>();
        private final Deque<T> out = new ArrayDeque<>();

        void enqueue(T item) {
            in.push(item);
        }

        T dequeue() {
            if (out.isEmpty()) {
                while (!in.isEmpty()) out.push(in.pop());      // reverses the order once
            }
            if (out.isEmpty()) throw new NoSuchElementException("queue is empty");
            return out.pop();
        }
    }

    // 35. Binary tree: height and in-order traversal
    record TreeNode(int value, TreeNode left, TreeNode right) { }

    static int height(TreeNode node) {
        return node == null ? 0 : 1 + Math.max(height(node.left()), height(node.right()));
    }

    static void inOrder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inOrder(node.left(), out);
        out.add(node.value());
        inOrder(node.right(), out);
    }

    public static void main(String[] args) {
        Node list = new Node(1, new Node(2, new Node(3, new Node(4, null))));
        System.out.println(show(list));                          // 1 -> 2 -> 3 -> 4
        list = reverse(list);
        System.out.println(show(list));                          // 4 -> 3 -> 2 -> 1
        System.out.println(hasCycle(list));                      // false

        Node tail = list;
        while (tail.next != null) tail = tail.next;
        tail.next = list.next;                                   // link the last node back to the second
        System.out.println(hasCycle(list));                      // true

        System.out.println(isBalanced("{[()]}"));                // true
        System.out.println(isBalanced("([)]"));                  // false
        System.out.println(isBalanced("(("));                    // false

        QueueWithStacks<Integer> queue = new QueueWithStacks<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        int first = queue.dequeue();
        queue.enqueue(4);
        System.out.println(first + " " + queue.dequeue() + " " + queue.dequeue() + " " + queue.dequeue());   // 1 2 3 4

        TreeNode tree = new TreeNode(4,
                new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
                new TreeNode(6, new TreeNode(5, null, null), null));
        List<Integer> visited = new ArrayList<>();
        inOrder(tree, visited);
        System.out.println(height(tree));                        // 3
        System.out.println(visited);                             // [1, 2, 3, 4, 5, 6]
    }
}