Java Coding Interview Questions: 90 String, Array and Automation Architect Problems With Solutions

Java coding interview questions for SDET and automation roles rarely open with anything exotic. The first live-coding screen is usually a string or an array problem that fits in fifteen lines: reverse it, find the duplicate, count the characters, rotate it by k. None of these are hard. They work as a filter, and candidates fail it for ordinary reasons. No null check. An off-by-one in a loop bound. A nested loop where a HashMap would have done the job. A solution that passes the one example on the whiteboard and nothing else.

This page puts 90 of those problems in one place, in five groups: 24 Java string interview questions, 34 Java array programming questions, 4 number and logic questions, 8 collections, streams and concurrency problems aimed at automation architect interviews, and a final group of 20 advanced problems for senior and architect rounds. They run from the warm-ups that open almost every Java round to the design-flavoured code (an LRU cache, a retry helper, a rate limiter, per-thread resources) that senior SDET and architect rounds favour.

Each one comes with the approach you would say out loud, a solution, the time and space complexity, and the edge cases that decide whether the answer holds up. Every solution was compiled and run on Java 21 (and compiles for Java 8) against the examples shown, so what you read here is what actually prints.

Do not memorise the code. Interviewers can tell, and a small change to the question (distinct values only, sorted input, Unicode) breaks memorised code immediately. Learn the pattern underneath each problem instead. Two pointers, a hash map for counting, a sliding window, prefix and suffix products: a handful of patterns cover most of what gets asked, and a section near the end maps each problem to its pattern.

Ground Rules That Apply to Every Problem

Before the first line of code, spend thirty seconds on the input. It is the cheapest way to look senior in a coding round, and it prevents most of the bugs people hit later.

• Ask what can be null or empty, and what the method should return for it. Throwing and returning a default are both defensible. Having no answer is not.
• Ask about duplicates, negatives, case sensitivity, spaces and non-ASCII characters, depending on whether it is a string or an array question.
• Say the brute-force approach first, with its complexity, then improve it. Showing the improvement is the point of the exercise.
• Finish by walking one small example through the code by hand, and state time and space complexity in terms of n.

All snippets below assume import java.util.*; and sit inside a utility class; the concurrency and streams problems in the last group also need java.util.concurrent.*, java.util.function.* and java.util.stream.*. They use nothing newer than Java 8.

Java String Interview Questions

Two facts sit under almost every string question. First, a String is immutable. Every concatenation inside a loop creates a new object, which is why code that builds output in a loop uses StringBuilder instead of +=. Second, == compares references, not content. Use equals() or equalsIgnoreCase() for text. String literals are shared through the string pool, so "a" == "a" is true while new String("a") == "a" is false, and that difference is a favourite follow-up question. StringBuilder is not synchronised and is the default choice; StringBuffer is the synchronised older version you rarely need. The official String Javadoc lists every method used below.

1. Reverse a String

Reversing a string is the classic warm-up, and interviewers use it to see whether you reach for a library call or can do it by hand. Know both. The one-liner is new StringBuilder(s).reverse().toString(). The manual version swaps characters from both ends and moves inward, which is the two-pointer pattern you will reuse for palindromes, arrays and sorted-input problems.

static String reverse(String s) {
    if (s == null) return null;
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    while (left < right) {
        char tmp = chars[left];
        chars[left++] = chars[right];
        chars[right--] = tmp;
    }
    return new String(chars);
}

static String reverseWithBuilder(String s) {
    return s == null ? null : new StringBuilder(s).reverse().toString();
}

reverse("selenium") returns "muineles", and an empty string comes back empty. Time is O(n) and space is O(n) for the copied char array. Mention one caveat if you get the chance: StringBuilder.reverse() treats surrogate pairs (many emoji and some non-Latin characters) as single characters, while the char swap above would split them. For interview purposes, say it once and move on.

Brute Force and Follow-Ups

Starting point. The first version most people write loops backwards and builds the answer with result += s.charAt(i). It gives the right output, but a String is immutable, so every concatenation allocates a new object and copies everything built so far. For n characters that adds up to O(n²) time. A recursive version (reverse the rest of the string, then append the first character) has the same cost and also uses O(n) stack, so a long input can end in a StackOverflowError. Moving the work into a char array or a StringBuilder removes both problems.

Follow-ups to expect. Expect “reverse it without using StringBuilder.reverse”, which is the swap loop above. Another favourite is “reverse the words but not the letters”, which is the reverse-words problem later in this section. A sharper question is why the character swap can break on emoji: a code point outside the Basic Multilingual Plane is stored as two char values, and swapping them one at a time reverses the pair. StringBuilder.reverse() handles that case, and knowing the reason is worth more than the code.

2. Check Whether a String Is a Palindrome

A palindrome check usually comes with a twist: ignore case, spaces and punctuation. The tempting solution builds a cleaned copy of the string and compares it with its reverse. It works, but it uses extra memory. Two pointers do the job in place: move each pointer past anything that is not a letter or digit, compare the two characters in lowercase, and step inward.

static boolean isPalindrome(String s) {
    if (s == null) return false;
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

isPalindrome("A man, a plan, a canal: Panama") is true, "race a car" is false, and the empty string is true. Time is O(n) and space is O(1). The inner loops keep left < right so that a string made only of punctuation cannot run off the end. Agree with the interviewer on what null should return; the version here returns false.

Brute Force and Follow-Ups

Starting point. The obvious approach builds a cleaned copy (lowercase, letters and digits only), reverses it, and compares the two strings. That is O(n) time but needs O(n) extra memory and two or three passes over the data. A recursive check of the first and last characters is just as correct and costs O(n) stack. The two-pointer version in the solution does the same job in one pass with no copy, which is why it is the version to present once you have mentioned the simple one.

Follow-ups to expect. A very common variation is “valid palindrome after deleting at most one character”: run the same two pointers, and on the first mismatch try skipping the left character or the right character and check whether either remainder is a palindrome. The next step up is “find the longest palindromic substring”, covered later in this guide. Interviewers also ask about case and Unicode: Character.toLowerCase per character is simple, but text with accents may need java.text.Normalizer first. Say which assumption you made before you code.

3. Check Whether Two Strings Are Anagrams

Two strings are anagrams when they contain the same characters with the same counts. Sorting both and comparing works in O(n log n) and is fine to mention first. Counting is O(n): add one to a map for every character of the first string, then subtract for the second, and fail as soon as a count would go below zero.

static boolean isAnagram(String a, String b) {
    if (a == null || b == null) return false;
    String x = a.replaceAll("\\s+", "").toLowerCase(Locale.ROOT);
    String y = b.replaceAll("\\s+", "").toLowerCase(Locale.ROOT);
    if (x.length() != y.length()) return false;

    Map<Character, Integer> counts = new HashMap<>();
    for (char c : x.toCharArray()) counts.merge(c, 1, Integer::sum);
    for (char c : y.toCharArray()) {
        Integer n = counts.get(c);
        if (n == null || n == 0) return false;
        counts.put(c, n - 1);
    }
    return true;
}

isAnagram("Listen", "Silent") is true, "hello" and "world" is false, and "Dormitory" and "dirty room" is true because spaces are stripped and case is ignored. Ask whether spaces and case should matter; some versions of this question say they do. toLowerCase(Locale.ROOT) avoids locale surprises, such as the Turkish dotted capital I. If the input is guaranteed to be lowercase a to z, an int[26] counter is faster than a HashMap and worth offering as the optimisation.

Brute Force and Follow-Ups

Starting point. Sorting both strings and comparing them is the simplest correct answer and costs O(n log n). A weaker brute force takes each character of the first string and removes its first occurrence from a copy of the second, which is O(n²) and mutates a string repeatedly. The counting solution reaches O(n) by recording how many times each character occurs and checking that the two counts cancel out exactly, and it exits early as soon as a count would go negative.

Follow-ups to expect. Ask what the alphabet is. For lowercase a to z, an int[26] is faster than a HashMap; for full Unicode, a map is the right tool. A strong follow-up is “find all start positions in a long string where an anagram of a short pattern begins”, which is a sliding window that keeps a count array and updates it as the window moves, giving O(n) overall. Another is “group a list of words by anagram”, which is the group-anagrams problem later on. Mention that spaces and case are part of the problem statement, not an afterthought.

4. Find the First Non-Repeating Character

This is two passes over the string. The first pass counts every character. The second returns the index of the first character whose count is 1. The second pass has to walk the original string, not the map, because a HashMap does not remember order.

static int firstNonRepeatingIndex(String s) {
    if (s == null) return -1;
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) counts.merge(c, 1, Integer::sum);
    for (int i = 0; i < s.length(); i++) {
        if (counts.get(s.charAt(i)) == 1) return i;
    }
    return -1;
}

firstNonRepeatingIndex("swiss") returns 1 (the w), "teeter" returns 5 (the r), and "aabb" returns -1. Time is O(n) and space is O(k), where k is the number of distinct characters. Returning the index instead of the character lets you signal “none found” without inventing a sentinel character.

Brute Force and Follow-Ups

Starting point. The nested-loop version takes each character and scans the whole string to see whether it appears again. It needs no extra memory but costs O(n²) time, and it is acceptable only for a very short string. The two-pass counting approach is the standard improvement: count everything once, then walk the original string again and stop at the first character whose count is one. The second pass uses the string, not the map, because a HashMap gives no ordering guarantee.

Follow-ups to expect. A good follow-up is “do it in a single pass over the data” or “the characters arrive as a stream and you cannot read them twice”. A LinkedHashMap that keeps counts in arrival order lets you read the first entry with a count of one at any moment. Another is to store the first index of each character in an array and mark repeats, then take the smallest remaining index. Interviewers also ask what to return when nothing is unique, which is why this version returns -1 for the index instead of a sentinel character.

5. Count Character Frequency and Find Duplicate Characters

Counting characters is the building block for half the problems in this section, so write it fluently. The detail worth mentioning is the map type. HashMap makes no promise about iteration order. LinkedHashMap iterates in the order characters first appeared, which is usually what a printed answer should show.

static Map<Character, Integer> charFrequency(String s) {
    Map<Character, Integer> freq = new LinkedHashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    return freq;
}

static Map<Character, Integer> duplicateChars(String s) {
    Map<Character, Integer> freq = charFrequency(s);
    freq.values().removeIf(count -> count == 1);
    return freq;
}

charFrequency("automation") gives {a=2, u=1, t=2, o=2, m=1, i=1, n=1}, and duplicateChars("automation") gives {a=2, t=2, o=2}. Both run in O(n) time. If you are asked to find duplicates without using a map, the honest answers are a nested loop at O(n²) or sorting a copy of the characters first at O(n log n).

Brute Force and Follow-Ups

Starting point. Looping over the string and, for every character, looping again to count its occurrences is O(n²), and it prints the same character repeatedly unless you track which ones were already handled. The map-based version does one pass and increments a counter per character, which is the standard answer. For plain ASCII text an int[128] or int[256] array indexed by the character is even faster than a HashMap and avoids boxing.

Follow-ups to expect. Typical extensions are “print the characters in sorted order” (use a TreeMap), “ignore case” (lowercase the string first), and “show the three most frequent characters” (sort the entries by count, or keep a small heap). Interviewers also like the question of why LinkedHashMap was chosen: it keeps first-seen order, so the output is predictable and easy to compare in a test. If the string is huge and you only need the top few characters, say that a heap of size k beats sorting every entry.

6. Count Vowels and Consonants

Simple on paper, and a good test of how carefully you read the question. Does y count as a vowel? Do digits and spaces count as consonants? The version below counts only the letters a to z, treats a, e, i, o and u as vowels, and treats every other letter as a consonant. State that assumption before you code it.

static int[] countVowelsAndConsonants(String s) {
    int vowels = 0, consonants = 0;
    for (char c : s.toLowerCase(Locale.ROOT).toCharArray()) {
        if (c >= 'a' && c <= 'z') {
            if ("aeiou".indexOf(c) >= 0) vowels++;
            else consonants++;
        }
    }
    return new int[] { vowels, consonants };
}

countVowelsAndConsonants("Hello World") returns [3, 7]: three vowels (e, o, o) and seven consonants (H, l, l, W, r, l, d). Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. There is no meaningful brute force here, since one pass is already linear. The variation is in how you test for a vowel. "aeiou".indexOf(c) is a quick check because the string has only five characters, and a Set<Character> or a switch statement do the same job. What matters more is deciding what counts: whether uppercase letters are included, whether y is a vowel, and whether digits, spaces and punctuation are consonants. The solution counts only letters from a to z.

Follow-ups to expect. Expect “what about accented letters such as é?”. A plain a-to-z test would skip them, so you would use Character.isLetter and normalise the text first. Another follow-up is “count each vowel separately”, which becomes a small frequency map. If the interviewer asks for a one-line version, a stream filter with chars() works, but it is slower and less readable than the loop, so offer it as an alternative, not as the main answer.

7. Reverse the Words in a Sentence

This reverses the order of the words, not the characters inside them. Trim the string, split on one or more whitespace characters, and walk the array backwards. Splitting on "\\s+" rather than a single space is what makes repeated spaces harmless.

static String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

reverseWords("the quick brown fox"), with its double space, returns "fox brown quick the". Empty and all-space inputs return an empty string. Time and space are O(n). Check which problem the interviewer means: reversing each word in place (“eht kciuq”) is a different question with a different solution.

Brute Force and Follow-Ups

Starting point. A manual version scans from the end of the string, collecting characters until a space, and builds each word by hand. It avoids regular expressions but is long and error-prone around repeated and leading spaces. The split-based answer is shorter, but note that split("\\s+") compiles a regular expression on every call and creates an array of all the words. For ordinary strings that cost is irrelevant, and for very large inputs you would process the text in a single pass.

Follow-ups to expect. The classic harder version asks you to do it in place on a char[] with O(1) extra space: reverse the entire character array, then reverse each word back to its correct orientation. Another variation is “reverse each word but keep the word order”, which is the same idea without the first step. Be ready to say what happens with leading, trailing and repeated spaces, since the expected output for those is part of the problem and different interviewers want different behaviour.

8. Longest Substring Without Repeating Characters

This is the step up from the counting problems, and it appears constantly because it tests the sliding-window pattern. The brute force checks every substring and is O(n²) at best. The window version keeps a start index and the last position of every character; when the current character was last seen inside the window, start jumps to one past that position.

static int longestUniqueSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int best = 0, start = 0;
    for (int end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        Integer prev = lastSeen.get(c);
        if (prev != null && prev >= start) start = prev + 1;
        lastSeen.put(c, end);
        best = Math.max(best, end - start + 1);
    }
    return best;
}

longestUniqueSubstring("abcabcbb") returns 3, "bbbbb" returns 1, "pwwkew" returns 3, and the empty string returns 0. The check prev >= start matters. In "abba", when the second a arrives its last-seen position is 0, but start has already moved to 2, so the old position has to be ignored. Without that check the window moves backwards and the answer is wrong. Time is O(n), space is O(k).

Brute Force and Follow-Ups

Starting point. Checking every substring for duplicate characters is O(n³) if each check scans the substring, or O(n²) if you stop at the first repeat with a set. Either is too slow for long input. The sliding window works because as the right end moves forward, the left end only ever moves forward as well, so no position is visited more than twice. Storing the last index of each character lets the left end jump straight past the previous occurrence instead of moving one step at a time.

Follow-ups to expect. A very common follow-up is “return the substring, not just its length”, which needs you to record the start index whenever a new best is found. The generalisation is “longest substring with at most k distinct characters”, which keeps a count map for the window and shrinks it when it holds more than k keys. If the alphabet is only ASCII, an int[128] array of last positions replaces the HashMap and is faster. Ask whether case matters before you start, because it changes which characters are considered equal.

9. Compress a String (Run-Length Encoding)

Turn aaabbbccc into a3b3c3. Build the output in a StringBuilder, never with += in a loop, and handle the last run by letting the loop index run one past the end of the string. The usual follow-up is to return the original string when the compressed version is not shorter.

static String compress(String s) {
    if (s == null || s.isEmpty()) return s;
    StringBuilder sb = new StringBuilder();
    int count = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) {
            count++;
        } else {
            sb.append(s.charAt(i - 1)).append(count);
            count = 1;
        }
    }
    return sb.length() < s.length() ? sb.toString() : s;
}

compress("aaabbbccc") returns "a3b3c3", "aabcccccaaa" returns "a2b1c5a3", and "abc" comes back as "abc" because "a1b1c1" would be longer. Counts above 9 work fine ("a12"), though a decoder would then need to read multi-digit numbers. Time and space are O(n).

Brute Force and Follow-Ups

Starting point. The simplest version builds the result with result += ch + count inside the loop. It is correct and quadratic, because each concatenation copies the string built so far. Switching to a StringBuilder makes it linear. Another subtle point is the last run: the loop must flush the final group after the last character, which is why the solution runs the index one past the end of the string instead of adding a special case below the loop.

Follow-ups to expect. Interviewers often ask for the reverse operation, decompression, which has to read multi-digit counts. A harder version compresses a char[] in place with O(1) extra space, using a read pointer and a write pointer. You may also be asked why the method returns the original string when the compressed one is not shorter; the answer is that run-length encoding can expand data that has few repeated characters, so a real implementation checks the result before returning it.

10. Check Whether One String Is a Rotation of Another

Is erbottlewat a rotation of waterbottle? The trick is that every rotation of a string appears as a substring of the string joined to itself. So check that the lengths match, then check whether b is contained in a + a.

static boolean isRotation(String a, String b) {
    if (a == null || b == null) return false;
    return a.length() == b.length() && (a + a).contains(b);
}

isRotation("waterbottle", "erbottlewat") is true, and "abcd" with "acbd" is false. The length check is not optional: without it, "abc" would be reported as a rotation of "ab", because "abcabc" contains "ab". With a linear-time substring search the whole thing is O(n). Java’s String.contains uses a simple search whose worst case is O(n·m), though it is fast in practice, so say “O(n) conceptually” only if you are ready to explain that.

Brute Force and Follow-Ups

Starting point. Trying every possible rotation, building each rotated string and comparing it with the second string, is O(n²). The doubling trick reduces the problem to a single substring search: every rotation of a string is a substring of the string joined to itself. That is why the length check matters. Without it, a shorter string that happens to appear inside the doubled string would be reported as a rotation.

Follow-ups to expect. A natural extension is “how many positions was it rotated by?”, which is the index returned by (a + a).indexOf(b). Interviewers also ask for the cost: Java’s contains uses a simple search that is O(n·m) in the worst case, even though it is fast in practice, so a guaranteed linear bound would need the KMP algorithm. Be honest about that distinction instead of claiming O(n). A related question is “rotate a string by k positions”, which uses the same three-reversal idea as array rotation.

11. Valid Parentheses (Balanced Brackets)

Given a string containing (), [] and {}, decide whether every bracket is closed by the right type in the right order. This is the standard stack question. Scan left to right; on an opening bracket push the closing bracket you expect, and on a closing bracket pop and compare. If the stack is empty when you need to pop, or anything is left on it at the end, the string is not balanced. Use ArrayDeque as the stack. The legacy Stack class is synchronised and extends Vector, and most interviewers prefer to see Deque.

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

"()[]{}" and "{[()]}" are valid, "(]" is not, "((" is not because the stack is not empty at the end, and a lone "]" is not because there is nothing to pop. The empty string is valid. Characters that are not brackets are ignored here, so "a(b)c" is valid; say that out loud as an assumption. Time is O(n) and space is O(n). The same idea checks that a JSON-like or XML-like payload is well formed before you try to parse it.

Brute Force and Follow-Ups

Starting point. A well-known brute force repeatedly removes the substrings (), [] and {} from the string until nothing changes, and then checks whether the string is empty. It is neat but O(n²), because each removal creates a new string and a pass may remove only one pair. The stack solution does one left-to-right pass and is the one to give, with the brute force as a quick mention.

Follow-ups to expect. Expect “return the index of the first bracket that breaks the rule”, which means pushing indexes onto the stack along with the expected character. A related question is “what is the minimum number of brackets to add to make it valid?”, which for a single bracket type needs only two counters and no stack. Another is “generate all valid combinations of n pairs of parentheses”, which is a small backtracking problem and a good one to practise next. State whether non-bracket characters are ignored.

