DSA Java QA Harness — 40 Questions + 20 Algorithms (and more)

Animated walkthroughs of every question/algorithm, generated with the manim-storytelling-skills pack (HeyGen-inspired narrative to 5-act Manim walkthrough, closed with a "verified by test" beat). Each question shows the real problem statement, a diagram, the actual Java function, the real JUnit test, then the full-width animation.

Most-asked DSA questions to ace your next interview:

➤ Arrays and Strings

• Find the maximum sum subarray.
• Find all substrings that are palindromes.
• Implement the "two sum" problem.
• Implement Kadane's algorithm for maximum subarray sum.
• Find the missing number in an array of integers.
• Merge two sorted arrays into one sorted array.
• Check if a string is a palindrome.
• Find the first non-repeating character in a string.
• Write a program to remove duplicates from a sorted array.

➤ Linked Lists 10. Reverse a linked list. 11. Detect a cycle in a linked list. 12. Find the middle of a linked list. 13. Merge two sorted linked lists. 14. Implement a stack using linked list. 15. Find the intersection point of two linked lists.

➤ Stacks and Queues 16. Implement a stack using an array. 17. Implement a stack that supports push, pop, top, and retrieving the minimum element. 18. Implement a circular queue. 19. Design a max stack that supports push, pop, top, retrieve maximum element. 20. Design a queue using stacks.

➤ Trees and Binary Search Trees 21. Find the height of a binary tree. 22. Find the lowest common ancestor of two nodes in a binary tree. 23. Validate if a binary tree is a valid binary search tree. 24. Serialize and deserialize a binary tree. 25. Implement an inorder traversal of a binary tree. 26. Find the diameter of a binary tree. 27. Convert a binary tree to its mirror tree.

➤ Graphs 28. Implement depth-first search (DFS). 29. Implement breadth-first search (BFS). 30. Find the shortest path between two nodes in an unweighted graph. 31. Detect a cycle in an undirected graph using DFS. 32. Check if a graph is bipartite. 33. Find the number of connected components in an undirected graph. 34. Find bridges in a graph.

➤ Sorting and Searching 35. Implement (bubble, insertion, selection, merge) sort. 36. Implement quicksort. 37. Implement binary search. 38. Implement interpolation search. 39. Find the kth smallest element in an array. 40. Given an array of integers, count the number of inversions it has. An inversion occurs when two elements in the array are out of order.

---

A runnable, tested study guide: 40 DSA interview questions and 20+ core algorithms, implemented in modern Java (records, sealed, var, Stream API, generics + wildcards, Optional, pattern-matching switch) and pinned down with 96 JUnit 5 tests. Every question and algorithm below has its own Manim animated explainer (GIF) and, where drawn, a mermaid diagram.

🗺️ Start here — architecture & coverage

graph TD
    subgraph Questions["40 Questions by topic"]
        Q1[Arrays & Strings]
        Q2[Linked Lists]
        Q3[Trees & BST]
        Q4[Graphs]
        Q5[Dynamic Programming]
        Q6[Bit Manipulation]
    end
    subgraph Algos["20+ Algorithms"]
        A1[Sorting]
        A2[Graph traversals]
        A3[Number theory]
        A4[Data structures]
        A5[Backtracking]
    end
    JUnit[JUnit 5 - 96 tests] --> Questions
    JUnit --> Algos

Loading

🚀 Quick start (clone → run → test)

git clone https://github.com/dbillion/dsa-java-gradleqa.git
cd dsa-java-gradleqa
export JAVA_HOME="$HOME/.sdkman/candidates/java/17.0.12-graal"
export PATH="$JAVA_HOME/bin:$PATH"
./gradlew test          # 96 JUnit tests, all green

---

Index

Interview Questions

• Q1. Find the maximum sum subarray (and return the subarray itself, not just the sum).
• Q2. Find all substrings that are palindromes.
• Q3. Implement the "two sum" problem.
• Q4. Implement Kadane's algorithm for maximum subarray sum (prefix-sum framing).
• Q5. Missing number
• Q6. Group anagrams
• Q6. Merge two sorted
• Q7. Max area
• Q8. First unique char
• Q9. Three sum
• Q9. Remove duplicates from a sorted array (in place, return new length).
• Q10. Length of longest substring
• Q11. Check if a string is a palindrome.
• Q12. Longest common prefix
• Q13. Is valid parentheses
• Q14. Run length encode
• Q15. Implement binary search.
• Q16. Implement a stack using an array.
• Q16. Search rotated
• Q17. First bad version
• Q17. Implement a stack supporting push/pop/top/get-min, all O(1).
• Q18. Implement a circular queue.
• Q18. Median of sorted
• Q19. Design a max stack supporting push/pop/top/retrieve-max.
• Q19. Reverse list
• Q20. Detect a cycle in a linked list.
• Q20. Queue with stacks
• Q21. Merge two lists
• Q22. Lca
• Q22. Remove nth from end
• Q23. Is valid bst
• Q23. Max depth
• Q24. Implement an inorder traversal of a binary tree (as a lazy generator).
• Q24. Serialize tree
• Q25. Is same tree
• Q26. Diameter
• Q26. Num islands
• Q27. Clone graph
• Q27. Mirror
• Q28. Can finish
• Q29. Dijkstra
• Q30. Find the shortest path between two nodes in an unweighted graph.
• Q31. Fib
• Q31. Cycle undirected
• Q32. Climb stairs
• Q32. Bipartite
• Q33. Coin change
• Q33. Connected components
• Q34. Length of lis
• Q34. Bridges
• Q35. Edit distance
• Q36. Knapsack
• Q38. Implement interpolation search.
• Q39. Kth small est
• Q40. Count inversions

Algorithms

• A1. Bubble sort
• A2. Merge sort
• A3. Quick sort
• A4. Heap sort
• A5. Implement breadth-first search.
• A6. Implement depth-first search (as a lazy generator over a Graph).
• A7. Union find
• A8. Sieve
• A11. Sliding window max
• A12. Topo sort
• A13. Kruskal
• A15. Lcs
• A16. Level order
• A17. Prim
• A18. Matrix chain
• A21. Selection sort
• A22. Insertion sort
• A25. Kmp
• A26. Rabin karp
• A27. Trie
• A28. Subsets
• A29. Permutations
• A30. N queens
• A31. Segment tree

Graph Extras

• G0. Astar
• G0. Bellmanford
• G0. Floodfill
• G0. Floydwarshall

