Perfect Squares in Java

Problem

We want to find the minimal number of perfect squares we need to add to reach a given integer. For example, 5 needs 2 squares (5 = 1 + 4), 14 needs 3 (14 = 9 + 4 + 1) and 75 needs 3 (75 = 25 + 25 + 25).

Algorithm

This is a typical problem of exploration of a tree of possibilities. It can be tackled by recursion with backtracking, or by dynamic programming. Let's go the dynamic programming way. In dynamic programming, the principle is to deduce the solution for the current problem from solutions of smaller problems. If the number of smaller problems is not too large, dynamic programming can be quite efficient by computing the solutions of all the smaller problems first.
In our case, finding the minimal number of perfect squares for a target sum can be computed by solving the problem for all the substractions of the target sum by each perfect square, and finding the minimum of these solutions.
For efficiency, we can initialize our solution by the worst sum of squares that we can imagine: a sum of only ones (i.e. 5 = 1 + 1 + 1 + 1 + 1). Also, it is a good idea to avoid using a square root function and the conversion from double to int.
In terms of data structure, we use an array to store at each index the minimum number of perfect square to sum to reach that index. We avoid writing to this array more than once for efficiency.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public class Solution { public int numSquares(int n) { // Array to find the minimum count for each sum below n. int[] counts = new int[n+1]; // We fill the array from sum = 1 until we reach n. for (int sum = 1; sum <= n; sum++) { // We now compute the minimum number of perfect // squares needed to reach sum. // We know that the worst solution is to use a sum // of ones. int min = sum; // For each sum, we look at which perfect square we // could use to make our count the smallest. // No need to consider ones again, since our initial // value for min, already considers solutions made // of ones. We avoid using the square root function // by directly comparing j ^ 2 to i. for(int j = 2; j * j <= sum; j++){ // Calculate the number of squares to reach i if // we use j * j, and update the current minimum. min = Math.min(counts[sum - j * j] + 1, min); } // Fill the array with the minimum we computed. counts[sum] = min; } return counts[n]; } }

This problem can be found on career cup and leet code.

Serialize and Deserialize a binary tree in Java

Problem

For a binary tree class containing integer values, we want to write a pair of serialization and deserialization function. As a reminder, serialization is the process of taking an object and converting is into bytes, usually for either sending the data over the network or for storing it on disk. Many programming languages, like Java, offer some default serialization, but those are usually not human-readable.

Algorithm

For serialization, the easiest way is to go through the tree breadth-first and serializing the values as we go. The matching deserialization algorithm needs to reconstruct the tree from the result of the serialization algoritm. Since values are in breadth-first order, deserialization will follow a similar strategy as serialization, keeping a queue containing the nodes from the previous level in order to rebuild the current level.
In terms of data structures, using a StringBuilder for serialization is recommended, as it allows efficient append. For the breadth-first search part, we obviously need a queue.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

// Encodes a tree to a single string. public String serialize(TreeNode root) { // We store the result in a StringBuilder for efficiency. StringBuilder result = new StringBuilder(); // Breadth-first search requires a queue. Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (queue.size() > 0) { // We pop the current node from the queue. TreeNode node = queue.remove(); // We need to add it to the serialization. if (node == null) { result.append("null"); } else { result.append(String.valueOf(node.val)); // Add the children to the queue. queue.add(node.left); queue.add(node.right); } // We use space as a separator. result.append(" "); // Note that we will have an extra space at the end. } return result.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.length() == 0) { return null; } // Our data is space-separated: we need to split it. String[] elements = data.split(" "); // We use a queue to reconstruct the tree in a // breadth-first search way. Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode root = StringToTreeNode(elements[0]); queue.add(root); // We iterate through the elements. Since we have an extra // space, we iterate only until elements.length - 1. int i = 1; while(i < elements.length - 1) { TreeNode local_root = queue.remove(); // If the element on the queue is null, then its children // could not have been serialized, we can skip to the next // node on the queue. if (local_root == null) { continue; } // local_root is not null, meaning that the serialization // appended the two children to the queue. Therefore we // know they are the next elements. TreeNode left = StringToTreeNode(elements[i]); local_root.left = left; queue.add(left); TreeNode right = StringToTreeNode(elements[i + 1]); local_root.right = right; queue.add(right); i = i + 2; } return root; } // An auxiliary function to convert from String to TreeNode. private TreeNode StringToTreeNode(String s) { if (s.equals("null")) { return null; } else { return new TreeNode(Integer.parseInt(s)); } }

This problem can be found on leetcode and career cup.

Remove adjacent duplicates in Java

Problem

Given a string, we want to repeatedly remove all adjacent duplicate characters until there are no adjacent duplicate characters. For example, "abbbc" would become "ac" and "acbbcd" would become "ad".

An interesting aspect of this problem is that it does not completely define a function: there are several correct answers to a given string, depending on the order in which the deletion happens. For example, "acbbccb" can be reduced to "acb" or just "a".

Algorithm

The algorithm that feels natural is to go through the initial string character by character, and check if that character is equal to the previous one, in which case both should be omitted. However, this is incorrect if a character appears three times in a row: we need a way to process all consecutive duplicates.
Our final algorithm will therefore go through the string and compare any new character with the last character we appended to our result. If they are equal, we will fast-forward as long as the following characters are identical. Once we run out of identical characters, we can safely delete the last character of our result. If the new character is different from the previous character, we append it to the result.
In terms of data structure, using a StringBuilder (or a Stack) is recommended, as it allows efficient append and removal. StringBuilder has the nice advantage of offering a simple toString method.
The final time complexity is linear in the size of the original string. The memory complexity is also linear and we cannot do better with the required API, since Java String objects are immutable. If our function takes a char[] as argument, it is possible to write an in-place version of this algorithm.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

private static String solve(String str){ // Variable result will hold our solution. StringBuilder result = new StringBuilder(); int i = 0; while (i < str.length()) { // Check wheter the character at position i is identical // to the last character that we have seen. if (result.length() > 0 && str.charAt(i) == result.charAt(result.length() - 1)) { // We found a duplicate! Let's skip it. i++; // Are there more of that same character? while (i < str.length() && str.charAt(i) == result.charAt(result.length() - 1)) { // We skip them as well. i++; } // There are no more characters identical to the last we // have seen. We can now delete it. result.deleteCharAt(result.length() - 1); } else { // This character is either the first, or is // different from the previous one: we can add it // to the result. result.append(str.charAt(i)); i++; } } return result.toString(); }

This problem can be found on career cup.

Check whether a linked list is a palindrome in Java

Problem

Given a singly linked list, write a method which can tell if the integers in the list form a palindrome. As a reminder, a palindrome is a word which reads the same from left to right and from right to left. For example, the list [1,5,3,5,1] is a palindrome, but [1,8,3,8,3,1,6] is not.

A constraint to the problem is to do it in O(n) time and O(1) space

Algorithm

Since linked lists can only be read from the head to the tail, it is not possible to use the standard technique which consists on comparing values one by one while reading from both ends. Moreover, the constraint of using O(1) space prevents us from copying the linked list into a more friendly data structure like an ArrayList.

The solution proposed below consists in 3 steps. First, we need to find the middle of the list. Once the middle of the list is found, we need to split the original list in two and reverse one of the two halves. Finally, we can go through both lists and compare them element by element.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

public class Solution { public boolean isPalindrome(ListNode head) { // Return true if the list has zero or one element. if (head == null || head.next == null) { return true; } // Use two pointers to find the middle of the list. // The fast pointer goes twice faster than the slow one. ListNode fast = head; ListNode slow = head; // After the loop, the fast pointer has reached the end, // while the slow pointer is at the middle element. while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // The second half of the list starts at slow. // We reverse it using two pointers and a // temporary variable. ListNode previous = null; ListNode current = slow; while (current != null) { ListNode temp = current.next; current.next = previous; previous = current; current = temp; } // After reversal, the variable previous points // to the head of the reversed second half's list. // Compare the first half with the second half. ListNode firstHalf = head; ListNode secondHalf = previous; while (secondHalf != null) { if (firstHalf.val != secondHalf.val) { return false; } firstHalf = firstHalf.next; secondHalf = secondHalf.next; } return true; } }

This problem can be found on leetcode and career cup.

Validate a binary search tree in Java

Problem

In this problem, we want to validate if a binary tree is actually a binary search tree. As a reminder, a binary search tree has the property that, for every sub-tree, the value of the sub-tree root is greater that all values in the left child, and smaller than all values in the right child. Wikipedia has more on binary search trees.

Algorithm

Our strategy is to go through the tree using using in-order traversal (one of the depth-first search flavours). A valid binary search tree will only see increasing values when using that traversal. To verify this, we maintain the value of the last element seen in order to be able to compare it with the current element. This value is kept as an Integer instance variable that is easily accessed by the multiple recursive calls.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Validate Binary Search Tree public class Solution { Integer previous = null; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } // Recursive call to the left child. if (!isValidBST(root.left)) { return false; } // In-order check that the current value is ordered. if (previous != null && previous => root.val) { return false; } // Update the previous value for the next checks. previous = root.val; // Recursive call to the right child. if (!isValidBST(root.right)) { return false; } return true; } }

This problem is a classic problem that notably appears on leetcode and career cup.