12. Group Anagrams

This extends the anagram check from earlier: given a list of words, group the ones that are anagrams of each other. The key insight is that all anagrams share the same sorted-character form, so that sorted string can be the key in a map from key to list of words.

static List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new LinkedHashMap<>();
    for (String w : words) {
        char[] chars = w.toCharArray();
        Arrays.sort(chars);
        groups.computeIfAbsent(new String(chars), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

For {"eat", "tea", "tan", "ate", "nat", "bat"} the result is [[eat, tea, ate], [tan, nat], [bat]]. LinkedHashMap keeps the groups in the order they were first seen. Sorting each word costs O(k log k) for word length k, so the total is O(n · k log k). If the words are lowercase a to z, replace the sorted key with a 26-element count signature and the cost drops to O(n · k). computeIfAbsent is the idiomatic way to build a map of lists without a null check.

Brute Force and Follow-Ups

Starting point. The naive method compares every word with every other word using the anagram check, which is O(n² · k log k) for n words of length k. It also needs a way to avoid placing a word in more than one group. Using the sorted form of each word as a map key removes the pairwise comparison entirely: all anagrams share one key, so each word is handled once.

Follow-ups to expect. A faster key for lowercase words is a signature of 26 counts, for example "1#0#2#...", which avoids sorting each word and gives O(n · k). Interviewers often ask for the groups in a specific order, such as sorted alphabetically within each group, which is a small post-processing step. If the number of words is very large, you can discuss memory: the map holds every word once, so memory grows with the total input, which is unavoidable if all groups must be returned.

13. Longest Palindromic Substring

Find the longest substring that reads the same in both directions. Checking every substring is O(n³). The standard answer expands around each possible centre: a palindrome of odd length is centred on a character, and one of even length is centred between two. That gives 2n – 1 centres, and each expansion is at most O(n).

static String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";
    int bestStart = 0, bestLen = 1;
    for (int center = 0; center < s.length(); center++) {
        for (int pass = 0; pass < 2; pass++) {          // pass 0 = odd length, pass 1 = even length
            int left = center, right = center + pass;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            int len = right - left - 1;
            if (len > bestLen) {
                bestLen = len;
                bestStart = left + 1;
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

longestPalindrome("babad") returns "bab", and "aba" is equally correct, so check with the interviewer whether any answer is accepted when there is a tie. "cbbd" returns "bb", which needs the even-length pass. "ac" returns "a" and the empty string returns an empty string. Time is O(n²) and space is O(1). Manacher’s algorithm does it in O(n), and naming it shows depth, but nobody expects you to code it from memory.

Brute Force and Follow-Ups

Starting point. Checking every substring to see whether it is a palindrome is O(n³). A dynamic-programming table that records whether each range is a palindrome brings the time to O(n²) but also needs O(n²) memory. Expanding around each centre is also O(n²) time but needs only O(1) extra space, and it is shorter to write, so it is usually the best choice to present. There are 2n – 1 centres because palindromes can be centred on a character or between two characters.

Follow-ups to expect. Expect “count all palindromic substrings”, which is the same expansion with a counter instead of a best length. “Return the length only” is simply a simplification. Candidates who know it can name Manacher’s algorithm, which finds the longest palindromic substring in O(n) time by reusing earlier results, and it is fine to say you would not write it from memory. Clarify what to return when there are ties; this solution returns the first one it finds.

14. Longest Common Prefix

Find the longest prefix shared by every string in an array. Start with the first word as the prefix and shorten it until each following word starts with it. The loop stops early once the prefix is empty.

static String longestCommonPrefix(String[] words) {
    if (words == null || words.length == 0) return "";
    String prefix = words[0];
    for (int i = 1; i < words.length && !prefix.isEmpty(); i++) {
        while (!words[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
        }
    }
    return prefix;
}

{"flower", "flow", "flight"} gives "fl", {"dog", "racecar", "car"} gives an empty string, and a single-word array returns that word. Return an empty string for an empty array. Worst case is O(S), where S is the total number of characters across all the words. It is a quick problem, but it checks whether you handle the empty-array and empty-prefix cases without being prompted.

Brute Force and Follow-Ups

Starting point. A character-by-character scan takes the first character of every word, then the second, and stops at the first column where the words disagree. It runs in O(S), where S is the total number of characters, and uses no extra memory. The solution above does something similar by shortening a candidate prefix until every word starts with it. Both are fine, and the shortening approach is easier to write without index errors.

Follow-ups to expect. A neat trick is to sort the array and compare only the first and the last word, because those two are the most different; their common prefix is the common prefix of the whole array. Another variation is a binary search on the prefix length. If you need to answer many prefix queries over the same words, a trie is the right data structure. Be ready to say what happens with an empty array or an empty string inside the array.

15. Convert a String to an Integer (atoi)

Write your own parseInt. It looks trivial and is mostly a test of edge-case discipline: leading spaces, an optional sign, digits until the first non-digit, and clamping on overflow instead of wrapping around. Accumulate in a long and clamp as soon as the value leaves the int range, so the accumulator can never overflow itself.

static int myAtoi(String s) {
    if (s == null) return 0;
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') i++;
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        if (s.charAt(i) == '-') sign = -1;
        i++;
    }
    long result = 0;
    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
        result = result * 10 + (s.charAt(i) - '0');
        if (sign * result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (sign * result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        i++;
    }
    return (int) (sign * result);
}

myAtoi(" -42") returns -42, "4193 with words" returns 4193, "words and 987" returns 0 because the first non-space character is not a digit, "99999999999" clamps to 2147483647, and "-91283472332" clamps to -2147483648. The digit test uses >= '0' && <= '9' rather than Character.isDigit, because isDigit also accepts digits from other scripts and the subtraction would then be wrong. Be ready to explain how this differs from Integer.parseInt: the JDK version throws NumberFormatException on bad input, while this one is deliberately lenient. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. The shortcut is Integer.parseInt inside a try-catch, but it is normally not allowed in this question, and it behaves differently: it throws on bad input, rejects leading spaces and trailing text, and does not clamp on overflow. The manual solution trims leading spaces, reads an optional sign, accumulates digits until the first non-digit, and clamps at the int limits. Accumulating in a long and checking after each digit prevents the accumulator itself from overflowing.

Follow-ups to expect. Interviewers like to extend this with decimals (“parse a double”), other bases (“parse hexadecimal”), or “report an error instead of clamping”. Each one tests whether you can adapt a parser without rewriting it. Another point is whitespace: the solution skips only the space character, while a real parser may need to skip tabs and newlines as well. Whenever you write a parser, list its edge cases aloud: empty input, only a sign, only spaces, and a value exactly at the limit.

16. Generate All Permutations of a String

Print or return every arrangement of the characters. This is the standard introduction to backtracking: fix a character at the current position, recurse on the rest, then undo the swap so the next choice starts from a clean state. The used set at each level skips repeated letters, so a string like "aab" does not produce duplicate permutations.

static List<String> permutations(String s) {
    List<String> out = new ArrayList<>();
    permute(s.toCharArray(), 0, out);
    return out;
}

private static void permute(char[] c, int index, List<String> out) {
    if (index == c.length) {
        out.add(new String(c));
        return;
    }
    Set<Character> used = new HashSet<>();               // skip repeated letters at this position
    for (int i = index; i < c.length; i++) {
        if (!used.add(c[i])) continue;
        swapChars(c, index, i);
        permute(c, index + 1, out);
        swapChars(c, index, i);                          // backtrack
    }
}

private static void swapChars(char[] c, int i, int j) {
    char tmp = c[i];
    c[i] = c[j];
    c[j] = tmp;
}

permutations("abc") returns [abc, acb, bac, bca, cba, cab], and permutations("aab") returns the three distinct arrangements [aab, aba, baa]. The count grows as n!: 4 characters give 24 results, 8 give 40,320 and 10 give over 3.6 million, so say plainly that this does not scale and that you would never feed it a long string. Time is O(n · n!). The test-automation connection is combination generation for test data, where the usual answer to the explosion is pairwise or orthogonal-array testing instead of every combination.

Brute Force and Follow-Ups

Starting point. A common alternative builds each permutation with a boolean[] used array and a StringBuilder, choosing one unused character at every position. It is just as correct but uses more auxiliary structures. The swap-based version below modifies one array in place and undoes each swap after the recursive call, which is the essence of backtracking. Without the per-level set, a string with repeated letters would produce duplicate permutations.

Follow-ups to expect. Expect “generate the next permutation in lexicographic order”, which is an O(n) algorithm that does not need recursion, and “find the kth permutation”, which uses the factorial number system. The same template solves “all subsets”, “all combinations of size k” and “all valid parentheses”. Be ready to talk about growth: the number of results is n!, so the method is only usable for short strings, and you should say so before an interviewer asks you to run it on twenty characters.

17. Character Frequency and First Non-Repeating Character with Streams

Many interviewers now ask for the same string problems written with Java 8 streams, to see whether you are comfortable with them without overusing them. s.chars() gives an IntStream of UTF-16 code units, mapToObj(c -> (char) c) boxes them to Character, and groupingBy with counting() builds the frequency map. Passing LinkedHashMap::new as the map factory keeps first-seen order.

static Map<Character, Long> charFrequencyStreams(String s) {
    return s.chars()
            .mapToObj(c -> (char) c)
            .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));
}

static Optional<Character> firstNonRepeatingStreams(String s) {
    return charFrequencyStreams(s).entrySet().stream()
            .filter(e -> e.getValue() == 1)
            .map(Map.Entry::getKey)
            .findFirst();
}

charFrequencyStreams("automation") gives {a=2, u=1, t=2, o=2, m=1, i=1, n=1}. firstNonRepeatingStreams("swiss") returns Optional[w], and "aabb" returns an empty Optional, which is a cleaner way to say “none found” than returning -1. Two details worth knowing: counting() produces Long values, not Integer, and the stream version boxes every character, so for a hot path the plain loop from earlier in the page is faster. Use streams when they make the code shorter and clearer, not because they look modern.

Brute Force and Follow-Ups

Starting point. The plain loop version earlier in this guide is the baseline: one pass with a LinkedHashMap and merge. The streams version is not faster. It boxes every character into a Character object and creates intermediate stream stages, so on a hot path the loop is the better choice. The streams version earns its place when it is shorter and clearer, and an interviewer who asks for it usually wants to see that you can use groupingBy and counting correctly.

Follow-ups to expect. Questions to expect are “why is the count a Long and not an Integer?” (because Collectors.counting() returns Long), and “why pass LinkedHashMap::new?” (to keep encounter order, since the default map does not). A deeper one is “does this work for emoji?”. It does not, because chars() gives UTF-16 code units, and codePoints() is the method to use. Do not recommend parallel streams here: the ordering requirement and the tiny workload make them slower.

18. Remove All Whitespace from a String

The one-liner is s.replaceAll("\\s+", ""), and it is the answer to give first. The manual version loops once and appends every character that is not whitespace. Use a StringBuilder for the output. Building the result with result += c inside the loop creates a new String on every iteration, which turns an O(n) job into O(n²) and is exactly the kind of detail interviewers notice.

static String removeWhitespace(String s) {
    StringBuilder sb = new StringBuilder(s.length());
    for (char c : s.toCharArray()) {
        if (!Character.isWhitespace(c)) sb.append(c);
    }
    return sb.toString();
}

static String removeWhitespaceRegex(String s) {
    return s.replaceAll("\\s+", "");
}

removeWhitespace("hello world") returns "helloworld", and " a\tb\nc " returns "abc", because tabs and newlines count as whitespace as well as spaces. Character.isWhitespace is the safer check than comparing with ' '. If the question only asks about spaces, say so and use the narrower test. Time is O(n) and space is O(n).

Brute Force and Follow-Ups

Starting point. The loop that appends each non-space character to a String with += is the version that interviewers expect to see criticised: it is O(n²) because each step copies the string built so far. A StringBuilder fixes that. The regular-expression one-liner replaceAll("\\s+", "") is the shortest answer, but it compiles a pattern on each call, so inside a tight loop you would precompile a Pattern.

Follow-ups to expect. Interviewers often narrow or widen the request. “Remove only leading and trailing spaces” is trim(), or strip() on Java 11 and later, which also removes Unicode whitespace that trim() leaves behind. “Collapse repeated spaces into one” is replaceAll("\\s+", " "). “Remove all non-alphanumeric characters” is the same idea with a different character class. Always confirm whether tabs and newlines count as whitespace for this question.

19. Remove Duplicate Characters from a String

Keep the first occurrence of every character and drop the rest, preserving order: "programming" becomes "progamin". A LinkedHashSet does this in one pass, because it ignores repeats and remembers first-seen order. Avoid the tempting version that calls sb.indexOf(...) for every character; it works, but each check scans the whole builder, so the total is O(n²).

static String removeDuplicateChars(String s) {
    Set<Character> seen = new LinkedHashSet<>();           // keeps first-seen order
    for (char c : s.toCharArray()) seen.add(c);
    StringBuilder sb = new StringBuilder(seen.size());
    for (char c : seen) sb.append(c);
    return sb.toString();
}

removeDuplicateChars("programming") returns "progamin", "aabbcc" returns "abc", and an empty string returns an empty string. Time is O(n) and space is O(k) for k distinct characters. If the interviewer wants the characters that appear only once instead, that is a different question and goes back to the counting map from the frequency problem.

Brute Force and Follow-Ups

Starting point. Checking each character against the output built so far with sb.indexOf is simple, but every call scans the builder, so the total is O(n²). Using a set to remember what has been seen turns each check into an O(1) lookup. LinkedHashSet is the most compact form, because it both removes repeats and remembers the first-seen order, so the output can be read straight from the set.

Follow-ups to expect. A related question is “remove the characters that appear more than once, keeping only those that are unique”, which needs the counting map instead. Another is “keep the last occurrence instead of the first”, which you can solve by walking the string backwards and reversing the result. A third is “do it ignoring case but keep the original characters”, which needs a set of lowercase keys alongside the output. Mention that the set approach uses O(k) memory for k distinct characters.

20. Count the Words in a Sentence

Trim the string, split on one or more whitespace characters, and take the length of the array. The two edge cases are what the question is really about. Splitting an empty string with split("\\s+") gives an array with one empty element, so an empty or all-space input would wrongly count as one word unless you check for it. Counting spaces and adding one fails for the same reason and also breaks on repeated spaces.

static int countWords(String s) {
    if (s == null) return 0;
    String trimmed = s.trim();
    return trimmed.isEmpty() ? 0 : trimmed.split("\\s+").length;
}

countWords("Java is awesome") returns 3, " hello world " returns 2, and "", " " and null all return 0. Time and space are O(n). If memory matters for very long text, loop through the characters and count transitions from whitespace to non-whitespace instead; that needs no array at all.

Brute Force and Follow-Ups

Starting point. Counting spaces and adding one is the version many candidates write first, and it fails on leading and trailing spaces, on runs of several spaces, and on an empty string. The trim and split("\\s+") combination handles those cases once you add an explicit check for the empty result. A single manual pass that counts transitions from whitespace to a non-whitespace character handles everything with no array and no regular expression.

Follow-ups to expect. Expect “words may also be separated by punctuation”, which suggests splitting on \W+, or better, extracting runs of letters. “Count the unique words” puts the words into a set, and “which word appears most often?” uses a frequency map. For multilingual text, a whitespace split is not always the right definition of a word, and java.text.BreakIterator exists for that case. State your definition of a word before you write code.

21. Check That a String Contains Only Digits

The regex answer is s.matches("\\d+"). The manual answer loops and checks each character. Both are fine, and a good answer notes one subtlety: Character.isDigit returns true for digits from other scripts (the Arabic-Indic digit three, for example), while the \d in Java regex matches only ASCII digits by default. If the requirement is “a number I can parse with Integer.parseInt“, compare against '0' and '9' directly.

static boolean isDigitsOnly(String s) {
    if (s == null || s.isEmpty()) return false;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c < '0' || c > '9') return false;              // ASCII digits only
    }
    return true;
}

isDigitsOnly("12345") is true, "12a45" is false, "12 3" is false, and the empty string is false, because “only digits” is normally meant to require at least one. State that choice when you code it. Time is O(n) and space is O(1). Remember that a digits-only string can still overflow an int, so a numeric check on its own does not prove it is safe to parse.

Brute Force and Follow-Ups

Starting point. Trying Integer.parseInt and catching NumberFormatException looks quick, but it accepts a leading plus or minus sign and fails on valid digit strings that are too long for an int. A loop that checks every character is exact. The regular expression \d+ does the same in one line. The two differ from Character.isDigit, which also accepts digits from other scripts, so match what the requirement actually asks.

Follow-ups to expect. Interviewers often extend it to “is this a valid decimal number?”, which can be done with the pattern -?\d+(\.\d+)?, or to “is this a number that fits in an int?”, which needs a range check after the digit check. Leading zeros are another discussion point: whether "007" is valid depends on the requirement. In test automation the same check validates fields that must contain only numbers, such as a postcode or an OTP, before the value is used in an assertion.

22. Find the First Repeated Character

Scan left to right with a set. The first character whose add returns false is the answer, because it is the first one to appear a second time. The wording of the question matters here, and it is a good one to clarify aloud. “First character that repeats” can mean the character whose second occurrence comes earliest, or the first character in the string that occurs more than once. They are different questions, and this code answers the first.

static Optional<Character> firstRepeatedChar(String s) {
    Set<Character> seen = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!seen.add(c)) return Optional.of(c);           // add() is false when already present
    }
    return Optional.empty();
}

firstRepeatedChar("programming") returns r, "abc" returns an empty Optional, and "abba" returns b, not a, because the second b arrives before the second a. Under the other interpretation the answer for "abba" would be a, and you would count frequencies first and then scan the string. Time is O(n) and space is O(k). Returning an Optional avoids picking a “not found” character.

Brute Force and Follow-Ups

Starting point. For each position, scanning the characters before it to see whether the current one has appeared is O(n²) and needs no memory. The set-based scan is O(n) and stops at the first character that cannot be added because it is already present. The subtlety is the definition: the set approach returns the character whose second occurrence appears earliest, which is not always the same as the first character in the string that occurs more than once.

Follow-ups to expect. Interviewers use that ambiguity on purpose, so ask which meaning is wanted. For “abba” the first answer is b and the second is a. The second version counts frequencies first and then scans the string for the first character with a count above one. A stream variant is “find the first duplicate in an incoming stream of values”, where the same set works because you never need to look back. Also say that returning an Optional avoids having to choose a special “not found” character.

23. Sort the Characters of a String

Convert the string to a char array, sort it, and build a new string. Strings are immutable, so you cannot sort in place. The same approach is the foundation of the sorted-key anagram check and of grouping anagrams.