---

Interview Questions

Q1. Find the maximum sum subarray (and return the subarray itself, not just the sum).

Diagram	Topic / Scene
	Arrays_Subarrays q1_max_sum_subarray

Function (Algorithms.java):

public static SubarrayResult maxSumSubarray(int[] nums) {
        int bestSum = nums[0], currentSum = nums[0];
        int bestStart = 0, bestEnd = 0, currentStart = 0;
        for (int i = 1; i < nums.length; i++) {
            if (currentSum < 0) { currentSum = nums[i]; currentStart = i; }
            else currentSum += nums[i];
            if (currentSum > bestSum) { bestSum = currentSum; bestStart = currentStart; bestEnd = i; }
        }
        return new SubarrayResult(bestSum, Arrays.copyOfRange(nums, bestStart, bestEnd + 1));
    }

Unit test (JUnit 5):

var r = Algorithms.maxSumSubarray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
 assertEquals(6, r.sum());
 assertArrayEquals(new int[]{4,-1,2,1}, r.subarray());

Q2. Find all substrings that are palindromes.

Diagram	Topic / Scene
	Strings q2_all_palindromic_substrings

Function (Algorithms.java):

public static List<String> allPalindromicSubstrings(String s) {
        List<String> result = new ArrayList<>();
        for (int center = 0; center < 2 * s.length() - 1; center++) {
            int left = center / 2, right = left + center % 2;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                result.add(s.substring(left, right + 1));
                left--; right++;
            }
        }
        return result;
    }

Unit test (JUnit 5):

var pals = Algorithms.allPalindromicSubstrings("abcba");
 assertEquals(7, pals.size());
 assertTrue(pals.containsAll(List.of("a","b","c","bcb","abcba")));

Q3. Implement the "two sum" problem.

Diagram	Topic / Scene
	TwoPointers q03_two_sum

Function (Algorithms.java):

public static int[] twoSum(int[] nums, int target) {
        var seen = new HashMap<Integer, Integer>();
        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 NoSuchElementException("no two sum solution");
    }

Unit test (JUnit 5):

assertArrayEquals(new int[]{0,1}, Algorithms.twoSum(new int[]{2,7,11,15}, 9));

Q4. Implement Kadane's algorithm for maximum subarray sum (prefix-sum framing).

Diagram	Topic / Scene
	Arrays_Subarrays q4_kadane_via_prefix_sums

Function (Algorithms.java):

public static int kadaneViaPrefixSums(int[] nums) {
        int[] minPrefix = {0};   // running minimum of prefix sums (starts at 0 for empty prefix)
        int[] best = {nums[0]};
        int[] running = {0};     // running prefix sum
        for (int n : nums) {
            running[0] += n;
            best[0] = Math.max(best[0], running[0] - minPrefix[0]);
            minPrefix[0] = Math.min(minPrefix[0], running[0]);
        }
        return best[0];
    }

Unit test (JUnit 5):

assertEquals(6, Algorithms.kadaneViaPrefixSums(new int[]{-2,1,-3,4,-1,2,1,-5,4}));

Q5. Missing number

Diagram	Topic / Scene
	Arrays_Subarrays q05_missing_number

Function (Algorithms.java):

public static int missingNumber(int[] nums) {
        int x = nums.length;
        for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
        return x;
    }

Unit test (JUnit 5):

assertEquals(2, Algorithms.missingNumber(new int[]{3,0,1}));

Q6. Group anagrams

Diagram	Topic / Scene
	Strings q6_group_anagrams

Function (Algorithms.java):

public static List<List<String>> groupAnagrams(String[] words) {
        return new ArrayList<>(Arrays.stream(words)
                .collect(Collectors.groupingBy(w -> w.chars().sorted()
                        .collect(StringBuilder::new, (sb, c) -> sb.append((char) c), StringBuilder::append).toString()))
                .values());
    }

Unit test (JUnit 5):

var groups = Algorithms.groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"});
 assertEquals(3, groups.size());

Q6. Merge two sorted

Diagram	Topic / Scene
	Strings q6_merge_two_sorted

Function (Algorithms.java):

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

Unit test (JUnit 5):

assertArrayEquals(new int[]{1,2,3,4,5,6}, Algorithms.mergeTwoSorted(new int[]{1,3,5}, new int[]{2,4,6}));

Q7. Max area

Diagram	Topic / Scene
	Other q07_max_area

Function (Algorithms.java):

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

Unit test (JUnit 5):

assertEquals(49, Algorithms.maxArea(new int[]{1,8,6,2,5,4,8,3,7}));

Q8. First unique char

Diagram	Topic / Scene
	Strings q8_first_unique_char

Function (Algorithms.java):

public static OptionalInt firstUniqueChar(String s) {
        var counts = s.chars().boxed()
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        for (int i = 0; i < s.length(); i++) {
            if (counts.get((int) s.charAt(i)) == 1L) return OptionalInt.of(i);
        }
        return OptionalInt.empty();
    }

Unit test (JUnit 5):

assertEquals(0, Algorithms.firstUniqueChar("leetcode").getAsInt());
 assertTrue(Algorithms.firstUniqueChar("aabb").isEmpty());

Q9. Three sum

Diagram	Topic / Scene
	TwoPointers q09_three_sum

Function (Algorithms.java):

public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        var result = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.add(List.of(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < 0) l++; else r--;
            }
        }
        return result;
    }

Unit test (JUnit 5):

assertEquals(List.of(List.of(-1,-1,2), List.of(-1,0,1)),
 Algorithms.threeSum(new int[]{-1,0,1,2,-1,-4}));

Q9. Remove duplicates from a sorted array (in place, return new length).

Diagram	Topic / Scene
	Strings q9_remove_duplicates

Function (Algorithms.java):

public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int k = 1;
        for (int i = 1; i < nums.length; i++) if (nums[i] != nums[k - 1]) nums[k++] = nums[i];
        return k;
    }

Unit test (JUnit 5):

int[] a = {1,1,2,2,3}; assertEquals(3, Algorithms.removeDuplicates(a));
 assertArrayEquals(new int[]{1,2,3,2,3}, a);

Q10. Length of longest substring

Diagram	Topic / Scene
no diagram	Strings q10_longest_substring

Function (Algorithms.java):

public static int lengthOfLongestSubstring(String s) {
        var seen = new HashSet<Character>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            while (seen.contains(s.charAt(right))) seen.remove(s.charAt(left++));
            seen.add(s.charAt(right));
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.lengthOfLongestSubstring("abcabcbb"));

