Chapter 3: Algorithms & Data Structures
These exercises cover classic algorithm questions asked in Java interviews. Each solution includes time/space complexity and a key phrase to say in an interview.
Exercise 1 — Word Frequency Counter (HashMap)
"Count the frequency of each word in a string."
Imperative Solution
public Map<String, Integer> wordCount(String text) {
Map<String, Integer> freq = new HashMap<>();
for (String word : text.toLowerCase().split("\\s+")) {
freq.merge(word, 1, Integer::sum);
}
return freq;
}
Solution with Streams
public Map<String, Long> wordCountStream(String text) {
return Arrays.stream(text.toLowerCase().split("\\s+"))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
Test: "hello world hello java" → {hello=2, world=1, java=1}
"I used merge() for the imperative approach and groupingBy for the stream approach. Both are O(n)."
Exercise 2 — Valid Parentheses Check (Stack)
"Check if a string of parentheses is valid: (), [], "
Solution
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
Tests:
"({[]})" → true
"({[}])" → false
"(((" → false
"" → true
Complexity: O(n) time, O(n) space.
"Classic stack problem. O(n) time, O(n) space. I used ArrayDeque instead of the legacy Stack class because it's faster and recommended by the Java documentation."
Exercise 3 — Reverse a Linked List
"Reverse a singly linked list."
Solution
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save the next
curr.next = prev; // reverse the pointer
prev = curr; // advance prev
curr = next; // advance curr
}
return prev;
}
Visualization:
Before: 1 → 2 → 3 → null
After: 3 → 2 → 1 → null
Complexity: O(n) time, O(1) space.
"Three pointers: prev, curr, next. O(n) time, O(1) space. This is a classic that tests pointer manipulation."
Exercise 4 — Binary Search
"Implement a binary search on a sorted array."
Solution
public int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids integer overflow
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
}
Test: [1, 3, 5, 7, 9, 11], target = 7 → returns 3 (index)
Complexity: O(log n) time, O(1) space.
Why lo + (hi - lo) / 2 instead of (lo + hi) / 2?
Because lo + hi can exceed Integer.MAX_VALUE if both values are large. It's a detail interviewers love.
"I use lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow. Classic O(log n) search on sorted data."
Exercise 5 — Two Sum
"Find two numbers in an array whose sum equals a target."
O(n) Solution with HashMap
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[] { seen.get(complement), i };
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
Test: [2, 7, 11, 15], target = 9 → returns [0, 1] (because 2 + 7 = 9)
Complexity: O(n) time, O(n) space.
The Idea
For each number x, we check if target - x has already been seen. The HashMap allows us to do this check in O(1).
"Single-pass HashMap solution. For each number, I check if the complement exists in the map. O(n) time instead of the brute-force O(n²)."
Exercise 6 — FizzBuzz (the classic)
"Print numbers from 1 to n. For multiples of 3: 'Fizz'. For multiples of 5: 'Buzz'. For both: 'FizzBuzz'."
Clean Solution
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) result.add("FizzBuzz");
else if (i % 3 == 0) result.add("Fizz");
else if (i % 5 == 0) result.add("Buzz");
else result.add(String.valueOf(i));
}
return result;
}
Extensible Solution (if the interviewer adds rules)
public List<String> fizzBuzz(int n) {
record Rule(int divisor, String word) {}
List<Rule> rules = List.of(
new Rule(3, "Fizz"),
new Rule(5, "Buzz"),
new Rule(7, "Jazz") // easy to add!
);
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
final int num = i;
String s = rules.stream()
.filter(r -> num % r.divisor() == 0)
.map(Rule::word)
.collect(Collectors.joining());
result.add(s.isEmpty() ? String.valueOf(i) : s);
}
return result;
}
"I start with the simple version, but if the interviewer asks for extensibility, I switch to a rule-based approach. Adding a new rule is just one line."
Exercise 7 — Find the First Duplicate
"Find the first duplicated element in an array."
Solution
public int firstDuplicate(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return num;
}
return -1; // no duplicate
}
Tip: Set.add() returns false if the element already exists — no need for separate contains().
Test: [2, 1, 3, 5, 3, 2] → returns 3 (first duplicate encountered)
Complexity: O(n) time, O(n) space.
Exercise 8 — Check if Two Strings are Anagrams
"Check if two strings are anagrams."
Solution
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
Test: "listen", "silent" → true
Complexity: O(n) time, O(1) space (fixed array of 26).
"I use a frequency counter array instead of sorting (O(n log n)). Single pass, O(n) time, O(1) space since the alphabet is fixed."
Complexity Summary
| Exercise | Time | Space | Key Structure |
|---|---|---|---|
| Word Frequency | O(n) | O(n) | HashMap |
| Valid Parentheses | O(n) | O(n) | Stack (ArrayDeque) |
| Reverse linked list | O(n) | O(1) | 3 pointers |
| Binary Search | O(log n) | O(1) | Division by 2 |
| Two Sum | O(n) | O(n) | HashMap (complement) |
| FizzBuzz | O(n) | O(n) | Modulo |
| First Duplicate | O(n) | O(n) | HashSet |
| Anagram | O(n) | O(1) | Frequency array |
⬅️ Chapter 2: Refactoring | Chapter 4: REST Design & Patterns →