static String sortCharacters(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

sortCharacters("dcba") returns "abcd" and "banana" returns "aaabnn". Sorting is by character code, so uppercase letters come before lowercase ones: "baBA" becomes "ABab". If the question wants a case-insensitive order, you need a different approach, such as sorting boxed Characters with a comparator. Arrays.sort on a primitive array is O(n log n) time. For a fixed alphabet such as lowercase a to z, counting sort does it in O(n).

Brute Force and Follow-Ups

Starting point. Writing your own bubble sort or selection sort on the character array is O(n²), and it is the example of what not to hand-write in an interview when Arrays.sort exists. For primitives the JDK uses a dual-pivot quicksort, which is O(n log n) on average. If the characters come from a small, known alphabet such as a to z, counting sort does the job in O(n) with a 26-element array.

Follow-ups to expect. Likely extensions are “sort case-insensitively”, which needs boxed Character objects and a comparator because the natural order puts every uppercase letter before every lowercase letter, and “sort by frequency”, which needs the counting map and a comparator that orders by count and breaks ties by character. A conceptual question is why you cannot sort a String in place: it is immutable, so you always copy to a char array first. The sorted form of a string is also the key used in the anagram problems.

24. Print All Substrings of a String

Fix a start index, extend the end index one step at a time, and take substring(start, end) each time. A string of length n has n(n + 1) / 2 substrings, so the output size alone is quadratic.

static List<String> allSubstrings(String s) {
    List<String> out = new ArrayList<>();
    for (int start = 0; start < s.length(); start++) {
        for (int end = start + 1; end <= s.length(); end++) {
            out.add(s.substring(start, end));
        }
    }
    return out;
}

allSubstrings("abc") returns [a, ab, abc, b, bc, c], a four-character string gives 10 results, and the empty string gives none. The code does O(n²) iterations, but each substring call copies characters, so the real cost is O(n³) time, and storing them all takes O(n³) characters of space. In an interview this is usually a building block, for example for a brute-force palindrome check, and the follow-up is to replace it with something smarter, such as expanding around a centre.

Brute Force and Follow-Ups

Starting point. This problem is the brute force: two nested loops choosing a start and an end. The honest complexity is O(n³), because the loops are O(n²) and each substring call copies up to n characters. There are n(n + 1) / 2 substrings, so the output alone is quadratic in size, and printing or storing them takes cubic space in characters. If you only need to know how many substrings there are, the formula answers in O(1) without generating anything.

Follow-ups to expect. Interviewers often ask for “all distinct substrings”, which puts the results in a HashSet, and for “all subsequences”, which is a different problem with 2 to the power n results, solved by recursion or a bitmask over the positions. They may also ask you to improve a brute-force palindrome check built on top of this, which leads back to expanding around a centre. A good closing remark is that most real tasks do not need every substring; they need a property of them, and a window or a map answers that directly.

Java Array Programming Questions

Arrays in Java are fixed-size and zero-indexed, and the vocabulary trips people up: arr.length is a field on arrays, length() is a method on String, and size() belongs to collections. The Arrays utility class does the routine work. Arrays.toString prints, Arrays.equals compares contents, Arrays.copyOf resizes, and Arrays.sort sorts in O(n log n). Primitive arrays use a dual-pivot quicksort, and object arrays use a stable merge-based sort (TimSort). The Arrays Javadoc is worth ten minutes before an interview.

Most array problems come down to one of two moves: a hash map or set when you need to remember what you have already seen, and two pointers when you can reorganise the array in place. The problems below alternate between them on purpose.

25. Reverse an Array in Place

This is the same two-pointer swap as the string version, but done directly on the array, so space is O(1). It is also the building block for rotating an array and a matrix later on this page, which is why the range version is split out.

static void reverseRange(int[] a, int i, int j) {
    while (i < j) {
        int tmp = a[i];
        a[i++] = a[j];
        a[j--] = tmp;
    }
}

static void reverseArray(int[] a) {
    reverseRange(a, 0, a.length - 1);
}

Reversing {1, 2, 3, 4, 5} gives {5, 4, 3, 2, 1}, an even-length array works the same way, and an empty array is a no-op. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Copying the elements into a new array in reverse order is the easy answer. It is O(n) time and O(n) extra space, and it leaves the original untouched, which can be exactly what a caller wants. The two-pointer swap works in place with O(1) extra space and only visits half of the elements. Which one is right depends on whether the caller expects the array to be modified.

Follow-ups to expect. Expect “reverse only a section”, which is what the range helper does, and it is the building block of array and matrix rotation. For collections, Collections.reverse(list) does it for a List. A classic trap is Arrays.asList(intArray): for a primitive int[] it produces a list with a single element, the array itself, so reversing that list changes nothing. Use Integer[] or convert the values to a List first.

26. Find the Largest and Second Largest Element

Sorting the array and reading the last two elements is correct and O(n log n), and it also changes the caller’s array. A single pass is O(n) with O(1) space: keep the two biggest values seen so far. The detail that catches people is duplicates. In {5, 5, 3}, is the second largest 5 or 3? Most versions of the question want the second largest distinct value, which is what this code returns.

static int[] largestAndSecondLargest(int[] a) {
    long first = Long.MIN_VALUE, second = Long.MIN_VALUE;
    for (int n : a) {
        if (n > first) {
            second = first;
            first = n;
        } else if (n > second && n < first) {
            second = n;
        }
    }
    if (second == Long.MIN_VALUE) {
        throw new IllegalStateException("No distinct second largest value");
    }
    return new int[] { (int) first, (int) second };
}

For {12, 35, 1, 10, 34, 1} the result is [35, 34]. For {5, 5, 3} it is [5, 3]. For {7, 7, 7} or a single element there is no distinct second value, so the method throws instead of returning a misleading number. The running values are long because starting them at Integer.MIN_VALUE would wrongly reject an array that genuinely contains that value. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Sorting and taking the second element from the end is O(n log n) and changes the caller’s array unless you copy it. It also forces a decision about duplicates: in {5, 5, 3}, the element at the second-last position is 5. A two-pass version finds the maximum first and then the largest value strictly below it, which is O(n) but reads the data twice. The single-pass version tracks both values as it goes.

Follow-ups to expect. The generalisation is “find the kth largest element”, which is solved with a min-heap of size k or with quickselect, both covered later on this page. Equally likely is “find the second smallest”, which mirrors the same logic. Interviewers love the edge cases: an array with a single element, an array whose values are all equal, and an array containing Integer.MIN_VALUE. The long sentinels in the solution exist for that last case.

27. Remove Duplicates from a Sorted Array in Place

Because the array is sorted, duplicates sit next to each other. Keep a write index for the next unique slot and a read index scanning ahead, and copy a value only when it differs from the last one written. The method returns the new length k, and only the first k elements are meaningful.

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;
}

On {1, 1, 2, 2, 3, 4, 4} the method returns 4 and the first four elements are {1, 2, 3, 4}. Whatever sits after index 3 is leftover data, so never read past k. Time is O(n), space is O(1). If the array is not sorted, this approach is wrong; use a LinkedHashSet or sort first, and say which trade-off you chose.

Brute Force and Follow-Ups

Starting point. One brute force copies the unique values into a new array through a set. It is O(n) time but uses O(n) space and loses the benefit of the sorted input. Another shifts all the following elements left every time it finds a duplicate, which is O(n²). The two-pointer solution uses the sorted order to compare each element only with the last unique value written, so it needs one pass and no extra space.

Follow-ups to expect. The usual variation is “allow each value to appear at most twice”, which compares the current element with the one two positions behind the write pointer instead of one position behind. Another is “remove all occurrences of a given value in place”, which is nearly the same loop. For an unsorted array the technique fails, so say plainly that you would use a set or sort first. Always clarify what the method should return, because here it returns the new length and the tail of the array is left as it was.

28. Find the Missing Number in 1 to n

An array holds the numbers 1 to n with one missing. The sum of 1 to n is n(n+1)/2, so subtract the actual sum and what remains is the missing number. Use long for the sums: with n around 100,000 the expected total is over five billion, which overflows an int.

static int missingNumber(int[] a, int n) {
    long expected = (long) n * (n + 1) / 2;
    long actual = 0;
    for (int x : a) actual += x;
    return (int) (expected - actual);
}

{1, 2, 4, 5, 6} with n = 6 gives 3. XOR-ing all the numbers 1 to n with all the array elements also works, with no overflow risk, and is a good alternative to mention. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Checking every number from 1 to n with a search through the array is O(n²). Sorting the array and looking for the first gap is O(n log n). A boolean array of size n marking the numbers seen is O(n) time but also O(n) space. The sum formula is O(n) time and O(1) space, and the only trap is overflow, which is why the solution uses a long for the sums.

Follow-ups to expect. Interviewers often ask for the XOR approach: XOR all numbers from 1 to n with all the array elements, and what remains is the missing number, with no overflow risk. Harder versions ask for two missing numbers, or for one duplicate and one missing value, which need either the sum and the sum of squares or in-place marking. If the range is 0 to n instead of 1 to n, the formula changes slightly, so confirm the range before you code.

29. Two Sum

Find two numbers that add up to a target and return their indices. The brute force checks every pair and is O(n²). The standard improvement stores each value’s index in a HashMap as you scan and, for each element, asks whether target - value has been seen already. One pass, O(n) time, O(n) space.

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

{2, 7, 11, 15} with target 9 returns [0, 1]. {3, 2, 4} with target 6 returns [1, 2], which shows why the same element cannot be used twice (3 + 3 would be wrong there). {3, 3} with target 6 returns [0, 1], which works because the map is checked before the current value is stored. If the interviewer says the array is already sorted, switch to two pointers moving inward and drop the extra space.

Brute Force and Follow-Ups

Starting point. Checking every pair with two nested loops is O(n²) time and O(1) space, and it is the correct first answer to say aloud. The hash-map version stores each value with its index as it scans, and for every element asks whether the complement has already been seen. That makes it one pass, O(n) time and O(n) space. Checking the map before storing the current value is what prevents an element from pairing with itself.

Follow-ups to expect. If the array is sorted, move two pointers inward from both ends and you need no map. If the question asks for all pairs, or for the count of pairs, the map must hold counts instead of single indexes. The natural next problems are three sum and four sum, which build on this idea, and “two sum with a data stream”, where numbers arrive one at a time and you maintain a map. Be clear about whether the answer should be the values or the indices.

30. Move All Zeros to the End

Move every zero to the end while keeping the order of the non-zero elements, in place. Keep a write index for the next non-zero slot, scan with a read index, and swap each non-zero element into position.

static void moveZeros(int[] a) {
    int write = 0;
    for (int read = 0; read < a.length; read++) {
        if (a[read] != 0) {
            int tmp = a[write];
            a[write] = a[read];
            a[read] = tmp;
            write++;
        }
    }
}

{0, 1, 0, 3, 12} becomes {1, 3, 12, 0, 0}. An all-zero array or an array with no zeros is left unchanged. One pass, O(n) time, O(1) space. When the read and write indexes are equal the swap is a harmless self-swap.

Brute Force and Follow-Ups

Starting point. Creating a new array, copying the non-zero values first and then filling the rest with zeros, is O(n) with O(n) extra space. A bubble-sort-style approach that swaps zeros towards the end one step at a time is O(n²). The write-pointer method keeps the relative order of the non-zero elements, which is the actual requirement, and it works in place with one pass.

Follow-ups to expect. A cleaner way to see the solution is as a partition by a predicate: everything that satisfies “is not zero” goes to the front in its original order. That insight solves “move all zeros to the front” and “move all even numbers to the front” with the same loop. A subtle optimisation is to skip the swap when the read and write indexes are equal, which avoids pointless writes on an array with no zeros. Interviewers sometimes ask you to minimise the total number of writes, which is the reason to mention it.

31. Rotate an Array by k Positions

Rotate the array to the right by k positions, in place. Copying into a second array is easy but costs O(n) space. The in-place version is three reversals: reverse the whole array, then reverse the first k elements, then reverse the rest.

static void rotateRight(int[] a, int k) {
    int n = a.length;
    if (n == 0) return;
    k = ((k % n) + n) % n;
    reverseRange(a, 0, n - 1);
    reverseRange(a, 0, k - 1);
    reverseRange(a, k, n - 1);
}

{1, 2, 3, 4, 5, 6, 7} with k = 3 becomes {5, 6, 7, 1, 2, 3, 4}. The modulo line reduces k to the array length, so a k larger than the array works, and a negative k rotates left. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Rotating by one position, k times, is O(n · k). Copying into a second array, placing each value at index (i + k) % n, is O(n) time but O(n) space. The three-reversal approach achieves O(n) time and O(1) space, which is why it is the expected answer. Reducing k modulo n first matters: rotating an array of length 7 by 7, or by 70, should do nothing.

Follow-ups to expect. Rotating left by k is the same with k replaced by n – k, or with a negative k as in the solution. A more advanced answer is the cyclic-replacement method, which moves each element directly to its final position and follows the cycles created by the greatest common divisor of n and k. Interviewers may also ask the same question for a string or a linked list. Mention that the standard library already offers Collections.rotate(list, distance) for lists, which you would use in production code.

32. Maximum Subarray Sum (Kadane’s Algorithm)

At each element, decide whether to extend the running subarray or start fresh from here. Whichever is larger becomes the new running value, and the best value seen so far is tracked alongside it. The maximum subarray problem article covers the history if you want it.

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;
}

{-2, 1, -3, 4, -1, 2, 1, -5, 4} gives 6, from the subarray {4, -1, 2, 1}. An all-negative array such as {-3, -1, -2} gives -1, and this is the case that catches solutions which start the best value at 0. The method needs a non-empty array. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Computing the sum of every subarray with two nested loops is O(n²) when the running sum is updated incrementally, and O(n³) if each sum is recomputed from scratch. Kadane’s algorithm replaces that with one decision per element: either extend the current run or start a new one at this element. That works because a run with a negative total can only make any later run worse, so it is always better to drop it.

Follow-ups to expect. “Return the start and end indexes of the best subarray” needs two extra variables that record where the current run began. “Maximum product subarray” is trickier because a negative number can turn the smallest product into the largest, so you track both the minimum and the maximum. The circular-array version combines Kadane with the total sum. If an empty subarray is allowed, the answer can never be below zero, so the all-negative case changes; always check that detail.

33. Merge Two Sorted Arrays

This is the merge step of merge sort, so it is worth knowing cold. Walk both arrays with one index each and always take the smaller front element. When one array runs out, copy the rest of the other.

static int[] mergeSorted(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;
}

{1, 3, 5} and {2, 4, 6, 8} merge to {1, 2, 3, 4, 5, 6, 8}. Using <= in the comparison means that on a tie the element from the first array goes first, which keeps the merge stable. Time is O(n + m), space is O(n + m) for the output.

Brute Force and Follow-Ups

Starting point. Concatenating the two arrays and sorting the result is correct and takes O((n + m) log(n + m)), which wastes the fact that both inputs are already sorted. The two-pointer merge uses that fact to finish in O(n + m). It is the merge step of merge sort, which is a good thing to point out because it shows you understand where the technique comes from.

Follow-ups to expect. A favourite variation gives you a first array with enough free space at the end and asks you to merge the second array into it in place; the trick is to merge from the back, filling the largest values first so nothing is overwritten. Another is “merge k sorted arrays”, solved with a heap later on this page. Using <= rather than < in the comparison keeps the merge stable, which matters when the elements are records sorted by a key.

34. Find Duplicate Elements in an Array

A set remembers what has been seen. Add each element to it, and if add returns false, the value is a duplicate. Collecting the duplicates in a LinkedHashSet means each repeated value is reported once, in the order it was first detected.

static List<Integer> findDuplicates(int[] a) {
    Set<Integer> seen = new HashSet<>();
    Set<Integer> duplicates = new LinkedHashSet<>();
    for (int x : a) {
        if (!seen.add(x)) duplicates.add(x);
    }
    return new ArrayList<>(duplicates);
}

{4, 2, 7, 2, 9, 4, 4} gives [2, 4], and the 4 appears three times but is reported once. Time is O(n), space is O(n). Alternatives to mention: sort and compare neighbours (O(n log n) time, no extra set), or, if the values are known to be in the range 1 to n, mark visited positions in the array itself for O(1) extra space.

A frequent variation asks only for the first duplicate: stop at the first value whose add returns false. Return an OptionalInt rather than -1, because -1 can be a perfectly valid element of the array and a sentinel value then becomes ambiguous.

static OptionalInt firstDuplicate(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) return OptionalInt.of(x);
    }
    return OptionalInt.empty();
}

{1, 3, 4, 2, 2} gives 2, {1, 2, 3} gives an empty result, and {-1, -1} gives -1 as a real answer, which a “return -1 if none” design could not tell apart from “not found”. Time is O(n) and it stops as soon as it finds the duplicate.

Brute Force and Follow-Ups

Starting point. Comparing every pair of elements is O(n²) and needs no extra memory. Sorting a copy and checking neighbouring values is O(n log n). The set-based scan is O(n) time and O(n) space. Collecting the results in a LinkedHashSet guarantees that a value repeated many times is reported only once, in the order in which it was first found to be a duplicate.

Follow-ups to expect. A well-known constraint turns this into a memory puzzle: the array has n + 1 values, each between 1 and n, so at least one value must repeat; find it in O(1) space. The array can be treated as a linked list of indexes and solved with the same fast and slow pointers used for cycle detection, or by marking visited positions with negative signs. Interviewers also ask for the count of each duplicate, which is the frequency map, and for the first duplicate by position, which stops at the first failed add.

35. Sort an Array of 0s, 1s and 2s

Sort an array containing only 0, 1 and 2 in a single pass, without a general sort. This is the Dutch national flag problem. Keep three regions: everything before low is 0, everything after high is 2, and mid scans the unknown middle.

static void sortZeroOneTwo(int[] a) {
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a, low++, mid++);
        } else if (a[mid] == 1) {
            mid++;
        } else {
            swap(a, mid, high--);
        }
    }
}

static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

{2, 0, 2, 1, 1, 0} becomes {0, 0, 1, 1, 2, 2}. The detail interviewers watch for: after swapping a 2 to the high end, mid does not advance, because the element that came in from the high end has not been examined yet. After swapping a 0 to the low end, both low and mid advance. Time is O(n), space is O(1).

Brute Force and Follow-Ups

Starting point. Counting how many 0s, 1s and 2s there are and then overwriting the array in that order is O(n) time and O(1) space, in two passes. It is perfectly acceptable and simple, and it can be mentioned first. The Dutch national flag algorithm does it in a single pass by maintaining three regions: zeros at the front, twos at the back, and an unexamined middle that shrinks until it disappears.

Follow-ups to expect. The classic detail is that after swapping a 2 to the back, the middle pointer does not move, because the value that arrived has not been looked at yet. Interviewers also ask for the version with k colours, which needs a different approach such as counting sort, and for “partition the array around a pivot”, which is the partition step of quicksort and a three-way partition handles many equal keys well. Naming that connection to quicksort is a useful signal of depth.

36. Product of Array Except Self

Return an array where each element is the product of all the other elements, without using division. Division fails on zeros, and the interviewer will ask about that. The solution fills each slot with the product of everything to its left, then sweeps right to left, multiplying in the product of everything to its right.

static int[] productExceptSelf(int[] a) {
    int n = a.length;
    int[] out = new int[n];
    if (n == 0) return out;
    out[0] = 1;
    for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        out[i] *= right;
        right *= a[i];
    }
    return out;
}

{1, 2, 3, 4} gives {24, 12, 8, 6}. {0, 1, 2} gives {2, 0, 0}, so zeros are handled without special cases. The int product can overflow for large values, so switch to long if the question allows big inputs. Time is O(n), space is O(1) beyond the output array.

Brute Force and Follow-Ups

Starting point. Multiplying all the other elements for every position is O(n²). Multiplying everything once and dividing by each element is O(n), but it fails when the array contains a zero, and the problem statement usually forbids division. The prefix and suffix technique stores the product of everything to the left in the output array, then sweeps from the right with a running product of everything to the right, so no division is needed.

Follow-ups to expect. Interviewers push on zeros. With exactly one zero, every position except the zero’s own is 0, and that position holds the product of the others; with two or more zeros, the whole result is 0. The prefix and suffix method handles all of those cases without any special code, which is its strength. They may also ask about overflow, which suggests long or BigInteger, and about the space: using the output array as workspace keeps the extra space at O(1).

37. Binary Search

Binary search needs sorted input and halves the search range at every step, so it is O(log n). Almost every bug lives in the details: the loop condition (low <= high), the midpoint, and the update (mid + 1 and mid - 1, not mid). Write the midpoint as low + (high - low) / 2 rather than (low + high) / 2, which can overflow on very large arrays.

static int binarySearch(int[] a, int target) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

On {1, 3, 5, 7, 9, 11}, searching for 7 returns 3 and searching for 4 returns -1. Note that the JDK’s Arrays.binarySearch returns -(insertion point) - 1 when the key is missing, not a plain -1, so keep the two conventions straight when you compare results.

Brute Force and Follow-Ups

Starting point. A linear scan is O(n), works on unsorted data, and is the right answer when the array is tiny or unsorted. Binary search needs sorted input and halves the range on every step for O(log n). The common failure points are the loop condition (low <= high), the updates (mid + 1 and mid - 1) and the midpoint calculation, where (low + high) / 2 can overflow for very large arrays.

Follow-ups to expect. Expect “find the first or last occurrence of a value”, which is solved by not stopping when the value is found and continuing to search in one half. Other classics are “search in a rotated sorted array”, “find the insertion position”, and “binary search on the answer”, where the thing being searched is a numeric result such as the minimum capacity that meets a condition. Interviewers also compare the iterative and recursive forms; the iterative one uses O(1) space, while recursion uses O(log n) stack.