Q11. Check if a string is a palindrome.

Diagram	Topic / Scene
	Strings q11_is_palindrome

Function (Algorithms.java):

public static boolean isPalindrome(String s) {
        String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        return IntStream.range(0, cleaned.length() / 2)
                .allMatch(i -> cleaned.charAt(i) == cleaned.charAt(cleaned.length() - 1 - i));
    }

Unit test (JUnit 5):

assertTrue(Algorithms.isPalindrome("A man, a plan, a canal: Panama"));
 assertFalse(Algorithms.isPalindrome("race a car"));

Q12. Longest common prefix

Diagram	Topic / Scene
	Strings q12_longest_common_prefix

Function (Algorithms.java):

public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (String s : strs) {
            while (!s.startsWith(prefix)) prefix = prefix.substring(0, prefix.length() - 1);
        }
        return prefix;
    }

Unit test (JUnit 5):

assertEquals("fl", Algorithms.longestCommonPrefix(new String[]{"flower","flow","flight"}));

Q13. Is valid parentheses

Diagram	Topic / Scene
no diagram	Stacks_Queues s06_valid_parentheses

Function (Algorithms.java):

public static boolean isValidParentheses(String s) {
        var stack = new ArrayDeque<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (stack.isEmpty() || !matches(stack.pop(), c)) return false;
        }
        return stack.isEmpty();
    }

Unit test (JUnit 5):

assertTrue(Algorithms.isValidParentheses("()[]{}"));
 assertFalse(Algorithms.isValidParentheses("(]"));

Q14. Run length encode

Diagram	Topic / Scene
	Strings q14_run_length_encode

Function (Algorithms.java):

public static RLE runLengthEncode(String s) {
        if (s.isEmpty()) return new RLE("");
        var 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 new RLE(sb.toString());
    }

Unit test (JUnit 5):

assertEquals("a3b2c1", Algorithms.runLengthEncode("aaabbc").encoded());

Q15. Implement binary search.

Diagram	Topic / Scene
no diagram	Searching s01_binary_search

Function (Algorithms.java):

public static int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            if (nums[m] < target) l = m + 1; else r = m - 1;
        }
        return -1;
    }

Unit test (JUnit 5):

assertEquals(4, Algorithms.binarySearch(new int[]{-1,0,3,5,9,12}, 9));
 assertEquals(-1, Algorithms.binarySearch(new int[]{-1,0,3,5,9,12}, 2));

Q16. Implement a stack using an array.

Diagram	Topic / Scene
	Stacks_Queues q16_array_stack

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var s = new Algorithms.ArrayStack(3); s.push(1); s.push(2);
 assertEquals(2, s.top()); assertEquals(2, s.pop()); assertEquals(1, s.pop());

Q16. Search rotated

Diagram	Topic / Scene
	Searching q16_search_rotated

Function (Algorithms.java):

public static int searchRotated(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {
                if (target >= nums[l] && target < nums[m]) r = m - 1; else l = m + 1;
            } else {
                if (target > nums[m] && target <= nums[r]) l = m + 1; else r = m - 1;
            }
        }
        return -1;
    }

Unit test (JUnit 5):

assertEquals(4, Algorithms.searchRotated(new int[]{4,5,6,7,0,1,2}, 0));

Q17. First bad version

Diagram	Topic / Scene
	Searching q17_first_bad_version

Function (Algorithms.java):

public static int firstBadVersion(int n, IntPredicate isBad) {
        int l = 1, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isBad.test(m)) r = m; else l = m + 1;
        }
        return l;
    }

Unit test (JUnit 5):

assertEquals(4, Algorithms.firstBadVersion(5, v -> v >= 4));

Q17. Implement a stack supporting push/pop/top/get-min, all O(1).

Diagram	Topic / Scene
	Stacks_Queues q17_min_stack

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var s = new Algorithms.MinStack(); s.push(3); s.push(1); s.push(2);
 assertEquals(1, s.getMin()); s.pop(); assertEquals(1, s.getMin());

Q18. Implement a circular queue.

Diagram	Topic / Scene
	Stacks_Queues q18_circular_queue

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var q = new Algorithms.CircularQueue(3);
 assertTrue(q.enqueue(1)); assertTrue(q.enqueue(2)); assertEquals(1, q.dequeue());
 assertEquals(2, q.dequeue()); assertTrue(q.isEmpty());

Q18. Median of sorted

Diagram	Topic / Scene
	Heap_PQ q18_median_of_sorted

Function (Algorithms.java):

public static OptionalDouble medianOfSorted(int[] a, int[] b) {
        if (a.length == 0 && b.length == 0) return OptionalDouble.empty();
        var merged = IntStream.concat(IntStream.of(a), IntStream.of(b)).sorted().toArray();
        int n = merged.length;
        return OptionalDouble.of(n % 2 == 1 ? merged[n / 2]
                : (merged[n / 2 - 1] + merged[n / 2]) / 2.0);
    }

Unit test (JUnit 5):

assertEquals(2.0, Algorithms.medianOfSorted(new int[]{1,3}, new int[]{2}).getAsDouble());

Q19. Design a max stack supporting push/pop/top/retrieve-max.

Diagram	Topic / Scene
	Stacks_Queues q19_max_stack

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var s = new Algorithms.MaxStack(); s.push(1); s.push(3); s.push(2);
 assertEquals(3, s.getMax()); s.pop(); assertEquals(3, s.top()); assertEquals(3, s.getMax());

Q19. Reverse list

Diagram	Topic / Scene
no diagram	LinkedLists s07_reverse_list

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var h = new Algorithms.ListNode(1); h.next = new Algorithms.ListNode(2); h.next.next = new Algorithms.ListNode(3);
 var r = Algorithms.reverseList(h);
 assertEquals(3, r.val); assertEquals(2, r.next.val); assertEquals(1, r.next.next.val);

Q20. Detect a cycle in a linked list.

Diagram	Topic / Scene
	LinkedLists q20_has_cycle

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var a = new Algorithms.ListNode(1); a.next = new Algorithms.ListNode(2); a.next.next = a;
 assertTrue(Algorithms.hasCycle(a));
 var b = new Algorithms.ListNode(1); b.next = new Algorithms.ListNode(2);
 assertFalse(Algorithms.hasCycle(b));

Q20. Queue with stacks

