String & Collection Programs — Interview Questions

How to use this lesson

These programs test whether you can use collections fluently. For each one, state the approach and its complexity, then mention the edge case the interviewer is waiting for: empty input, case sensitivity, duplicates, or iteration-order assumptions.

Q1. Count the number of occurrences of each word in a string using a HashMap.

Short answer: Normalise the text, split it on whitespace, and count with Map.merge (or getOrDefault). O(n) time.

static Map<String, Integer> countWords(String text) {
    Map<String, Integer> counts = new HashMap<>();
    if (text == null || text.isBlank()) return counts;
    for (String word : text.trim().toLowerCase(Locale.ROOT).split("\\s+")) {
        counts.merge(word, 1, Integer::sum);
    }
    return counts;
}
// "the cat and the hat" → {the=2, cat=1, and=1, hat=1}

Key points to cover:

• Without trim(), leading whitespace produces an empty first "word", because " a".split("\\s+") gives ["", "a"].
• Decide with the interviewer: case-insensitive? strip punctuation (split("\\W+"))?
• Stream version: Arrays.stream(words).collect(groupingBy(identity(), counting())).
• For output sorted by word, use a TreeMap. For first-seen order, use a LinkedHashMap.

Learn it in depth → HashMap Deep Dive

Q2. Iterate over a HashMap using a while loop and an enhanced for loop.

Short answer: Iterate over entrySet(), so you get the key and the value together without extra lookups. Use the enhanced for loop for reading. Use an explicit Iterator in a while loop when you need to remove entries as you go.

Map<String, Integer> stock = new HashMap<>(Map.of("apple", 5, "pear", 0, "kiwi", 12));

for (Map.Entry<String, Integer> e : stock.entrySet()) {          // enhanced for
    System.out.println(e.getKey() + " -> " + e.getValue());
}

Iterator<Map.Entry<String, Integer>> it = stock.entrySet().iterator();
while (it.hasNext()) {                                            // while + Iterator
    Map.Entry<String, Integer> e = it.next();
    if (e.getValue() == 0) it.remove();                           // safe removal
}

stock.forEach((k, v) -> System.out.println(k + " -> " + v));     // Java 8

Key points to cover:

• Iterating over keySet() and calling map.get(key) inside the loop does a second lookup per entry.
• HashMap has no defined order, so don't write code or tests that depend on it.
• Removing through map.remove inside a for-each loop throws a ConcurrentModificationException. Use it.remove() or map.entrySet().removeIf(...).

Q3. Iterate over an ArrayList using a for loop, a while loop and an enhanced for loop.

List<Integer> list = List.of(10, 20, 30);

for (int i = 0; i < list.size(); i++) System.out.println(list.get(i));   // index-based

int j = 0;
while (j < list.size()) System.out.println(list.get(j++));               // while

for (int value : list) System.out.println(value);                         // enhanced for (uses the Iterator)

list.forEach(System.out::println);                                        // Java 8

Key points to cover:

• Index-based loops are fine for ArrayList, where get(i) is O(1), but they're O(n²) overall for a LinkedList. The enhanced for loop is O(n) for both.
• Enhanced for over a List<Integer> into an int unboxes each element. A null element causes an NPE.
• ListIterator lets you walk backwards, or modify the list while iterating.

Learn it in depth → Iterators & Modification Semantics

Q4. Find the duplicate characters in a string.

Short answer: Count each character in a map (or in an int[] for a small alphabet), then report the characters with a count above 1. O(n) time.

static Map<Character, Integer> duplicateChars(String s) {
    Map<Character, Integer> counts = new LinkedHashMap<>();        // keeps first-seen order
    for (char c : s.toCharArray()) {
        if (!Character.isWhitespace(c)) counts.merge(c, 1, Integer::sum);
    }
    counts.values().removeIf(n -> n == 1);
    return counts;
}
// "programming" → {r=2, g=2, m=2}

Key points to cover:

• For lowercase ASCII letters, an int[26] counter is faster, and uses less memory than a map of boxed Character/Integer values.
• To find only which characters repeat, a Set<Character> "seen" check is enough: if (!seen.add(c)) duplicates.add(c);.
• Clarify case sensitivity with the interviewer: should 'P' and 'p' count as the same character?

Q5. Find the second-highest number in an array.

Short answer: Scan once, tracking the highest and the second highest. When a value beats highest, the old highest becomes second. Skip values equal to highest, so duplicates don't count. O(n) time, O(1) space.

static OptionalInt secondHighest(int[] nums) {
    long highest = Long.MIN_VALUE, second = Long.MIN_VALUE;   // long sentinels: works even if the array contains Integer.MIN_VALUE
    for (int n : nums) {
        if (n > highest) {
            second = highest;
            highest = n;
        } else if (n < highest && n > second) {
            second = n;
        }
    }
    return second == Long.MIN_VALUE ? OptionalInt.empty() : OptionalInt.of((int) second);
}
// [4, 9, 9, 2] → 4        [5, 5] → empty

Key points to cover:

• Returning Integer.MIN_VALUE for "no answer" is ambiguous, because it could be a real value. OptionalInt (or an exception) makes "not found" explicit.
• Sorting works too, at O(n log n): Arrays.stream(nums).distinct().sorted(), then take the second-last element.
• For the k-th largest, use a min-heap of size k: O(n log k).

Learn it in depth → Kth Largest Element in an Array

Q6. Remove all whitespace from a string without using replace().

Short answer: Build a new string with a StringBuilder, appending only the characters that aren't whitespace. O(n).

static String removeWhitespace(String s) {
    StringBuilder sb = new StringBuilder(s.length());
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!Character.isWhitespace(c)) sb.append(c);     // spaces, tabs, newlines, …
    }
    return sb.toString();
}

Common trap: checking only c != ' ', which leaves tabs and newlines in place. Character.isWhitespace covers them all. (replaceAll("\\s+", "") is the one-line version when replace is allowed.)

Q7. Accept comma-separated strings, sort them, and output them concatenated.

Short answer: Split on commas, trim each part, drop the empty parts, sort, then join.

static String sortAndConcatenate(String input) {
    return Arrays.stream(input.split(","))
            .map(String::trim)
            .filter(s -> !s.isEmpty())
            .sorted()                                     // natural (lexicographic) order
            .collect(Collectors.joining());               // or joining(",") to keep separators
}
// "pear, apple,banana" → "applebananapear"

Key points to cover:

• Lexicographic order is case-sensitive: uppercase letters sort before lowercase ones. Use String.CASE_INSENSITIVE_ORDER if needed.
• Without trim, " apple" sorts before "banana" because of the leading space.

Follow-up questions this topic invites — and their answers

Q: How do you find the first non-repeating character in a string? A: Count the characters into a LinkedHashMap (or an int[]), then scan the string again, or iterate the map, and return the first character with a count of 1. O(n) time.

Q: How do you check whether two strings are anagrams? A: If the lengths match, count the characters of one string up and the other down in an int[26] array. They're anagrams if every count ends at 0. O(n). Alternatively, sort both char arrays and compare, which is O(n log n).

Q: How would you sort a HashMap by its values? A: map.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (a, b) -> a, LinkedHashMap::new)). The LinkedHashMap keeps the sorted order.

Q: How do you remove duplicates from a list while keeping the order? A: new ArrayList<>(new LinkedHashSet<>(list)), or list.stream().distinct().toList().