38. Intersection of Two Arrays

Return the values that appear in both arrays, each reported once. Put the first array in a HashSet, scan the second, and collect matches in a TreeSet so the output comes out sorted and free of duplicates. If both arrays are already sorted, two pointers do the same job with no extra set.

static int[] intersection(int[] a, int[] b) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) seen.add(x);
    Set<Integer> common = new TreeSet<>();
    for (int x : b) {
        if (seen.contains(x)) common.add(x);
    }
    int[] out = new int[common.size()];
    int i = 0;
    for (int x : common) out[i++] = x;
    return out;
}

{1, 2, 2, 1} and {2, 2} give {2}, {4, 9, 5} and {9, 4, 9, 8, 4} give {4, 9}, and arrays with nothing in common give an empty array. Time is O(n + m) for the lookups plus the cost of ordering the result. Ask whether the interviewer wants each common value once or as many times as it appears in both arrays; the second version needs a count map instead of a set.

Brute Force and Follow-Ups

Starting point. Comparing every element of one array with every element of the other is O(n · m), and you still have to remove duplicates from the result. Putting the first array in a HashSet and checking the second against it is O(n + m). If both arrays are sorted, two pointers find the common elements in O(n + m) with no extra structure.

Follow-ups to expect. The first question to ask is whether each common value should appear once or as many times as it occurs in both arrays. The second form needs a count map rather than a set: decrement the count each time a match is found. If one array is much smaller than the other, put the smaller one in the set to save memory. When neither array fits in memory, the discussion moves to external sorting or hashing into partitions, which is where interviewers sometimes take this problem.

39. Kth Largest Element in an Array

Sorting and indexing from the end is O(n log n) and always acceptable as a first answer. The better answer keeps a min-heap of size k: push every element, and whenever the heap grows past k, remove the smallest. When the scan ends, the top of the heap is the kth largest. Time is O(n log k) and space is O(k), which matters when k is small and n is large.

static int kthLargest(int[] a, int k) {
    if (k < 1 || k > a.length) throw new IllegalArgumentException("k out of range");
    PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap holding the k largest so far
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();
}

{3, 2, 1, 5, 6, 4} with k = 2 gives 5, and {3, 2, 3, 1, 2, 4, 5, 5, 6} with k = 4 gives 4. Duplicates count as separate elements, which is why the second answer is 4 and not 3. The method rejects a k outside 1 to n instead of failing with a confusing null-pointer error. Quickselect solves the same problem in O(n) on average, and it is worth a sentence if the interviewer pushes for better.

Brute Force and Follow-Ups

Starting point. Sorting the array and indexing from the end is O(n log n) and is the first answer to give. The min-heap of size k improves it to O(n log k) with O(k) space, because the heap always holds the k largest values seen so far and its smallest element is the answer. When k is close to n, the roles can be reversed: a max-heap of size n – k + 1 finds the same value with less work.

Follow-ups to expect. Quickselect finds the kth largest in O(n) on average by partitioning like quicksort and recursing into only one side, with an O(n²) worst case unless the pivot is chosen randomly. A streaming variant asks for the kth largest after every new number arrives, and the same heap maintained between calls solves it. Be sure to clarify whether duplicates count as separate elements; in this solution, the second largest of {5, 5, 3} is 5, not 3.

40. First Missing Positive

Find the smallest positive integer that is not in the array, in O(n) time and O(1) extra space. A set solves it in O(n) space. The constant-space trick is to use the array as its own hash table: place each value v from 1 to n at index v – 1 by swapping, then scan for the first index where the value is wrong. The answer is that index plus one, or n + 1 if everything is in place.

static int firstMissingPositive(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        while (a[i] > 0 && a[i] <= n && a[a[i] - 1] != a[i]) {
            Solutions.swap(a, i, a[i] - 1);               // put value v at index v - 1
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] != i + 1) return i + 1;
    }
    return n + 1;
}

{1, 2, 0} gives 3, {3, 4, -1, 1} gives 2, {7, 8, 9, 11, 12} gives 1 and {1, 2, 3} gives 4. The inner while looks like it might be quadratic, but every swap places one value permanently, so the total number of swaps is at most n. The check a[a[i] - 1] != a[i] also stops the loop from spinning forever on duplicates such as {1, 1}. Note that the method modifies its input; say so, or copy the array first.

Brute Force and Follow-Ups

Starting point. Sorting and scanning is O(n log n). A hash set of all the values, then counting up from 1 until a value is missing, is O(n) time and O(n) space. The in-place technique is the real challenge: use the array itself as a hash table by moving every value v in the range 1 to n into position v – 1, then look for the first position that holds the wrong value.

Follow-ups to expect. A central insight is that the answer is always between 1 and n + 1, so any value outside that range can be ignored. Interviewers ask what you would do if you were not allowed to modify the input; then you would copy it or fall back to a set. A related problem, “find all numbers disappeared from an array of 1 to n”, uses the same swap or negative-marking idea. The inner loop of the solution looks quadratic, but each swap puts at least one value in its final position, so the whole thing is O(n).

41. Majority Element (Boyer-Moore Voting)

Find the element that appears more than n/2 times, assuming one exists. Counting with a HashMap is O(n) time and O(n) space. Boyer-Moore voting does it in O(1) space: keep a candidate and a counter, add one when the next value matches the candidate, subtract one when it does not, and adopt a new candidate whenever the counter hits zero. A true majority element cannot be cancelled out by all the others.

static int majorityElement(int[] a) {
    int candidate = 0, count = 0;
    for (int x : a) {
        if (count == 0) candidate = x;
        count += (x == candidate) ? 1 : -1;
    }
    return candidate;                                      // valid only if a majority element exists
}

{2, 2, 1, 1, 1, 2, 2} gives 2 and {3, 2, 3} gives 3. The catch is in the comment on the return line: if no majority exists, the method still returns some value. If the problem does not guarantee a majority, add a second pass that counts the candidate and confirms it.

Brute Force and Follow-Ups

Starting point. Counting every element with a nested loop is O(n²). A HashMap of counts is O(n) time and O(n) space. Sorting and taking the middle element is O(n log n), and it works because a value that appears more than n/2 times must occupy the middle position. Boyer-Moore voting is O(n) with O(1) space, and its idea is that every non-majority element can cancel out at most one occurrence of the majority element.

Follow-ups to expect. The standard generalisation is “find all elements that appear more than n/3 times”, which uses two candidates and two counters. If the problem does not promise that a majority element exists, add a second pass that counts the final candidate and confirms it passes the threshold, because the voting phase alone returns something even when nothing qualifies. A bit-by-bit approach, taking the majority bit at each position, also works, and it is occasionally asked as a curiosity.

42. Merge Overlapping Intervals

Given a list of intervals, merge the ones that overlap. Sort by start time, then walk through: if the next interval starts at or before the current end, extend the end; otherwise, close the current interval and start a new one. In test automation the same logic merges time ranges, for example finding how long a set of parallel tests kept a shared environment busy.

static int[][] mergeIntervals(int[][] intervals) {
    if (intervals.length == 0) return new int[0][];
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (x, y) -> Integer.compare(x[0], y[0]));
    List<int[]> merged = new ArrayList<>();
    int[] current = sorted[0].clone();
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] <= current[1]) {
            current[1] = Math.max(current[1], sorted[i][1]);
        } else {
            merged.add(current);
            current = sorted[i].clone();
        }
    }
    merged.add(current);
    return merged.toArray(new int[0][]);
}

[[1,3], [2,6], [8,10], [15,18]] becomes [[1,6], [8,10], [15,18]]. [[1,4], [4,5]] becomes [[1,5]], because intervals that touch are treated as overlapping here (confirm that rule with the interviewer). Unsorted input such as [[8,10], [1,4], [2,9]] becomes [[1,10]]. The method sorts a clone so the caller’s array is left alone. Time is O(n log n) for the sort and space is O(n).

Brute Force and Follow-Ups

Starting point. Repeatedly scanning for any two overlapping intervals, merging them, and starting again until no overlaps remain is O(n²) or worse. Sorting by start time first means that overlaps can only occur between neighbours, so a single pass is enough and the total is O(n log n), dominated by the sort. Each interval either extends the current merged interval or starts a new one.

Follow-ups to expect. Expect “insert a new interval into a sorted list of non-overlapping intervals”, and “what is the minimum number of meeting rooms required?”, which is solved with a heap of end times or by sorting the start and end times separately. Always ask whether intervals that merely touch, such as [1, 4] and [4, 5], should be merged; the solution says yes. Sorting a copy rather than the input array is a courtesy to the caller and a detail some interviewers explicitly check.

43. Three Sum

Find all unique triplets that add up to zero. Checking every triple is O(n³). Sort the array, then for each element as an anchor, run the two-pointer technique on the rest: if the sum is too small move the left pointer up, if too large move the right pointer down. Skipping repeated anchors and repeated values after a hit is what keeps the output free of duplicate triplets.

static List<List<Integer>> threeSum(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < a.length - 2; i++) {
        if (a[i] > 0) break;
        if (i > 0 && a[i] == a[i - 1]) continue;           // skip duplicate anchors
        int left = i + 1, right = a.length - 1;
        while (left < right) {
            int sum = a[i] + a[left] + a[right];
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.add(Arrays.asList(a[i], a[left], a[right]));
                left++;
                right--;
                while (left < right && a[left] == a[left - 1]) left++;
                while (left < right && a[right] == a[right + 1]) right--;
            }
        }
    }
    return result;
}

{-1, 0, 1, 2, -1, -4} gives [[-1, -1, 2], [-1, 0, 1]], {0, 0, 0, 0} gives [[0, 0, 0]], and arrays with fewer than three useful elements give an empty list. Time is O(n²) and space is O(1) beyond the output and the sorted copy. The two dedup lines are where most candidates lose marks, so practise them until you can write them without thinking.

Brute Force and Follow-Ups

Starting point. Three nested loops over all triples is O(n³), and you still need a way to avoid reporting the same triple twice, usually by sorting each triple and placing it in a set. Sorting the array first lets you fix one number and use two pointers to find the other two in linear time, so the total is O(n²). The skipping of repeated anchor values and repeated pointer values is what keeps the output free of duplicates without a set.

Follow-ups to expect. Variations include “3Sum closest”, which tracks the sum nearest to the target instead of looking for an exact match; “4Sum”, which adds one more loop for O(n³); and “count the triplets” instead of listing them. Interviewers like to ask why the loop can stop once the anchor is positive: in a sorted array, three non-negative numbers whose first one is positive cannot sum to zero. Mention that integer overflow is possible with very large values.

44. Subarray Sum Equals K

Count the contiguous subarrays whose sum is exactly k. The array can contain negatives, so a sliding window does not work. Use prefix sums: if the running sum up to the current index is S, then every earlier prefix with sum S – k marks the start of a subarray ending here that adds up to k. A HashMap from prefix sum to how many times it has occurred gives the answer in one pass.

static int subarraySumEqualsK(int[] a, int k) {
    Map<Integer, Integer> prefixCounts = new HashMap<>();
    prefixCounts.put(0, 1);                                // the empty prefix
    int sum = 0, count = 0;
    for (int x : a) {
        sum += x;
        count += prefixCounts.getOrDefault(sum - k, 0);
        prefixCounts.merge(sum, 1, Integer::sum);
    }
    return count;
}

{1, 1, 1} with k = 2 gives 2, {1, 2, 3} with k = 3 gives 2 (the subarrays {1, 2} and {3}), and {1, -1, 0} with k = 0 gives 3. Seeding the map with 0 -> 1 is the detail that makes subarrays starting at index 0 count. Time is O(n) and space is O(n). This prefix-sum-plus-map idea is one of the most reusable patterns in interviews.

Brute Force and Follow-Ups

Starting point. Checking every subarray and summing it is O(n²) with a running sum, which is acceptable only for small arrays. The prefix-sum method turns the question into a lookup: the sum of a subarray ending at index i equals k exactly when some earlier prefix sum equals the current prefix sum minus k. Keeping a map from each prefix sum to the number of times it has occurred answers every position in O(1).

Follow-ups to expect. “Find the longest subarray with sum k” changes the map to store only the first index at which each prefix sum appeared. “Count subarrays whose sum is divisible by k” uses the prefix sum modulo k as the key. A good conceptual question is why a sliding window does not work here: with negative numbers, adding an element can decrease the sum and removing one can increase it, so the window has no direction in which to move. The seed entry for the empty prefix is the detail that is most often forgotten.

45. Longest Consecutive Sequence

Find the length of the longest run of consecutive integers in an unsorted array, for example {100, 4, 200, 1, 3, 2} contains 1, 2, 3, 4. Sorting is O(n log n). The O(n) approach puts everything in a HashSet and only starts counting from numbers that have no predecessor in the set, so each run is walked exactly once.

static int longestConsecutive(int[] a) {
    Set<Integer> set = new HashSet<>();
    for (int x : a) set.add(x);
    int best = 0;
    for (int x : set) {
        if (!set.contains(x - 1)) {                        // x starts a run
            int len = 1;
            while (set.contains(x + len)) len++;
            best = Math.max(best, len);
        }
    }
    return best;
}

The example gives 4, {0, 3, 7, 2, 5, 8, 4, 6, 0, 1} gives 9 (0 through 8, with the duplicate 0 ignored), and an empty array gives 0. The line !set.contains(x - 1) is what avoids the quadratic behaviour: without it you would re-walk the same run from every element inside it. Time is O(n) and space is O(n).

Brute Force and Follow-Ups

Starting point. Sorting the array and scanning for runs is O(n log n) and is fine if the interviewer does not insist on linear time. The linear solution puts all values in a HashSet and counts a run only when it starts at a value whose predecessor is not in the set. Without that start test, you would recount the same run from every element inside it and the algorithm would drift back to O(n²).

Follow-ups to expect. Expect “return the actual sequence”, which means remembering the start of the best run, and “what if the array contains duplicates?”, which the set handles automatically. A union-find version also solves it by uniting each number with its neighbours and then taking the largest component, and it is a good alternative to mention. If the interviewer asks about numbers arriving as a stream, a map of run lengths keyed by run endpoints supports O(1) updates.

46. Best Time to Buy and Sell Stock

Given daily prices, find the maximum profit from one buy followed by one later sell. Track the lowest price seen so far and, at each day, the profit if you sold today. It is Kadane’s idea in another form: a running best-so-far combined with a running minimum.

static int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        best = Math.max(best, p - minPrice);
    }
    return best;
}

{7, 1, 5, 3, 6, 4} gives 5 (buy at 1, sell at 6). {7, 6, 4, 3, 1} gives 0, because prices only fall and the best choice is not to trade. An empty array also gives 0. Time is O(n) and space is O(1). The follow-up is to allow as many transactions as you like, where the answer is the sum of every positive day-over-day gain.

Brute Force and Follow-Ups

Starting point. Trying every pair of days, with a buy day before a sell day, is O(n²). The single pass tracks the lowest price seen so far and, at each day, computes the profit if you sold today. That is exactly Kadane’s idea applied to price differences. It needs only two variables and answers zero when prices never rise, which is the correct “do nothing” result.

Follow-ups to expect. The follow-ups form a family: “as many transactions as you like” is the sum of every positive day-to-day rise; “at most two transactions” needs dynamic programming with four state variables; “with a cooldown day” or “with a transaction fee” are further extensions of the same state machine. If you are asked to return the buy and sell days as well, record the index of the minimum and the index at which the best profit was found. Clarify early whether you may buy and sell on the same day.

47. Container With Most Water

Each number is the height of a vertical line. Pick two lines that, together with the x-axis, hold the most water. Start with the widest pair, then move the pointer at the shorter line inward, because moving the taller one can never improve the area when the width is shrinking.

static int maxArea(int[] heights) {
    int left = 0, right = heights.length - 1, best = 0;
    while (left < right) {
        best = Math.max(best, Math.min(heights[left], heights[right]) * (right - left));
        if (heights[left] < heights[right]) left++;
        else right--;
    }
    return best;
}

{1, 8, 6, 2, 5, 4, 8, 3, 7} gives 49, from the lines of height 8 and 7 that are 7 apart, and {1, 1} gives 1. Time is O(n) and space is O(1). The reason interviewers like it is the justification: you have to explain why discarding the shorter line is safe, and that explanation matters more than the code.

Brute Force and Follow-Ups

Starting point. Computing the area for every pair of lines is O(n²). The two-pointer approach starts with the widest container and moves the pointer at the shorter line inward. The reasoning is the heart of the problem: the area is limited by the shorter line, so keeping the shorter line and shrinking the width can only make the area smaller, and the only chance of improvement is to discard the shorter line.

Follow-ups to expect. Interviewers usually ask why the shorter side is the one to move, and a clear one-sentence proof is worth more than code. A related problem, trapping rain water, appears later in this guide and uses similar pointer reasoning. Expect a question about equal heights: when both lines are the same height, either pointer can move. If asked about a three-dimensional version, say it needs a heap and a different technique.

48. Rotate a Matrix by 90 Degrees

Rotate an n by n matrix clockwise, in place. Transpose the matrix (swap element [i][j] with [j][i]) and then reverse every row. It reuses the reverseRange helper from the array-reversal problem, which is a nice way to show how the small building blocks combine.

static void rotateMatrix(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++) {                          // transpose
        for (int j = i + 1; j < n; j++) {
            int tmp = m[i][j];
            m[i][j] = m[j][i];
            m[j][i] = tmp;
        }
    }
    for (int[] row : m) Solutions.reverseRange(row, 0, n - 1);   // then reverse each row
}

[[1,2,3], [4,5,6], [7,8,9]] becomes [[7,4,1], [8,5,2], [9,6,3]], and [[1,2], [3,4]] becomes [[3,1], [4,2]]. Time is O(n²), which is optimal because every cell has to move, and extra space is O(1). For a counter-clockwise rotation, reverse the rows first and then transpose, or transpose and reverse the columns.

Brute Force and Follow-Ups

Starting point. Allocating a second matrix and writing each element to its rotated position, result[c][n - 1 - r] = m[r][c], is simple and uses O(n²) extra space. The in-place solution transposes the matrix and reverses each row, which has the same time cost and O(1) extra space. A third method rotates four cells at a time, layer by layer, and is the version to present if the interviewer asks for a single pass.

Follow-ups to expect. “Rotate counter-clockwise” reverses the rows first and then transposes, or transposes and then reverses the columns. A non-square matrix cannot be rotated in place, because its shape changes, so you must return a new matrix. Another variation is “rotate the image by 180 degrees”, which is two rotations or a double reversal. Mention that the transposition loop starts the inner index at i + 1 so that each pair is swapped once, not twice.

49. Top K Frequent Elements

Return the k most frequent values. Count with a map, then keep a min-heap of size k ordered by count, dropping the least frequent entry whenever the heap exceeds k. Time is O(n log k). Bucket sort by frequency gets it to O(n) and is the usual follow-up.

static List<Integer> topKFrequent(int[] a, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int x : a) counts.merge(x, 1, Integer::sum);
    PriorityQueue<Map.Entry<Integer, Integer>> heap =
            new PriorityQueue<>((x, y) -> Integer.compare(x.getValue(), y.getValue()));
    for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
        heap.offer(e);
        if (heap.size() > k) heap.poll();
    }
    List<Integer> out = new ArrayList<>();
    while (!heap.isEmpty()) out.add(heap.poll().getKey());
    Collections.reverse(out);                              // most frequent first
    return out;
}

{1, 1, 1, 2, 2, 3} with k = 2 gives [1, 2]. The heap pops the least frequent first, so the result is reversed to put the most frequent value at the front. If two values tie for the last place, the problem usually says any answer is fine, so check. This is the same shape as finding the most frequent error messages in a test log or the slowest endpoints in a performance run.

Brute Force and Follow-Ups

Starting point. Counting values and sorting all the distinct entries by frequency is O(d log d) for d distinct values, and it is the simplest correct answer. A min-heap of size k reduces it to O(d log k) and keeps memory small. Bucket sort by frequency does it in O(n): create an array of lists indexed by count, put each value in the bucket for its count, and read the buckets from the highest count downwards.