Diagram	Topic / Scene
	LinkedLists q20_queue_with_stacks

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var q = new Algorithms.QueueWithStacks(); q.enqueue(1); q.enqueue(2);
 assertEquals(1, q.dequeue()); assertEquals(2, q.dequeue());

Q21. Merge two lists

Diagram	Topic / Scene
	LinkedLists q21_merge_two_lists

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var x = new Algorithms.ListNode(1); x.next = new Algorithms.ListNode(3);
 var y = new Algorithms.ListNode(2); y.next = new Algorithms.ListNode(4);
 var m = Algorithms.mergeTwoLists(x, y);
 assertEquals(1, m.val); assertEquals(2, m.next.val); assertEquals(3, m.next.next.val);

Q22. Lca

Diagram	Topic / Scene
	Trees q22_lca

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode r = new Algorithms.TreeNode(1);
 r.left = new Algorithms.TreeNode(2); r.right = new Algorithms.TreeNode(3);
 r.left.left = new Algorithms.TreeNode(4); r.left.right = new Algorithms.TreeNode(5);
 assertEquals(2, Algorithms.lowestCommonAncestor(r, r.left.left, r.left.right).val);

Q22. Remove nth from end

Diagram	Topic / Scene
	LinkedLists q22_remove_nth_from_end

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var h = new Algorithms.ListNode(1); h.next = new Algorithms.ListNode(2); h.next.next = new Algorithms.ListNode(3);
 var r = Algorithms.removeNthFromEnd(h, 2);
 assertEquals(1, r.val); assertEquals(3, r.next.val);

Q23. Is valid bst

Diagram	Topic / Scene
	Trees q23_is_valid_b_s_t

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode r = new Algorithms.TreeNode(2);
 r.left = new Algorithms.TreeNode(1); r.right = new Algorithms.TreeNode(3);
 assertTrue(Algorithms.isValidBST(r));
 Algorithms.TreeNode bad = new Algorithms.TreeNode(5);
 bad.left = new Algorithms.TreeNode(6); bad.right = new Algorithms.TreeNode(7);
 assertFalse(Algorithms.isValidBST(bad));

Q23. Max depth

Diagram	Topic / Scene
no diagram	Trees s04_max_depth

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode root = new Algorithms.TreeNode(1);
 root.left = new Algorithms.TreeNode(2); root.right = new Algorithms.TreeNode(3);
 root.left.left = new Algorithms.TreeNode(4);
 assertEquals(3, Algorithms.maxDepth(root));

Q24. Implement an inorder traversal of a binary tree (as a lazy generator).

Diagram	Topic / Scene
	Trees q24_inorder

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode root = new Algorithms.TreeNode(2);
 root.left = new Algorithms.TreeNode(1); root.right = new Algorithms.TreeNode(3);
 assertEquals(List.of(1,2,3), Algorithms.inorder(root));

Q24. Serialize tree

Diagram	Topic / Scene
	Trees q24_serialize_tree

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode r = new Algorithms.TreeNode(1);
 r.left = new Algorithms.TreeNode(2); r.right = new Algorithms.TreeNode(3);
 assertEquals(List.of(1,2,3), Algorithms.serializeTree(r));

Q25. Is same tree

Diagram	Topic / Scene
	Trees q25_is_same_tree

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode a = new Algorithms.TreeNode(1); a.left = new Algorithms.TreeNode(2);
 Algorithms.TreeNode b = new Algorithms.TreeNode(1); b.left = new Algorithms.TreeNode(2);
 assertTrue(Algorithms.isSameTree(a, b));

Q26. Diameter

Diagram	Topic / Scene
	Trees q26_diameter

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode r = new Algorithms.TreeNode(1);
 r.left = new Algorithms.TreeNode(2); r.left.left = new Algorithms.TreeNode(4);
 r.right = new Algorithms.TreeNode(3); r.right.right = new Algorithms.TreeNode(5);
 assertEquals(4, Algorithms.diameter(r)); // 4->2->1->3->5 path length 4

Q26. Num islands

Diagram	Topic / Scene
no diagram	Graphs s13_num_islands

Function (Algorithms.java):

public static int numIslands(char[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
        return count;
    }

Unit test (JUnit 5):

char[][] g = {{'1','1','0'},{'0','1','0'},{'0','0','0'}};
 assertEquals(1, Algorithms.numIslands(g));

Q27. Clone graph

Diagram	Topic / Scene
	Graphs q27_clone_graph

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var n0 = new Algorithms.GraphNode(0);
 var n1 = new Algorithms.GraphNode(1);
 n0.neighbors.add(n1); n1.neighbors.add(n0);
 var clone = Algorithms.cloneGraph(n0);
 assertNotSame(n0, clone);
 assertEquals(1, clone.neighbors.size());
 assertEquals(0, clone.neighbors.get(0).neighbors.get(0).val); // points back to clone(0)

Q27. Mirror

Diagram	Topic / Scene
	Trees q27_mirror

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode r = new Algorithms.TreeNode(1);
 r.left = new Algorithms.TreeNode(2); r.right = new Algorithms.TreeNode(3);
 Algorithms.mirror(r);
 assertEquals(3, r.left.val); assertEquals(2, r.right.val);

Q28. Can finish

Diagram	Topic / Scene
	Graphs q28_can_finish

Function (Algorithms.java):

public static boolean canFinish(int numCourses, int[][] prerequisites) {
        var adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (var p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
        var q = IntStream.range(0, numCourses).filter(i -> indeg[i] == 0).boxed().collect(Collectors.toCollection(ArrayDeque::new));
        int visited = 0;
        while (!q.isEmpty()) {
            int u = q.poll(); visited++;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return visited == numCourses;
    }

Unit test (JUnit 5):

assertTrue(Algorithms.canFinish(2, new int[][]{{1,0}}));
 assertFalse(Algorithms.canFinish(2, new int[][]{{1,0},{0,1}}));

Q29. Dijkstra

Diagram	Topic / Scene
no diagram	Graphs s14_dijkstra

Function (Algorithms.java):

public static int dijkstra(int n, int[][] edges, int src, int dst) {
        var adj = new ArrayList<List<int[]>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (var e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }
        var dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
        var pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]); pq.add(new int[]{src, 0});
        while (!pq.isEmpty()) {
            var cur = pq.poll();
            if (cur[0] == dst) return cur[1];
            if (cur[1] > dist[cur[0]]) continue;
            for (var nb : adj.get(cur[0])) if (cur[1] + nb[1] < dist[nb[0]]) {
                dist[nb[0]] = cur[1] + nb[1]; pq.add(new int[]{nb[0], dist[nb[0]]});
            }
        }
        return -1;
    }

Unit test (JUnit 5):

int[][] e = {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5}};
 assertEquals(4, Algorithms.dijkstra(4, e, 0, 3));

