Tech TribersTop 50 Java Programs Asked in Interviews (With Output and Complexity)
50 Java coding interview programs on strings, numbers, arrays, collections, linked lists and threads, each run on JDK 25 with real output, complexity and a follow-up.
New44 min read
These are the Java programs asked in interviews most often, from fresher campus drives to experienced-hire coding rounds: 50 of them, grouped by topic, each with a clean solution, the real output, its time and space complexity, and the follow-up question an interviewer is likely to ask next.
Every program on this page is a complete class that compiles and runs. We ran all 50 on JDK 25 and pasted the actual output, so you can trust what you see. The code uses plain, modern Java (records, var, streams where they help) and works on Java 17 or later. For the ten problems that come up most, you also get the brute-force version first and the optimal version second, because "start simple, then improve" is exactly what interviewers want to watch you do.
Use it two ways: read a section the night before an interview, or, better, close the page, try each problem yourself for ten minutes, then compare.
In this guide
- How to use these programs (and run them in one command)
- String programs (1-12): palindrome, anagram, first unique character, longest substring
- Number programs (13-23): Fibonacci series, prime, factorial, Armstrong, GCD
- Array programs (24-35): two sum, missing number, Kadane, rotation, binary search
- Collections and Streams programs (36-41)
- Linked list, stack and recursion programs (42-47)
- OOP and multithreading programs (48-50)
- How to answer a coding question in the interview
- FAQ
How to use these programs
Save any program as a file named after its class, for example PalindromeString.java, and run it directly. Since Java 11 you do not need to call javac first for a single file:
java PalindromeString.javaEach solution keeps the logic in a small static method and uses main only to print a few test cases. That is also the shape to aim for in an interview: a method with a clear signature, then a couple of calls that prove it works, including an edge case.
On Java 25 you could drop the class wrapper entirely, because JEP 512 made compact source files and instance main methods final. We kept the classic form here because online judges and many company laptops still run Java 17 or 21.
A note on the complexity lines: n is the length of the input string, array or list unless stated otherwise. "Space" means extra space beyond the input.
String programs
String questions dominate fresher interviews because they test loops, indexes and the String API in a few lines. Know that Java strings are immutable, so building a result in a loop should use StringBuilder, not +=.
1. How do you reverse a string in Java without using reverse()?
Convert the string to a char[], swap characters from both ends moving inward, and build a new string. In real code, new StringBuilder(s).reverse() is the one-liner, and it is fine to mention it after you show the manual version. It also keeps surrogate pairs (emoji and other characters outside the Basic Multilingual Plane) in the right order, which the manual char swap does not.
public class ReverseString {
static String reverse(String s) {
char[] c = s.toCharArray();
for (int i = 0, j = c.length - 1; i < j; i++, j--) {
char t = c[i]; c[i] = c[j]; c[j] = t;
}
return new String(c);
}
public static void main(String[] args) {
System.out.println(reverse("TechTriber"));
System.out.println(new StringBuilder("TechTriber").reverse());
}
}Output:
rebirThceT
rebirThceTComplexity: O(n) time, O(n) space for the char array. Follow-up: "Reverse it recursively." The recursive version is O(n²) with naive substring concatenation, which is a good point to raise.
2. How do you check if a string is a palindrome in Java?
A palindrome reads the same forwards and backwards. The brute-force way builds a reversed copy and compares. The optimal way uses two pointers from both ends, skipping punctuation, and needs no extra string at all. This is the same problem as Valid Palindrome on LeetCode.
public class PalindromeString {
// Brute force: build the reversed string, then compare. O(n) time, O(n) extra space
static boolean isPalindromeBrute(String s) {
String clean = s.toLowerCase().replaceAll("[^a-z0-9]", "");
return clean.equals(new StringBuilder(clean).reverse().toString());
}
// Optimal: two pointers that skip non-alphanumerics. O(n) time, O(1) extra space
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(isPalindromeBrute("Madam"));
System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
System.out.println(isPalindrome("race a car"));
}
}Output:
true
true
falseBrute force vs optimal: both are O(n) time, but the brute force allocates a cleaned copy and a reversed copy (O(n) space), while two pointers use O(1) extra space. Follow-up: "Can you make it a palindrome by deleting at most one character?" Use the same two pointers; on the first mismatch, try skipping either side once.
3. How do you check if two strings are anagrams?
Two strings are anagrams if they contain the same characters with the same counts. Sorting both and comparing is the simple answer. Counting letters in a 26-slot array is the optimal one.
import java.util.Arrays;
public class Anagram {
// Brute force: sort both and compare. O(n log n)
static boolean isAnagramSort(String a, String b) {
char[] x = a.toCharArray(), y = b.toCharArray();
Arrays.sort(x);
Arrays.sort(y);
return Arrays.equals(x, y);
}
// Optimal: count letters. O(n) time, O(1) space (26 counters)
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(isAnagramSort("listen", "silent"));
System.out.println(isAnagram("listen", "silent"));
System.out.println(isAnagram("rat", "car"));
}
}Output:
true
true
falseBrute force vs optimal: sorting is O(n log n); counting is O(n) time and O(1) space, because the array size is fixed at 26. Follow-up: "What about Unicode or uppercase?" Normalize the case and use a HashMap<Character, Integer> instead of the fixed array.
4. How do you count vowels and consonants in a string?
Lowercase the string, skip anything that is not a letter, then check each letter against "aeiou". Forgetting to skip digits and spaces is the common bug: they are not consonants.
public class VowelsConsonants {
public static void main(String[] args) {
String s = "Java Interview 2026";
int vowels = 0, consonants = 0;
for (char c : s.toLowerCase().toCharArray()) {
if (c < 'a' || c > 'z') continue; // skip digits, spaces, symbols
if ("aeiou".indexOf(c) >= 0) vowels++; else consonants++;
}
System.out.println("vowels=" + vowels + ", consonants=" + consonants);
}
}Output:
vowels=6, consonants=7Complexity: O(n) time, O(1) space. Follow-up: "Do it with streams." s.chars().filter(...).count() works, but the loop is clearer for two counters.
5. How do you find the first non-repeated character in a string?
Count every character, then return the first one whose count is 1. A LinkedHashMap keeps insertion order, so the second loop finds the first unique character directly.
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonRepeated {
// Brute force: for each char, scan the whole string. O(n^2)
static Character brute(String s) {
for (int i = 0; i < s.length(); i++) {
if (s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i))) return s.charAt(i);
}
return null;
}
// Optimal: count once, then find the first count of 1. O(n)
static Character firstUnique(String s) {
Map<Character, Integer> count = new LinkedHashMap<>();
for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
for (var e : count.entrySet()) if (e.getValue() == 1) return e.getKey();
return null;
}
public static void main(String[] args) {
System.out.println(brute("swiss"));
System.out.println(firstUnique("swiss"));
System.out.println(firstUnique("aabb"));
}
}Output:
w
w
nullBrute force vs optimal: the indexOf / lastIndexOf trick looks short but scans the string for every character, so it is O(n²). Counting first is O(n) time and O(k) space for k distinct characters. Follow-up: "The input is a stream of characters; return the first unique one at any moment." Keep the counts plus a queue of candidates and pop from the front while the front repeats.
6. How do you count the frequency of each character?
Loop over the characters and call map.merge(c, 1, Integer::sum), which inserts 1 or adds 1 in one call. The stream version uses groupingBy with counting(). A TreeMap sorts the output so it is easy to read.
import java.util.Map;
import java.util.TreeMap;
import java.util.function.Function;
import java.util.stream.Collectors;
public class CharFrequency {
public static void main(String[] args) {
String s = "programming";
Map<Character, Integer> freq = new TreeMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
System.out.println(freq);
Map<Character, Long> viaStream = s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(Function.identity(), TreeMap::new, Collectors.counting()));
System.out.println(viaStream);
}
}Output:
{a=1, g=2, i=1, m=2, n=1, o=1, p=1, r=2}
{a=1, g=2, i=1, m=2, n=1, o=1, p=1, r=2}Complexity: O(n log k) with a TreeMap, O(n) with a HashMap. Follow-up: "Print the most frequent character." Track the maximum while counting, as in program 37.
7. How do you remove duplicate characters from a string?
Walk the string once and keep only the first occurrence of each character, using a boolean[] (or a Set) to remember what you have seen. chars().distinct() does the same in one line and keeps the order.
public class RemoveDuplicateChars {
static String removeDuplicates(String s) {
boolean[] seen = new boolean[Character.MAX_VALUE + 1];
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (!seen[c]) { seen[c] = true; sb.append(c); }
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(removeDuplicates("programming"));
System.out.println("banana".chars().distinct()
.collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append));
}
}Output:
progamin
banComplexity: O(n) time. Follow-up: "Remove characters that appear more than once entirely" (so "banana" becomes "b"). Count first, then keep characters with a count of 1.
8. How do you reverse the words in a sentence?
Trim, split on one or more spaces with "\\s+", reverse the list and join with single spaces. Splitting on a single space is the classic bug: extra spaces produce empty words.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class ReverseWords {
public static void main(String[] args) {
String s = " Java is fun ";
List<String> words = Arrays.asList(s.trim().split("\\s+"));
Collections.reverse(words);
System.out.println("[" + String.join(" ", words) + "]");
}
}Output:
[fun is Java]Complexity: O(n) time and space. Follow-up: "Do it in place on a char array." Reverse the whole array, then reverse each word.
9. How do you check if one string is a rotation of another?
If b is a rotation of a, then b appears inside a + a. Check the lengths first, otherwise "ab" would wrongly count as a rotation of "abab".
public class Rotation {
static boolean isRotation(String a, String b) {
return a.length() == b.length() && (a + a).contains(b);
}
public static void main(String[] args) {
System.out.println(isRotation("waterbottle", "erbottlewat"));
System.out.println(isRotation("abcd", "acbd"));
}
}Output:
true
falseComplexity: O(n) space for the doubled string; contains is typically fast but its worst case depends on the JDK's search implementation. Follow-up: "Guarantee linear time." Use KMP string matching on a + a.
10. How do you find the longest substring without repeating characters?
Use a sliding window. Move right one character at a time; if that character was already seen inside the window, jump left just past its previous position. Track the best window length. This is LeetCode problem 3 and a very common medium-level interview problem.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class LongestUniqueSubstring {
// Brute force: try every start, extend until a repeat. O(n^2)
static int brute(String s) {
int best = 0;
for (int i = 0; i < s.length(); i++) {
Set<Character> seen = new HashSet<>();
for (int j = i; j < s.length() && seen.add(s.charAt(j)); j++) {
best = Math.max(best, j - i + 1);
}
}
return best;
}
// Optimal: sliding window, remember the last index of each char. O(n)
static int longest(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last[c] >= left) left = last[c] + 1; // jump past the repeat
last[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(brute("abcabcbb"));
System.out.println(longest("abcabcbb"));
System.out.println(longest("pwwkew"));
}
}Output:
3
3
3Brute force vs optimal: trying every start position is O(n²) (and O(n³) if you re-check each substring from scratch). The window visits each character once: O(n) time, O(1) space for a fixed 128-slot ASCII table. Follow-up: "Return the substring itself, not the length." Record left whenever you update best.
11. How do you compress a string like aabcccccaaa?
Walk runs of equal characters and append the character plus the run length. If the result is not shorter than the input, return the original.
public class CompressString {
static String compress(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
sb.append(s.charAt(i)).append(j - i);
i = j;
}
return sb.length() < s.length() ? sb.toString() : s;
}
public static void main(String[] args) {
System.out.println(compress("aabcccccaaa"));
System.out.println(compress("abc"));
}
}Output:
a2b1c5a3
abcComplexity: O(n) time. Follow-up: "Decompress it again." Parse a character, then read digits until the next letter, because counts can have more than one digit.
12. How do you count the occurrences of each word in a sentence?
Split on whitespace and group the words with a counting collector. This is a favorite "Java 8 streams" warm-up.
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;
public class WordCount {
public static void main(String[] args) {
String text = "the cat and the hat and the bat";
Map<String, Long> counts = Arrays.stream(text.split("\\s+"))
.collect(Collectors.groupingBy(w -> w, TreeMap::new, Collectors.counting()));
System.out.println(counts);
}
}Output:
{and=2, bat=1, cat=1, hat=1, the=3}Complexity: O(n) to split, plus O(w log w) for the sorted TreeMap of w distinct words. Follow-up: "Ignore case and punctuation." Lowercase first and split on "\\W+".
Number programs
Number programs test arithmetic edge cases: overflow, negatives, zero and one. Say these edge cases out loud before you code. It is the cheapest way to look senior.
13. How do you print the Fibonacci series in Java?
Keep the last two numbers and add them to get the next. Use long: fib(47) is already too big for an int.
public class FibonacciSeries {
public static void main(String[] args) {
int n = 10;
long a = 0, b = 1;
StringBuilder out = new StringBuilder();
for (int i = 0; i < n; i++) {
out.append(a).append(i < n - 1 ? " " : "");
long next = a + b;
a = b;
b = next;
}
System.out.println(out);
}
}Output:
0 1 1 2 3 5 8 13 21 34Complexity: O(n) time, O(1) space. Follow-up: "Print it with recursion." See the next program for why that is a trap.
14. How do you find the nth Fibonacci number? Recursion vs memoization vs iteration
Plain recursion follows the definition but recomputes the same values exponentially many times. Memoization caches each result, and iteration keeps just two variables. Interviewers often ask for all three to see if you can explain the cost of each.
import java.util.HashMap;
import java.util.Map;
public class NthFibonacci {
static long calls = 0;
// Brute force: plain recursion. O(2^n) time
static long fibRec(int n) {
calls++;
return n < 2 ? n : fibRec(n - 1) + fibRec(n - 2);
}
// Memoised: each n computed once. O(n) time, O(n) space
static long fibMemo(int n, Map<Integer, Long> memo) {
if (n < 2) return n;
Long cached = memo.get(n);
if (cached != null) return cached;
long v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.put(n, v);
return v;
}
// Iterative: O(n) time, O(1) space
static long fibIter(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
return a;
}
public static void main(String[] args) {
System.out.println("recursive fib(30) = " + fibRec(30) + " after " + calls + " calls");
System.out.println("memoised fib(50) = " + fibMemo(50, new HashMap<>()));
System.out.println("iterative fib(90) = " + fibIter(90));
}
}Output:
recursive fib(30) = 832040 after 2692537 calls
memoised fib(50) = 12586269025
iterative fib(90) = 2880067194370816120Look at the first line of output: 2,692,537 method calls to compute one number. That is the exponential cost made visible.
Brute force vs optimal: recursion is O(2ⁿ) time (more precisely about O(1.618ⁿ)) and O(n) stack. Memoization is O(n) time and O(n) space. Iteration is O(n) time and O(1) space. Follow-up: "Faster than O(n)?" Matrix exponentiation computes fib(n) in O(log n) multiplications. Also, fib(93) overflows long, so switch to BigInteger beyond fib(92).
15. How do you find the factorial of a number?
Multiply 2 through n in a loop. The real test is overflow: 20! is the largest factorial that fits in a long. Use Math.multiplyExact to fail loudly, or BigInteger for large inputs.
import java.math.BigInteger;
public class Factorial {
static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) result = Math.multiplyExact(result, i); // throws on overflow
return result;
}
static BigInteger bigFactorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) result = result.multiply(BigInteger.valueOf(i));
return result;
}
public static void main(String[] args) {
System.out.println(factorial(5));
System.out.println(factorial(20));
System.out.println(bigFactorial(25));
try {
factorial(21);
} catch (ArithmeticException e) {
System.out.println("21! overflows long: " + e.getMessage());
}
}
}Output:
120
2432902008176640000
15511210043330985984000000
21! overflows long: long overflowComplexity: O(n) multiplications. Follow-up: "Write it recursively and tell me the risk." A deep recursion can throw StackOverflowError, and Java does not optimize tail calls.
16. How do you check if a number is prime in Java?
A number n > 1 is prime if no number from 2 up to the square root of n divides it. After handling 2, you only need to test odd divisors.
public class PrimeCheck {
// Brute force: try every divisor below n. O(n)
static boolean isPrimeBrute(int n) {
if (n < 2) return false;
for (int d = 2; d < n; d++) if (n % d == 0) return false;
return true;
}
// Optimal: only odd divisors up to sqrt(n). O(sqrt n)
static boolean isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
for (int d = 3; (long) d * d <= n; d += 2) if (n % d == 0) return false;
return true;
}
public static void main(String[] args) {
System.out.println(isPrimeBrute(97));
System.out.println(isPrime(97) + " " + isPrime(1) + " " + isPrime(2) + " " + isPrime(91));
System.out.println(isPrime(2_147_483_647)); // largest int, a prime
}
}Output:
true
true false true false
trueBrute force vs optimal: testing every divisor below n is O(n). Stopping at √n is O(√n), and skipping even divisors halves the work again. The (long) d * d cast prevents overflow near Integer.MAX_VALUE, which, as the last line shows, is itself prime. Follow-up: "Is 1 prime?" No, and neither are 0 or negative numbers.
17. How do you print all prime numbers up to N?
Use the Sieve of Eratosthenes: for each prime, mark its multiples as composite, starting from its square. What is left unmarked is prime.
import java.util.ArrayList;
import java.util.List;
public class Sieve {
static List<Integer> primesUpTo(int n) {
boolean[] composite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (composite[i]) continue;
primes.add(i);
for (long j = (long) i * i; j <= n; j += i) composite[(int) j] = true;
}
return primes;
}
public static void main(String[] args) {
System.out.println(primesUpTo(50));
}
}Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]Complexity: O(n log log n) time, O(n) space. Follow-up: "Why start crossing off at i * i?" Smaller multiples of i were already crossed off by smaller primes.
18. How do you check if a number is a palindrome?
Reverse the digits with % 10 and / 10, then compare with the original. Negative numbers are not palindromes because of the minus sign.
public class PalindromeNumber {
static boolean isPalindrome(int x) {
if (x < 0) return false;
int original = x, reversed = 0;
while (x > 0) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return original == reversed;
}
public static void main(String[] args) {
System.out.println(isPalindrome(12321) + " " + isPalindrome(1231) + " " + isPalindrome(-121));
}
}Output:
true false falseComplexity: O(d) for d digits. Follow-up: "Avoid overflow when reversing." Reverse only half the digits and compare the halves.
19. How do you check for an Armstrong number?
An Armstrong number equals the sum of its digits, each raised to the power of the number of digits. 153 = 1³ + 5³ + 3³.
import java.util.stream.IntStream;
public class Armstrong {
static boolean isArmstrong(int n) {
String digits = String.valueOf(n);
int power = digits.length();
int sum = 0;
for (char c : digits.toCharArray()) sum += (int) Math.pow(c - '0', power);
return sum == n;
}
public static void main(String[] args) {
System.out.println(isArmstrong(153) + " " + isArmstrong(9474) + " " + isArmstrong(123));
System.out.println(IntStream.rangeClosed(1, 1000).filter(Armstrong::isArmstrong).boxed().toList());
}
}Output:
true true false
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]Complexity: O(d) per number. Follow-up: "Avoid Math.pow." Multiply in a small loop to stay in integer arithmetic.
20. How do you swap two numbers without a third variable?
Use addition and subtraction, or XOR. Mention that the arithmetic version can overflow for large values (it still works in Java because int wraps around, but it is confusing), and that XOR has no overflow.
public class SwapNoTemp {
public static void main(String[] args) {
int a = 10, b = 20;
a = a + b; // 30
b = a - b; // 10
a = a - b; // 20
System.out.println("a=" + a + ", b=" + b);
int x = 7, y = 3;
x ^= y; y ^= x; x ^= y; // XOR swap, no overflow
System.out.println("x=" + x + ", y=" + y);
}
}Output:
a=20, b=10
x=3, y=7Complexity: O(1). Follow-up: "Does XOR swap work if both variables are the same memory location?" For array elements a[i] ^= a[j] with i equal to j, it zeroes the value. In real code just use a temp variable.
21. How do you find the GCD and LCM of two numbers?
Euclid's algorithm: replace (a, b) with (b, a % b) until b is 0; then a is the GCD. LCM is a / gcd × b, dividing first to reduce overflow risk.
public class GcdLcm {
static int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return Math.abs(a);
}
static long lcm(int a, int b) {
return Math.abs((long) a / gcd(a, b) * b);
}
public static void main(String[] args) {
System.out.println("gcd(48, 18) = " + gcd(48, 18));
System.out.println("lcm(4, 6) = " + lcm(4, 6));
}
}Output:
gcd(48, 18) = 6
lcm(4, 6) = 12Complexity: O(log min(a, b)). Follow-up: "GCD of an array?" Fold it: gcd(gcd(a0, a1), a2) and so on.
22. How do you reverse an integer and handle overflow?
Pop digits with % 10 and push them onto the result with * 10. Reversing 1,534,236,469 gives a number larger than Integer.MAX_VALUE, so use Math.multiplyExact and Math.addExact and return 0 on overflow, which is the usual contract for this question.
public class ReverseInteger {
static int reverse(int x) {
int result = 0;
while (x != 0) {
try {
result = Math.addExact(Math.multiplyExact(result, 10), x % 10);
} catch (ArithmeticException overflow) {
return 0; // the usual interview contract: return 0 on overflow
}
x /= 10;
}
return result;
}
public static void main(String[] args) {
System.out.println(reverse(12345) + " " + reverse(-120) + " " + reverse(1_534_236_469));
}
}Output:
54321 -21 0Complexity: O(d). Follow-up: "Without the Exact methods?" Before multiplying, check result > Integer.MAX_VALUE / 10 (and the negative equivalent).
23. How do you print a star pyramid pattern?
Row i has (rows - i) leading spaces and (2i - 1) stars. String.repeat (Java 11+) removes the inner loops.
public class Pyramid {
public static void main(String[] args) {
int rows = 5;
for (int i = 1; i <= rows; i++) {
System.out.println(" ".repeat(rows - i) + "*".repeat(2 * i - 1));
}
}
}Output:
*
***
*****
*******
*********Complexity: O(rows²) characters printed. Follow-up: "Print a diamond." Print the pyramid, then the same rows in reverse without the middle row.
Array programs
Array problems are where interviewers check whether you can move from O(n²) to O(n). The tools are almost always the same: a hash set or map, two pointers, a running sum, or sorting.
24. How do you find the largest and second largest element in an array?
One pass with two variables. When a new maximum appears, the old maximum becomes the second. Skip values equal to the maximum so duplicates of the max do not become the "second largest".
public class LargestTwo {
public static void main(String[] args) {
int[] a = {12, 35, 1, 10, 34, 35};
int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
for (int x : a) {
if (x > first) { second = first; first = x; }
else if (x > second && x != first) second = x; // skip duplicates of the max
}
System.out.println("largest=" + first + ", second=" + second);
}
}Output:
largest=35, second=34Complexity: O(n) time, O(1) space. Sorting would be O(n log n). Follow-up: "What if all elements are equal?" Then there is no second largest; return an empty OptionalInt or throw, and say which you chose.
25. How do you reverse an array in place?
Swap the elements at i and j, moving the two indexes toward each other until they meet.
import java.util.Arrays;
public class ReverseArray {
static void reverse(int[] a) {
for (int i = 0, j = a.length - 1; i < j; i++, j--) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5};
reverse(a);
System.out.println(Arrays.toString(a));
}
}Output:
[5, 4, 3, 2, 1]Complexity: O(n) time, O(1) space. Follow-up: "Reverse a List." Use Collections.reverse, or since Java 21, list.reversed() for a reversed view.
26. How do you find the missing number in an array of 1 to n?
Subtract the actual sum from the expected sum n(n + 1)/2. The XOR version avoids any chance of overflow: XOR all numbers 1 to n and all array elements, and the pairs cancel out.
public class MissingNumber {
// Numbers 1..n with exactly one missing
static int missing(int[] a, int n) {
int xor = 0;
for (int i = 1; i <= n; i++) xor ^= i;
for (int x : a) xor ^= x;
return xor; // pairs cancel out, the missing number is left
}
public static void main(String[] args) {
int[] a = {1, 2, 4, 5, 6};
long expected = 6L * 7 / 2; // sum formula n(n+1)/2
long actual = 0;
for (int x : a) actual += x;
System.out.println("sum formula: " + (expected - actual));
System.out.println("xor: " + missing(a, 6));
}
}Output:
sum formula: 3
xor: 3Complexity: O(n) time, O(1) space. Follow-up: "Two numbers are missing." Use the sum and the sum of squares, or XOR plus a split on a set bit.
27. How do you find duplicate elements in an array?
Add each element to a HashSet. add returns false for an element already present, which is exactly a duplicate.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
public class FindDuplicates {
// Brute force: compare every pair. O(n^2)
static Set<Integer> brute(int[] a) {
Set<Integer> dups = new LinkedHashSet<>();
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] == a[j]) dups.add(a[i]);
return dups;
}
// Optimal: one pass with a HashSet. O(n) time, O(n) space
static List<Integer> duplicates(int[] a) {
Set<Integer> seen = new HashSet<>();
Set<Integer> dups = new LinkedHashSet<>();
for (int x : a) if (!seen.add(x)) dups.add(x);
return new ArrayList<>(dups);
}
public static void main(String[] args) {
int[] a = {4, 3, 2, 7, 8, 2, 3, 1, 3};
System.out.println(brute(a));
System.out.println(duplicates(a));
}
}Output:
[3, 2]
[2, 3]The two outputs list the same duplicates in a different order: the brute force reports a duplicate when it finds the first matching pair, the HashSet version when it sees the second copy.
Brute force vs optimal: comparing every pair is O(n²) time and O(1) space. The HashSet pass is O(n) time and O(n) space, the classic time-for-memory trade. Follow-up: "Values are in the range 1 to n and you may not use extra space." Mark visited values by negating a[|x| - 1].
28. How do you solve Two Sum in Java?
For each number, check whether target - number is already in a map of value to index. If it is, you have the pair; if not, store the current number and move on. This is LeetCode problem 1, and the HashMap answer is the one interviewers expect.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
// Brute force: every pair. O(n^2)
static int[] brute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] == target) return new int[] {i, j};
return new int[0];
}
// Optimal: remember what we have seen. O(n) time, O(n) space
static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexOf = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer j = indexOf.get(target - nums[i]);
if (j != null) return new int[] {j, i};
indexOf.put(nums[i], i);
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
System.out.println(Arrays.toString(brute(nums, 9)));
System.out.println(Arrays.toString(twoSum(nums, 9)));
System.out.println(Arrays.toString(twoSum(new int[] {3, 2, 4}, 6)));
}
}Output:
[0, 1]
[0, 1]
[1, 2]Brute force vs optimal: nested loops are O(n²). The map makes it O(n) time and O(n) space. If the array is sorted, two pointers from both ends give O(n) time and O(1) space. Follow-up: "Return all pairs" or "Three Sum": sort, then fix one element and run two pointers on the rest, O(n²). If you want to know why the map lookup is O(1), see how HashMap works internally.
29. How do you move all zeros to the end of an array?
Copy every non-zero element forward using a write index, then fill the rest with zeros. The order of non-zero elements is kept.
import java.util.Arrays;
public class MoveZeros {
static void moveZeros(int[] a) {
int write = 0;
for (int x : a) if (x != 0) a[write++] = x; // keep order of non-zeros
while (write < a.length) a[write++] = 0;
}
public static void main(String[] args) {
int[] a = {0, 1, 0, 3, 12};
moveZeros(a);
System.out.println(Arrays.toString(a));
}
}Output:
[1, 3, 12, 0, 0]Complexity: O(n) time, O(1) space. Follow-up: "Minimize the number of writes." Swap a non-zero element with the write position only when they differ.
30. How do you rotate an array by k positions?
To rotate right by k: reverse the whole array, then reverse the first k elements, then reverse the rest. Take k % n first so k larger than the array still works.
import java.util.Arrays;
public class RotateArray {
// Brute force: shift right by one, k times. O(n * k)
static void rotateBrute(int[] a, int k) {
for (int r = 0; r < k % a.length; r++) {
int last = a[a.length - 1];
System.arraycopy(a, 0, a, 1, a.length - 1);
a[0] = last;
}
}
// Optimal: three reversals. O(n) time, O(1) space
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);
}
static void reverse(int[] a, int i, int j) {
for (; i < j; i++, j--) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7};
int[] b = a.clone();
rotateBrute(a, 3);
rotate(b, 3);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
}
}Output:
[5, 6, 7, 1, 2, 3, 4]
[5, 6, 7, 1, 2, 3, 4]Brute force vs optimal: shifting by one position k times is O(n × k). Three reversals are O(n) time and O(1) space. Copying into a new array is O(n) time but O(n) space. Follow-up: "Rotate left instead." Rotating left by k equals rotating right by n - k.
31. How do you find the maximum subarray sum (Kadane's algorithm)?
At each element decide: extend the current subarray, or start a new one here, whichever is larger. Track the best sum seen. This is Maximum Subarray and is asked in almost every DSA round.
public class Kadane {
// Brute force: every subarray. O(n^2)
static int brute(int[] a) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
int sum = 0;
for (int j = i; j < a.length; j++) { sum += a[j]; best = Math.max(best, sum); }
}
return best;
}
// Optimal: Kadane's algorithm. O(n) time, O(1) space
static int maxSubArray(int[] a) {
int current = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
current = Math.max(a[i], current + a[i]); // extend or restart
best = Math.max(best, current);
}
return best;
}
public static void main(String[] args) {
int[] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(brute(a));
System.out.println(maxSubArray(a));
System.out.println(maxSubArray(new int[] {-3, -1, -2}));
}
}Output:
6
6
-1Brute force vs optimal: summing every subarray is O(n²) (O(n³) without the running sum). Kadane is O(n) time and O(1) space. Starting best at a[0], not 0, handles the all-negative case, which the last line proves. Follow-up: "Return the start and end indexes too." Record the index whenever you restart and whenever best improves.
32. How do you merge two sorted arrays?
Walk both arrays with two indexes and always take the smaller current element, then copy whatever is left. This is the merge step of merge sort.
import java.util.Arrays;
public class MergeSorted {
static int[] merge(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < a.length) out[k++] = a[i++];
while (j < b.length) out[k++] = b[j++];
return out;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(merge(new int[] {1, 4, 7, 10}, new int[] {2, 3, 8})));
}
}Output:
[1, 2, 3, 4, 7, 8, 10]Complexity: O(n + m) time and space. Follow-up: "Merge in place when the first array has spare room at the end." Fill from the back so nothing is overwritten.
33. How do you implement binary search in Java?
Keep a low and high index, check the middle, and discard the half that cannot contain the target. Compute the middle as lo + (hi - lo) / 2 so a huge array cannot overflow lo + hi.
public class BinarySearch {
static int search(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, 56, 72, 91};
System.out.println(search(a, 23) + " " + search(a, 7));
}
}Output:
5 -1Complexity: O(log n) time, O(1) space. Requires a sorted array. Follow-up: "Find the first occurrence of a duplicate value." On a match, record it and keep searching the left half.
34. How do you write bubble sort, and how do you make it stop early?
Repeatedly swap adjacent elements that are out of order; the largest element bubbles to the end each pass. Add a swapped flag: if a full pass makes no swaps, the array is sorted and you can stop.
import java.util.Arrays;
public class BubbleSort {
static int passes = 0;
static void sort(int[] a) {
for (int end = a.length - 1; end > 0; end--) {
boolean swapped = false;
passes++;
for (int i = 0; i < end; i++) {
if (a[i] > a[i + 1]) {
int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
swapped = true;
}
}
if (!swapped) break; // already sorted: stop early
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
sort(a);
System.out.println(Arrays.toString(a) + " in " + passes + " passes");
passes = 0;
sort(new int[] {1, 2, 3, 4, 5});
System.out.println("sorted input: " + passes + " pass");
}
}Output:
[1, 2, 4, 5, 8] in 3 passes
sorted input: 1 passComplexity: O(n²) worst and average, O(n) best case on sorted input thanks to the early exit. Follow-up: "What does Java's Arrays.sort use?" A dual-pivot quicksort for primitive arrays and TimSort, a stable merge sort variant, for objects.
35. How do you remove duplicates from a sorted array in place?
Because duplicates are adjacent in a sorted array, keep a write index k and copy an element only when it differs from the last one written.
import java.util.Arrays;
public class RemoveDupsSorted {
// Returns the new length; the first k slots hold the unique values
static int dedupe(int[] a) {
if (a.length == 0) return 0;
int k = 1;
for (int i = 1; i < a.length; i++) if (a[i] != a[k - 1]) a[k++] = a[i];
return k;
}
public static void main(String[] args) {
int[] a = {1, 1, 2, 2, 2, 3, 4, 4};
int k = dedupe(a);
System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));
}
}Output:
4 [1, 2, 3, 4]Complexity: O(n) time, O(1) space. Follow-up: "Allow each value at most twice." Compare with a[k - 2] instead of a[k - 1].
Collections and Streams programs
These questions check whether you pick the right collection. Know the one-line reason for each: HashMap for O(1) lookup, LinkedHashMap or LinkedHashSet to keep insertion order, TreeMap for sorted keys.
36. How do you sort a HashMap by value?
Stream the entries, sort them with Map.Entry.comparingByValue(), and collect into a LinkedHashMap so the sorted order survives. Collecting into a plain HashMap would throw the order away.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;
public class SortMapByValue {
public static void main(String[] args) {
Map<String, Integer> scores = Map.of("Asha", 82, "Ravi", 95, "Meena", 78, "John", 91);
Map<String, Integer> sorted = scores.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
(x, y) -> x, LinkedHashMap::new)); // keep the sorted order
System.out.println(sorted);
}
}Output:
{Ravi=95, John=91, Asha=82, Meena=78}Complexity: O(n log n). Follow-up: "Top 3 only." Add .limit(3) after sorting, or use a size-3 PriorityQueue for O(n log 3).
37. How do you find the most frequent element in an array?
Count with merge and keep track of the current leader in the same loop, so you do not need a second pass over the map.
import java.util.HashMap;
import java.util.Map;
public class MostFrequent {
public static void main(String[] args) {
int[] a = {3, 1, 3, 2, 1, 3, 4};
Map<Integer, Integer> count = new HashMap<>();
int best = a[0];
for (int x : a) {
int c = count.merge(x, 1, Integer::sum);
if (c > count.get(best)) best = x;
}
System.out.println(best + " appears " + count.get(best) + " times");
}
}Output:
3 appears 3 timesComplexity: O(n) time, O(k) space. Follow-up: "More than half the array is one value; find it in O(1) space." That is the Boyer-Moore majority vote algorithm.
38. How do you remove duplicates from a list and keep the order?
Copy the list into a LinkedHashSet, which drops duplicates and preserves insertion order. stream().distinct() gives the same result.
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
public class DedupeList {
public static void main(String[] args) {
List<String> names = List.of("Ravi", "Asha", "Ravi", "John", "Asha");
System.out.println(new ArrayList<>(new LinkedHashSet<>(names)));
System.out.println(names.stream().distinct().toList());
}
}Output:
[Ravi, Asha, John]
[Ravi, Asha, John]Complexity: O(n). Follow-up: "Why not a HashSet?" It does not guarantee any order.
39. How do you find the common elements of two lists?
Put one list into a HashSet and keep the elements of the other that the set contains. retainAll does it in one call on a copy.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CommonElements {
public static void main(String[] args) {
List<Integer> a = List.of(1, 2, 3, 4, 5, 5);
List<Integer> b = List.of(4, 5, 6, 7, 5);
Set<Integer> inB = new HashSet<>(b);
List<Integer> common = new ArrayList<>();
Set<Integer> added = new HashSet<>();
for (int x : a) if (inB.contains(x) && added.add(x)) common.add(x);
System.out.println(common);
Set<Integer> viaRetain = new HashSet<>(a);
viaRetain.retainAll(b);
System.out.println(viaRetain);
}
}Output:
[4, 5]
[4, 5]Complexity: O(n + m) with a HashSet. Calling retainAll with a List argument on a big collection can degrade to O(n × m), because each contains on a list is linear. Follow-up: "Keep duplicates (multiset intersection)." Count one list in a map and decrement as you match.
40. How do you group anagrams together?
Sort the letters of each word to get a key ("tea" becomes "aet") and group words by that key with computeIfAbsent.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class GroupAnagrams {
public static void main(String[] args) {
String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
Map<String, List<String>> groups = new LinkedHashMap<>();
for (String w : words) {
char[] c = w.toCharArray();
Arrays.sort(c); // "tea" -> "aet"
groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w);
}
System.out.println(groups.values());
}
}Output:
[[eat, tea, ate], [tan, nat], [bat]]Complexity: O(w × k log k) for w words of length k. Follow-up: "Avoid sorting." Use the 26 letter counts as the key, which makes each key O(k).
41. How do you find the highest-paid employee in each department with streams?
Group by department, then reduce each group with maxBy on the salary. This and "find the second highest salary" are two of the most common Java 8 stream questions.
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;
public class TopEarnerByDept {
record Employee(String name, String dept, int salary) {}
public static void main(String[] args) {
List<Employee> staff = List.of(
new Employee("Asha", "Engineering", 120),
new Employee("Ravi", "Engineering", 135),
new Employee("Meena", "HR", 80),
new Employee("John", "HR", 75),
new Employee("Lee", "Sales", 90));
Map<String, String> topByDept = staff.stream().collect(Collectors.groupingBy(
Employee::dept, TreeMap::new,
Collectors.collectingAndThen(
Collectors.maxBy(Comparator.comparingInt(Employee::salary)),
e -> e.orElseThrow().name())));
System.out.println(topByDept);
int secondHighest = staff.stream().map(Employee::salary).distinct()
.sorted(Comparator.reverseOrder()).skip(1).findFirst().orElseThrow();
System.out.println("second highest salary = " + secondHighest);
}
}Output:
{Engineering=Ravi, HR=Meena, Sales=Lee}
second highest salary = 120Complexity: O(n) for the grouping, O(n log n) for the sorted second-highest query. Follow-up: "Average salary per department." Swap maxBy for averagingInt(Employee::salary). More stream problems like this are in our Java Stream API coding questions.
Linked list, stack and recursion programs
These programs test pointer handling and recursion. Draw the pointers before you code; interviewers are happy to watch you sketch.
42. How do you reverse a linked list in Java?
Walk the list with three references: prev, curr and next. For each node, save next, point curr.next back at prev, then move both forward. When curr is null, prev is the new head. This is Reverse Linked List.
public class ReverseLinkedList {
static final 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; // 1. save the rest of the list
curr.next = prev; // 2. turn the arrow around
prev = curr; // 3. move prev forward
curr = next; // 4. move curr forward
}
return prev;
}
static 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;
}
static String show(Node n) {
StringBuilder sb = new StringBuilder();
for (; n != null; n = n.next) sb.append(n.val).append(n.next != null ? " -> " : "");
return sb.toString();
}
public static void main(String[] args) {
Node head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
head = reverse(head);
System.out.println(show(head));
System.out.println(show(reverseRecursive(head)));
}
}Output:
4 -> 3 -> 2 -> 1
1 -> 2 -> 3 -> 4Complexity: iterative O(n) time and O(1) space; recursive O(n) time and O(n) stack. Follow-up: "Reverse it in groups of k" or "reverse only positions m to n". Both reuse the same three-pointer loop on a sublist.
43. How do you detect a cycle in a linked list?
Floyd's algorithm: move a slow pointer one step and a fast pointer two steps. If there is a cycle, they must meet; if fast reaches null, there is none.
public class DetectCycle {
static final class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
// Floyd's tortoise and hare: O(n) time, O(1) space
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;
}
public static void main(String[] args) {
Node a = new Node(1), b = new Node(2), c = new Node(3), d = new Node(4);
a.next = b; b.next = c; c.next = d;
System.out.println(hasCycle(a));
d.next = b; // 4 points back to 2
System.out.println(hasCycle(a));
}
}Output:
false
trueComplexity: O(n) time, O(1) space. A HashSet of visited nodes also works but uses O(n) space. Follow-up: "Find where the cycle starts." After they meet, move one pointer to the head and step both one at a time; they meet at the cycle start.
44. How do you find the middle of a linked list in one pass?
Same slow and fast pointers: when fast reaches the end, slow is in the middle. For an even length this returns the second middle node.
public class MiddleOfList {
record Node(int val, Node next) {}
static int middle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next();
fast = fast.next().next();
}
return slow.val(); // for even length, the second middle
}
static Node list(int... values) {
Node head = null;
for (int i = values.length - 1; i >= 0; i--) head = new Node(values[i], head);
return head;
}
public static void main(String[] args) {
System.out.println(middle(list(1, 2, 3, 4, 5)) + " " + middle(list(1, 2, 3, 4, 5, 6)));
}
}Output:
3 4Complexity: O(n) time, O(1) space. Follow-up: "Return the first middle for even lengths." Start fast at head.next.
45. How do you print all permutations of a string?
Recursively pick each remaining character as the next one and permute the rest. When nothing is left, the prefix is a full permutation.
import java.util.ArrayList;
import java.util.List;
public class Permutations {
static void permute(String prefix, String rest, List<String> out) {
if (rest.isEmpty()) { out.add(prefix); return; }
for (int i = 0; i < rest.length(); i++) {
permute(prefix + rest.charAt(i),
rest.substring(0, i) + rest.substring(i + 1), out);
}
}
public static void main(String[] args) {
List<String> out = new ArrayList<>();
permute("", "abc", out);
System.out.println(out);
}
}Output:
[abc, acb, bac, bca, cab, cba]Complexity: O(n × n!) time, because there are n! permutations of length n. Follow-up: "The string has duplicate letters." Skip a character at a position if the same character was already tried there, or collect into a Set.
46. How do you check for balanced parentheses?
Push every opening bracket onto a stack. For every closing bracket, the top of the stack must be its matching opener. At the end, the stack must be empty. Use ArrayDeque, not the legacy synchronized Stack class.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class BalancedBrackets {
static final Map<Character, Character> PAIRS = Map.of(')', '(', ']', '[', '}', '{');
static boolean isBalanced(String s) {
Deque<Character> stack = new ArrayDeque<>(); // not java.util.Stack
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') stack.push(c);
else if (PAIRS.containsKey(c)) {
if (stack.isEmpty() || !stack.pop().equals(PAIRS.get(c))) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isBalanced("{[()()]}") + " " + isBalanced("([)]") + " " + isBalanced("(("));
}
}Output:
true false falseNote the equals() call. stack.pop() != PAIRS.get(c) would compare two boxed Character references, which only happens to work because Java caches small Character values. Compare boxed values with equals(), or unbox to char first.
Complexity: O(n) time, O(n) space. Follow-up: "Only round brackets." Then a single counter is enough: increment on "(", decrement on ")", fail if it goes negative.
47. How do you generate all subsets (the power set) of an array?
For each element, recurse twice: once without it and once with it, then undo the choice (backtrack). This "take or skip" pattern is the base of many recursion questions.
import java.util.ArrayList;
import java.util.List;
public class Subsets {
static void subsets(int[] a, int i, List<Integer> current, List<List<Integer>> out) {
if (i == a.length) { out.add(new ArrayList<>(current)); return; }
subsets(a, i + 1, current, out); // skip a[i]
current.add(a[i]);
subsets(a, i + 1, current, out); // take a[i]
current.remove(current.size() - 1); // backtrack
}
public static void main(String[] args) {
List<List<Integer>> out = new ArrayList<>();
subsets(new int[] {1, 2, 3}, 0, new ArrayList<>(), out);
System.out.println(out);
}
}Output:
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]Complexity: O(n × 2ⁿ): there are 2ⁿ subsets and copying each costs up to n. Follow-up: "Do it without recursion." Count from 0 to 2ⁿ - 1 and use the bits of the counter to decide which elements to include.
OOP and multithreading programs
For experienced roles, the "programs" round often includes a design-flavored task. These three come up constantly.
48. How do you write a thread-safe singleton in Java?
Use the holder idiom: a private static nested class holds the instance, and the JVM's class initialization guarantees it is created once, lazily and safely, without explicit locking. An enum with one constant is even simpler and also resists reflection and serialization attacks.
public class SingletonDemo {
// Lazy and thread-safe: the JVM initialises Holder only on first use
static final class Config {
private Config() { System.out.println("Config created"); }
private static final class Holder {
static final Config INSTANCE = new Config();
}
static Config getInstance() { return Holder.INSTANCE; }
}
// The simplest correct singleton: an enum (also safe against reflection and serialization)
enum Registry { INSTANCE }
public static void main(String[] args) {
System.out.println("before first call");
System.out.println(Config.getInstance() == Config.getInstance());
System.out.println(Registry.INSTANCE == Registry.valueOf("INSTANCE"));
}
}Output:
before first call
Config created
true
trueThe output shows the lazy part: "Config created" prints only after "before first call", on the first getInstance().
Follow-up: "What about double-checked locking?" It works only if the instance field is volatile; without it, another thread can see a partly constructed object. Prefer the holder or enum forms.
49. How do you create an immutable class in Java?
Make the class final, all fields private final, provide no setters, and make defensive copies of mutable inputs and outputs. A record handles most of this automatically, but you still need a copy for mutable components like lists.
import java.util.ArrayList;
import java.util.List;
public class ImmutableClass {
// final class, private final fields, no setters, defensive copies in and out
static final class Order {
private final String id;
private final List<String> items;
Order(String id, List<String> items) {
this.id = id;
this.items = List.copyOf(items); // copy in: caller changes don't leak
}
String id() { return id; }
List<String> items() { return items; } // List.copyOf is already unmodifiable
}
// Since Java 16 a record does most of this for you (still copy mutable components)
record OrderRecord(String id, List<String> items) {
OrderRecord { items = List.copyOf(items); }
}
public static void main(String[] args) {
List<String> source = new ArrayList<>(List.of("pen", "ink"));
Order order = new Order("A1", source);
source.add("pad");
System.out.println(order.items());
try {
order.items().add("hack");
} catch (UnsupportedOperationException e) {
System.out.println("cannot modify: " + e.getClass().getSimpleName());
}
System.out.println(new OrderRecord("A2", source).items());
}
}Output:
[pen, ink]
cannot modify: UnsupportedOperationException
[pen, ink, pad]The first line proves the defensive copy: adding "pad" to the source list after construction did not change the order.
Follow-up: "Why are immutable objects useful?" They are thread-safe without locks, safe as HashMap keys, and easy to cache.
50. How do you print odd and even numbers with two threads?
Share a counter and a lock. Each thread waits until it is its turn (odd or even), prints, increments and notifies the other. The while loop around wait() protects against spurious wake-ups.
public class OddEvenThreads {
private static final int MAX = 10;
private static int counter = 1;
private static final Object lock = new Object();
static void print(boolean odd) {
synchronized (lock) {
while (counter <= MAX) {
if ((counter % 2 == 1) == odd) {
System.out.println(Thread.currentThread().getName() + ": " + counter++);
lock.notify();
} else {
try { lock.wait(); } catch (InterruptedException e) { return; }
}
}
lock.notify(); // wake the other thread so it can exit
}
}
public static void main(String[] args) throws InterruptedException {
Thread odd = new Thread(() -> print(true), "odd");
Thread even = new Thread(() -> print(false), "even");
odd.start(); even.start();
odd.join(); even.join();
}
}Output:
odd: 1
even: 2
odd: 3
even: 4
odd: 5
even: 6
odd: 7
even: 8
odd: 9
even: 10Follow-up: "Do it without wait and notify." Use two Semaphores that hand a permit back and forth, or a ReentrantLock with two Conditions.
How to answer a coding question in the interview
The code above is only half of what is being graded. The other half is how you get there. A simple routine that works for every program on this page:
- Restate and clarify. Ask about input size, case sensitivity, negatives, empty input and duplicates. Each answer may change the solution.
- Say the brute force first. One sentence plus its complexity. It proves you can solve the problem and gives you a baseline.
- Improve it out loud. Name the tool: hash map, two pointers, sliding window, sorting, prefix sum. Then state the new complexity before you code.
- Write a small method. Clear names, no clever tricks, guard clauses for edge cases.
- Test by hand. Walk through one normal case and one edge case, exactly like the outputs in this article.
What the interviewer is checking: not whether you memorized program 31, but whether you can explain why the O(n) version works and what it costs in memory. If you can say something like "this spends O(n) extra space to bring the time down from O(n²) to O(n)" for each answer above, you are ready.
Practise with the full question bank
Fifty programs cover the core. If you want the full set with edge cases and more patterns, these TechTriber PDFs go deeper in the same style:
- Top 100 Java Coding Interview Programs with Solutions: the 100 coding problems asked most in Java interviews, each with the optimal approach, complexity, edge cases and verified Java code.
- Java Strings: 100 Interview Questions with Answers: the string pool, immutability, every key method, StringBuilder, Unicode, regex and 31 coding problems.
- Java Tricky Output Questions: 100 "what will this print?" puzzles with real output and the rule behind each.
Related reading
- Java Stream API coding questions with output
- DSA patterns cheat sheet in Java: sliding window, two pointers and more, the patterns behind half of this list.
- Fresher interview questions for TCS, Infosys, Wipro and Accenture
- How HashMap works internally in Java
FAQ
Which Java programs are asked most in fresher interviews?
String reversal, palindrome, anagram, Fibonacci series, prime check, factorial, swapping two numbers, the largest and second largest element, duplicates in an array and pattern printing. They are programs 1 to 35 above. Practise writing them without an IDE.
Can I use built-in methods like StringBuilder.reverse() in an interview?
Mention them, because they show you know the API, but be ready to write the logic by hand. A good answer is: "In production I would use reverse(); here is the two-pointer version."
How many Java programs should I practise before an interview?
Fifty well-understood programs beat two hundred memorized ones. If you can solve every program here from scratch and explain its complexity, you are covered for most service-company rounds; product companies will add medium DSA problems on top.
Should I write Java coding answers with streams or loops?
Use loops for algorithm questions (they make the complexity obvious) and streams for data-processing questions like grouping, counting and sorting records. Interviewers for Java roles usually ask at least one stream question.
Do these programs work on Java 8?
Most logic does, but some code uses newer features: records and Stream.toList() need Java 16, String.repeat needs Java 11, and single-file launching with java File.java needs Java 11. Everything here runs on Java 17, 21 and 25.