Follow-ups to expect. “Top K frequent words” adds a tie-break rule, such as alphabetical order, which changes the comparator. Ask what should happen when several values tie for the last place; the problem normally says any one is acceptable. For a data stream, the counts are kept in a map and the heap is refreshed as needed, though an exact answer then needs more care. This pattern is how you would find the most common failures in a test run or the slowest endpoints in a load test.

50. Find the Minimum and Maximum Elements

The simplest array question, and one that still catches people. Start with the first element as both minimum and maximum, then scan the rest once. Starting from Integer.MAX_VALUE and Integer.MIN_VALUE also works, but the first-element start is safer because it needs no assumption about the data. Decide what an empty array should do before you write the loop; here it throws.

static int[] minAndMax(int[] a) {
    if (a == null || a.length == 0) throw new IllegalArgumentException("array must not be empty");
    int min = a[0], max = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] < min) min = a[i];
        else if (a[i] > max) max = a[i];
    }
    return new int[] { min, max };
}

{3, 5, 1, 9, 2} gives minimum 1 and maximum 9, a single-element array gives that element for both, and {-5, -1, -9} gives -9 and -1. Because an element cannot be both a new minimum and a new maximum, the second check is an else if, which saves comparisons. Time is O(n) and space is O(1). With streams, Arrays.stream(a).min() and .max() return an OptionalInt, which handles the empty array for you, at the cost of two passes.

Brute Force and Follow-Ups

Starting point. Sorting the array and taking the first and last elements is O(n log n) and sorts more than the question needs. One pass with two variables is O(n). A well-known refinement compares the elements in pairs, comparing the two members of the pair with each other first and then the smaller with the minimum and the larger with the maximum, which brings the comparison count down to about 3n/2 instead of 2n.

Follow-ups to expect. Interviewers may ask for the minimum and maximum of a two-dimensional array, which is the same loop over both dimensions, or for the positions of the extremes rather than the values. With streams, Arrays.stream(a).min() returns an OptionalInt, which neatly handles the empty array at the cost of two passes. The edge cases to mention are an empty array, a single element, all-equal values, and extreme values such as Integer.MIN_VALUE.

51. Remove Duplicates from an Unsorted Array

When the array is not sorted, the in-place two-pointer trick from earlier does not work. Use a LinkedHashSet: it drops repeats and keeps the order in which values first appeared. Copy the set back into an int array if the caller needs an array.

static int[] removeDuplicatesUnsorted(int[] a) {
    Set<Integer> unique = new LinkedHashSet<>();
    for (int x : a) unique.add(x);
    int[] out = new int[unique.size()];
    int i = 0;
    for (int x : unique) out[i++] = x;
    return out;
}

{1, 2, 2, 3, 4, 4} gives {1, 2, 3, 4}, {3, 1, 3, 2, 1} gives {3, 1, 2} (first-seen order, not sorted), and an empty array gives an empty array. Time is O(n) and space is O(n). The stream version is a single expression: Arrays.stream(a).distinct().toArray(), and for an ordered source it also keeps first-seen order. Return a HashSet instead and the order is no longer guaranteed, which is a common reason answers get marked down.

Brute Force and Follow-Ups

Starting point. The in-place brute force checks each element against everything already kept, which is O(n²) and needs no extra memory. Sorting first and then removing neighbours is O(n log n), but it destroys the original order. The LinkedHashSet approach is O(n) and keeps first-seen order, which is what most interview versions of the question want.

Follow-ups to expect. Expect “keep the last occurrence rather than the first”, which you can do by walking from the right and reversing the output. If the question says “stable” or “preserve order”, the answer is a LinkedHashSet or a HashSet plus a result list; a plain HashSet makes no promise about order. A concise alternative is Arrays.stream(a).distinct().toArray(). Boxing every int into an Integer has a memory cost, so for very large primitive arrays a sort-based or bitset approach may be preferred.

52. Union of Two Arrays

The union is every distinct value that appears in either array. Add both arrays to a LinkedHashSet and the set removes the duplicates for you. It is the mirror image of the intersection problem, where a HashSet records the first array and the second array is checked against it.

static int[] unionOf(int[] a, int[] b) {
    Set<Integer> union = new LinkedHashSet<>();
    for (int x : a) union.add(x);
    for (int x : b) union.add(x);
    int[] out = new int[union.size()];
    int i = 0;
    for (int x : union) out[i++] = x;
    return out;
}

{1, 2, 3} and {3, 4, 5} give {1, 2, 3, 4, 5}, and {1, 1} with an empty array gives {1}. Time is O(n + m) and space is O(n + m). If both arrays are already sorted, a merge-style pass with two pointers produces the sorted union with no set at all, and offering that as the follow-up shows you know the trade-off.

Brute Force and Follow-Ups

Starting point. Concatenating the two arrays and removing duplicates with a nested loop is O(n²). A LinkedHashSet does it in one pass over each array. If both arrays are sorted, a merge with two pointers produces the sorted union in O(n + m) with no extra structure, and it is worth offering as the optimisation.

Follow-ups to expect. Natural neighbours are the intersection (values in both), the difference (values in one but not the other) and the symmetric difference (values in exactly one). For arrays that may contain repeated values, interviewers sometimes ask for a multiset union, which keeps the larger count of each value, and that needs frequency maps. A practical note: in test automation, comparing the union of expected and actual values is the quick way to see everything that either side contains.

53. Frequency Count of Array Elements

Count how many times each value appears. It is the array twin of the character-frequency problem and uses the same merge(x, 1, Integer::sum) idiom, which avoids the longer put(x, getOrDefault(x, 0) + 1) pattern. LinkedHashMap keeps the values in first-seen order so the printed result is predictable.

static Map<Integer, Integer> elementFrequency(int[] a) {
    Map<Integer, Integer> freq = new LinkedHashMap<>();
    for (int x : a) freq.merge(x, 1, Integer::sum);
    return freq;
}

{1, 2, 2, 3, 3, 3} gives {1=1, 2=2, 3=3}, and an empty array gives an empty map. Time is O(n) and space is O(k) for k distinct values. This is the building block for most-frequent-element questions, finding elements that appear exactly once, and checking whether two arrays hold the same multiset of values.

Brute Force and Follow-Ups

Starting point. Counting each value with a nested loop is O(n²). The map-based count is O(n). When the values are small non-negative integers, a plain int[] indexed by value is simpler and faster than a map. The merge(x, 1, Integer::sum) idiom replaces the longer put(x, getOrDefault(x, 0) + 1) form and is worth using consistently.

Follow-ups to expect. Typical extensions are “find the element that appears most often”, “find the elements that appear exactly once”, and “sort the elements by frequency and then by value”. Each of those starts from this map. For sorting by frequency, a stream over the map entries with a comparator is the most readable form. If the range of values is known to be small, mention counting sort. Remember that a HashMap prints in an unspecified order unless you choose LinkedHashMap or TreeMap.

54. Check Whether an Array Is Sorted

A single pass comparing each element with the one before it. The moment one pair is out of order, return false. The questions to ask first are whether equal neighbours are allowed (usually yes) and whether the check is for ascending order, descending, or either.

static boolean isSortedAscending(int[] a) {
    for (int i = 1; i < a.length; i++) {
        if (a[i - 1] > a[i]) return false;
    }
    return true;
}

{1, 2, 3, 4} is sorted, {1, 3, 2} is not, {2, 2, 2} is sorted because the comparison is non-strict, and the empty array and a single element are sorted by definition, since there is no pair to violate the order. Time is O(n) and space is O(1). In test automation this is the check behind “verify the table is sorted by this column”: read the column into a list and run the same loop.

Brute Force and Follow-Ups

Starting point. Copying the array, sorting the copy and comparing the two is O(n log n) and needs extra memory, and it is an example of doing more work than the problem requires. A single scan that compares each element with the previous one is O(n) with no allocation and stops at the first violation. The empty array and the single-element array are sorted by definition, because there is no pair to break the order.

Follow-ups to expect. “Check whether the array is sorted in either ascending or descending order” needs you to detect the direction from the first unequal pair and then keep it consistent. “Is it strictly increasing?” changes the comparison from greater-than to greater-than-or-equal. A tricky variation is “is this a sorted array that has been rotated?”, which holds when there is at most one place where a value is smaller than its predecessor, counting the wrap-around from the last element to the first. For strings, the equivalent check uses compareTo, and UI tables may use locale-aware collation.

55. Find the Leaders in an Array

A leader is an element that is greater than everything to its right. The last element is always a leader. Scan from right to left and keep the running maximum, so each element is compared with just one number instead of every element after it. That brings a brute-force O(n²) answer down to O(n).

static List<Integer> leaders(int[] a) {
    LinkedList<Integer> out = new LinkedList<>();
    int maxFromRight = 0;
    for (int i = a.length - 1; i >= 0; i--) {
        if (i == a.length - 1 || a[i] > maxFromRight) {    // the last element is always a leader
            maxFromRight = a[i];
            out.addFirst(a[i]);                            // addFirst keeps left-to-right order
        }
    }
    return out;
}

{16, 17, 4, 3, 5, 2} gives [17, 5, 2]. Because the scan runs right to left, addFirst puts the results back into left-to-right order; printing as you go instead gives them reversed. {3, 2, 1} gives all three, {1, 2, 3} gives only [3], and {5, 5} gives [5] because “greater than” is strict. The i == a.length - 1 test, rather than starting the maximum at Integer.MIN_VALUE, is what keeps an array whose last value is Integer.MIN_VALUE correct. Time is O(n) and space is O(1) beyond the output.

Brute Force and Follow-Ups

Starting point. For each element, scanning everything to its right to see whether it is larger than all of them is O(n²). Scanning from the right keeps a single running maximum, so each element is compared with one number and the work drops to O(n) with O(1) extra space. The last element is always a leader because nothing lies to its right.

Follow-ups to expect. This problem is a cousin of “next greater element”, which uses a monotonic stack: for each element, find the first larger value to its right. If an interviewer changes the definition to “greater than or equal to everything on its right”, the comparison changes to >=. Printing as you go yields the leaders in reverse order, so mention how you restore the left-to-right order, as the solution does with addFirst. Check the empty-array case.

56. Left Rotate an Array by One Position

Save the first element, shift everything else one place to the left, and put the saved element at the end. System.arraycopy does the shifting and is the idiomatic choice; a plain loop that copies a[i + 1] into a[i] is equally acceptable. For rotating by k positions, use the three-reversal method from the rotate-by-k problem above, where a negative k rotates left.

static void rotateLeftByOne(int[] a) {
    if (a.length < 2) return;
    int first = a[0];
    System.arraycopy(a, 1, a, 0, a.length - 1);            // shift everything one place left
    a[a.length - 1] = first;
}

{1, 2, 3, 4, 5} becomes {2, 3, 4, 5, 1}, and an array with zero or one elements is left unchanged. Time is O(n) and space is O(1). Rotating left by one is O(n) each time, so rotating by k with this method repeatedly would cost O(n · k), which is why the reversal approach is preferred for larger k.

Brute Force and Follow-Ups

Starting point. Allocating a new array and copying each element to index (i + n - 1) % n is O(n) time and space. Saving the first element and shifting the rest is the in-place alternative, and System.arraycopy does the shifting using a fast native copy, which handles overlapping ranges correctly. Writing the shift as a plain loop that copies from i + 1 to i is equivalent.

Follow-ups to expect. Rotating by k positions with this method repeated k times is O(n · k), which is why the three-reversal method is better for larger k. A right rotation by one is the mirror image: save the last element, shift everything right, and place the saved element first. For lists, Collections.rotate(list, -1) does it in one call. A deque, such as ArrayDeque, rotates in O(1) by moving one element from one end to the other, which is worth mentioning if rotation is frequent.

57. Find a Pair With a Given Difference

Does any pair of elements differ by exactly k? For every element x, the partner would be x – k or x + k, so a set of the values seen so far answers each lookup in O(1). One pass, no sorting. The code takes the absolute value of the difference, so a negative k behaves like a positive one.

static boolean hasPairWithDifference(int[] a, int diff) {
    long d = Math.abs((long) diff);                        // long: abs(Integer.MIN_VALUE) overflows an int
    Set<Long> seen = new HashSet<>();
    for (int x : a) {
        if (seen.contains(x - d) || seen.contains(x + d)) return true;
        seen.add((long) x);
    }
    return false;
}

{1, 5, 3, 4, 2} with difference 2 is true (1 and 3), and with difference 10 it is false. A difference of 0 is true only when the array holds a duplicate: {1, 1} is true and {1, 2} is false. The set holds Long values and the difference is a long so that extreme inputs such as Integer.MIN_VALUE cannot overflow. Time is O(n) and space is O(n). On a sorted array, two pointers solve it in O(1) space.

Brute Force and Follow-Ups

Starting point. Checking every pair is O(n²) with no extra space. The set-based scan asks, for each element x, whether x – k or x + k has been seen before, which gives O(n) time and O(n) space. If the array is already sorted, two pointers moving forward find a pair with the given difference in O(n) time and O(1) space, because the difference grows or shrinks predictably as each pointer moves.

Follow-ups to expect. Interviewers often ask for the number of distinct pairs rather than a yes or no, which needs a map of counts and special handling of the case where k is zero, since then a pair needs a repeated value. Another variation returns the pair itself. Using absolute values makes negative k behave like positive k, and using long for the arithmetic protects against overflow at the ends of the int range. Say all of that aloud as you code.

58. Find a Subarray With a Given Sum (Sliding Window)

When every value is non-negative, a sliding window finds a contiguous subarray with a target sum in one pass. Add the next element on the right, and while the sum is too large, remove elements from the left. If the sum equals the target, return the window. The whole technique depends on the values being non-negative: with negatives, shrinking the window no longer guarantees a smaller sum, and you need the prefix-sum approach from earlier.

static int[] findSubarrayWithSum(int[] a, int target) {    // works for non-negative values only
    int start = 0;
    long sum = 0;
    for (int end = 0; end < a.length; end++) {
        sum += a[end];
        while (sum > target && start <= end) {
            sum -= a[start++];                             // shrink from the left
        }
        if (sum == target && start <= end) return new int[] { start, end };
    }
    return new int[] { -1, -1 };
}

For {1, 2, 3, 7, 5} and target 12, the first window that hits 12 is indices 1 to 3 (2 + 3 + 7). The window 7 + 5 at indices 3 to 4 also sums to 12, and the code returns the earliest one it finds; ask whether any match is acceptable or whether all are wanted. {1, 4, 20, 3, 10, 5} with target 33 returns indices 2 to 4, and a missing sum returns {-1, -1}. Time is O(n), because each element enters and leaves the window at most once, and space is O(1). Compare this with the earlier subarray-sum-equals-k problem, which handles negatives with a hash map at the cost of O(n) space.

Brute Force and Follow-Ups

Starting point. Summing every subarray is O(n²). The sliding window is O(n) because each element is added once and removed at most once. It relies on all the values being non-negative: removing an element from the left can then only decrease the sum, so the window always has a direction in which to move. That assumption must be stated, because the algorithm gives wrong answers on negative values.

Follow-ups to expect. With negative numbers allowed, switch to the prefix-sum and hash-map approach from the earlier problem. A closely related and very common question is “find the length of the smallest subarray whose sum is at least a given target”, which uses the same window but records the minimum length each time the sum reaches the target. Another is “return all subarrays that add up to the target”. Ask whether the first match is enough or all matches are wanted.

Number and Logic Questions

These are the short problems that open many screening rounds. They take two minutes if you know the standard answer, so the real test is whether you notice the edge case: overflow, negatives, zero or the largest allowed input.

59. Fibonacci Number

The recursive version, fib(n - 1) + fib(n - 2), is O(2^n) and is the answer interviewers want you to reject. The iterative version keeps the last two values and is O(n) time and O(1) space. Memoised recursion is the middle option and shows you know why the naive version is slow.