Q30. Find the shortest path between two nodes in an unweighted graph.

Diagram	Topic / Scene
	Graphs q30_shortest_path

Function (Algorithms.java):

public static OptionalInt shortestPath(char[][] grid, int[] start, int[] end) {
        if (grid[start[0]][start[1]] == '#' || grid[end[0]][end[1]] == '#') return OptionalInt.empty();
        var q = new ArrayDeque<int[]>(); q.add(new int[]{start[0], start[1], 0});
        var seen = new HashSet<String>(); seen.add(start[0] + "," + start[1]);
        while (!q.isEmpty()) {
            var cur = q.poll();
            if (cur[0] == end[0] && cur[1] == end[1]) return OptionalInt.of(cur[2]);
            for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                String key = nr + "," + nc;
                if (nr >= 0 && nc >= 0 && nr < grid.length && nc < grid[0].length
                        && grid[nr][nc] != '#' && seen.add(key))
                    q.add(new int[]{nr, nc, cur[2] + 1});
            }
        }
        return OptionalInt.empty();
    }

Unit test (JUnit 5):

char[][] g = {{'.','.','.'},{'.','#','.'},{'.','.','.'}};
 assertEquals(4, Algorithms.shortestPath(g, new int[]{0,0}, new int[]{2,2}).getAsInt());

Q31. Fib

Diagram	Topic / Scene
no diagram	Backtracking s05_fibonacci

Function (Algorithms.java):

public static long fib(int n) {
        if (n < 2) return n;
        var memo = new long[n + 1];
        memo[0] = 0; memo[1] = 1;
        for (int i = 2; i <= n; i++) memo[i] = memo[i - 1] + memo[i - 2];
        return memo[n];
    }

Unit test (JUnit 5):

assertEquals(55, Algorithms.fib(10));

Q31. Cycle undirected

Diagram	Topic / Scene
no diagram	Graphs s15_cycle_undirected

Function (Algorithms.java):

public static boolean hasCycleUndirected(int n, int[][] edges) {
        var adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (var e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        var seen = new boolean[n];
        for (int i = 0; i < n; i++)
            if (!seen[i] && dfsCycle(adj, i, -1, seen)) return true;
        return false;
    }

Unit test (JUnit 5):

assertTrue(Algorithms.hasCycleUndirected(3, new int[][]{{0,1},{1,2},{2,0}}));
 assertFalse(Algorithms.hasCycleUndirected(3, new int[][]{{0,1},{1,2}}));

Q32. Climb stairs

Diagram	Topic / Scene
	DynamicProgramming q32_climb_stairs

Function (Algorithms.java):

public static int climbStairs(int n) {
        if (n < 3) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) { int t = a + b; a = b; b = t; }
        return b;
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.climbStairs(3));

Q32. Bipartite

Diagram	Topic / Scene
no diagram	Graphs s16_bipartite

Function (Algorithms.java):

public static boolean isBipartite(int n, int[][] edges) {
        var adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (var e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        int[] color = new int[n];
        for (int i = 0; i < n; i++) {
            if (color[i] != 0) continue;
            color[i] = 1; var q = new ArrayDeque<Integer>(); q.add(i);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (color[v] == 0) { color[v] = -color[u]; q.add(v); }
                    else if (color[v] == color[u]) return false;
                }
            }
        }
        return true;
    }

Unit test (JUnit 5):

assertTrue(Algorithms.isBipartite(4, new int[][]{{0,1},{1,2},{2,3},{3,0}}));
 assertFalse(Algorithms.isBipartite(3, new int[][]{{0,1},{1,2},{2,0}}));

Q33. Coin change

Diagram	Topic / Scene
	DynamicProgramming q33_coin_change

Function (Algorithms.java):

public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.coinChange(new int[]{1,2,5}, 11));

Q33. Connected components

Diagram	Topic / Scene
no diagram	Graphs s17_connected_components

Function (Algorithms.java):

public static int connectedComponents(int n, int[][] edges) {
        var uf = new UnionFind(n);
        for (var e : edges) uf.union(e[0], e[1]);
        int count = 0;
        for (int i = 0; i < n; i++) if (uf.find(i) == i) count++;
        return count;
    }

Unit test (JUnit 5):

assertEquals(2, Algorithms.connectedComponents(5, new int[][]{{0,1},{1,2},{3,4}}));

Q34. Length of lis

Diagram	Topic / Scene
	LinkedLists q34_lis

Function (Algorithms.java):

public static int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if (i < 0) i = -(i + 1);
            dp[i] = x;
            if (i == len) len++;
        }
        return len;
    }

Unit test (JUnit 5):

assertEquals(4, Algorithms.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));

Q34. Bridges

Diagram	Topic / Scene
no diagram	Graphs s18_bridges

Function (Algorithms.java):

public static List<List<Integer>> findBridges(int n, int[][] edges) {
        var adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (var e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        int[] disc = new int[n], low = new int[n]; int[] time = {0};
        boolean[] visited = new boolean[n];
        var bridges = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++)
            if (!visited[i]) tarjan(adj, i, -1, disc, low, time, visited, bridges);
        return bridges;
    }

Unit test (JUnit 5):

// path 0-1-2 has bridge [0,1] and [1,2]
 var b = Algorithms.findBridges(3, new int[][]{{0,1},{1,2}});
 assertEquals(2, b.size());

Q35. Edit distance

Diagram	Topic / Scene
	DynamicProgramming q35_edit_distance

Function (Algorithms.java):

public static int editDistance(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= b.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1),
                        dp[i-1][j-1] + (a.charAt(i-1) == b.charAt(j-1) ? 0 : 1));
        return dp[a.length()][b.length()];
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.editDistance("horse", "ros"));

Q36. Knapsack

Diagram	Topic / Scene
	DynamicProgramming q36_knapsack

Function (Algorithms.java):