static long fibonacci(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be >= 0");
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

fibonacci(0) is 0, fibonacci(1) is 1, fibonacci(10) is 55 and fibonacci(50) is 12,586,269,025. A long holds the sequence correctly up to fibonacci(92); after that it overflows, and BigInteger is the answer if the interviewer asks for larger values.

Brute Force and Follow-Ups

Starting point. The recursive definition fib(n - 1) + fib(n - 2) takes exponential time, about O(2ⁿ), because it recomputes the same values over and over, and it is the version interviewers want you to reject. Memoisation stores each result and brings the time to O(n) with O(n) space. The iterative version keeps only the last two values, giving O(n) time and O(1) space.

Follow-ups to expect. The question that separates strong candidates is “can you do better than O(n)?”. Matrix exponentiation or the fast-doubling method computes the nth Fibonacci number in O(log n) multiplications. Another is “what is the largest n that fits in a long?”, which is 92. Beyond that you need BigInteger. A common variation asks for the answer modulo a large number, which keeps values small, and another asks you to print the first n terms of the sequence rather than return one.

60. Check Whether a Number Is Prime

Trial division only needs to go up to the square root of n, because any factor larger than that pairs with a smaller one. Handle 2 and 3 first, reject the even numbers, and then test odd divisors only. That is O(√n).

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

1 is not prime, 2 is, 17 is, 25 is not, and 2,147,483,647 (the largest int) is prime. Zero and negative numbers are not prime. The loop variable is a long so that i * i cannot overflow near the top of the int range; with an int it would wrap to a negative number and the loop would misbehave on large inputs.

Brute Force and Follow-Ups

Starting point. Testing every divisor from 2 up to n – 1 is O(n). Stopping at n / 2 is still O(n), and stopping at the square root brings it to O(√n), because a larger factor always pairs with a smaller one. Skipping even numbers after checking 2 halves the work again. The solution also handles small and negative inputs explicitly, since 0, 1 and negative numbers are not prime.

Follow-ups to expect. If you need all primes up to a limit, the Sieve of Eratosthenes finds them in about O(n log log n), which is much faster than testing each number separately. For very large numbers, probabilistic tests such as Miller-Rabin are used, and Java exposes one through BigInteger.isProbablePrime. Interviewers also ask “count the primes below n”, which is the sieve again. The detail about using a long loop counter to avoid overflow in i * i is a good small sign of care.

61. Reverse an Integer Without Overflow

Reverse the digits of an int by repeatedly taking x % 10 and building up the result. The point of the question is what happens when the reversed value does not fit in an int. Check before multiplying by 10, and return 0 when the next step would overflow.

static int reverseInteger(int x) {
    int result = 0;
    while (x != 0) {
        int digit = x % 10;
        x /= 10;
        if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
        if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
        result = result * 10 + digit;
    }
    return result;
}

reverseInteger(123) is 321, -123 is -321, and 120 is 21, because trailing zeros vanish. 1534236469 reverses to 9646324351, which is too large for an int, so the method returns 0. Java’s remainder keeps the sign of the dividend, so negative numbers work without special handling. Time is O(log n) in the number of digits and space is O(1).

Brute Force and Follow-Ups

Starting point. Converting the number to a string, reversing it and parsing it back works, but it breaks on the sign and fails with a NumberFormatException when the reversed value is out of range. Doing the arithmetic directly, with x % 10 to take a digit and x / 10 to drop it, avoids strings. The key is to test for overflow before multiplying the result by 10, rather than after, because after the fact the value has already wrapped around.

Follow-ups to expect. A closely related problem is “is this integer a palindrome without converting it to a string?”, where you reverse only the second half of the digits and compare. Others are “sum the digits” and “count the digits”. Mention the asymmetry of the int range: the minimum value is one larger in magnitude than the maximum, which is why the two overflow tests compare the last digit with 7 and with -8. A solution using a long accumulator is simpler if the language allows it.

62. Greatest Common Divisor (Euclid’s Algorithm)

Replace the pair (a, b) with (b, a mod b) until b is zero; what remains in a is the GCD. It is about as short as a classic algorithm gets, and it is the basis of the least common multiple: lcm(a, b) = a / gcd(a, b) * b. Dividing before multiplying keeps the intermediate value smaller and avoids an unnecessary overflow.

static int gcd(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

gcd(48, 18) is 6, gcd(17, 5) is 1, gcd(0, 5) is 5, and gcd(-48, 18) is 6 because the method takes absolute values first. The running time is O(log(min(a, b))).

Brute Force and Follow-Ups

Starting point. Looping from the smaller of the two numbers down to 1 and returning the first divisor of both is O(min(a, b)). Euclid’s algorithm replaces the larger number with the remainder of dividing it by the smaller, and repeats until the remainder is zero. It runs in O(log(min(a, b))) steps, which is dramatically faster for large inputs, and the code is only a few lines.

Follow-ups to expect. The least common multiple follows directly: a / gcd(a, b) * b, dividing first to avoid an unnecessary overflow. The GCD of a whole array is a fold of the pairwise GCD. An extended version of the algorithm also returns the coefficients that express the GCD as a combination of the two numbers, and is the basis of modular inverses. Interviewers sometimes ask about the binary GCD algorithm, which uses shifts and subtraction instead of division, as a talking point.

Collections, Streams and Concurrency Problems for Automation Architects

At architect level the coding round moves away from pure algorithms and towards the code you would actually write for a test framework: caches, retries, rate limits, per-thread resources, parallel execution, and data comparison. These eight problems cover the ones that come up most often. They lean on a few facts about the standard library that are worth being able to state without looking them up. HashMap and ArrayList are not thread-safe, ConcurrentHashMap is, and wrapping a collection in Collections.synchronizedList only protects individual calls, not a sequence of them. ExecutorService manages a pool of threads for you and must always be shut down. Callable returns a value and may throw a checked exception, while Runnable does neither. The snippets in this part also need java.util.concurrent.*, java.util.function.* and java.util.stream.* imports.

63. Implement an LRU Cache

An LRU (least recently used) cache holds a fixed number of entries and evicts the one that has gone longest without being read or written. The quickest correct Java answer is a LinkedHashMap created in access order, with removeEldestEntry overridden to evict when the size passes the capacity. Be prepared for the follow-up, “now build it without LinkedHashMap”: a HashMap from key to node plus a doubly linked list, moving a node to the front on every access, which gives O(1) get and put.

static final class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true);                            // true = order by access, not insertion
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

With a capacity of 2, putting a and b, reading a, and then putting c evicts b, leaving the keys [a, c]. The true argument to the LinkedHashMap constructor is what switches ordering from insertion order to access order. This class is not thread-safe; for shared use, wrap it with Collections.synchronizedMap or guard it with a lock. In a framework, the typical use is caching expensive lookups such as auth tokens or reference data fetched from an API.

Brute Force and Follow-Ups

Starting point. Storing the entries in a list and scanning for a key on every access is O(n) per operation, which defeats the purpose of a cache. The LinkedHashMap answer works because it combines a hash table with a linked list, giving O(1) lookups and O(1) updates to the usage order. Access order is switched on through the constructor argument, and removeEldestEntry is called after each insertion to decide whether to evict.

Follow-ups to expect. The natural follow-up is to build the same thing from scratch, which is the next-level problem later in this guide. Others are “make it thread-safe”, which can be done by wrapping it with Collections.synchronizedMap or by guarding access with a lock, and “add an expiry time to each entry”, which needs a timestamp on every value and a check on read. Interviewers also ask about LFU, a cache that evicts the least frequently used entry, and how its data structure differs from LRU.

64. Retry With Exponential Backoff

Flaky infrastructure is a fact of life in automation, and a retry helper is something almost every framework contains. The architect-level version takes any Callable, retries a limited number of times, doubles the wait after each failure, and rethrows the last exception if every attempt fails. The two points interviewers listen for are that the retry count is bounded and that the delay grows.

static <T> T retry(Callable<T> action, int maxAttempts, long initialDelayMs) throws Exception {
    if (maxAttempts < 1) throw new IllegalArgumentException("maxAttempts must be >= 1");
    long delay = initialDelayMs;
    Exception last = null;
    for (int attempt = 1; attempt <= maxAttempts; attempt++) {
        try {
            return action.call();
        } catch (Exception e) {
            last = e;
            if (attempt < maxAttempts) {
                Thread.sleep(delay);
                delay *= 2;                                // exponential backoff
            }
        }
    }
    throw last;
}

An action that fails twice and then succeeds returns its value on the third call, and an action that always fails is called exactly maxAttempts times before the last exception is rethrown. The helper does not sleep after the final failure, and an InterruptedException from Thread.sleep escapes immediately instead of being swallowed. Also say what it should not do: retry only for exceptions you know are transient (timeouts, 503 responses), never retry on assertion failures, and keep in mind that retrying a failed test hides real defects unless the retries are reported. Real code often adds random jitter to the delay so that many clients do not all retry at the same moment.

Brute Force and Follow-Ups

Starting point. A bare loop that retries forever with a fixed sleep has two problems: it never gives up, and a fixed delay keeps hammering a service that is already struggling. The bounded loop with a doubling delay gives a failing dependency time to recover and gives up cleanly after the last attempt, rethrowing the final exception so the caller sees a real error. Not sleeping after the last attempt is a small detail that saves time.

Follow-ups to expect. Expect “add jitter”, meaning a random amount added to each delay so that many clients do not retry in lockstep, and “retry only for certain exceptions”, which means passing a Predicate<Exception> or a list of types. Another is “log each attempt”, which suggests a listener callback. The most important design question is idempotency: retrying an action that is not safe to repeat, such as a payment, can do damage, so say explicitly that this helper is for safe operations. Also mention that automatic test retries must be reported, or they hide real defects.

65. Flatten a Nested Map (JSON-Style Data)

API responses are nested maps and lists, and comparing or asserting on them is easier when each value has a flat path such as user.address.city or user.roles[0]. The solution is recursion over maps and lists, building the key as you descend.

static Map<String, Object> flatten(Map<String, Object> input) {
    Map<String, Object> out = new LinkedHashMap<>();
    flattenInto("", input, out);
    return out;
}

@SuppressWarnings("unchecked")
private static void flattenInto(String prefix, Map<String, Object> node, Map<String, Object> out) {
    for (Map.Entry<String, Object> e : node.entrySet()) {
        String key = prefix.isEmpty() ? e.getKey() : prefix + "." + e.getKey();
        Object value = e.getValue();
        if (value instanceof Map) {
            flattenInto(key, (Map<String, Object>) value, out);
        } else if (value instanceof List) {
            List<?> list = (List<?>) value;
            for (int i = 0; i < list.size(); i++) {
                String itemKey = key + "[" + i + "]";
                Object item = list.get(i);
                if (item instanceof Map) flattenInto(itemKey, (Map<String, Object>) item, out);
                else out.put(itemKey, item);
            }
        } else {
            out.put(key, value);
        }
    }
}

A user object with a name, a roles list and an address map, plus a top-level active flag, flattens to {user.name=Ajit, user.roles[0]=qa, user.roles[1]=lead, user.address.city=Pune, active=true}. A list of maps works too: items[0].id=7. An empty map gives an empty result. Time is O(total number of values). LinkedHashMap preserves the document order, which makes diffs readable. Once two responses are flattened, comparing them is a matter of comparing two flat maps, and the differences name the exact path that changed.

Brute Force and Follow-Ups

Starting point. An iterative version with an explicit stack of pending nodes avoids deep recursion but is harder to read. The recursive solution passes the key prefix down and writes each leaf value into a single output map, which makes the code short and the flow obvious. Recursion depth equals the nesting depth of the data, which is small for typical JSON.

Follow-ups to expect. “Unflatten” is the reverse: split each key on dots and brackets and rebuild the nested maps and lists. Keys that themselves contain a dot are ambiguous, so a real implementation chooses an escaping rule or a different separator. Interviewers also ask how to deal with null values and with empty maps or lists, which the code above handles by writing nothing for an empty container, a choice you should state. This function is the base for the JSON diff problem later on, and it is a good candidate for a unit test of its own.

66. Compare Two Lists Ignoring Order

An automation framework constantly compares what the UI shows with what the API returned, and the order often differs. Sorting both lists works, but a counting map is cleaner and tells you exactly what is wrong: add one for every expected item, subtract one for every actual item, and any non-zero count is a difference.

static List<String> diffLists(List<String> expected, List<String> actual) {
    Map<String, Integer> counts = new TreeMap<>();
    for (String s : expected) counts.merge(s, 1, Integer::sum);
    for (String s : actual) counts.merge(s, -1, Integer::sum);
    List<String> report = new ArrayList<>();
    for (Map.Entry<String, Integer> e : counts.entrySet()) {
        if (e.getValue() > 0) report.add("missing: " + e.getKey() + " x" + e.getValue());
        else if (e.getValue() < 0) report.add("unexpected: " + e.getKey() + " x" + (-e.getValue()));
    }
    return report;
}

Expected [a, b, b, c] against actual [b, a, d, b, b] reports [unexpected: b x1, missing: c x1, unexpected: d x1]: one extra b, one missing c, and an unexpected d. Two lists with the same items in a different order produce an empty report. A TreeMap makes the report order stable, which matters when the output goes into a test log. Counting rather than using a set is what handles duplicates correctly. Time is O(n + m) plus the sort of the distinct keys.

Brute Force and Follow-Ups

Starting point. Removing each expected item from a copy of the actual list is O(n · m) because each removal searches the list. Sorting both lists and comparing them element by element is O(n log n), but it only says whether they differ, not how. The counting map does the comparison in linear time and also produces a precise report of what is missing and what is unexpected, including duplicates.

Follow-ups to expect. Variations include “report only what is missing”, “treat the lists as sets and ignore duplicates”, and “compare in order and report the first index that differs”. Normalising values before counting, by trimming whitespace or ignoring case, is often part of the real requirement, and doing it in one place keeps the comparison honest. For lists of objects, the map key must be something stable, such as an id, or the class needs correct equals and hashCode methods.

67. Sliding-Window Rate Limiter

Allow at most N requests in any window of T milliseconds. Keep the timestamps of accepted requests in a deque; on each call, drop those that have fallen out of the window, then accept the new request only if there is room. It is a good test of design thinking, because it has a clear data structure, a clear invariant, and a thread-safety question attached.

static final class RateLimiter {
    private final int maxRequests;
    private final long windowMs;
    private final Deque<Long> timestamps = new ArrayDeque<>();

    RateLimiter(int maxRequests, long windowMs) {
        this.maxRequests = maxRequests;
        this.windowMs = windowMs;
    }

    synchronized boolean allow(long nowMs) {
        while (!timestamps.isEmpty() && nowMs - timestamps.peekFirst() >= windowMs) {
            timestamps.pollFirst();                        // drop requests outside the window
        }
        if (timestamps.size() < maxRequests) {
            timestamps.addLast(nowMs);
            return true;
        }
        return false;
    }
}

With a limit of 3 per 1,000 ms, requests at 0, 100 and 200 ms are accepted and the one at 300 ms is rejected. At 1,000 ms the request from time 0 has expired, so the next one is accepted; at 1,050 ms the window is full again, and at 1,100 ms the entry from 100 ms has expired and one more is accepted. The method is synchronized because several test threads may share the limiter. The caller passes the time in, which makes the class easy to unit test without sleeping. Mention the alternatives if asked: a fixed window is simpler but lets bursts through at window edges, and a token bucket allows controlled bursts.

Brute Force and Follow-Ups

Starting point. The simplest limiter keeps a counter that resets on a timer, which is a fixed window. It is easy but allows twice the intended rate around a window boundary: a full quota just before the reset and another one just after. The sliding window log stored here removes that flaw by remembering the timestamp of each accepted request, at the cost of memory proportional to the limit.

Follow-ups to expect. Expect “make it per user”, which uses a map from user id to limiter and needs eviction of idle users, and “make it work across several servers”, which moves the state into a shared store such as Redis. Interviewers also ask you to compare it with a token bucket, which allows controlled bursts and uses constant memory, and with a leaky bucket, which smooths output to a constant rate. Mention that passing the time in as a parameter makes the class testable without sleeping.

68. Thread-Safe Resource per Thread (ThreadLocal)

When tests run in parallel, objects such as a browser driver, an API client with session state, or a database connection cannot be shared between threads. The standard fix is ThreadLocal: each thread lazily gets its own instance on first use. This is the core of how parallel Selenium frameworks hold their drivers, and an architect is expected to explain it and its main pitfall.

static final class ResourceHolder<T> {
    private final ThreadLocal<T> local;

    ResourceHolder(Supplier<T> factory) {
        this.local = ThreadLocal.withInitial(factory);
    }

    T get() {
        return local.get();                                // one instance per thread
    }

    void remove() {
        local.remove();                                    // call in teardown to avoid leaks
    }
}

The same thread always gets the same instance back, and a different thread gets a different one. After remove() the next call on that thread builds a fresh instance. The pitfall is leaking: in a thread pool the threads outlive the tests, so a ThreadLocal that is never removed keeps its object alive and can leak the previous test’s state into the next one. Always call remove() in the teardown step, after closing the resource itself.

Brute Force and Follow-Ups

Starting point. The direct approach is to pass the driver or client as a parameter through every method that needs it. It works but clutters every signature. Another approach stores the objects in a map keyed by thread, which needs its own synchronisation and manual clean-up. ThreadLocal gives each thread its own copy and handles the lookup for you.

Follow-ups to expect. The main pitfall to mention is leaking. Thread pools reuse their threads, so a ThreadLocal that is never removed keeps its object alive and can leak one test’s state into the next, which is why remove() belongs in the teardown. InheritableThreadLocal copies the value to child threads, which is occasionally useful. Many architects prefer a dependency-injection approach, such as a test-scoped object created by the test framework, because it makes dependencies explicit; a good answer discusses both, and notes that ThreadLocal needs extra care with virtual threads.

69. Run Tasks in Parallel With ExecutorService

Running a batch of independent checks (health checks across ten endpoints, say, or data validation for several tenants) in parallel is a regular framework chore. Submit them as a list of Callables with invokeAll, read the Futures in order, and always shut the pool down in a finally block so the JVM can exit.

static List<String> runInParallel(List<Callable<String>> tasks, int threads) throws Exception {
    ExecutorService pool = Executors.newFixedThreadPool(threads);
    try {
        List<String> results = new ArrayList<>();
        for (Future<String> f : pool.invokeAll(tasks)) {   // futures come back in task order
            results.add(f.get());                          // rethrows a task failure as ExecutionException
        }
        return results;
    } finally {
        pool.shutdown();
    }
}

Five tasks with different sleep times finish in a different order than they started, but the results still come back as [t0, t1, t2, t3, t4], because invokeAll returns the Futures in the order of the original list. A task that throws surfaces as an ExecutionException when you call get(), with the real cause attached. Pool size is a judgement call: for I/O-bound work like HTTP calls it can be well above the CPU core count, while for CPU-bound work it should be close to the core count. CompletableFuture is the other tool to mention: it composes asynchronous steps without blocking, but for a simple fan-out and wait, the pool above is easier to read.

Brute Force and Follow-Ups

Starting point. Creating a new Thread for every task and joining each one is correct but expensive and unbounded: a thousand tasks create a thousand threads. A fixed thread pool reuses a small number of threads and queues the rest. invokeAll submits the whole batch and waits for all of it, and the returned futures are in the same order as the tasks, which keeps the results easy to match up.

Follow-ups to expect. Pool size is a judgement call: for CPU-bound work it should be close to the number of cores, and for I/O-bound work such as HTTP calls it can be much larger. Know the difference between shutdown (finish queued tasks, accept no more), shutdownNow (try to interrupt running tasks) and awaitTermination (wait for the pool to finish). invokeAny returns the first successful result instead of all of them. A task that throws does not crash the pool; the exception appears when you call get on its future.

70. Summarise Test Results With Streams

The last problem is the kind of data wrangling a reporting utility does: given a list of test results, count passes and failures and list the slowest tests. It shows whether you can use groupingBy, counting, sorted and limit fluently and still keep the code readable.

static final class TestResult {
    final String name;
    final String status;
    final long durationMs;

    TestResult(String name, String status, long durationMs) {
        this.name = name;
        this.status = status;
        this.durationMs = durationMs;
    }
}

static Map<String, Long> countByStatus(List<TestResult> results) {
    return results.stream()
            .collect(Collectors.groupingBy(t -> t.status, TreeMap::new, Collectors.counting()));
}

static List<String> slowestTests(List<TestResult> results, int n) {
    return results.stream()
            .sorted(Comparator.comparingLong((TestResult t) -> t.durationMs).reversed())
            .limit(n)
            .map(t -> t.name)
            .collect(Collectors.toList());
}

For five results, two failing and three passing, countByStatus returns {FAIL=2, PASS=3}, and the two slowest tests are [checkout, payment]. Passing TreeMap::new to groupingBy makes the status order predictable, where a default HashMap would not guarantee it. Comparator.comparingLong(...).reversed() needs the explicit (TestResult t) parameter type so the compiler can infer the lambda. Time is O(n log n) because of the sort.

Brute Force and Follow-Ups

Starting point. The loop version creates a map manually, increments counters and then sorts a list with a comparator. It works and some teams prefer it for clarity. The streams version expresses the same logic declaratively: groupingBy with counting builds the status counts, and sorted, limit and map produce the slowest tests. Passing TreeMap::new as the map factory makes the output order predictable.

Follow-ups to expect. Likely extensions are “average duration per status” (averagingLong), “split into passed and failed lists” (partitioningBy), and “which tests failed more than once across runs”. Interviewers also ask whether parallel streams would help; for a small list they only add overhead and break ordering assumptions. A thoughtful remark for an architect is that a report like this should be computed from structured results, such as JUnit or TestNG XML, not scraped from console output.

Advanced Problems for Senior and Architect Rounds

The problems so far cover what most candidates meet in a screening round. A senior SDET or automation architect interview usually goes a level further: the same patterns, but combined, tighter on complexity, or wrapped in something that looks like framework code. The twenty problems in this group are the ones that come up most often at that level. Some are classic algorithm questions that product companies ask (trapping rain water, sliding window maximum, number of islands). Others are data-structure questions you are expected to build from scratch (an LRU cache with a hand-written linked list, a min stack, a queue from two stacks). The rest are framework-flavoured, because that is where an architect is expected to show judgement: a polling helper, a token bucket, a thread-safe singleton, a producer-consumer pipeline, a fan-out of API calls, a test-data builder. Each one has the same layout as before: the idea, a tested solution, the result on real examples, and the follow-up you should expect.

71. Trapping Rain Water

An array of non-negative numbers describes an elevation map, where each number is the height of a bar of width one. After rain, how much water is trapped between the bars? The water above any one bar is limited by the shorter of the tallest bar to its left and the tallest bar to its right, minus the bar’s own height. That sentence is the whole problem; the rest is deciding how to compute it efficiently.

The brute force does exactly what the sentence says. For every bar, scan left to find the maximum, scan right to find the maximum, and add min(leftMax, rightMax) - height. That is O(n²) time. Precomputing the left-maximum and right-maximum arrays brings it to O(n) time but needs O(n) extra space. The two-pointer version below needs neither. It keeps a pointer at each end and always processes the side with the smaller bar, because for that side the water level is already decided: the smaller bar is a guaranteed wall on one side, and the running maximum on the same side is a wall on the other, so nothing that appears later in the array can change the answer for it.

static int trapRainWater(int[] h) {
    int left = 0, right = h.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (h[left] < h[right]) {
            if (h[left] >= leftMax) leftMax = h[left];
            else water += leftMax - h[left];               // water above this bar, bounded by leftMax
            left++;
        } else {
            if (h[right] >= rightMax) rightMax = h[right];
            else water += rightMax - h[right];
            right--;
        }
    }
    return water;
}

{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1} traps 6 units, {4, 2, 0, 3, 2, 5} traps 9, {2, 0, 2} traps 2, and an array that only rises or only falls traps nothing, as does an empty array. Time is O(n) with a single pass, and space is O(1). The usual follow-up is the three-dimensional version, a grid of heights, which is solved with a min-heap that always expands the lowest boundary cell first. You do not need to code it, but being able to say “the same idea, with a priority queue on the boundary” is a strong answer.

72. Sliding Window Maximum

Given an array and a window size k, return the maximum of every window of k consecutive elements as the window slides from left to right. Checking every window and scanning its k elements is O(n · k). A max-heap makes it O(n log n) but needs care to discard elements that have left the window. The best solution is O(n) and uses a deque of indices.

The deque holds indices whose values are in decreasing order, so the front is always the maximum of the current window. For each new element, do two things. First, if the index at the front has slid out of the window, remove it. Second, remove from the back every index whose value is less than or equal to the new element, because those values are older and smaller and can never be the maximum of any later window. Then add the new index at the back. Once the first full window exists, the front of the deque is the answer for each position.

static int[] slidingWindowMax(int[] a, int k) {
    if (k < 1 || k > a.length) return new int[0];
    int[] out = new int[a.length - k + 1];
    Deque<Integer> window = new ArrayDeque<>();            // indices, values in decreasing order
    for (int i = 0; i < a.length; i++) {
        if (!window.isEmpty() && window.peekFirst() <= i - k) window.pollFirst();   // left the window
        while (!window.isEmpty() && a[window.peekLast()] <= a[i]) window.pollLast(); // can never be a max
        window.addLast(i);
        if (i >= k - 1) out[i - k + 1] = a[window.peekFirst()];
    }
    return out;
}

{1, 3, -1, -3, 5, 3, 6, 7} with k = 3 gives {3, 3, 5, 5, 6, 7}, {9, 8, 7} with k = 2 gives {9, 8}, and a window of one returns the array itself. A k of zero or one larger than the array returns an empty result, which is a design decision worth stating aloud. Every index is added once and removed at most once, so the work is O(n) even though there is a loop inside the loop, and the deque never holds more than k indices. In performance testing the same structure computes a rolling peak, for example the highest response time in the last k samples, without rescanning the window each time.

73. Decode String (Nested Repeat Notation)

Expand a string such as 3[a2[c]], where k[text] means the text repeated k times and the groups can nest. It is a stack problem in disguise. Whenever you meet a [, you are about to start a new inner group and must remember two things about the outer one: the text built so far and the repeat count that applies to the group you are entering. A ] closes the innermost group, so you pop those two values, repeat the inner text, and append it to the outer text.

static String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> prefixes = new ArrayDeque<>();
    StringBuilder current = new StringBuilder();
    int number = 0;
    for (char c : s.toCharArray()) {
        if (c >= '0' && c <= '9') {
            number = number * 10 + (c - '0');
        } else if (c == '[') {
            counts.push(number);
            prefixes.push(current);
            current = new StringBuilder();
            number = 0;
        } else if (c == ']') {
            StringBuilder previous = prefixes.pop();
            int repeat = counts.pop();
            for (int i = 0; i < repeat; i++) previous.append(current);
            current = previous;
        } else {
            current.append(c);
        }
    }
    return current.toString();
}

decodeString("3[a]2[bc]") returns "aaabcbc", "3[a2[c]]" returns "accaccacc", and "2[abc]3[cd]ef" returns "abcabccdcdcdef". A multi-digit count such as 10[a] works because the digits are accumulated into number one at a time. Text with no brackets passes through unchanged, and an empty string returns an empty string. Time is proportional to the length of the output, which can be much larger than the input, so mention that a string like 999[999[a]] would be enormous. A recursive-descent parser solves the same problem in a more readable way, and the stack version is what you write when you want to avoid recursion depth limits. This is the inverse of the run-length compression problem earlier in this guide, and the pairing is a good way to show you see the connection.

74. Merge K Sorted Arrays

Merging two sorted arrays is a two-pointer loop. Merging k of them is the same idea with a min-heap choosing which front element is smallest. Put the first element of every array into a priority queue along with which array it came from and its position. Repeatedly remove the smallest, append it to the output, and push the next element from the same array.

static int[] mergeKSorted(int[][] arrays) {
    PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    int total = 0;
    for (int i = 0; i < arrays.length; i++) {
        total += arrays[i].length;
        if (arrays[i].length > 0) heap.offer(new int[] { arrays[i][0], i, 0 });   // {value, which array, position}
    }
    int[] out = new int[total];
    int k = 0;
    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        out[k++] = top[0];
        int next = top[2] + 1;
        if (next < arrays[top[1]].length) {
            heap.offer(new int[] { arrays[top[1]][next], top[1], next });
        }
    }
    return out;
}

[[1, 4, 5], [1, 3, 4], [2, 6]] merges to {1, 1, 2, 3, 4, 4, 5, 6}, an empty list of arrays gives an empty result, and empty arrays inside the list are skipped. If N is the total number of elements, the heap never holds more than k entries, so each of the N operations costs O(log k) and the total is O(N log k). Concatenating everything and sorting is O(N log N), and merging the arrays pairwise one after another is O(N · k) in the worst case, so the heap is the answer interviewers are looking for. It is also the standard way to merge sorted log files from several parallel test workers into one timeline ordered by timestamp, with memory proportional to k, not to the total size of the logs.

75. Valid Sudoku

Given a 9 by 9 board where empty cells are marked with a dot, check that no digit repeats within any row, any column, or any of the nine 3 by 3 boxes. The task is to validate the filled cells, not to decide whether the puzzle can be solved. The clean way to do it is one pass over the board with a single set of strings that encode where a digit has been used: “5 in row 0”, “5 in column 0”, “5 in box 0-0”. The box index comes from integer division, row / 3 and column / 3. If adding any of the three strings fails because it is already present, the board is invalid.

static boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char v = board[r][c];
            if (v == '.') continue;
            if (!seen.add(v + " in row " + r)
                    || !seen.add(v + " in column " + c)
                    || !seen.add(v + " in box " + (r / 3) + "-" + (c / 3))) {
                return false;
            }
        }
    }
    return true;
}

The classic example board, with a 5 and a 3 in the top-left corner, is valid. Changing the first digit of the first row to an 8 creates a repeated 8 in the first column, so the board is invalid, and adding a second 5 inside the top-left box also makes the board invalid. The board size is fixed, so the work is constant, O(81), and the space is bounded by the same number. Bitmasks, one integer per row, column and box, are a faster alternative, and mentioning them shows you are thinking about constant factors. Wherever the interviewer mentions “validate this grid of data”, the same pattern of using an encoded key in a set applies.

76. Token Bucket Rate Limiter

An earlier problem built a rate limiter from a sliding window of timestamps. The token bucket is the other standard design, and architects are often asked to compare them. A bucket holds up to a fixed number of tokens and refills at a steady rate. Each request takes one token; if there is none, the request is rejected. Unlike the sliding window, it allows a short burst up to the bucket’s capacity while still enforcing the long-run average rate.

There is no background thread. The bucket refills lazily: each time a request arrives, it works out how much time has passed since the last refill, adds that many tokens (never beyond the capacity), and then decides. The caller supplies the current time, which keeps the class deterministic and easy to unit test.

static final class TokenBucket {
    private final double capacity;
    private final double tokensPerMs;
    private double tokens;
    private long lastRefillMs;

    TokenBucket(double capacity, double tokensPerMs, long startMs) {
        this.capacity = capacity;
        this.tokensPerMs = tokensPerMs;
        this.tokens = capacity;                            // start full, so an initial burst is allowed
        this.lastRefillMs = startMs;
    }

    synchronized boolean tryAcquire(long nowMs) {
        tokens = Math.min(capacity, tokens + (nowMs - lastRefillMs) * tokensPerMs);
        lastRefillMs = nowMs;
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;
    }
}

With a capacity of 3 and a refill rate of half a token per millisecond, three requests at time 0 are accepted and a fourth is rejected. One millisecond later only half a token has accumulated, so a request is still rejected; at 2 ms a full token is available and a request is accepted, and the next one is rejected again. After a quiet period, at 100 ms, the bucket is full again and exactly three requests get through before the fourth is refused. Each call is O(1) and the state is a few numbers. The method is synchronized because several threads usually share one limiter. In a framework you use this to keep a load or API test below a service’s published request limit, and the capacity is how you decide how bursty the test may be.

77. LRU Cache Without LinkedHashMap

The LinkedHashMap version of an LRU cache earlier on this page is the right answer in production code. In an interview the follow-up is almost always “now build it by hand”, and the point is to see whether you can combine two data structures to get O(1) for both operations. A HashMap from key to node gives O(1) lookup. A doubly linked list, ordered from most recently used to least recently used, gives O(1) removal of any node and O(1) insertion at the front, provided you already hold a reference to the node, which the map supplies.

Two sentinel nodes, a head and a tail that never hold real data, remove every null check from the pointer updates, because every real node always has a neighbour on each side. A read moves the node to the front. A write either updates an existing node and moves it to the front, or inserts a new node at the front and, if the cache is full, first removes the node just before the tail, which is the least recently used one.

static final class ManualLru<K, V> {
    private final class Node {
        final K key;
        V value;
        Node prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node> map = new HashMap<>();
    private final Node head = new Node(null, null);        // sentinel: most recently used side
    private final Node tail = new Node(null, null);        // sentinel: least recently used side

    ManualLru(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be >= 1");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    V get(K key) {
        Node node = map.get(key);
        if (node == null) return null;
        unlink(node);
        addFirst(node);                                    // reading makes it the most recent
        return node.value;
    }

    void put(K key, V value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            addFirst(node);
            return;
        }
        if (map.size() == capacity) {
            Node eldest = tail.prev;
            unlink(eldest);
            map.remove(eldest.key);
        }
        node = new Node(key, value);
        map.put(key, node);
        addFirst(node);
    }

    int size() {
        return map.size();
    }

    private void unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void addFirst(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}

With a capacity of two, put 1 and 2, read 1, then put 3: key 2 is the eldest and is evicted, so reading it returns null while keys 1 and 3 are still present. Updating key 1 and adding key 4 then evicts 3. The size never exceeds the capacity, and a capacity below one is rejected up front, because with a capacity of zero the eviction step would try to remove the head sentinel. Both operations are O(1) and the space is O(capacity). The class is not thread-safe; for concurrent use either synchronize the two public methods or discuss why a sharded or lock-striped design would be needed under heavy contention. The inner class needs access to the generic type parameters, which is why Node is a non-static inner class here.

78. Diff Two Nested JSON Structures

Comparing an actual API response with an expected one is the daily work of an automation framework, and a bare “not equal” is useless in a failure report. A helpful diff says which path is missing, which path is unexpected, and which path holds a different value. The approach reuses the flatten problem from earlier: flatten both structures so every value has a path such as user.address.city, take the union of all the paths in sorted order, and compare path by path.

static List<String> diffMaps(Map<String, Object> expected, Map<String, Object> actual) {
    Map<String, Object> e = Solutions2.flatten(expected);
    Map<String, Object> a = Solutions2.flatten(actual);
    Set<String> keys = new TreeSet<>(e.keySet());
    keys.addAll(a.keySet());
    List<String> report = new ArrayList<>();
    for (String key : keys) {
        boolean inExpected = e.containsKey(key), inActual = a.containsKey(key);
        if (inExpected && !inActual) {
            report.add("missing: " + key);
        } else if (!inExpected && inActual) {
            report.add("unexpected: " + key);
        } else if (!Objects.equals(e.get(key), a.get(key))) {
            report.add("changed: " + key + " expected=" + e.get(key) + " actual=" + a.get(key));
        }
    }
    return report;
}

Take an expected object with user.name set to Ajit and user.city set to Pune, and an actual object where the name is “Ajit M”, the city is absent and a new user.role exists. The report is [missing: user.city, changed: user.name expected=Ajit actual=Ajit M, unexpected: user.role], and comparing a structure with itself gives an empty list. A TreeSet makes the order stable, so the same two inputs always produce the same report, which matters when you compare reports over time. Objects.equals handles null values safely. Three things to say out loud: lists are compared by index, so reordered lists show up as many changes unless you sort them first; a number parsed as an Integer will not equal the same number parsed as a Double; and real responses contain dynamic fields such as timestamps and generated ids, which you remove from both flattened maps before diffing. Time is O(n log n) in the number of distinct paths.

79. Min Stack

Design a stack that supports push, pop, top and, in constant time, the current minimum. Scanning the stack for the minimum would be O(n). The trick is to store the answer alongside each element: every entry records its own value and the minimum of everything at or below it. When an entry is popped, the previous entry already carries the correct minimum for what remains, so there is nothing to recompute.

static final class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();  // each entry: {value, minimum so far}

    void push(int x) {
        int min = stack.isEmpty() ? x : Math.min(x, stack.peek()[1]);
        stack.push(new int[] { x, min });
    }

    int pop() {
        return stack.pop()[0];
    }

    int top() {
        return stack.peek()[0];
    }

    int getMin() {
        return stack.peek()[1];
    }

    boolean isEmpty() {
        return stack.isEmpty();
    }
}

Push 5, 3, 7 and 3 and the minimum is 3. Pop the second 3 and the minimum is still 3, because the first 3 is underneath. Pop the 7 and it is still 3. Pop the first 3 and the minimum falls back to 5, which is the value that was recorded with the 5. All four operations are O(1) and the extra space is one integer per element. A common variation keeps a second stack that holds only the successive minimums, which uses less memory when the minimum changes rarely, though it needs careful handling of duplicates. If the interviewer asks what happens on an empty stack, the answer is a design choice: here pop throws, while peek-based calls would fail with a null pointer, and a production class would check and throw a clear exception.

80. Implement a Queue Using Two Stacks

Build first-in-first-out behaviour from two last-in-first-out stacks. New items always go onto the “in” stack. When an item must be removed and the “out” stack is empty, pour everything from “in” into “out”; the pouring reverses the order, so the oldest item ends up on top. Removal and peeking then read from “out”, and the pour happens only when “out” is empty.

static final class TwoStackQueue<T> {
    private final Deque<T> in = new ArrayDeque<>();
    private final Deque<T> out = new ArrayDeque<>();

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

    T dequeue() {
        shiftIfNeeded();
        if (out.isEmpty()) throw new NoSuchElementException("queue is empty");
        return out.pop();
    }

    T peek() {
        shiftIfNeeded();
        if (out.isEmpty()) throw new NoSuchElementException("queue is empty");
        return out.peek();
    }

    private void shiftIfNeeded() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());      // reverses the order, so oldest ends on top
        }
    }
}

Enqueue 1, 2 and 3 and dequeue to get 1. Enqueue 4 and peek to get 2, because 2 was already waiting in the out stack; dequeue then returns 2, 3 and 4 in order, and a further dequeue on the empty queue throws. A single dequeue can cost O(n) when it triggers a pour, but every element is moved from one stack to the other at most once in its lifetime, so the amortised cost of each operation is O(1). That phrase, “amortised O(1)”, is the point of the question and is worth saying clearly. The mirror problem, a stack from two queues, is a common follow-up and is a good one to try on your own.

81. Reverse a Linked List

Linked-list questions use a small node class, so the block below defines one with two helpers: listOf builds a list from values, and toList turns a list back into a Java List so the results are easy to print.

static final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

static ListNode listOf(int... values) {
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : values) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

static List<Integer> toList(ListNode head) {
    List<Integer> out = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) out.add(n.val);
    return out;
}

Reversing a singly linked list means flipping every next pointer. Walk the list with three references: the previous node (initially null), the current node, and the next node that you must save before you overwrite current.next. Point the current node back at the previous one, then step all three forward. When the current node becomes null, the previous node is the new head.

static ListNode reverseList(ListNode head) {
    ListNode previous = null, current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = previous;                           // flip the link
        previous = current;
        current = next;
    }
    return previous;
}

The list 1, 2, 3, 4, 5 becomes 5, 4, 3, 2, 1, a single node and a two-node list reverse correctly, and a null list returns null. Time is O(n) and space is O(1), because only a few references are held. The recursive version is shorter to write but uses O(n) stack space and can overflow on a very long list, so state the trade-off. Related follow-ups include reversing only part of the list, reversing in groups of k, and checking whether a list is a palindrome by reversing its second half.

82. Detect a Cycle in a Linked List (Floyd’s Algorithm)

Does following the next pointers ever loop back on itself? Storing every visited node in a HashSet answers it in O(n) time but costs O(n) memory. Floyd’s tortoise and hare answers it in O(1) memory: move a slow pointer one step at a time and a fast pointer two steps at a time. If the list has no cycle, the fast pointer reaches the end. If it has one, the fast pointer enters the loop and eventually laps the slow one, and they meet.

static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;                     // the fast pointer lapped the slow one
    }
    return false;
}

A plain list 1, 2, 3, 4 has no cycle, and neither does a null list or a one-node list. Link the last node of that list back to its second node and the method returns true; so does a single node pointing to itself. The reason the two pointers must meet is that, once both are inside the loop, the gap between them shrinks by one on every step, so it reaches zero. The loop condition checks both fast and fast.next to avoid a null pointer on lists with an odd number of nodes. Time is O(n) and space is O(1). The follow-up is to find the node where the cycle begins, which uses the same two pointers with a second phase.

83. Top N Error Messages From a Log

When a CI run fails, the first question is which failure is most common. This is a counting problem with a Streams solution that shows off the whole pipeline: filter the lines that contain ERROR, extract the message that follows the level, group the identical messages and count them, then sort by count, descending, with the message as a tie-breaker so the output is stable, and keep the first N.

static List<String> topErrors(List<String> logLines, int n) {
    Map<String, Long> counts = logLines.stream()
            .filter(line -> line.contains("ERROR"))
            .map(line -> line.substring(line.indexOf("ERROR") + "ERROR".length()).trim())
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    return counts.entrySet().stream()
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed()
                    .thenComparing(Map.Entry.comparingByKey()))
            .limit(n)
            .map(e -> e.getKey() + " (" + e.getValue() + ")")
            .collect(Collectors.toList());
}

For a log with three “Timeout waiting for login” errors, two “Element not found: #save” errors and one “500 from /api/orders” error, asking for the top two returns [Timeout waiting for login (3), Element not found: #save (2)]. Asking for ten returns all three, and a log with no ERROR lines returns an empty list. Counting is O(n) and sorting the distinct messages is O(d log d) for d distinct messages. Two practical points: a real log line also carries a timestamp, so the message extraction should match your actual format (a regular expression is often safer than indexOf), and for large files read with Files.lines inside a try-with-resources block so the file is streamed instead of loaded into memory.

84. Wait Until a Condition Becomes True (Polling With a Timeout)

Every UI and API framework needs an explicit wait: keep checking a condition until it holds or time runs out. A fixed Thread.sleep is the wrong tool, because it is either too short and makes the test flaky or too long and makes the suite slow. A polling helper checks the condition at a short interval and returns as soon as it is true.

The version below measures time with System.nanoTime(), which is monotonic, instead of System.currentTimeMillis(), which can jump if the system clock is adjusted. It never sleeps past the deadline: the last sleep is shortened to the time that remains. It returns a boolean and leaves the decision to throw to the caller, which keeps the helper reusable.

static boolean waitUntil(BooleanSupplier condition, long timeoutMs, long pollMs) throws InterruptedException {
    long deadline = System.nanoTime() + TimeUnit.MILLISECONDS.toNanos(timeoutMs);
    while (true) {
        if (condition.getAsBoolean()) return true;
        long remainingMs = TimeUnit.NANOSECONDS.toMillis(deadline - System.nanoTime());
        if (remainingMs <= 0) return false;
        Thread.sleep(Math.max(1, Math.min(pollMs, remainingMs)));
    }
}

A condition that becomes true on its third check returns true after exactly three polls. A condition that is never true returns false after about the timeout, 60 ms in the test, and a condition that is already true returns immediately, even with a timeout of zero. Be ready to discuss what a production version adds: a message describing what was being waited for, so a timeout failure is readable; ignoring specific exceptions inside the condition, which is what Selenium’s FluentWait does (see the Selenium waits documentation) with NoSuchElementException; and a generic form that returns the value being waited for instead of a boolean. The most common mistake is a polling interval so small that the check itself becomes the load on the system under test.

85. Thread-Safe Singleton (Initialization-on-Demand Holder)

Singleton questions are really thread-safety questions. A naive lazy singleton, if (instance == null) instance = new ..., can create two instances when two threads reach the check together. The usual fixes are a synchronized accessor (correct but takes a lock on every call), double-checked locking with a volatile field (correct but easy to write wrongly), an enum with a single constant (the simplest safe choice), and the holder idiom shown here.

The holder idiom relies on a guarantee in the Java language specification: a class is initialised exactly once, lazily, the first time it is used, and the JVM makes that initialisation thread-safe. The singleton lives in a private static nested class, so it is not created until getInstance() first touches that nested class, and no locking code is needed in the accessor.