public static KnapsackResult knapsack(int[] weights, int[] values, int capacity) {
        int n = values.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++)
            for (int w = 0; w <= capacity; w++)
                dp[i][w] = w >= weights[i-1]
                        ? Math.max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) : dp[i-1][w];
        int w = capacity; var items = new ArrayList<Integer>();
        for (int i = n; i > 0 && dp[i][w] > 0; i--)
            if (dp[i][w] != dp[i-1][w]) { items.add(i-1); w -= weights[i-1]; }
        Collections.reverse(items);
        return new KnapsackResult(dp[n][capacity], items);
    }

Unit test (JUnit 5):

var r = Algorithms.knapsack(new int[]{1,3,4,5}, new int[]{1,4,5,7}, 7);
 assertEquals(9, r.value());

Q38. Implement interpolation search.

Diagram	Topic / Scene
	Searching q38_interpolation_search

Function (Algorithms.java):

public static int interpolationSearch(int[] a, int key) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi && key >= a[lo] && key <= a[hi]) {
            if (lo == hi) return a[lo] == key ? lo : -1;
            int pos = lo + (key - a[lo]) * (hi - lo) / (a[hi] - a[lo]);
            if (a[pos] == key) return pos;
            if (a[pos] < key) lo = pos + 1; else hi = pos - 1;
        }
        return -1;
    }

Unit test (JUnit 5):

int[] a = {10,20,30,40,50};
 assertEquals(2, Algorithms.interpolationSearch(a, 30));
 assertEquals(-1, Algorithms.interpolationSearch(a, 35));

Q39. Kth small est

Diagram	Topic / Scene
no diagram	Heap_PQ q39_kth_smallest

Function (Algorithms.java):

public static int kthSmallest(int[] a, int k) {
        var list = Arrays.stream(a).boxed().collect(Collectors.toList());
        return quickselect(list, k - 1);
    }

Unit test (JUnit 5):

assertEquals(7, Algorithms.kthSmallest(new int[]{7,10,4,3,20,15}, 3));

Q40. Count inversions

Diagram	Topic / Scene
	DynamicProgramming q40_count_inversions

Function (Algorithms.java):

public static int countInversions(int[] a) {
        return mergeSortCount(a, 0, a.length - 1, new int[a.length]);
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.countInversions(new int[]{2,4,1,3,5}));

Algorithms

A1. Bubble sort

Diagram	Topic / Scene
	Sorting a1_bubble_sort

Function (Algorithms.java):

public static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a.length - 1 - i; j++)
                if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; }
    }

Unit test (JUnit 5):

int[] a = {5,2,8,1,9}; Algorithms.bubbleSort(a);
 assertArrayEquals(new int[]{1,2,5,8,9}, a);

A2. Merge sort

Diagram	Topic / Scene
no diagram	Sorting s02_merge_sort

Function (Algorithms.java):

public static int[] mergeSort(int[] a) {
        if (a.length < 2) return a;
        int mid = a.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
        return mergeSorted(left, right);
    }

Unit test (JUnit 5):

assertArrayEquals(new int[]{1,2,5,8,9}, Algorithms.mergeSort(new int[]{5,2,8,1,9}));

A3. Quick sort

Diagram	Topic / Scene
	Sorting a3_quick_sort

Function (Algorithms.java):

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

Unit test (JUnit 5):

int[] a = {5,2,8,1,9}; Algorithms.quickSort(a);
 assertArrayEquals(new int[]{1,2,5,8,9}, a);

A4. Heap sort

Diagram	Topic / Scene
	Sorting a4_heap_sort

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

assertEquals(List.of(1,2,5,8,9), Algorithms.heapSort(List.of(5,2,8,1,9)));

A5. Implement breadth-first search.

Diagram	Topic / Scene
no diagram	Graphs s03_bfs

Function (Algorithms.java):

public static <N> List<N> bfs(Map<N, List<N>> graph, N start) {
        var visited = new LinkedHashSet<N>();
        var q = new ArrayDeque<N>(); q.add(start); visited.add(start);
        while (!q.isEmpty()) {
            var cur = q.poll();
            for (var nb : graph.getOrDefault(cur, List.of()))
                if (visited.add(nb)) q.add(nb);
        }
        return new ArrayList<>(visited);
    }

Unit test (JUnit 5):

Map<Integer, List<Integer>> g = Map.of(1, List.of(2,3), 2, List.of(4), 3, List.of(4), 4, List.of());
 assertEquals(List.of(1,2,3,4), Algorithms.bfs(g, 1));

A6. Implement depth-first search (as a lazy generator over a Graph).

Diagram	Topic / Scene
no diagram	Graphs s09_dfs

Function (Algorithms.java):

public static <N> List<N> dfs(Map<N, List<N>> graph, N start) {
        var visited = new LinkedHashSet<N>();
        var stack = new ArrayDeque<N>(); stack.push(start);
        while (!stack.isEmpty()) {
            var cur = stack.pop();
            if (visited.add(cur))
                for (var nb : graph.getOrDefault(cur, List.of())) if (!visited.contains(nb)) stack.push(nb);
        }
        return new ArrayList<>(visited);
    }

Unit test (JUnit 5):

Map<String, List<String>> g = Map.of("A", List.of("B","C"), "B", List.of("D"), "C", List.of(), "D", List.of());
 assertEquals(List.of("A","C","B","D"), Algorithms.dfs(g, "A"));

A7. Union find

Diagram	Topic / Scene
no diagram	UnionFind s10_union_find

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var uf = new Algorithms.UnionFind(4);
 assertTrue(uf.union(0,1)); assertTrue(uf.union(1,2));
 assertFalse(uf.union(0,2)); // already connected
 assertEquals(0, uf.find(2));

A8. Sieve

Diagram	Topic / Scene
no diagram	NumberTheory s08_sieve

Function (Algorithms.java):

public static List<Integer> sieve(int n) {
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        for (int p = 2; p * p <= n; p++)
            if (prime[p]) for (int i = p * p; i <= n; i += p) prime[i] = false;
        var out = new ArrayList<Integer>();
        for (int i = 2; i <= n; i++) if (prime[i]) out.add(i);
        return out;
    }

Unit test (JUnit 5):

assertEquals(List.of(2,3,5,7,11,13,17,19), Algorithms.sieve(20));

A11. Sliding window max

Diagram	Topic / Scene
	Arrays_Subarrays a11_sliding_window_max

Function (Algorithms.java):