static final class ConfigManager {
    private final Map<String, String> values = new ConcurrentHashMap<>();

    private ConfigManager() {}

    private static final class Holder {
        static final ConfigManager INSTANCE = new ConfigManager();   // created once, when Holder first loads
    }

    static ConfigManager getInstance() {
        return Holder.INSTANCE;
    }

    String get(String key, String defaultValue) {
        return values.getOrDefault(key, defaultValue);
    }

    void set(String key, String value) {
        values.put(key, value);                                      // ConcurrentHashMap rejects null values
    }
}

Eight threads asking for the instance at the same time all receive the very same object, and a value set through it is visible to later readers, with a default returned for a missing key. The backing map is a ConcurrentHashMap so concurrent reads and writes are safe, which also means it rejects null keys and values. Then say the architect’s caveat: a singleton is global mutable state, and global state is exactly what makes parallel tests interfere with each other. Use it for read-mostly configuration, pass collaborators in through constructors or dependency injection everywhere else, and keep anything that holds per-test state out of it.

86. Producer-Consumer With a BlockingQueue

One part of a framework generates work (test data, URLs to check, messages to send) and another part consumes it, which is the classic producer-consumer problem. A BlockingQueue connects them safely without any explicit wait and notify. With a bounded ArrayBlockingQueue, put blocks when the queue is full, which gives you backpressure for free, and take blocks when it is empty.

The remaining problem is how the consumer knows to stop. The usual answer is a poison pill: after the last real item, the producer puts a special value that no real item can equal, and the consumer exits when it sees it. With several consumers, the producer must put one pill per consumer.

static List<Integer> produceAndConsume(int itemCount, int queueCapacity) throws InterruptedException {
    BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(queueCapacity);
    final int poisonPill = -1;                                       // tells the consumer to stop
    List<Integer> consumed = new ArrayList<>();

    Thread producer = new Thread(() -> {
        try {
            for (int i = 1; i <= itemCount; i++) queue.put(i);       // blocks while the queue is full
            queue.put(poisonPill);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    });
    Thread consumer = new Thread(() -> {
        try {
            while (true) {
                int item = queue.take();                             // blocks while the queue is empty
                if (item == poisonPill) break;
                consumed.add(item);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    });
    producer.start();
    consumer.start();
    producer.join();
    consumer.join();
    return consumed;
}

With a queue holding only five items, a producer sending 200 numbers and a consumer receiving them, all 200 arrive in order and none is lost; zero items returns an empty list. Reading the consumed list after calling join on both threads is safe, because join guarantees that everything the thread did is visible to the caller. A plain ArrayList is acceptable here only because a single thread writes to it. Restoring the interrupt flag inside the catch blocks, rather than swallowing the exception, is a detail that senior interviewers look for. In real code you would normally use an ExecutorService instead of raw threads, but the queue and the stopping signal are the part this problem is about.

87. Fan Out API Calls With CompletableFuture and a Timeout

You need the results of several independent calls, such as health checks on five services, and the sequential time of all of them is too long. CompletableFuture lets you start every call at once, wait for all of them with allOf, and then read each result in the original order. The overall wait is bounded with get(timeout, unit), which throws a TimeoutException if the calls are not all finished in time.

static List<String> fetchAll(List<Supplier<String>> calls, long timeoutMs) throws Exception {
    List<CompletableFuture<String>> futures = new ArrayList<>();
    for (Supplier<String> call : calls) {
        futures.add(CompletableFuture.supplyAsync(call));
    }
    CompletableFuture<Void> all = CompletableFuture.allOf(futures.toArray(new CompletableFuture[0]));
    all.get(timeoutMs, TimeUnit.MILLISECONDS);                       // TimeoutException if too slow
    List<String> results = new ArrayList<>();
    for (CompletableFuture<String> f : futures) results.add(f.join());
    return results;
}

Three suppliers that sleep 50, 10 and 30 milliseconds return [a, b, c] in the order they were submitted, even though they finish in a different order. A supplier that takes 1.5 seconds with a 100 ms timeout makes the method throw a TimeoutException. A supplier that throws makes get raise an ExecutionException whose cause is the original exception, which is how you report which call failed and why. Three cautions are worth stating. First, a timeout does not stop a task that has already started; it only stops you waiting for it. Second, supplyAsync without an executor runs on the shared common pool, which is meant for short CPU work, so for blocking network calls pass your own executor to avoid starving other users of that pool. Third, Java 9 added orTimeout and completeOnTimeout directly on CompletableFuture, which this Java 8 version does without.

88. Builder Pattern for Test Data

Test data objects have many fields, and most tests care about only one or two. Constructors with long argument lists are hard to read and easy to get wrong, because the compiler cannot tell two strings apart. A builder gives every field a sensible default, lets a test set only what it cares about by name, and validates the result once in build().

static final class User {
    private final String name, email, role;
    private final int age;
    private final boolean active;

    private User(Builder b) {
        this.name = b.name;
        this.email = b.email;
        this.role = b.role;
        this.age = b.age;
        this.active = b.active;
    }

    static Builder builder() {
        return new Builder();
    }

    @Override
    public String toString() {
        return "User{name=" + name + ", email=" + email + ", role=" + role + ", age=" + age + ", active=" + active + "}";
    }

    static final class Builder {
        private String name = "Test User", email, role = "viewer";
        private int age = 30;
        private boolean active = true;

        Builder name(String v) { this.name = v; return this; }
        Builder email(String v) { this.email = v; return this; }
        Builder role(String v) { this.role = v; return this; }
        Builder age(int v) { this.age = v; return this; }
        Builder active(boolean v) { this.active = v; return this; }

        User build() {
            if (age < 0) throw new IllegalStateException("age must be >= 0");
            if (email == null) {
                email = name.toLowerCase(Locale.ROOT).replace(' ', '.') + "@example.test";
            }
            return new User(this);
        }
    }
}

A default build produces a viewer named “Test User” with the derived email test.user@example.test, aged 30 and active. Setting only the name derives a matching email, and setting every field overrides the defaults. A negative age makes build() throw, so an invalid object can never be created. The resulting User is immutable, because its fields are final and its constructor is private, which makes it safe to share between threads in a parallel run. Compare this with the alternatives if asked: telescoping constructors do not scale, setters leave the object half-built and mutable, and a static “object mother” factory with a few named presets is a good companion to a builder for the most common cases. Libraries such as Lombok can generate builders, but writing one by hand is still the expected interview answer.

89. Traverse a DOM-Like Tree and Find Its Depth

Every automation engineer works with a tree: the DOM. Questions about trees often use a simple node class with a tag, an optional id and a list of children. Two basic operations come up. Finding all nodes with a given tag in level order uses a queue: take a node, process it, add its children to the back of the queue, and repeat; that is breadth-first search. Finding the depth of the tree is naturally recursive: the depth of a node is one plus the depth of its deepest child.

static final class Node {
    final String tag, id;
    final List<Node> children = new ArrayList<>();

    Node(String tag, String id) {
        this.tag = tag;
        this.id = id;
    }

    Node add(Node child) {
        children.add(child);
        return this;
    }
}

static List<String> findIdsByTag(Node root, String tag) {
    List<String> ids = new ArrayList<>();
    Deque<Node> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        if (node.tag.equals(tag) && node.id != null) ids.add(node.id);
        queue.addAll(node.children);                                 // level by level
    }
    return ids;
}

static int maxDepth(Node node) {
    if (node == null) return 0;
    int deepest = 0;
    for (Node child : node.children) deepest = Math.max(deepest, maxDepth(child));
    return 1 + deepest;
}

For a tree where html contains body, which contains a div#main (holding a button, a link and an inner div with another button) and a footer, searching for button returns [save, cancel] and searching for div returns [main, inner]. A tag that does not occur returns an empty list. The depth of that tree is 5, and the depth of a null tree is 0. Both operations visit every node once, so the time is O(n); the queue can hold as many nodes as the widest level and the recursion uses as much stack as the tree is deep. Be precise about one thing: WebDriver returns matching elements in document order, which is a depth-first traversal, so breadth-first order is a different order of the same matches. Knowing which traversal you chose, and why, is the actual question.

90. Number of Islands

A grid contains 1 for land and 0 for water. Count the islands, where an island is a group of land cells connected horizontally or vertically. The standard method is a flood fill: scan the grid, and whenever you find an unvisited land cell, count a new island and then spread out from it, marking every connected land cell as visited so it is never counted again.

static int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    char[][] g = new char[grid.length][];
    for (int r = 0; r < grid.length; r++) g[r] = grid[r].clone();   // do not destroy the caller's grid
    int islands = 0;
    for (int r = 0; r < g.length; r++) {
        for (int c = 0; c < g[r].length; c++) {
            if (g[r][c] == '1') {
                islands++;
                sink(g, r, c);
            }
        }
    }
    return islands;
}

private static void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[r].length || g[r][c] != '1') return;
    g[r][c] = '0';                                                   // mark visited
    sink(g, r + 1, c);
    sink(g, r - 1, c);
    sink(g, r, c + 1);
    sink(g, r, c - 1);
}

The grid 11000 / 11000 / 00100 / 00011 has three islands. A grid of only water has none, a single land cell has one, an H-shaped block of land is one island, and a checkerboard of corner cells with a centre cell has five, because diagonal cells are not connected. The method works on a copy of the grid, so the caller’s data is left unchanged. Each cell is visited a constant number of times, so time is O(rows × columns). Recursive flood fill can overflow the stack on a large grid, so the iterative breadth-first version with a queue is the safer choice for big inputs, and union-find is the alternative when land cells are added over time. The same connected-components idea applies to many real problems, such as grouping dependent services in a graph or clusters of failing cells in a results matrix.

Beyond Coding: What Automation Architect Rounds Also Ask

The coding questions above are usually one part of an architect interview. The other part is design and judgement, and it helps to have a short, structured answer ready for each of the following.

• Design a test automation framework from scratch. Cover the layers (tests, page objects or API clients, core utilities), configuration per environment, test data management, reporting, parallel execution, CI/CD integration and how a new team member adds a test.
• Handle flaky tests. Separate causes (timing, shared state, environment, bad test data) from symptoms, quarantine and track flaky tests instead of silently retrying them, and fix the root cause.
• Make a framework thread-safe for parallel runs. One driver or client per thread (the ThreadLocal problem above), no shared mutable static state, isolated test data per test.
• Choose between UI, API and contract tests. Push as much verification as possible to the cheapest, fastest layer, and keep UI tests for the journeys that only the UI can prove.
• Apply design patterns appropriately. Page Object, Factory, Builder for test data, Strategy for pluggable behaviour such as retry policies, and Singleton with care, since global state makes parallel runs harder.
• Keep the framework maintainable. SOLID principles, dependency injection, clear naming, small utilities with their own unit tests, and code review for test code like production code.

For the Java and Selenium theory that sits behind these answers, the Java interview questions guide and the Selenium interview questions cover the fundamentals in question-and-answer form.

The Patterns Behind These Java Coding Interview Questions

Ninety problems collapse into a short list of patterns. Naming the pattern in an interview signals that you are solving a family of problems and not guessing.

• Two pointers: reverse a string, palindrome, reverse an array, remove duplicates from a sorted array, move zeros, merge sorted arrays, three sum, container with most water, and two sum on sorted input.
• Hash map or set (counting and lookup): anagram, group anagrams, first non-repeating and first repeated character, remove duplicate characters, character and element frequency, two sum, find duplicates, union, intersection, pair with a given difference, longest consecutive sequence, top K frequent.
• Prefix sums with a map: subarray sum equals k, product of array except self, and the sum trick in the missing-number problem.
• Sliding window: longest substring without repeating characters, subarray with a given sum (non-negative values), and the rate limiter.
• Expand around a centre: longest palindromic substring.
• Stack: valid parentheses.
• Heap (priority queue): kth largest, top K frequent.
• Backtracking: string permutations.
• In-place swapping and reversal: rotate an array, rotate a matrix, sort 0s, 1s and 2s, first missing positive.
• Single pass with a few variables: minimum and maximum, second largest, check sorted, leaders (right to left), maximum subarray (Kadane), best time to buy and sell stock, majority element.
• Sorting first, then a linear pass: merge intervals, three sum.
• Halving the search space: binary search.
• Careful string building and parsing: compress, reverse words, count words, remove whitespace, digits-only check, sort characters, all substrings, rotation check, atoi, longest common prefix.
• Monotonic deque and stack: sliding window maximum, min stack, decode string, valid parentheses, and trapping rain water (two pointers with running maximums).
• Linked-list pointers: reverse a list, detect a cycle with slow and fast pointers.
• Graph and grid traversal: number of islands (depth-first), DOM tree search (breadth-first), valid sudoku (set of encoded positions).
• Heap merging: merge k sorted arrays, kth largest, top K frequent.
• Framework building blocks: LRU cache (both ways), retry with backoff, polling wait, token bucket and sliding-window limiters, ThreadLocal, thread-safe singleton, producer-consumer, ExecutorService and CompletableFuture, builder for test data, flatten and diff of data.

Complexity Quick Reference by Approach

Use this table to review the usual time and space cost of each approach before an interview. Individual problems above note where they differ.

Quick Answers to Common Java Coding Interview Questions

What is the difference between an array and an ArrayList? An array has a fixed size set when it is created and can hold primitives such as int directly. An ArrayList resizes itself, holds only objects (so int values are boxed to Integer), and offers methods such as add and remove. Arrays are a little faster and lighter for plain index access; ArrayList is more convenient when the size changes.

When should I use a HashSet and when a HashMap? Use a HashSet when you only need to know whether a value has been seen: intersection, duplicates, pair finding. Use a HashMap when you need to attach information to each value, such as a count (frequency) or an index (two sum).

How does a sliding window work? Two indexes mark the ends of a contiguous range. The right end moves forward to take in the next element, and the left end moves forward whenever a condition is broken, such as the sum being too large or a character repeating. Each element enters and leaves the window at most once, which turns many O(n²) brute-force solutions into O(n).

What is the most efficient way to rotate an array? Reverse the whole array, then reverse the first k elements, then reverse the remaining n – k. That is O(n) time and O(1) extra space, with no second array.

Why does string concatenation in a loop get criticised? A String is immutable, so every += builds a brand-new String and copies the old contents. Over n iterations that is O(n²). A StringBuilder appends into a buffer it grows as needed, which keeps the whole loop at O(n).

Where to Practise Java Coding Interview Questions

Reading solutions teaches less than writing them. For timed practice with automatic test cases, work through the matching problems on LeetCode and HackerRank, and use GeeksforGeeks to see alternative solutions after you have written your own. The Big-O cheat sheet is a quick way to check the complexity of the collections you pick. The Oracle Java Tutorials cover the library classes used in the last two groups, in the Collections trail and the concurrency lesson.

Where This Shows Up in Test Automation Code

SDET interviews lean on these problems because the same moves appear in everyday test code. Checking a list of IDs returned by an API for duplicates is the find-duplicates problem with a set. Comparing the items on a page with the items in an API response, when order does not matter, is the anagram idea applied to lists: count with a map, then subtract. Verifying that a table column is sorted is a single loop comparing each element with its neighbour. Normalising text from the UI before asserting on it is string handling with the edge cases from the first half of this page: nulls, repeated spaces, case. A retry or rate-limit helper that only looks at the last N seconds of events is a sliding window. None of that needs a clever algorithm, but it does need the loop written correctly the first time.

How to Answer Java Coding Interview Questions Out Loud

The code is only part of what is being scored. A sequence that works for nearly every problem above:

1. Restate the problem in your own words and confirm the input and output types.
2. Ask the edge-case questions from the ground rules: null, empty, duplicates, case, sorted or not.
3. Say the brute-force approach and its complexity in a sentence or two.
4. Name the better approach and why it is better: one pass, constant space, no sort.
5. Write the code in small pieces and talk while you write. Silence reads as being stuck.
6. Run one small example through the code by hand, including one edge case.
7. State time and space complexity, and mention one trade-off you chose not to make.

Mistakes That Cost Marks

These show up in nearly every set of practice answers:

• Comparing strings with ==, or comparing Integer objects with ==. Boxed integers outside the range -128 to 127 are separate objects, so the comparison can fail for larger values.
• Off-by-one errors: looping to length instead of length - 1, or using <= where < was meant. Handling the last group in a run-length loop is the classic case.
• Forgetting empty and null input, then crashing on the first edge-case question.
• Expecting HashMap to keep insertion order. It does not; LinkedHashMap does.
• Removing elements from a list inside a for-each loop, which throws ConcurrentModificationException. Use an iterator or removeIf.
• Summing into an int when the total can pass roughly 2.1 billion.
• Calling Arrays.asList on an int[] and getting a list with one element (the array itself) instead of a list of numbers.

Practice Set: Variations to Try Without the Answers

If you can solve these cold after working through the page, you are in good shape: longest increasing subsequence, word break, coin change, course schedule (topological sort), lowest common ancestor of a binary tree, serialize and deserialize a binary tree, and an LFU cache. Pick three, set a 20-minute timer, and explain your reasoning out loud as you would in the real round.

References and Further Reading for Java Coding Interview Questions

These are the sources worth keeping open while you practise. The official documentation settles most “what does this method actually do” arguments, and the reference articles explain the algorithms behind the solutions above.

Official Java documentation

• HashMap Javadoc: iteration order, load factor and what happens on a collision.
• StringBuilder Javadoc: why repeated string concatenation in a loop is slow.
• PriorityQueue Javadoc: the heap behind every top-K and merge-K problem.
• ExecutorService Javadoc: thread pools for the parallel-execution questions.
• CompletableFuture Javadoc: chaining and combining asynchronous work.
• The Java Tutorials: Collections trail: a structured walk through List, Set, Map and Queue.
• The Java Tutorials: Concurrency lesson: threads, synchronization and the memory model in plain language.

Algorithm and pattern references

• Binary search: the boundary conditions that cause most off-by-one errors.
• Maximum subarray problem: Kadane’s algorithm and its history.
• Sieve of Eratosthenes: the standard way to list primes up to n.
• Token bucket: the rate-limiting algorithm used in the architect-level problems.
• Cycle detection: Floyd’s tortoise and hare for linked lists.
• Big-O cheat sheet: time and space complexity of common structures at a glance.

Test automation context

• Selenium waits documentation: the official explanation of explicit, implicit and fluent waits, which is the real-world version of the retry-with-timeout problem.
• Top 50 Java interview questions on QA Tribe: the theory side that pairs with these coding problems.
• Top 50 Selenium interview questions on QA Tribe: the framework side of the same interview loop.

Practice platforms

• LeetCode: timed practice with automatic test cases.
• HackerRank: good for warm-up problems and company-style assessments.
• GeeksforGeeks: alternative explanations when a solution above does not click.

What to Take Away

The Java coding interview questions on this page are small on purpose. A coding round for an SDET role is not looking for a competitive-programming result. It is checking whether you write clear, correct code under mild pressure and can talk about it like an engineer. Careful input handling, a sensible choice of data structure and a plain statement of complexity will carry a solution that is not the cleverest one in the room. Learn the patterns, practise saying the approach before you write it, and keep your solutions boring and correct.

Bookmark this page and work through it in order over a week rather than reading it once. Solve each problem without looking, compare with the solution, and write down the pattern in one line. That habit is what makes the next unfamiliar problem look like a familiar one.

🔥 Continue Your Learning Journey

Want to go beyond Playwright with Typescript setup and crack interviews faster? Check these hand-picked guides:

👉 🚀 Master TestNG Framework (Enterprise Level)
Build scalable automation frameworks with CI/CD, parallel execution, and real-world architecture
➡️ Read: TestNG Automation Framework – Complete Architect Guide

👉 🧠 Learn Cucumber (BDD from Scratch to Advanced)
Understand Gherkin, step definitions, and real-world BDD framework design
➡️ Read: Cucumber Automation Framework – Beginner to Advanced Guide

👉 🔐 API Authentication Made Simple
Master JWT, OAuth, Bearer Tokens with real API testing examples
➡️ Read: Ultimate API Authentication Guide

👉 ⚡ Crack Playwright Interviews (2026 Ready)
Top real interview questions with answers and scenarios
➡️ Read: Playwright Interview Questions Guide