public static int[] slidingWindowMax(int[] a, int k) {
        if (a.length == 0) return new int[0];
        var dq = new ArrayDeque<Integer>();
        int[] out = new int[a.length - k + 1];
        for (int i = 0; i < a.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
            while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
            dq.addLast(i);
            if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
        }
        return out;
    }

Unit test (JUnit 5):

assertArrayEquals(new int[]{3,3,5,5,6,7}, Algorithms.slidingWindowMax(new int[]{1,3,-1,-3,5,3,6,7}, 3));

A12. Topo sort

Diagram	Topic / Scene
no diagram	Spanning_Topo s12_topo_sort

Function (Algorithms.java):

public static List<Integer> topoSort(int n, int[][] edges) {
        var adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (var e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
        var q = IntStream.range(0, n).filter(i -> indeg[i] == 0).boxed().collect(Collectors.toCollection(ArrayDeque::new));
        var out = new ArrayList<Integer>();
        while (!q.isEmpty()) {
            int u = q.poll(); out.add(u);
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return out.size() == n ? out : List.of();
    }

Unit test (JUnit 5):

// 0->1, 0->2, 1->3, 2->3
 assertEquals(List.of(0,1,2,3), Algorithms.topoSort(4, new int[][]{{0,1},{0,2},{1,3},{2,3}}));

A13. Kruskal

Diagram	Topic / Scene
no diagram	Spanning_Topo s11_kruskal

Function (Algorithms.java):

public static int kruskal(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        var uf = new UnionFind(n); int total = 0, count = 0;
        for (var e : edges) if (uf.union(e[0], e[1])) { total += e[2]; count++; }
        return count == n - 1 ? total : -1;
    }

Unit test (JUnit 5):

// MST of triangle 0-1(1),1-2(2),0-2(3) => 1+2=3
 assertEquals(3, Algorithms.kruskal(3, new int[][]{{0,1,1},{1,2,2},{0,2,3}}));

A15. Lcs

Diagram	Topic / Scene
	DynamicProgramming a15_lcs

Function (Algorithms.java):

public static int lcs(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                dp[i][j] = a.charAt(i-1) == b.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
        return dp[a.length()][b.length()];
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.lcs("abcde", "ace"));

A16. Level order

Diagram	Topic / Scene
	Trees a16_level_order

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

Algorithms.TreeNode root = new Algorithms.TreeNode(1);
 root.left = new Algorithms.TreeNode(2); root.right = new Algorithms.TreeNode(3);
 assertEquals(List.of(List.of(1), List.of(2,3)), Algorithms.levelOrder(root));

A17. Prim

Diagram	Topic / Scene
	Spanning_Topo a17_prim

Function (Algorithms.java):

public static int prim(int n, int[][] edges) {
        var adj = new ArrayList<List<int[]>>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (var e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }
        var visited = new boolean[n]; var pq = new PriorityQueue<int[]>((x, y) -> x[1] - y[1]);
        pq.add(new int[]{0, 0}); int total = 0, count = 0;
        while (!pq.isEmpty() && count < n) {
            var cur = pq.poll();
            if (visited[cur[0]]) continue;
            visited[cur[0]] = true; total += cur[1]; count++;
            for (var nb : adj.get(cur[0])) if (!visited[nb[0]]) pq.add(nb);
        }
        return count == n ? total : -1;
    }

Unit test (JUnit 5):

assertEquals(3, Algorithms.prim(3, new int[][]{{0,1,1},{1,2,2},{0,2,3}}));

A18. Matrix chain

Diagram	Topic / Scene
	DynamicProgramming a18_matrix_chain

Function (Algorithms.java):

public static int matrixChain(int[] dims) {
        int n = dims.length - 1;
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]);
            }
        return dp[0][n-1];
    }

Unit test (JUnit 5):

// dims 10x20 x 20x30 => 6000
 assertEquals(6000, Algorithms.matrixChain(new int[]{10,20,30}));

A21. Selection sort

Diagram	Topic / Scene
	Sorting a21_selection_sort

Function (Algorithms.java):

public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }

Unit test (JUnit 5):

int[] a = {5,2,8,1,9}; Algorithms.selectionSort(a);
 assertArrayEquals(new int[]{1,2,5,8,9}, a);

A22. Insertion sort

Diagram	Topic / Scene
	Sorting a22_insertion_sort

Function (Algorithms.java):

public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
            a[j + 1] = key;
        }
    }

Unit test (JUnit 5):

int[] a = {5,2,8,1,9}; Algorithms.insertionSort(a);
 assertArrayEquals(new int[]{1,2,5,8,9}, a);

A25. Kmp

Diagram	Topic / Scene
	Strings a25_kmp

Function (Algorithms.java):

public static int kmpSearch(String text, String pat) {
        int n = text.length(), m = pat.length();
        int[] lps = new int[m];
        for (int i = 1, len = 0; i < m; ) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1]; else i++;
        }
        for (int i = 0, j = 0; i < n; ) {
            if (text.charAt(i) == pat.charAt(j)) { i++; j++; if (j == m) return i - m; }
            else if (j != 0) j = lps[j - 1]; else i++;
        }
        return -1;
    }

Unit test (JUnit 5):

assertEquals(2, Algorithms.kmpSearch("hello world", "llo"));
 assertEquals(-1, Algorithms.kmpSearch("hello", "xyz"));

A26. Rabin karp

Diagram	Topic / Scene
	Strings a26_rabin_karp

Function (Algorithms.java):

public static int rabinKarp(String text, String pat) {
        final int B = 31, MOD = 1_000_000_007;
        long ph = 0, pw = 1;
        for (char c : pat.toCharArray()) { ph = (ph * B + c) % MOD; pw = (pw * B) % MOD; }
        long th = 0;
        for (int i = 0; i < text.length(); i++) {
            th = (th * B + text.charAt(i)) % MOD;
            if (i >= pat.length()) th = (th - pw * text.charAt(i - pat.length()) % MOD + MOD) % MOD;
            if (i >= pat.length() - 1 && th == ph && text.substring(i - pat.length() + 1, i + 1).equals(pat))
                return i - pat.length() + 1;
        }
        return -1;
    }

Unit test (JUnit 5):

assertEquals(2, Algorithms.rabinKarp("hello world", "llo"));
 assertEquals(-1, Algorithms.rabinKarp("hello", "xyz"));

A27. Trie

Diagram	Topic / Scene
	Tries a27_trie

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var t = new Algorithms.Trie();
 t.insert("cat"); t.insert("car");
 assertTrue(t.search("cat")); assertFalse(t.search("cap"));
 assertTrue(t.startsWith("ca"));

A28. Subsets

Diagram	Topic / Scene
	Backtracking a28_subsets

Function (Algorithms.java):

public static List<List<Integer>> subsets(int[] nums) {
        var res = new ArrayList<List<Integer>>(); var cur = new ArrayList<Integer>();
        backtrackSubsets(nums, 0, cur, res);
        return res;
    }

Unit test (JUnit 5):

var s = Algorithms.subsets(new int[]{1,2});
 assertEquals(4, s.size());
 assertTrue(s.contains(List.of())); assertTrue(s.contains(List.of(1,2)));

A29. Permutations

Diagram	Topic / Scene
	Backtracking a29_permutations

Function (Algorithms.java):

public static List<List<Integer>> permutations(int[] nums) {
        var res = new ArrayList<List<Integer>>();
        var used = new boolean[nums.length];
        backtrackPerm(nums, new ArrayList<>(), used, res);
        return res;
    }

Unit test (JUnit 5):

assertEquals(6, Algorithms.permutations(new int[]{1,2,3}).size());

A30. N queens

Diagram	Topic / Scene
	Backtracking a30_n_queens

Function (Algorithms.java):

public static int nQueens(int n) {
        int[] cols = new int[n]; int[] count = {0};
        placeQueens(n, 0, cols, new boolean[n], new boolean[2 * n], new boolean[2 * n], count);
        return count[0];
    }

Unit test (JUnit 5):

assertEquals(2, Algorithms.nQueens(4));

A31. Segment tree

Diagram	Topic / Scene
	SegmentTree a31_segment_tree

Function (Algorithms.java):

source: Algorithms.java

Unit test (JUnit 5):

var st = new Algorithms.SegmentTree(new int[]{1,3,5,7,9});
 assertEquals(25, st.query(0,4));
 st.update(1, 10); assertEquals(32, st.query(0,4));

Graph Extras

G0. Astar

Diagram	Topic / Scene
no diagram	Graphs astar

Function (Algorithms.java):

public static OptionalInt astar(char[][] grid, int[] start, int[] end) {
        int m = grid.length, n = grid[0].length;
        var open = new PriorityQueue<int[]>(Comparator.comparingInt(a -> a[2]));
        open.add(new int[]{start[0], start[1], manhattan(start[0], start[1], end)});
        var g = new HashMap<String, Integer>(); g.put(start[0] + "," + start[1], 0);
        var seen = new HashSet<String>();
        while (!open.isEmpty()) {
            var cur = open.poll();
            String key = cur[0] + "," + cur[1];
            if (seen.contains(key)) continue; seen.add(key);
            if (cur[0] == end[0] && cur[1] == end[1]) return OptionalInt.of(cur[2] - manhattan(cur[0], cur[1], end));
            for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] == '#') continue;
                int ng = g.get(key) + 1;
                String nk = nr + "," + nc;
                if (ng < g.getOrDefault(nk, Integer.MAX_VALUE)) {
                    g.put(nk, ng); open.add(new int[]{nr, nc, ng + manhattan(nr, nc, end)});
                }
            }
        }
        return OptionalInt.empty();
    }

Unit test (JUnit 5):

char[][] g = {{'.','.','.'},{'.','#','.'},{'.','.','.'}};
 assertEquals(4, Algorithms.astar(g, new int[]{0,0}, new int[]{2,2}).getAsInt());

G0. Bellmanford

Diagram	Topic / Scene
no diagram	Graphs bellman_ford

Function (Algorithms.java):

public static int[] bellmanFord(int n, int[][] edges, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE / 2); dist[src] = 0;
        for (int i = 0; i < n - 1; i++)
            for (var e : edges) if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
        for (var e : edges) if (dist[e[0]] + e[2] < dist[e[1]]) return null;
        return dist;
    }

Unit test (JUnit 5):

int[][] e = {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5}};
 int[] d = Algorithms.bellmanFord(4, e, 0);
 assertArrayEquals(new int[]{0,3,1,4}, d);

G0. Floodfill

Diagram	Topic / Scene
no diagram	Graphs flood_fill

Function (Algorithms.java):

public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int target = image[sr][sc];
        if (target == color) return image;
        var q = new ArrayDeque<int[]>(); q.add(new int[]{sr, sc});
        while (!q.isEmpty()) {
            var p = q.poll();
            if (image[p[0]][p[1]] != target) continue;
            image[p[0]][p[1]] = color;
            for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
                int nr = p[0] + d[0], nc = p[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < image.length && nc < image[0].length && image[nr][nc] == target)
                    q.add(new int[]{nr, nc});
            }
        }
        return image;
    }

Unit test (JUnit 5):

int[][] img = {{1,1,1},{1,1,0},{1,0,1}};
 int[][] out = Algorithms.floodFill(img, 1, 1, 2);
 assertEquals(2, out[0][0]); assertEquals(0, out[1][2]);

G0. Floydwarshall

Diagram	Topic / Scene
no diagram	Graphs floyd_warshall

Function (Algorithms.java):

public static int[][] floydWarshall(int n, int[][] edges) {
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(d[i], Integer.MAX_VALUE / 2);
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (var e : edges) d[e[0]][e[1]] = e[2];
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        return d;
    }

Unit test (JUnit 5):

int[][] e = {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5}};
 int[][] d = Algorithms.floydWarshall(4, e);
 assertEquals(4, d[0][3]);

---

🧪 Testing

./gradlew test

• 96 tests, all passing. Every @Test is named <Q|A><n>_<topic> so a failure maps straight to a question or algorithm.

---

🗂️ Layout

dsa-java-gradleqa/
├── build.gradle
├── settings.gradle
├── gradle/wrapper/        # Gradle 8.2.1 (Java 17)
├── scripts/gen_qa_diagrams.py
├── docs/diagrams/         # per-method PNGs + .mmd sources
└── src/
    ├── main/java/dsa/Algorithms.java      # all Q + A methods
    └── test/java/dsa/AlgorithmsTest.java  # 96 JUnit tests (named per method)

---

🔧 Tech & conventions

• Java 17 (sdkman 17.0.12-graal) · Gradle 8.2.1 · JUnit 5.9.1
• Modern Java: record, sealed, var, Stream API, generics + wildcards, Optional, pattern-matching switch.
• Diagrams: generated with Mermaid CLI (mmdc) → PNG only (no SVG), one per question/algorithm.