FizzBuzz #basic #pulse test
Write a function that iterates over the numbers 1 through 100. If the number is divisible by 3, output "Fizz". If the number is divisible by 5, output "Buzz". If the number is divisible by both 3 and 5, output "FizzBuzz". If the number is divisible by none of these, output the number.
1. public class FizzBuzz {
2. public static void fizzBuzz() {
3. for (int i = 1; i <= 100; i++) {
4. if (i % 3 == 0 && i % 5 == 0)
5. System.out.println("FizzBuzz");
6. else if (i % 3 == 0)
7. System.out.println("Fizz");
8. else if (i % 5 == 0)
9. System.out.println("Buzz");
10. else
11. System.out.println(i);
12. }
13. }
14. }
This is a basic "can this guy write a line of code" question that we should be able to do in our sleep. It's simply a for loop with an if-else chain. Don't get offended if asked this in an interview. Many times grad students applying for a software engineering job haven't written a line of code in years and struggle through this one. It should get us warmed up and in the coding mindset.
Two are true #logic #basic
Write a function that takes 3 booleans and return true if at least two of them are true.
1. public class Solution {
2. public static boolean atLeastTwo(boolean a, boolean b, boolean c) {
3. return a ? (b || c) : (b && c);
4. }
5. }
The key here is to be succinct and think before we start blindly writing down code. We must avoid writing many lines of spaghetti code and if-else statements when the solution can be accomplished with a relatively straight forward ternary operator. If readability is more important to us, we can also achieve the same effect with a simple if-else statement.
Complexity:
Time: O(1)
Space: O(1)
String Manipulation
String reversal #string manipulation #basic
Given a string, write a function that returns a string that contains the same characters in the reverse order.
1. public class Solution {
2. public static String reverse(String input) {
3. StringBuilder builder = new StringBuilder();
4. char[] characters = input.toCharArray();
5. for (int i = characters.length - 1; i >= 0; i--) {
6. builder.append(characters[i]);
7. }
8. return builder.toString();
9. }
10. }
This is a straight forward question used to test basic coding ability. The only slight trick is to use a string builder because Java strings are immutable. We simply iterate through the input string backwards, append the characters to a string builder, and output the results.
Complexity:
Time: O(n)
Space: O(n)
String rotation #string manipulation #tricky
Given two strings, write a function to check if one string is a rotation of the other
1. public class Solution {
2. public static boolean isRotation(String one, String two) {
3. return (one.length() == two.length()) &&
4. ((one + one).indexOf(two) != -1);
5. }
6. }
We first check to make sure that the two strings are the same length. We then concatenate the first string with itself, and see if the second string is a substring of this concatenated string. Take for example the inputs "tionssolu" and "solutions". When we concatenate the first input with itself we get "tionssolutionssolu". Now we can clearly see that this string contains "solutions".
Complexity:
Time: O(n2)
Space: O(n)
Character uniqueness #string manipulation #hash map #hash set
Given a string, write a function that checks to see if every character in the string is unique.
1. import java.util.HashSet;
3. public class Solution {
4. public static boolean isUnique(String str) {
5. if (str.isEmpty())
6. return false;
8. HashSet<Character> map = new HashSet<Character>();
9. char[] characters = str.toCharArray();
10. for (int i = 0; i < characters.length; i++) {
11. if (map.contains(characters[i]))
12. return false;
13. else
14. map.add(characters[i]);
15. }
16. return true;
17. }
18. }
This is a relatively straight forward hash map problem. Here we've opted to use a hash set because there is really no "value" that needs to be stored in the hash map. We simply iterate through the characters, adding each character to a hash set. If we come upon a character that already exists in the has set, we have a repeat character. Otherwise, all the characters in the string are unique.
Complexity:
Time: O(n)
Space: O(n)
Remove duplicates from string #string manipulation #hash set #string builder
Given a string, write a function that returns the string with all duplicate characters removed.
1. import java.util.LinkedHashSet;
2. import java.util.Set;
4. public class Solution {
5. public static String removeDuplicates(String string) {
6. char[] chars = string.toCharArray();
7. Set<Character> charSet = new LinkedHashSet<Character>();
8. for (char c : chars)
9. charSet.add(c);
11. StringBuilder sb = new StringBuilder();
12. for (Character character : charSet)
13. sb.append(character);
14. return sb.toString();
15. }
16. }
Here we use a data structure called a linked hash set. It allows us to add the characters from the string to the set efficiently in order to remove duplicates. We can then then iterate over the characters in the set efficiently to rebuild the string without duplicates. We opt to use a string builder in this case because strings in Java are immutable, so using a string builder is more memory efficient.
Complexity:
Time: O(n)
Space: O(n)
Word order reversal #string manipulation #tricky
Given a string that contains words separated by spaces, write a function that reverses the order of the words.
1. public class Solution {
2. public static char[] reverseWordOrder(char[] words) {
3. reverseCharacters(words, 0, words.length);
4. int lastSpace = 0;
5. for (int i = 0; i < words.length; i++) {
6. if (words[i] == ' ') {
7. reverseCharacters(words, lastSpace, i);
8. lastSpace = i + 1;
9. }
10. }
11. reverseCharacters(words, lastSpace, words.length);
12. return words;
13. }
14. private static void reverseCharacters(char[] words, int min, int max) {
15. for (int i = 0; i < (max - min) / 2; i++) {
16. char temp = words[min + i];
17. words[min + i] = words[max - i - 1];
18. words[max - i - 1] = temp;
19. }
20. }
21. }
We first iterate over the characters in the string, reversing the characters by swapping each letter with the corresponding letter from the end of the string. We then make a second pass over the string, looking for spaces. Each time we encounter a space, reverse the characters we've seen since the last space. We must make sure to also flip the last chunk of characters, as there may be no space at the end of the string.
Complexity:
Time: O(n)
Space: O(1)
String to integer #conversion #string manipulation
Given an integer represented as a string, write a function to convert it to an integer.
1. public class Solution {
2. public static int stringToInteger(String input) {
3. int result = 0;
4. int i = 0;
5. boolean isNegative = false;
6. if (input.charAt(i) == '-') {
7. isNegative = true;
8. i++;
9. }
10. for (; i < input.length(); i++) {
11. result *= 10;
12. result += ((int) input.charAt(i) - 48);
13. }
14. if (isNegative)
15. result *= -1;
16. return result;
17. }
18. }
We must first check to see if the first character in the string is a minus sign. If it is, we'll have to multiply the number by -1 when we've parsed the rest of the number. We can then iterate over the rest of the characters in the string, multiplying the result by 10 at each step and adding the next digit. A digit can be obtained from a character by subtracting the value of the '0' character, which is Complexity:
Time: O(n)
Space: O(1)
Longest common substring #string manipulation #dynamic programming
Given two strings, find the length of the longest substring that they have in common.
1. public class Solution {
2. public static int longestCommonSubstring(String one, String two) {
3. int n = one.length();
4. int m = two.length();
6. if (n == 0 || m == 0)
7. return 0;
9. int maxLenth = 0;
10. int[][] memoized = new int[n][m];
11.
12. for (int i = 0; i < n; i++)
13. for (int j = 0; j < m; j++) {
14. if (one.charAt(i) == two.charAt(j)) {
15. if (i == 0 || j == 0)
16. memoized[i][j] = 1;
17. else
18. memoized[i][j] = memoized[i - 1][j - 1] + 1;
19. if (memoized[i][j] > maxLenth)
20. maxLenth = memoized[i][j];
21. }
22. }
23. return maxLenth;
24. }
25. }
This is a classic dynamic programming problem. We compute the max length for smaller substrings, saving our results in the "memoized" table and building larger and larger solutions using the previously memoized results. We obtain our maximum length by finding the longest common substring out of all of the subproblems we compute substrings for.
Complexity:
Time: O(nm)
Space: O(nm)
Bit Twiddling
Computing 2x #bit manipulation
Write a function to compute 2x without using the multiplication operator or any looping structures.
1. public class Solution {
2. public static int twoToThe(int x) {
3. return 1 << x;
4. }
5. }
When we shift a base 2 integer to the left by 1, it is equivalent to multiplying that number by 2. This means that if we shift 2 to the left x times, we get 2x.
Power of 2 check #bit manipulation
Given an integer, write a function to check if the number is a power of two using bitwise operators.
1. public class Solution {
2. public static boolean isPowerOfTwo(int x) {
3. return (x & (x - 1)) == 0;
4. }
5. }
If the number we are checking is a power of two, the binary representation will be a one followed by zeros. If we subtract one from a power of two, it is equivalent to fliping every to the right of the 1, including the 1 itself. Bitwise anding these two numbers together will always result in zero if x is a power of two, and will always result in a non-zero number if x is not a power of two.
Swap in place
#bit manipulation #tricky
Given two integers, write a function to swap them without using any temporary storage.
1. public class Solution {
2. public static void swapInPlace(int a, int b) {
3. a = a ^ b;
4. b = a ^ b;
5. a = a ^ b;
6. }
7. }
Because the XOR function is its own inverse, and it is commutative, we can perform the XOR operation 3 times, storing it in the first variable, then the second, then the first again. This results in swapping the two values without using any additional storage.
Bit swap #bit manipulation
Write a function that takes a byte and swaps the the first 4 bits with the last 4 bits.
1. public class Solution {
2. public static byte swapBits(byte x) {
3. return (byte) (((x & 0xf0) >> 4) | ((x & 0x0f) << 4));
4. }
5. }
This is a classic bit twiddling problem. First we create a mask for the first 4 bits, then a mask for the last 4 bits. We then shift the result of ANDing the first mask with the byte to the right by 4, and the result of ANDing the second mask with the byte to the left by
Find the lone integer
#bitwise #hash table #tricky
Given an array of integers where each number appears exactly twice, except for one integer that appears exactly once, find the lone integer.
1. public class Solution {
2. public static int findTheLoner(int[] input) {
3. int value = 0;
4. for (int i = 0; i < input.length; i++) {
5. value = value ^ input[i];
6. }
7. return value;
8. }
9. }
This can be solved using the standard hash table approach, but a better solution (in terms of space complexity) can be achieved using bitwise operations. The bitwise XOR operator is commutative, and it is its own inverse. This means that if we XOR every integer in the array together, each pair will cancel out, and we will be left with the number that only appears once. Tricky!
Complexity:
Time: O(n)
Space: O(1)
Same sign check #bit manipulation
Given two integers, write a function that checks to see if the two numbers are the same sign using bitwise operators.
1. public class Solution43 {
2. public static boolean isSameSign(int x, int y) {
3. return ((x ^ y) < 0);
4. }
5. }
It is important to understand how negative numbers are represented in binary in order to solve this question. Negative numbers are represented using what's called "two's compliment." This means that the highest bit will be 1 in a negative number, and 0 in a positive number. This means when we XOR the two numbers together, if the sign is the same, we will get a negative number or 1 in the highest position. If they are different we will get a 0 in the highest position, which represents a positive number. This means we can check the sign of the result of XORing the two inputs together in order to check if the two inputs have the same sign or not.
Linked Lists
Linked list #linked list #explanation
Explain how linked lists work.
1. public class Node {
2. public String data;
3. public Node next;
4.
5. public Node(String data) {
6. this(data, null);
7. }
8. public Node(String data, Node node) {
9. this.data = data;
10. next = node;
11. }
12. }
A linked list is a simple data structure that is represented by a collection of nodes in which each node has a pointer to the next node. The last node can either have a pointer to null, or maintain a "sentinal node" that represents the end. A linked list can either be singly linked or doubly linked. A doubly linked list has a pointer to the previous node in addition to the next node. Linked lists have an insertion time of O(1) and a lookup time of O(n).
Doubly linked list node removal #linked list #basic
Given a doubly linked list and an integer, write a function that removes the first occurrence of that integer from the list.
1. public class Solution {
2. public static void removeTargetNode(Node head, int target) {
3. Node current = head;
4. while (current != null) {
5. if (current.value == target) {
6. if (current.next != null)
7. current.next.previous = current.previous;
8. if (current.previous != null)
9. current.previous.next = current.next;
10. break;
11. }
12. current = current.next;
13. }
14. }
16. private class Node {
17. public Node next;
18. public Node previous;
19. public int value;
20. }
21. }
We first iterate over the linked list until we find a node with the given target value. We then update the previous pointer in the next node to point to the node previous to the current node. We then update the next pointer in the previous node to point to the next node of the current pointer. Now we have effectively cut the current node out of the list.
Complexity:
Time: O(n)
Space: O(1)
Finding cycles in singly linked lists
#linked list #cycle #tricky
Given a singly linked list, write a function to determine if the linked list contains a cycle.
1. public class Solution {
2. public static boolean hasCycle(Node head) {
3. if (head == null)
4. return false;
5. Node turtle, rabbit;
6. turtle = rabbit = head;
7. while (true) {
8. turtle = turtle.next;
9. if (rabbit.next != null)
10. rabbit = rabbit.next.next;
11. else
12. return false;
13. if (turtle == null || rabbit == null)
14. return false;
15. if (turtle == rabbit)
16. return true;
17. }
18. }
20. private class Node {
21. public Node next;
22. public int value;
23. }
24. }
We can detect if the linked list has a cycle by creating two pointers starting at the beginning of the list that travel at different speeds. We'll call the fast pointer the "rabbit" who will travel twice as fast as the slow pointer, which we will call the "turtle." If the rabbit reaches the end of the list, we know there is no cycle. If the turtle and the rabbit meet, this means there has to be a cycle, because there is no other way for the turtle to catch up to the rabbit.
Complexity:
Time: O(n)
Space: O(1)
Linked list integer addition #linked list
Given two integers represented as linked lists, write a function that returns a linked list representing the sum of the two integers. The digits stored in the linked list are in reverse order (least significant digit to most significant digit). For example if the input were (1 ⇢ 5 ⇢ 8) + (1 ⇢ 2 ⇢ 3), the result would be (2 ⇢ 7 ⇢ 1 ⇢ 1) which represents 851 + 321 = 1. public class Solution {
2. public static Node addLinkedListNumbers(Node first, Node second) {
3. int carry = 0;
4. Node result = null;
5. Node iter = null;
6. while (first != null || second != null) {
7. int firstValue = first == null ? 0 : first.value;
8. int secondValue = second == null ? 0 : second.value;
9. int sum = (firstValue + secondValue + carry) % 10;
10. carry = (firstValue + secondValue + carry) / 10;
12. Node node = new Node();
13. node.value = sum;
14. node.next = null;
15. if (result == null) {
16. iter = node;
17. result = node;
18. } else {
19. iter.next = node;
20. iter = node;
21. }
23. first = (first == null) ? null : first.next;
24. second = (second == null) ? null : second.next;
25. }
26. if (carry != 0) {
27. Node node = new Node();
28. node.value = carry;
29. node.next = null;
30. iter.next = node;
31. iter = node;
32. }
33. return result;
34. }
36. private static class Node {
37. public Node next;
38. public int value;
39. }
40. }
We iterate over the linked list nodes in both lists, adding each digit together and keeping track of the carry. If we have a carry at the end, we must make sure to add an extra node ad the end of the list representing the carry digit.
Complexity:
Time: O(n)
Space: O(n)
Binary Search Trees
Binary search tree #binary search tree #explanation
Explain how binary search trees work.
1. public class BinarySearchTree {
2. public static void insert(Node head, Node newNode) {
3.
4. if (newNode.value < head.value) {
5. if (head.left == null)
6. head.left = newNode;
7. else
8. insert(head.left, newNode);
9. } else {
10. if (head.right == null)
11. head.right = newNode;
12. else
13. insert(head.right, newNode);
14. }
15. }
17. private class Node {
18. public Node left;
19. public Node right;
20. public int value;
21. }
22. }
A binary search tree is a tree data structure, in which elements are inserted and kept in order. Each node in the BST contains exactly two children, one or both of which can be null. The special property that makes a BST a search tree, and not just any old binary tree, is that the left child of any node is less than or equal to its parent, and the right child is greater than or equal to its parent. The left and right children of any node are also roots of BSTs themselves. Searching a binary search tree can be performed in O(log n) time, assuming a well balanced BST. This is performed by going down the left path if the target value is smaller than the current node, or going down the right path if the target value is larger than the current node.
Binary search tree validity
#binary search tree #basic #recursive
Given the pointer to a node, determine if the node is the root of a binary search tree. We can assume the integers in the tree are distinct i.e. there are no repeating numbers.
1. public class Solution {
2. public static boolean isValidBST(Node root) {
3. return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
4. }
6. private static boolean isValidBST(Node current, int min, int max) {
7. if (current.right != null) {
8. if (current.right.value > max ||
9. !isValidBST(current.right, current.value, max))
10. return false;
11. }
12. if (current.left != null) {
13. if (current.left.value < min ||
14. !isValidBST(current.left, min, current.value))
15. return false;
16. }
17. return true;
18. }
20. private class Node {
21. public Node left;
22. public Node right;
23. public int value;
24. }
25. }
In order to check if the node is the root of a binary search tree, we can first check if the left child's value is less than the current node's value. We can then recursively check if the left node is itself the root of a binary search tree. We can then do the same for the right child, making sure it's value is larger than the current node's value. We must also make sure that the values are within the min and max values allowed given the ancestors of the current node. This is accomplished by passing down allowed min and max values when we are making our recursive calls.
Complexity:
Time: O(n)
Space: O(1)
Binary search tree successor #binary search tree #search
Given the root of a binary search tree and a value, find the "successor" of that value, even if the value doesn't exist in the tree. The "successor" is defined as the node appearing immediately after the given node when performing an in-order traversal.
1. public class Solution {
2. private static Node getLeftMost(Node head) {
3. Node current = head;
4. while (current.left != null)
5. current = current.left;
6. return current;
7. }
9. private static Node getRightMost(Node head) {
10. Node current = head;
11. while (current.right != null)
12. current = current.right;
13. return current;
14. }
16. public static int getSuccessor(Node head, int target) {
17. Node current = head;
18. int successor = 0;
19. while (current != null) {
20. if (current.value < target && current.right != null)
21. current = current.right;
22. else if (current.value > target) {
23. if (current.left != null &&
24. getRightMost(current.left).value > target)
25. current = current.left;
26. else {
27. successor = current.value;
28. current = null;
29. }
30. } else {
31. if (current.right != null)
32. successor = getLeftMost(current.right).value;
33. current = null;
34. }
35. }
36. return successor;
37. }
39. private static class Node {
40. private int value;
41. private Node left;
42. private Node right;
43. }
44. }
We start off by moving down our binary search tree looking for the target value. There are two cases that need to be considered when looking for the "successor" in a binary search tree. The first is when our target value has a right child, the successor is simply the leftmost node in our target's right subtree. If our target doesn't have a right child, or our target doesn't exist, we must check the rightmost node in our left subtree. If it is less than our target, we have found our successor. Otherwise we need to move down the left subtree.
Complexity:
Time: O(log n)
Space: O(1)
Least common ancestor #binary search tree
Given the root of a binary search tree and two values, find the least common ancestor of the two values.
1. public class Solution {
2. public Node findLowestCommonAncestor(Node node, int value1,
3. int value2) {
4. if (node == null)
5. return null;
7. if (node.value > value2 && node.value > value1)
8. return findLowestCommonAncestor(node.left, value1, value2);
9. else if (node.value < value2 && node.value < value1)
10. return findLowestCommonAncestor(node.right, value1, value2);
11. else
12. return node;
13. }
15. private class Node {
16. public Node left;
17. public Node right;
18. public int value;
19. }
20. }
This is a relatively straightforward recursive solution once we realize that the lowest common ancestor is the first node where each of the two values we are looking for lies in different child subtrees of the node we are looking for. We simply search recursively down as we would searching for a value in a binary search tree until our paths diverge. At that point, we return the node at which our paths diverge.
Complexity:
Time: O(n)
Space: O(1)
Binary search tree path #binary search tree
Given the root of a binary search tree and two values, write a function that returns the path between the two values.
1. import java.util.ArrayList;
2. import java.util.List;
4. public class Solution {
5. public static List<Node> findShortestPath(Node head, int x, int y) {
6. List<Node> result = new ArrayList<Node>();
7. head = findLowestCommonAncestor(head, x, y);
8. List<Node> left = findPath(head, x);
9. List<Node> right = findPath(head, y);
10. if (x < y) {
11. left.remove(left.size() - 1);
12. result.addAll(left);
13. result.addAll(right);
14. } else {
15. right.remove(right.size() - 1);
16. result.addAll(right);
17. result.addAll(left);
18. }
19. return result;
20. }
22. public static List<Node> findPath(Node head, int x) {
23. List<Node> result = new ArrayList<Node>();
24. if (head.value == x) {
25. result.add(head);
26. return result;
27. }
28. if (head.value > x) {
29. List<Node> left = findPath(head.left, x);
30. result.addAll(left);
31. result.add(head);
32. }
33. if (head.value < x) {
34. result.add(head);
35. List<Node> right = findPath(head.right, x);
36. result.addAll(right);
37. }
38. return result;
39. }
41. private static Node findLowestCommonAncestor(Node node, int value1,
42. int value2) {
43. if (node == null)
44. return null;
46. if (node.value > value2 && node.value > value1)
47. return findLowestCommonAncestor(node.left, value1, value2);
48. else if (node.value < value2 && node.value < value1)
49. return findLowestCommonAncestor(node.right, value1, value2);
50. else
51. return node;
52. }
54. private static class Node {
55. public Node left;
56. public Node right;
57. public int value;
58. }
59. }
We can reuse the code that we wrote in the least common ancestor problem, because the least common ancestor will be the root of our path. Once we have the least common ancestor, we can simply build a path to the value on the right, and a path to the value on the left, and combine the two to get the path between the two nodes.
Complexity:
Time: O(n) where n is the length of the path
Space: O(n)
Searching & Sorting
Searching a sorted array
#basic #search #binary search
Given a sorted array of integers and a target value, write a function that finds the index of the target value in the array.
1. public class Solution {
2. public static int findValue(int[] input, int target) {
3. return findValue(input, target, 0, input.length);
4. }
6. public static int findValue(int[] input, int target, int min, int max) {
7. int mid = (min + max) / 2;
8. if (input[mid] == target)
9. return mid;
10. if (min >= max)
11. return -1;
12. if (target < mid)
13. return findValue(input, target, min, mid);
15. return findValue(input, target, mid + 1, max);
16. }
17. }
The solution to this problem is a simple binary search, no tricks. If the middle number is our target, return its value. If the target is less than our middle number, recur to the left. If our target is greater than our middle number, recur to the right.
Complexity:
Time: O(n log n)
Space: O(1)
Target sum #sorting
Given an array of integers and a target value, write a function to determine whether the array contains two numbers that add up to the target value.
1. import java.util.Arrays;
3. public class Solution {
4. public static int[] targetSum(int[] input, int target) {
5. Arrays.sort(input);
6. int start = 0;
7. int end = input.length - 1;
8. while (start < end) {
9. int sum = input[start] + input[end];
10. if (sum == target) {
11. int[] answer = { start, end };
12. return answer;
13. }
14. if (sum < target)
15. start++;
16. if (sum > target)
17. end--;
18. }
19. return null;
20. }
21. }
We start by sorting the array and creating a pointer at the beginning and one at the end. When the sum of the two values at each pointer is less than the target, move the first pointer forward. When the sum is greater than the target, move the second pointer backward. If the two pointers meet, there is no pair of numbers in the array that sum to the target.
Complexity:
Time: O(n log n)
Space: O(1)
Search on a rotated sorted array #binary search #tricky
Given a sorted array of integers that has been rotated, find a particular value in the array without finding the pivot.
1. public class Solution {
2. public static int rotatedSearch(int[] values, int min, int max, int x) {
3. if (values[min] == x)
4. return min;
5. else if (values[max] == x)
6. return max;
7. else if (max - min == 1)
8. return -1;
10. int mid = (min + max) / 2;
12. if (values[min] <= values[mid]) {
13. if (x <= values[mid] && x >= values[min])
14. return rotatedSearch(values, min, mid, x);
15. else
16. return rotatedSearch(values, mid, max, x);
17. } else {
18. if (x >= values[mid] && x <= values[max])
19. return rotatedSearch(values, mid, max, x);
20. else
21. return rotatedSearch(values, min, mid, x);
22. }
23. }
24. }
At first this problem seems difficult since we can't explicitly find the pivot point. One key observation allows us to treat this problem as a slightly modified binary search. The key is to realize that when we split the array in half, one side will be in sorted order, while the other will contain the pivot. This means if we see that one side is in order, and our value should be on that side (based on that min and max, which will be located at each end), we can simply perform a standard binary search on that side. If our value is not in the sorted side, it must be in the out of order side, and we can recur on the out of order side.
Complexity:
Time: O(n log n)
Space: O(1)
Quicksort
#quicksort #sorting #explanation
Explain how quicksort works.
1. public class QuickSort {
2. public static void swap(int input[], int a, int b) {
3. int temp = input[a];
4. input[a] = input[b];
5. input[b] = temp;
6. }
8. public static int partition(int input[], int front, int end) {
9. int pivot = input[front];
10. while (front < end) {
11. while (input[front] < pivot)
12. front++;
13. while (input[end] > pivot)
14. end--;
15. swap(input, front, end);
16. }
17. return front;
18. }
20. public static void quickSort(int input[], int front, int end) {
21. if (front >= end)
22. return;
23. int pivot = partition(input, front, end);
24. quickSort(input, front, pivot);
25. quickSort(input, pivot + 1, end);
26. }
27. }
Quicksort is one of the the most commonly used sorts, because it is one of the O(n log n) sorts in the average case, and it can be performed in place, without and additional memory. Quicksort works by selecting a pivot and partitioning the array based on that pivot. This involves putting all the numbers less than the pivot on the left side of the pivot, and all the numbers greater on the right side of the pivot. This is accomplished by creating pointers at both the front and end of the partition, and then swapping numbers that are out of place. These left and right sides of the pivot are then sorted recursively until partitions are of size 1 and the array is sorted.
Complexity:
Time: worst case O(n2), average case O(n log n)
Space: O(1)
K smallest elements #sorting #pivot #quicksort
Given an array of n elements, write a function that returns the k smallest numbers.
1. import java.util.Arrays;
3. public class Solution {
4. public static void swap(int input[], int a, int b) {
5. int temp = input[a];
6. input[a] = input[b];
7. input[b] = temp;
8. }
10. public static int partition(int input[], int front, int end) {
11. int pivot = input[front];
12. while (front < end) {
13. while (input[front] < pivot)
14. front++;
15. while (input[end] > pivot)
16. end--;
17. swap(input, front, end);
18. }
19. return front;
20. }
22. public static int[] findKSmallest(int input[], int front, int end,
23. int k) {
24. if (front >= end)
25. return null;
26. int pivot = partition(input, front, end);
27. if (pivot == k)
28. return Arrays.copyOfRange(input, 0, pivot);
29. else {
30. if (pivot > k)
31. return findKSmallest(input, front, pivot, k);
32. return findKSmallest(input, pivot + 1, end, k);
33. }
34. }
36. public static int[] findKSmallest(int input[], int k) {
37. return findKSmallest(input, 0, input.length - 1, k);
38. }
39. }
This problem can be solved with a slight modification to quicksort. The modification is to check whether the pivot index at any given point is less than or greater than the k value. If it is less, we recur on the left side of the pivot. If the pivot is greater than the k value, we recur on the right side of the pivot. If the pivot index is equal to the k value, then the part of the array to the left of the pivot represents the k smallest values, and the pivot represents the kth number. A special case of this solution where k = n / 2 can be used to find the median in O(n) time.
Complexity:
Time: O(n)
Space: O(1)
Hash Maps
Hash tables vs hash maps #hash table #comparison
Explain the difference between a hash table and a hash map.
1. import java.util.HashMap;
2. import java.util.Hashtable;
3.
4. class Solution {
5. HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
6. Hashtable<String, Integer> hashTable = new Hashtable<String, Integer>();
7. }
Hash tables and hash maps have three key differences:
Hash tables are synchronized and thread safe while hash maps are not. Concurrent access is not allowed for hash tables, so only one thread can access a hash table at a time.
Hash maps allow both null keys and null values, while hash tables do not. If we try to insert a null key or value into a hash table, we will get a null pointer exception.
When iterating through a hash map, and we try to modify one of the values, we will get a concurrent modification exception. If we try to modify a hash table during iteration, we will not get an error.
Generate all valid anagrams
#hash table #anagrams #string manipulation
Given an string and an English dictionary, write a function to find all valid anagrams for the string. We can pre-compute and store whatever we'd like to speed up lookup time.
1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.HashMap;
4. import java.util.List;
6. public class Solution {
7. private static HashMap<String, List<String>> map =
8. new HashMap<String, List<String>>();
9. public static void preCompute(List<String> englishDictionary) {
10. for (String word : englishDictionary) {
11. char[] letters = word.toCharArray();
12. Arrays.sort(letters);
13. String sortedWord = String.valueOf(letters);
14. if (map.get(sortedWord) != null) {
15. map.get(sortedWord).add(word);
16. } else {
17. List<String> words = new ArrayList<String>();
18. words.add(word);
19. map.put(sortedWord, words);
20. }
21. }
22. }
24. public static List<String> getAnagrams(String input) {
25. char[] letters = input.toCharArray();
26. Arrays.sort(letters);
27. return map.get(String.valueOf(letters));
28. }
29. }
When we have the option to pre-compute, we want to do as much work as possible before hand to make lookups faster. In this case we can pre-compute a hashmap from each string with its characters in sorted order to a list of other words that are anagrams of that word. For lookups, we can simply sort the characters of the given string and return the list of words we find in the hash map for that value.
Complexity:
Time: O(n log n), were n is the length of the word
Space: O(n)
Counting gets and puts #hash map
Extend HashMap to count the number of get and put operations across all instances of the data structure.
1. import java.util.HashMap;
3. public class CountedMap<K, V> extends HashMap<K, V> {
4. private static int numGets = 0;
5. private static int numPuts = 0;
7. @Override
8. public V put(K key, V value) {
9. numPuts++;
10. return super.put(key, value);
11. }
13. @Override
14. public V get(Object key) {
15. numGets++;
16. return super.get(key);
17. }
19. public int getNumGets() {
20. return numGets;
21. }
23. public int getNumPuts() {
24. return numPuts;
25. }
26. }
In order to count the number of puts and gets that are performed, we extend HashMap, and overwrite the put and get methods. When either method is called, we increment the corresponding count and then call the correct super method. In order to keep count across all instances of the class, we make our counting variables static, so there is just one instance of each.
Stacks & Queues
Stacks vs queues #stack #queue #explanation
Explain the differences between a stack and a queue.
1. import java.util.LinkedList;
2. import java.util.Queue;
3. import java.util.Stack;
5. public class StackQueue {
6. Stack<Object> stack = new Stack<Object>();
7. Queue<Object> queue = new LinkedList<Object>();
8. }
Stacks behave like stacks of dishes, while queues behave like lines of people waiting for tickets. The difference lies in the order in which elements are removed from each data structure. A stack uses what is called a first-in, first-out (FIFO) model. A queue on the other hand uses a last-in, first-out (LIFO) model. This means that with a stack, like a stack of dishes, when we remove a dish it will be the last dish that we placed on the stack. On the other hand with a queue, like a line of people waiting for tickets, the first person in line will get their tickets first. A stack typically uses the terminology push and pop for its add and remove methods, while queues typically use enqueue and dequeue.
Queue using stacks #stack #queue #tricky
Implement a queue data structure using only stacks. It must support the queue and dequeue operations. Don't worry about concurrency issues.
1. import java.util.Stack;
3. public class Solution {
4. public class Queue<E> {
5. private Stack<E> incoming = new Stack<E>();
6. private Stack<E> outgoing = new Stack<E>();
7.
8. public void queue(E item) {
9. incoming.push(item);
10. }
12. public E dequeue() {
13. if (outgoing.isEmpty()) {
14. while (!incoming.isEmpty()) {
15. outgoing.push(incoming.pop());
16. }
17. }
18. return outgoing.pop();
19. }
20. }
21. }
We can create a queue using two stacks, an incoming stack and an outgoing stack. When we queue a new item, simply push it onto the incoming stack. When we have to dequeue an item, we simply pop an item off of the outgoing stack. If the outgoing stack is empty, we pop all of the items off of the incoming stack, reversing their order, and place them on the outgoing stack.
Complexity:
Time: Amortized O(1)
Space: O(n)
Minimum stack #stack #minimum
Create a data structure that extends Stack and supports findMin in O(1) time.
1. import java.util.Stack;
3. public class MinimumStack<E extends Comparable<E>> extends Stack<E> {
4. private Stack<E> minStack;
6. public MinimumStack() {
7. super();
8. minStack = new Stack<E>();
9. }
10. @Override
11. public E push(E element) {
12. if (element.compareTo(minStack.peek()) <= 0)
13. minStack.push(element);
14. return super.push(element);
15. }
16. @Override
17. public E pop() {
18. E element = super.pop();
19. if (element.compareTo(minStack.peek()) == 0)
20. minStack.pop();
21. return element;
22. }
23. public E findMin() {
24. return minStack.peek();
25. }
26. }
We can keep track of the minimums with a seperate min stack. When we push a new element onto the stack, we check to see whether this element is smaller than the old min. If it is, add it to the min stack. When we pop an element, we check to see if it is the current minimum on the min stack. If it is, we pop it off of the min stack as well. When we want to perform findMin, we can simply call peek on the min stack.
Complexity:
Time: O(1)
Space: O(n)
Probability & Randomness
Random range expansion #random #tricky #probability
Given a random number generator that gives us an integer between 1 and 5 (inclusive), write a function that generates a random number between 1 and 7 (inclusive).
1. public class Solution {
2. public static int randomNumber7() {
3. int values[][] = {
4. { 1, 1, 1, 2, 2 },
5. { 2, 3, 3, 3, 4 },
6. { 4, 4, 5, 5, 5 },
7. { 6, 6, 6, 7, 7 },
8. { 7, 0, 0, 0, 0 }
9. };
11. int result = 0;
12. while (result == 0) {
13. int i = randomNumber5();
14. int j = randomNumber5();
15. result = values[i-1][j-1];
16. }
17. return result;
18. }
20. public static int randomNumber5() {
21. // implemented for us
22. }
23. }
We need to make sure we maintain the same probability that we choose any number between 1 and 7. In order to accomplish this, we use our working random function to select two numbers between 1 and 5. This gives us 25 possibilities. Keeping the probabilities even, we can have 3 sets of possibilities between 1 and 7 (3*7 = 21 < 25). This means there are possible outcomes in which we need to try again. For the rest of the numbers, we simply assign 3 numbers that correspond with each number from 1 to 7. Programmatically, this can be achieved in the most straight forward fashion by creating a two dimensional array of values, and using the generated numbers to select a value in the array. If the selected value is one of the values that should be thrown away, we select another pair of random numbers.
Complexity:
Time: Worst case it runs forever, but the probability of this is infinitesimally small. The average
case is between 1 and 2 selections.
Space: O(1)
Random number shuffling #probability #random
Given an array of integers, write a function to shuffle the integers randomly, so that each permutation is equally likely.
1. public class Solution {
2. public static int[] shuffleArray(int[] input) {
3. for (int i = 0; i < input.length; i++) {
4. int swap = i + (int) (Math.random() * (input.length - i));
5. int temp = input[swap];
6. input[swap] = input[i];
7. input[i] = temp;
8. }
9. return input;
10. }
11. }
We have to be careful to not give one element a larger probability to be swapped than any other in order to make each possible permutation equally likely. In order to accomplish this we can iterate over the array in order, swapping each element with a random element that comes after the current element.
Complexity:
Time: O(n)
Space: O(1)
Coin flips to die rolls #probability #random
Given a function that gives us the result of a coin flip (1 or 2), write a function that gives us the result of a dice roll (1 to 6 inclusive).
1. public class Solution {
2. public static int dieRoll() {
3. int result = 0;
4. while (result < 1 || result > 6) {
5. result = 0;
6. if (coinFlip() == 1)
7. result |= 1;
8. if (coinFlip() == 1)
9. result |= 2;
10. if (coinFlip() == 1)
11. result |= 4;
12. }
13. return result;
14. }
16. private static int coinFlip() {
17. // implemented for us
18. }
19. }
There are many solutions to this problem. One solution is to flip the coin three times and use the results of the coin flips to decide whether or not to turn on each of the three lowest bits in an integer. This will give us a result between 0 and 7. If we get 0 or 7, we'll need to roll again and continue to do so until we get a valid die roll.
Complexity:
Time: This could run forever, but the chance of that is infinitesimally small
Space: O(1)
Optimization
Find nearest neighbors #sorting
Given array of people, each represented by their name (a string) and their position in line (an integer). Write a function that takes a name and returns their 3 nearest neighbors. We can assume for the sake of simplicity that there are at least 4 people in the list.
1. import java.util.Arrays;
3. public class Solution {
4. public static Person[] findNearestNeighbors(Person[] people,
5. String target) {
6. Person[] neighbors = new Person[3];
7. Arrays.sort(people);
8. for (int i = 0; i < people.length; i++) {
9. if (people[i].name.equals(target)) {
10. int before = i - 1;
11. int after = i + 1;
12. int index = 0;
13. while (index < 3) {
14. if (after < people.length && (before < 0 ||
Math.abs(people[before].position - people[i].position) >
Math.abs(people[after].position - people[i].position))) {
neighbors[index] = people[after];
after++;
19. } else {
neighbors[index] = people[before];
before--;
22. }
23. index++;
24. }
25. }
26. }
27. return neighbors;
28. }
30. private static class Person implements Comparable<Person> {
31. public String name;
32. public int position;
33. @Override
34. public int compareTo(Person other) {
35. return ((Person) other).position - this.position;
36. }
37. }
38. }
We can solve this quite easily by first sorting the array by each person's position. The 3 nearest neighbors will then be located in either in the three positions immediately before or immediately after the target.
Complexity:
Time: O(n log n)
Space: O(1)
Stock market timing #stock market #optimization
Given an array of integers, where each element represents the stock price on consecutive days. Write a function to find the maximum profit if we're allowed to buy exactly once and sell exactly once over the time period.
1. public class Solution {
2. public static int findBiggestProfit(int[] days) {
3. int minPrice = days[0];
4. int maxProfit = 0;
5. for (int i = 1; i < days.length; i++) {
6. if (days[i] < minPrice)
7. minPrice = days[i];
8. int currentProfit = days[i] - minPrice;
9. if (currentProfit > maxProfit)
10. maxProfit = currentProfit;
11. }
12. return maxProfit;
13. }
14. }
We can go over the stock price data day by day keeping track of the lowest price we've seen so far, and the best profit we've seen so far. Best profit is updated when we find a stock price that, when the min price is subtracted, is greater than the old max profit.
Complexity:
Time: O(n)
Space: O(1)
Maximal subarray #optimization
Given an array, describe an algorithm to identify the subarray with the maximum sum. For example, if the input is [1, -3, 5, 2, 9, -8, -6, 4], the output would be [5, 2, 9].
1. public class Solution {
2. public static int maxSubarray(int[] input) {
3. int maxSoFar = 0;
4. int maxEndingHere = 0;
5. for(int i = 0; i < input.length; i++) {
6. maxEndingHere = Math.max(0, maxEndingHere + input[i]);
7. maxSoFar = Math.max(maxSoFar, maxEndingHere);
8. }
9. return maxSoFar;
10. }
11. }
While this may seem like a dynamic programming problem, we can further optimize the memory usage by only keeping track of the maximum we've seen so far and the maximum ending at the current position instead of memoizing these values across the entire array. For the max ending here value, we add the current value to the last max ending value if the sum is greater than zero, otherwise we reset the value to zero. We then use this value and check it against the maximum we've seen so far, and update it if the current value is greater.
Complexity:
Time: O(n)
Space: O(1)
Path finding #a star, path finding
Given a two dimensional grid with weights representing the cost of moving through each square, write a function that finds the minimum path between a given start and end cell.
1. import java.util.ArrayList;
2. import java.util.HashSet;
3. import java.util.List;
4. import java.util.Set;
6. public class AStar {
7. public class Node {
8. List<Node> neighbors = new ArrayList<Node>();
9. Node parent;
10. int xPos;
11. int yPos;
12. int fCost;
13. int gCost;
14. int hCost;
15. int cost;
16. }
18. public List<Node> aStar(Node start, Node goal) {
19. Set<Node> open = new HashSet<Node>();
20. Set<Node> closed = new HashSet<Node>();
22. start.gCost = 0;
23. start.hCost = estimateDistance(start, goal);
24. start.fCost = start.hCost;
26. open.add(start);
27. while (true) {
28. Node current = null;
29. if (open.size() == 0)
30. throw new RuntimeException("No path exists");
31. for (Node node : open) {
32. if (current == null || node.fCost < current.fCost)
33. current = node;
34. }
36. if (current == goal)
37. break;
39. open.remove(current);
40. closed.add(current);
41.
42. for (Node neighbor : current.neighbors) {
43. if (neighbor == null)
44. continue;
45. int nextG = current.gCost + neighbor.cost;
46. if (nextG < neighbor.gCost) {
47. open.remove(neighbor);
48. closed.remove(neighbor);
49. }
51. if (!open.contains(neighbor) && !closed.contains(neighbor)) {
52. neighbor.gCost = nextG;
53. neighbor.hCost = estimateDistance(neighbor, goal);
54. neighbor.fCost = neighbor.gCost + neighbor.hCost;
55. neighbor.parent = current;
56. open.add(neighbor);
57. }
58. }
59. }
61. List<Node> nodes = new ArrayList<Node>();
62. Node current = goal;
63. while (current.parent != null) {
64. nodes.add(current);
65. current = current.parent;
66. }
67. nodes.add(start);
69. return nodes;
70. }
72. public int estimateDistance(Node node1, Node node2) {
73. return Math.abs(node1.xPos - node2.xPos) +
74. Math.abs(node1.yPos - node2.yPos);
75. }
76. }
This question is a set up for us to use the A* path finding algorithm.
Complexity:
Time: O(N) where N is the number of cells in the grid
Design Patterns
Listener design pattern
#design patterns #listener #explanation
Explain the listener design pattern.
1. public class Listener {
2. public static void listener() {
3. EventSource eventSource = new EventSource();
4. EventListener eventListener = new EventListener();
5.
6. eventSource.addListener(eventListener);
7. }
8. }
This is a design pattern that is often used when handling user interface actions. The idea is that there are a group of "listeners" who are interested in a certain event happening. These listeners register themselves as listeners with the event source. When the event occurs, the event source knows to go through its list of listeners for that event, and notify them that the event has occurred. An example of this would be if we had a button on a page that was supposed to make a ball bounce on the page when clicked. The object controlling the ball would subscribe to an "onClick" event for the button. When the object receives a click event from the button, it knows to make the ball bounce. This is a very flexible design pattern that can be used in many situations.
Model view controller #model view controller #mvc #design pattern #explanation
Explain the model view controller design pattern.
1. public class Model {
2. // Contains program state, variables, etc
3. }
5. public class View {
6. // Contains user interface, text fields, buttons, etc.
7. }
9. public class Controller {
10. // Listens for inputs from view and makes changes to model
11. // Listens for model changes and makes changes to view
12. }
The model view controller (MVC) design pattern is used when developing user facing applications in order to separate the application's data from the user interface. The idea is that the user interface should be able the change without affecting the underlying data model and vice versa. The model contains the application state, the view contains the application's user interface, and the controller handles communication between the two.
Singleton pattern
#singleton #design patterns #explanation
Explain the singleton design pattern.
1. public class Singleton {
2. private static final Singleton instance;
3.
4. static {
5. instance = new Singleton();
6. }
8. public static Singleton getInstance() {
9. return instance;
10. }
12. private Singleton() {
13. }
14. }
The singleton pattern is used in order to maintain a single instance of an object in our program. Singletons contain private constructors that are never called externally. Instead, the "getInstance()" method is called when an instance of the singleton object is needed. Singletons can be initialized either lazily (when the getInstance method is first called) or eagerly (when the object is created).
Parallelism & Concurrency
Threads and processes #parallelism #explanation
Explain threads and processes.
1. public class MyThread extends Thread {
3. public void run() {
4. // Code that we want to execute on the thread
5. }
7. public static void main(String args[]) {
8. (new MyThread()).start();
9. }
10. }
Threads and processes are both paradigms that allow computers to run more than one piece of code at the same time. If our computer has multiple cores it can actually execute them at the same time, while single core machines only simulate this simultaneous execution using context switching. A process is a program that is run by a user. Our web browser runs on one processes, while our text editor runs on another. This makes it appear as if both are running at the same time. Each process can have one or more threads. Our web browser may run each window on a separate thread, so if we have two windows open at once, we can see each one functioning at the same time. Likewise, a program that has a user interface and is performing some heavy computation at the same time (like rendering graphics) will likely take user input and perform the processing on different threads. This allows clicks and key presses to be registered very quickly, without having to wait for the heavy computation to finish. Threads can share memory, while processes have separate chunks of memory allocated to them.
Mutex vs semaphore #parallelism #explanation
Explain the difference between a mutex and a semaphore.
1. import java.util.concurrent.Semaphore;
3. class UseSemaphore {
4. private static final int NUM_RESOURCES = 100;
5. private final Semaphore semaphore = new Semaphore(NUM_RESOURCES, true);
6.
7. public void useSemaphore() throws InterruptedException {
8. semaphore.acquire();
9. // Do something that requires one of the resources
10. semaphore.release();
11. }
12. }
Both mutexes and semaphores are used in parallel programming to prevent multiple threads from accessing a shared resource at the same time. A semaphore is used when we have a limited pool of resources. Let's say for example we don't want to have more than 5 connections open to a server at one time. We can create a semaphore with the limit of 5. Each time a thread wants to open a connection, it must acquire a resource from the semaphore, and then release it when it is done. A mutex is like a semaphore with only a single resource. Mutexes are like locks and are used to prevent concurrent access on a single object or resource.
Synchronized methods #parallelism #java
Explain Java synchronized methods.
1. public class SynchronizedCounter {
2. private int count = 0;
4. public synchronized void increment() {
5. count++;
6. }
8. public synchronized void decrement() {
9. count--;
10. }
12. public synchronized int value() {
13. return count;
14. }
15. }
Objects in Java have their own mutexes, or locks. When a method is called that is synchronized, the object's mutex is locked. When the method is finished, the mutex is unlocked. This ensures only one synchronized method can be called on an object at a time.
Preventing deadlocks #parallelism #deadlocks
Explain one way to prevent deadlocks.
1. public class Deadlock {
2. public static void deadLockThreadOne() {
3. lockA();
4. lockB();
5. }
7. public static void deadLockThreadTwo() {
8. lockB();
9. lockA();
10. }
11. }
Deadlocks can be prevented by having a well defined access order when accessing multiple resources that require locks. This prevents the case where two threads are competing for the same resources, and one thread obtains a lock for resource A at the same time as another thread obtains a lock for resource B. Now thread one needs to obtain a lock for B, while the other thread is waiting to obtain the lock for A. The two threads will wait forever. If both threads obtained lock A first, then lock B, this situation would not happen.
Matrix manipulation
Matrix rotation in place #matrix manipulation #tricky
Write a function that rotates an two dimensional square matrix 90 degrees using O(1) additional memory.
1. public class Solution {
2. public static void rotateMatrix(int input[][]) {
3. int n = input.length;
4. if (n <= 1)
5. return;
7. for (int i = 0; i < n / 2; i++) {
8. for (int j = i; j < n - i - 1; j++) {
9. int temp = input[i][j];
10. input[i][j] = input[n - j - 1][i];
11. input[n - j - 1][i] = input[n - 1 - i][n - 1 - j];
12. input[n - 1 - i][n - 1 - j] = input[j][n - 1 - i];
13. input[j][n - 1 - i] = temp;
14. }
15. }
16. }
17. }
The key to this problem is that we have to rotate 4 numbers at once, storing the first value that is overwritten as a temporary variable and then restoring it in the end. We work our way from the outside to the inside in "layers" performing these four way swaps until we reach the center.
Complexity:
Time: O(n)
Space: O(1)
Write a function that iterates over the numbers 1 through 100. If the number is divisible by 3, output "Fizz". If the number is divisible by 5, output "Buzz". If the number is divisible by both 3 and 5, output "FizzBuzz". If the number is divisible by none of these, output the number.
1. public class FizzBuzz {
2. public static void fizzBuzz() {
3. for (int i = 1; i <= 100; i++) {
4. if (i % 3 == 0 && i % 5 == 0)
5. System.out.println("FizzBuzz");
6. else if (i % 3 == 0)
7. System.out.println("Fizz");
8. else if (i % 5 == 0)
9. System.out.println("Buzz");
10. else
11. System.out.println(i);
12. }
13. }
14. }
This is a basic "can this guy write a line of code" question that we should be able to do in our sleep. It's simply a for loop with an if-else chain. Don't get offended if asked this in an interview. Many times grad students applying for a software engineering job haven't written a line of code in years and struggle through this one. It should get us warmed up and in the coding mindset.
Two are true #logic #basic
Write a function that takes 3 booleans and return true if at least two of them are true.
1. public class Solution {
2. public static boolean atLeastTwo(boolean a, boolean b, boolean c) {
3. return a ? (b || c) : (b && c);
4. }
5. }
The key here is to be succinct and think before we start blindly writing down code. We must avoid writing many lines of spaghetti code and if-else statements when the solution can be accomplished with a relatively straight forward ternary operator. If readability is more important to us, we can also achieve the same effect with a simple if-else statement.
Complexity:
Time: O(1)
Space: O(1)
String Manipulation
String reversal #string manipulation #basic
Given a string, write a function that returns a string that contains the same characters in the reverse order.
1. public class Solution {
2. public static String reverse(String input) {
3. StringBuilder builder = new StringBuilder();
4. char[] characters = input.toCharArray();
5. for (int i = characters.length - 1; i >= 0; i--) {
6. builder.append(characters[i]);
7. }
8. return builder.toString();
9. }
10. }
This is a straight forward question used to test basic coding ability. The only slight trick is to use a string builder because Java strings are immutable. We simply iterate through the input string backwards, append the characters to a string builder, and output the results.
Complexity:
Time: O(n)
Space: O(n)
String rotation #string manipulation #tricky
Given two strings, write a function to check if one string is a rotation of the other
1. public class Solution {
2. public static boolean isRotation(String one, String two) {
3. return (one.length() == two.length()) &&
4. ((one + one).indexOf(two) != -1);
5. }
6. }
We first check to make sure that the two strings are the same length. We then concatenate the first string with itself, and see if the second string is a substring of this concatenated string. Take for example the inputs "tionssolu" and "solutions". When we concatenate the first input with itself we get "tionssolutionssolu". Now we can clearly see that this string contains "solutions".
Complexity:
Time: O(n2)
Space: O(n)
Character uniqueness #string manipulation #hash map #hash set
Given a string, write a function that checks to see if every character in the string is unique.
1. import java.util.HashSet;
3. public class Solution {
4. public static boolean isUnique(String str) {
5. if (str.isEmpty())
6. return false;
8. HashSet<Character> map = new HashSet<Character>();
9. char[] characters = str.toCharArray();
10. for (int i = 0; i < characters.length; i++) {
11. if (map.contains(characters[i]))
12. return false;
13. else
14. map.add(characters[i]);
15. }
16. return true;
17. }
18. }
This is a relatively straight forward hash map problem. Here we've opted to use a hash set because there is really no "value" that needs to be stored in the hash map. We simply iterate through the characters, adding each character to a hash set. If we come upon a character that already exists in the has set, we have a repeat character. Otherwise, all the characters in the string are unique.
Complexity:
Time: O(n)
Space: O(n)
Remove duplicates from string #string manipulation #hash set #string builder
Given a string, write a function that returns the string with all duplicate characters removed.
1. import java.util.LinkedHashSet;
2. import java.util.Set;
4. public class Solution {
5. public static String removeDuplicates(String string) {
6. char[] chars = string.toCharArray();
7. Set<Character> charSet = new LinkedHashSet<Character>();
8. for (char c : chars)
9. charSet.add(c);
11. StringBuilder sb = new StringBuilder();
12. for (Character character : charSet)
13. sb.append(character);
14. return sb.toString();
15. }
16. }
Here we use a data structure called a linked hash set. It allows us to add the characters from the string to the set efficiently in order to remove duplicates. We can then then iterate over the characters in the set efficiently to rebuild the string without duplicates. We opt to use a string builder in this case because strings in Java are immutable, so using a string builder is more memory efficient.
Complexity:
Time: O(n)
Space: O(n)
Word order reversal #string manipulation #tricky
Given a string that contains words separated by spaces, write a function that reverses the order of the words.
1. public class Solution {
2. public static char[] reverseWordOrder(char[] words) {
3. reverseCharacters(words, 0, words.length);
4. int lastSpace = 0;
5. for (int i = 0; i < words.length; i++) {
6. if (words[i] == ' ') {
7. reverseCharacters(words, lastSpace, i);
8. lastSpace = i + 1;
9. }
10. }
11. reverseCharacters(words, lastSpace, words.length);
12. return words;
13. }
14. private static void reverseCharacters(char[] words, int min, int max) {
15. for (int i = 0; i < (max - min) / 2; i++) {
16. char temp = words[min + i];
17. words[min + i] = words[max - i - 1];
18. words[max - i - 1] = temp;
19. }
20. }
21. }
We first iterate over the characters in the string, reversing the characters by swapping each letter with the corresponding letter from the end of the string. We then make a second pass over the string, looking for spaces. Each time we encounter a space, reverse the characters we've seen since the last space. We must make sure to also flip the last chunk of characters, as there may be no space at the end of the string.
Complexity:
Time: O(n)
Space: O(1)
String to integer #conversion #string manipulation
Given an integer represented as a string, write a function to convert it to an integer.
1. public class Solution {
2. public static int stringToInteger(String input) {
3. int result = 0;
4. int i = 0;
5. boolean isNegative = false;
6. if (input.charAt(i) == '-') {
7. isNegative = true;
8. i++;
9. }
10. for (; i < input.length(); i++) {
11. result *= 10;
12. result += ((int) input.charAt(i) - 48);
13. }
14. if (isNegative)
15. result *= -1;
16. return result;
17. }
18. }
We must first check to see if the first character in the string is a minus sign. If it is, we'll have to multiply the number by -1 when we've parsed the rest of the number. We can then iterate over the rest of the characters in the string, multiplying the result by 10 at each step and adding the next digit. A digit can be obtained from a character by subtracting the value of the '0' character, which is Complexity:
Time: O(n)
Space: O(1)
Longest common substring #string manipulation #dynamic programming
Given two strings, find the length of the longest substring that they have in common.
1. public class Solution {
2. public static int longestCommonSubstring(String one, String two) {
3. int n = one.length();
4. int m = two.length();
6. if (n == 0 || m == 0)
7. return 0;
9. int maxLenth = 0;
10. int[][] memoized = new int[n][m];
11.
12. for (int i = 0; i < n; i++)
13. for (int j = 0; j < m; j++) {
14. if (one.charAt(i) == two.charAt(j)) {
15. if (i == 0 || j == 0)
16. memoized[i][j] = 1;
17. else
18. memoized[i][j] = memoized[i - 1][j - 1] + 1;
19. if (memoized[i][j] > maxLenth)
20. maxLenth = memoized[i][j];
21. }
22. }
23. return maxLenth;
24. }
25. }
This is a classic dynamic programming problem. We compute the max length for smaller substrings, saving our results in the "memoized" table and building larger and larger solutions using the previously memoized results. We obtain our maximum length by finding the longest common substring out of all of the subproblems we compute substrings for.
Complexity:
Time: O(nm)
Space: O(nm)
Bit Twiddling
Computing 2x #bit manipulation
Write a function to compute 2x without using the multiplication operator or any looping structures.
1. public class Solution {
2. public static int twoToThe(int x) {
3. return 1 << x;
4. }
5. }
When we shift a base 2 integer to the left by 1, it is equivalent to multiplying that number by 2. This means that if we shift 2 to the left x times, we get 2x.
Power of 2 check #bit manipulation
Given an integer, write a function to check if the number is a power of two using bitwise operators.
1. public class Solution {
2. public static boolean isPowerOfTwo(int x) {
3. return (x & (x - 1)) == 0;
4. }
5. }
If the number we are checking is a power of two, the binary representation will be a one followed by zeros. If we subtract one from a power of two, it is equivalent to fliping every to the right of the 1, including the 1 itself. Bitwise anding these two numbers together will always result in zero if x is a power of two, and will always result in a non-zero number if x is not a power of two.
Swap in place
#bit manipulation #tricky
Given two integers, write a function to swap them without using any temporary storage.
1. public class Solution {
2. public static void swapInPlace(int a, int b) {
3. a = a ^ b;
4. b = a ^ b;
5. a = a ^ b;
6. }
7. }
Because the XOR function is its own inverse, and it is commutative, we can perform the XOR operation 3 times, storing it in the first variable, then the second, then the first again. This results in swapping the two values without using any additional storage.
Bit swap #bit manipulation
Write a function that takes a byte and swaps the the first 4 bits with the last 4 bits.
1. public class Solution {
2. public static byte swapBits(byte x) {
3. return (byte) (((x & 0xf0) >> 4) | ((x & 0x0f) << 4));
4. }
5. }
This is a classic bit twiddling problem. First we create a mask for the first 4 bits, then a mask for the last 4 bits. We then shift the result of ANDing the first mask with the byte to the right by 4, and the result of ANDing the second mask with the byte to the left by
Find the lone integer
#bitwise #hash table #tricky
Given an array of integers where each number appears exactly twice, except for one integer that appears exactly once, find the lone integer.
1. public class Solution {
2. public static int findTheLoner(int[] input) {
3. int value = 0;
4. for (int i = 0; i < input.length; i++) {
5. value = value ^ input[i];
6. }
7. return value;
8. }
9. }
This can be solved using the standard hash table approach, but a better solution (in terms of space complexity) can be achieved using bitwise operations. The bitwise XOR operator is commutative, and it is its own inverse. This means that if we XOR every integer in the array together, each pair will cancel out, and we will be left with the number that only appears once. Tricky!
Complexity:
Time: O(n)
Space: O(1)
Same sign check #bit manipulation
Given two integers, write a function that checks to see if the two numbers are the same sign using bitwise operators.
1. public class Solution43 {
2. public static boolean isSameSign(int x, int y) {
3. return ((x ^ y) < 0);
4. }
5. }
It is important to understand how negative numbers are represented in binary in order to solve this question. Negative numbers are represented using what's called "two's compliment." This means that the highest bit will be 1 in a negative number, and 0 in a positive number. This means when we XOR the two numbers together, if the sign is the same, we will get a negative number or 1 in the highest position. If they are different we will get a 0 in the highest position, which represents a positive number. This means we can check the sign of the result of XORing the two inputs together in order to check if the two inputs have the same sign or not.
Linked Lists
Linked list #linked list #explanation
Explain how linked lists work.
1. public class Node {
2. public String data;
3. public Node next;
4.
5. public Node(String data) {
6. this(data, null);
7. }
8. public Node(String data, Node node) {
9. this.data = data;
10. next = node;
11. }
12. }
A linked list is a simple data structure that is represented by a collection of nodes in which each node has a pointer to the next node. The last node can either have a pointer to null, or maintain a "sentinal node" that represents the end. A linked list can either be singly linked or doubly linked. A doubly linked list has a pointer to the previous node in addition to the next node. Linked lists have an insertion time of O(1) and a lookup time of O(n).
Doubly linked list node removal #linked list #basic
Given a doubly linked list and an integer, write a function that removes the first occurrence of that integer from the list.
1. public class Solution {
2. public static void removeTargetNode(Node head, int target) {
3. Node current = head;
4. while (current != null) {
5. if (current.value == target) {
6. if (current.next != null)
7. current.next.previous = current.previous;
8. if (current.previous != null)
9. current.previous.next = current.next;
10. break;
11. }
12. current = current.next;
13. }
14. }
16. private class Node {
17. public Node next;
18. public Node previous;
19. public int value;
20. }
21. }
We first iterate over the linked list until we find a node with the given target value. We then update the previous pointer in the next node to point to the node previous to the current node. We then update the next pointer in the previous node to point to the next node of the current pointer. Now we have effectively cut the current node out of the list.
Complexity:
Time: O(n)
Space: O(1)
Finding cycles in singly linked lists
#linked list #cycle #tricky
Given a singly linked list, write a function to determine if the linked list contains a cycle.
1. public class Solution {
2. public static boolean hasCycle(Node head) {
3. if (head == null)
4. return false;
5. Node turtle, rabbit;
6. turtle = rabbit = head;
7. while (true) {
8. turtle = turtle.next;
9. if (rabbit.next != null)
10. rabbit = rabbit.next.next;
11. else
12. return false;
13. if (turtle == null || rabbit == null)
14. return false;
15. if (turtle == rabbit)
16. return true;
17. }
18. }
20. private class Node {
21. public Node next;
22. public int value;
23. }
24. }
We can detect if the linked list has a cycle by creating two pointers starting at the beginning of the list that travel at different speeds. We'll call the fast pointer the "rabbit" who will travel twice as fast as the slow pointer, which we will call the "turtle." If the rabbit reaches the end of the list, we know there is no cycle. If the turtle and the rabbit meet, this means there has to be a cycle, because there is no other way for the turtle to catch up to the rabbit.
Complexity:
Time: O(n)
Space: O(1)
Linked list integer addition #linked list
Given two integers represented as linked lists, write a function that returns a linked list representing the sum of the two integers. The digits stored in the linked list are in reverse order (least significant digit to most significant digit). For example if the input were (1 ⇢ 5 ⇢ 8) + (1 ⇢ 2 ⇢ 3), the result would be (2 ⇢ 7 ⇢ 1 ⇢ 1) which represents 851 + 321 = 1. public class Solution {
2. public static Node addLinkedListNumbers(Node first, Node second) {
3. int carry = 0;
4. Node result = null;
5. Node iter = null;
6. while (first != null || second != null) {
7. int firstValue = first == null ? 0 : first.value;
8. int secondValue = second == null ? 0 : second.value;
9. int sum = (firstValue + secondValue + carry) % 10;
10. carry = (firstValue + secondValue + carry) / 10;
12. Node node = new Node();
13. node.value = sum;
14. node.next = null;
15. if (result == null) {
16. iter = node;
17. result = node;
18. } else {
19. iter.next = node;
20. iter = node;
21. }
23. first = (first == null) ? null : first.next;
24. second = (second == null) ? null : second.next;
25. }
26. if (carry != 0) {
27. Node node = new Node();
28. node.value = carry;
29. node.next = null;
30. iter.next = node;
31. iter = node;
32. }
33. return result;
34. }
36. private static class Node {
37. public Node next;
38. public int value;
39. }
40. }
We iterate over the linked list nodes in both lists, adding each digit together and keeping track of the carry. If we have a carry at the end, we must make sure to add an extra node ad the end of the list representing the carry digit.
Complexity:
Time: O(n)
Space: O(n)
Binary Search Trees
Binary search tree #binary search tree #explanation
Explain how binary search trees work.
1. public class BinarySearchTree {
2. public static void insert(Node head, Node newNode) {
3.
4. if (newNode.value < head.value) {
5. if (head.left == null)
6. head.left = newNode;
7. else
8. insert(head.left, newNode);
9. } else {
10. if (head.right == null)
11. head.right = newNode;
12. else
13. insert(head.right, newNode);
14. }
15. }
17. private class Node {
18. public Node left;
19. public Node right;
20. public int value;
21. }
22. }
A binary search tree is a tree data structure, in which elements are inserted and kept in order. Each node in the BST contains exactly two children, one or both of which can be null. The special property that makes a BST a search tree, and not just any old binary tree, is that the left child of any node is less than or equal to its parent, and the right child is greater than or equal to its parent. The left and right children of any node are also roots of BSTs themselves. Searching a binary search tree can be performed in O(log n) time, assuming a well balanced BST. This is performed by going down the left path if the target value is smaller than the current node, or going down the right path if the target value is larger than the current node.
Binary search tree validity
#binary search tree #basic #recursive
Given the pointer to a node, determine if the node is the root of a binary search tree. We can assume the integers in the tree are distinct i.e. there are no repeating numbers.
1. public class Solution {
2. public static boolean isValidBST(Node root) {
3. return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
4. }
6. private static boolean isValidBST(Node current, int min, int max) {
7. if (current.right != null) {
8. if (current.right.value > max ||
9. !isValidBST(current.right, current.value, max))
10. return false;
11. }
12. if (current.left != null) {
13. if (current.left.value < min ||
14. !isValidBST(current.left, min, current.value))
15. return false;
16. }
17. return true;
18. }
20. private class Node {
21. public Node left;
22. public Node right;
23. public int value;
24. }
25. }
In order to check if the node is the root of a binary search tree, we can first check if the left child's value is less than the current node's value. We can then recursively check if the left node is itself the root of a binary search tree. We can then do the same for the right child, making sure it's value is larger than the current node's value. We must also make sure that the values are within the min and max values allowed given the ancestors of the current node. This is accomplished by passing down allowed min and max values when we are making our recursive calls.
Complexity:
Time: O(n)
Space: O(1)
Binary search tree successor #binary search tree #search
Given the root of a binary search tree and a value, find the "successor" of that value, even if the value doesn't exist in the tree. The "successor" is defined as the node appearing immediately after the given node when performing an in-order traversal.
1. public class Solution {
2. private static Node getLeftMost(Node head) {
3. Node current = head;
4. while (current.left != null)
5. current = current.left;
6. return current;
7. }
9. private static Node getRightMost(Node head) {
10. Node current = head;
11. while (current.right != null)
12. current = current.right;
13. return current;
14. }
16. public static int getSuccessor(Node head, int target) {
17. Node current = head;
18. int successor = 0;
19. while (current != null) {
20. if (current.value < target && current.right != null)
21. current = current.right;
22. else if (current.value > target) {
23. if (current.left != null &&
24. getRightMost(current.left).value > target)
25. current = current.left;
26. else {
27. successor = current.value;
28. current = null;
29. }
30. } else {
31. if (current.right != null)
32. successor = getLeftMost(current.right).value;
33. current = null;
34. }
35. }
36. return successor;
37. }
39. private static class Node {
40. private int value;
41. private Node left;
42. private Node right;
43. }
44. }
We start off by moving down our binary search tree looking for the target value. There are two cases that need to be considered when looking for the "successor" in a binary search tree. The first is when our target value has a right child, the successor is simply the leftmost node in our target's right subtree. If our target doesn't have a right child, or our target doesn't exist, we must check the rightmost node in our left subtree. If it is less than our target, we have found our successor. Otherwise we need to move down the left subtree.
Complexity:
Time: O(log n)
Space: O(1)
Least common ancestor #binary search tree
Given the root of a binary search tree and two values, find the least common ancestor of the two values.
1. public class Solution {
2. public Node findLowestCommonAncestor(Node node, int value1,
3. int value2) {
4. if (node == null)
5. return null;
7. if (node.value > value2 && node.value > value1)
8. return findLowestCommonAncestor(node.left, value1, value2);
9. else if (node.value < value2 && node.value < value1)
10. return findLowestCommonAncestor(node.right, value1, value2);
11. else
12. return node;
13. }
15. private class Node {
16. public Node left;
17. public Node right;
18. public int value;
19. }
20. }
This is a relatively straightforward recursive solution once we realize that the lowest common ancestor is the first node where each of the two values we are looking for lies in different child subtrees of the node we are looking for. We simply search recursively down as we would searching for a value in a binary search tree until our paths diverge. At that point, we return the node at which our paths diverge.
Complexity:
Time: O(n)
Space: O(1)
Binary search tree path #binary search tree
Given the root of a binary search tree and two values, write a function that returns the path between the two values.
1. import java.util.ArrayList;
2. import java.util.List;
4. public class Solution {
5. public static List<Node> findShortestPath(Node head, int x, int y) {
6. List<Node> result = new ArrayList<Node>();
7. head = findLowestCommonAncestor(head, x, y);
8. List<Node> left = findPath(head, x);
9. List<Node> right = findPath(head, y);
10. if (x < y) {
11. left.remove(left.size() - 1);
12. result.addAll(left);
13. result.addAll(right);
14. } else {
15. right.remove(right.size() - 1);
16. result.addAll(right);
17. result.addAll(left);
18. }
19. return result;
20. }
22. public static List<Node> findPath(Node head, int x) {
23. List<Node> result = new ArrayList<Node>();
24. if (head.value == x) {
25. result.add(head);
26. return result;
27. }
28. if (head.value > x) {
29. List<Node> left = findPath(head.left, x);
30. result.addAll(left);
31. result.add(head);
32. }
33. if (head.value < x) {
34. result.add(head);
35. List<Node> right = findPath(head.right, x);
36. result.addAll(right);
37. }
38. return result;
39. }
41. private static Node findLowestCommonAncestor(Node node, int value1,
42. int value2) {
43. if (node == null)
44. return null;
46. if (node.value > value2 && node.value > value1)
47. return findLowestCommonAncestor(node.left, value1, value2);
48. else if (node.value < value2 && node.value < value1)
49. return findLowestCommonAncestor(node.right, value1, value2);
50. else
51. return node;
52. }
54. private static class Node {
55. public Node left;
56. public Node right;
57. public int value;
58. }
59. }
We can reuse the code that we wrote in the least common ancestor problem, because the least common ancestor will be the root of our path. Once we have the least common ancestor, we can simply build a path to the value on the right, and a path to the value on the left, and combine the two to get the path between the two nodes.
Complexity:
Time: O(n) where n is the length of the path
Space: O(n)
Searching & Sorting
Searching a sorted array
#basic #search #binary search
Given a sorted array of integers and a target value, write a function that finds the index of the target value in the array.
1. public class Solution {
2. public static int findValue(int[] input, int target) {
3. return findValue(input, target, 0, input.length);
4. }
6. public static int findValue(int[] input, int target, int min, int max) {
7. int mid = (min + max) / 2;
8. if (input[mid] == target)
9. return mid;
10. if (min >= max)
11. return -1;
12. if (target < mid)
13. return findValue(input, target, min, mid);
15. return findValue(input, target, mid + 1, max);
16. }
17. }
The solution to this problem is a simple binary search, no tricks. If the middle number is our target, return its value. If the target is less than our middle number, recur to the left. If our target is greater than our middle number, recur to the right.
Complexity:
Time: O(n log n)
Space: O(1)
Target sum #sorting
Given an array of integers and a target value, write a function to determine whether the array contains two numbers that add up to the target value.
1. import java.util.Arrays;
3. public class Solution {
4. public static int[] targetSum(int[] input, int target) {
5. Arrays.sort(input);
6. int start = 0;
7. int end = input.length - 1;
8. while (start < end) {
9. int sum = input[start] + input[end];
10. if (sum == target) {
11. int[] answer = { start, end };
12. return answer;
13. }
14. if (sum < target)
15. start++;
16. if (sum > target)
17. end--;
18. }
19. return null;
20. }
21. }
We start by sorting the array and creating a pointer at the beginning and one at the end. When the sum of the two values at each pointer is less than the target, move the first pointer forward. When the sum is greater than the target, move the second pointer backward. If the two pointers meet, there is no pair of numbers in the array that sum to the target.
Complexity:
Time: O(n log n)
Space: O(1)
Search on a rotated sorted array #binary search #tricky
Given a sorted array of integers that has been rotated, find a particular value in the array without finding the pivot.
1. public class Solution {
2. public static int rotatedSearch(int[] values, int min, int max, int x) {
3. if (values[min] == x)
4. return min;
5. else if (values[max] == x)
6. return max;
7. else if (max - min == 1)
8. return -1;
10. int mid = (min + max) / 2;
12. if (values[min] <= values[mid]) {
13. if (x <= values[mid] && x >= values[min])
14. return rotatedSearch(values, min, mid, x);
15. else
16. return rotatedSearch(values, mid, max, x);
17. } else {
18. if (x >= values[mid] && x <= values[max])
19. return rotatedSearch(values, mid, max, x);
20. else
21. return rotatedSearch(values, min, mid, x);
22. }
23. }
24. }
At first this problem seems difficult since we can't explicitly find the pivot point. One key observation allows us to treat this problem as a slightly modified binary search. The key is to realize that when we split the array in half, one side will be in sorted order, while the other will contain the pivot. This means if we see that one side is in order, and our value should be on that side (based on that min and max, which will be located at each end), we can simply perform a standard binary search on that side. If our value is not in the sorted side, it must be in the out of order side, and we can recur on the out of order side.
Complexity:
Time: O(n log n)
Space: O(1)
Quicksort
#quicksort #sorting #explanation
Explain how quicksort works.
1. public class QuickSort {
2. public static void swap(int input[], int a, int b) {
3. int temp = input[a];
4. input[a] = input[b];
5. input[b] = temp;
6. }
8. public static int partition(int input[], int front, int end) {
9. int pivot = input[front];
10. while (front < end) {
11. while (input[front] < pivot)
12. front++;
13. while (input[end] > pivot)
14. end--;
15. swap(input, front, end);
16. }
17. return front;
18. }
20. public static void quickSort(int input[], int front, int end) {
21. if (front >= end)
22. return;
23. int pivot = partition(input, front, end);
24. quickSort(input, front, pivot);
25. quickSort(input, pivot + 1, end);
26. }
27. }
Quicksort is one of the the most commonly used sorts, because it is one of the O(n log n) sorts in the average case, and it can be performed in place, without and additional memory. Quicksort works by selecting a pivot and partitioning the array based on that pivot. This involves putting all the numbers less than the pivot on the left side of the pivot, and all the numbers greater on the right side of the pivot. This is accomplished by creating pointers at both the front and end of the partition, and then swapping numbers that are out of place. These left and right sides of the pivot are then sorted recursively until partitions are of size 1 and the array is sorted.
Complexity:
Time: worst case O(n2), average case O(n log n)
Space: O(1)
K smallest elements #sorting #pivot #quicksort
Given an array of n elements, write a function that returns the k smallest numbers.
1. import java.util.Arrays;
3. public class Solution {
4. public static void swap(int input[], int a, int b) {
5. int temp = input[a];
6. input[a] = input[b];
7. input[b] = temp;
8. }
10. public static int partition(int input[], int front, int end) {
11. int pivot = input[front];
12. while (front < end) {
13. while (input[front] < pivot)
14. front++;
15. while (input[end] > pivot)
16. end--;
17. swap(input, front, end);
18. }
19. return front;
20. }
22. public static int[] findKSmallest(int input[], int front, int end,
23. int k) {
24. if (front >= end)
25. return null;
26. int pivot = partition(input, front, end);
27. if (pivot == k)
28. return Arrays.copyOfRange(input, 0, pivot);
29. else {
30. if (pivot > k)
31. return findKSmallest(input, front, pivot, k);
32. return findKSmallest(input, pivot + 1, end, k);
33. }
34. }
36. public static int[] findKSmallest(int input[], int k) {
37. return findKSmallest(input, 0, input.length - 1, k);
38. }
39. }
This problem can be solved with a slight modification to quicksort. The modification is to check whether the pivot index at any given point is less than or greater than the k value. If it is less, we recur on the left side of the pivot. If the pivot is greater than the k value, we recur on the right side of the pivot. If the pivot index is equal to the k value, then the part of the array to the left of the pivot represents the k smallest values, and the pivot represents the kth number. A special case of this solution where k = n / 2 can be used to find the median in O(n) time.
Complexity:
Time: O(n)
Space: O(1)
Hash Maps
Hash tables vs hash maps #hash table #comparison
Explain the difference between a hash table and a hash map.
1. import java.util.HashMap;
2. import java.util.Hashtable;
3.
4. class Solution {
5. HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
6. Hashtable<String, Integer> hashTable = new Hashtable<String, Integer>();
7. }
Hash tables and hash maps have three key differences:
Hash tables are synchronized and thread safe while hash maps are not. Concurrent access is not allowed for hash tables, so only one thread can access a hash table at a time.
Hash maps allow both null keys and null values, while hash tables do not. If we try to insert a null key or value into a hash table, we will get a null pointer exception.
When iterating through a hash map, and we try to modify one of the values, we will get a concurrent modification exception. If we try to modify a hash table during iteration, we will not get an error.
Generate all valid anagrams
#hash table #anagrams #string manipulation
Given an string and an English dictionary, write a function to find all valid anagrams for the string. We can pre-compute and store whatever we'd like to speed up lookup time.
1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.HashMap;
4. import java.util.List;
6. public class Solution {
7. private static HashMap<String, List<String>> map =
8. new HashMap<String, List<String>>();
9. public static void preCompute(List<String> englishDictionary) {
10. for (String word : englishDictionary) {
11. char[] letters = word.toCharArray();
12. Arrays.sort(letters);
13. String sortedWord = String.valueOf(letters);
14. if (map.get(sortedWord) != null) {
15. map.get(sortedWord).add(word);
16. } else {
17. List<String> words = new ArrayList<String>();
18. words.add(word);
19. map.put(sortedWord, words);
20. }
21. }
22. }
24. public static List<String> getAnagrams(String input) {
25. char[] letters = input.toCharArray();
26. Arrays.sort(letters);
27. return map.get(String.valueOf(letters));
28. }
29. }
When we have the option to pre-compute, we want to do as much work as possible before hand to make lookups faster. In this case we can pre-compute a hashmap from each string with its characters in sorted order to a list of other words that are anagrams of that word. For lookups, we can simply sort the characters of the given string and return the list of words we find in the hash map for that value.
Complexity:
Time: O(n log n), were n is the length of the word
Space: O(n)
Counting gets and puts #hash map
Extend HashMap to count the number of get and put operations across all instances of the data structure.
1. import java.util.HashMap;
3. public class CountedMap<K, V> extends HashMap<K, V> {
4. private static int numGets = 0;
5. private static int numPuts = 0;
7. @Override
8. public V put(K key, V value) {
9. numPuts++;
10. return super.put(key, value);
11. }
13. @Override
14. public V get(Object key) {
15. numGets++;
16. return super.get(key);
17. }
19. public int getNumGets() {
20. return numGets;
21. }
23. public int getNumPuts() {
24. return numPuts;
25. }
26. }
In order to count the number of puts and gets that are performed, we extend HashMap, and overwrite the put and get methods. When either method is called, we increment the corresponding count and then call the correct super method. In order to keep count across all instances of the class, we make our counting variables static, so there is just one instance of each.
Stacks & Queues
Stacks vs queues #stack #queue #explanation
Explain the differences between a stack and a queue.
1. import java.util.LinkedList;
2. import java.util.Queue;
3. import java.util.Stack;
5. public class StackQueue {
6. Stack<Object> stack = new Stack<Object>();
7. Queue<Object> queue = new LinkedList<Object>();
8. }
Stacks behave like stacks of dishes, while queues behave like lines of people waiting for tickets. The difference lies in the order in which elements are removed from each data structure. A stack uses what is called a first-in, first-out (FIFO) model. A queue on the other hand uses a last-in, first-out (LIFO) model. This means that with a stack, like a stack of dishes, when we remove a dish it will be the last dish that we placed on the stack. On the other hand with a queue, like a line of people waiting for tickets, the first person in line will get their tickets first. A stack typically uses the terminology push and pop for its add and remove methods, while queues typically use enqueue and dequeue.
Queue using stacks #stack #queue #tricky
Implement a queue data structure using only stacks. It must support the queue and dequeue operations. Don't worry about concurrency issues.
1. import java.util.Stack;
3. public class Solution {
4. public class Queue<E> {
5. private Stack<E> incoming = new Stack<E>();
6. private Stack<E> outgoing = new Stack<E>();
7.
8. public void queue(E item) {
9. incoming.push(item);
10. }
12. public E dequeue() {
13. if (outgoing.isEmpty()) {
14. while (!incoming.isEmpty()) {
15. outgoing.push(incoming.pop());
16. }
17. }
18. return outgoing.pop();
19. }
20. }
21. }
We can create a queue using two stacks, an incoming stack and an outgoing stack. When we queue a new item, simply push it onto the incoming stack. When we have to dequeue an item, we simply pop an item off of the outgoing stack. If the outgoing stack is empty, we pop all of the items off of the incoming stack, reversing their order, and place them on the outgoing stack.
Complexity:
Time: Amortized O(1)
Space: O(n)
Minimum stack #stack #minimum
Create a data structure that extends Stack and supports findMin in O(1) time.
1. import java.util.Stack;
3. public class MinimumStack<E extends Comparable<E>> extends Stack<E> {
4. private Stack<E> minStack;
6. public MinimumStack() {
7. super();
8. minStack = new Stack<E>();
9. }
10. @Override
11. public E push(E element) {
12. if (element.compareTo(minStack.peek()) <= 0)
13. minStack.push(element);
14. return super.push(element);
15. }
16. @Override
17. public E pop() {
18. E element = super.pop();
19. if (element.compareTo(minStack.peek()) == 0)
20. minStack.pop();
21. return element;
22. }
23. public E findMin() {
24. return minStack.peek();
25. }
26. }
We can keep track of the minimums with a seperate min stack. When we push a new element onto the stack, we check to see whether this element is smaller than the old min. If it is, add it to the min stack. When we pop an element, we check to see if it is the current minimum on the min stack. If it is, we pop it off of the min stack as well. When we want to perform findMin, we can simply call peek on the min stack.
Complexity:
Time: O(1)
Space: O(n)
Probability & Randomness
Random range expansion #random #tricky #probability
Given a random number generator that gives us an integer between 1 and 5 (inclusive), write a function that generates a random number between 1 and 7 (inclusive).
1. public class Solution {
2. public static int randomNumber7() {
3. int values[][] = {
4. { 1, 1, 1, 2, 2 },
5. { 2, 3, 3, 3, 4 },
6. { 4, 4, 5, 5, 5 },
7. { 6, 6, 6, 7, 7 },
8. { 7, 0, 0, 0, 0 }
9. };
11. int result = 0;
12. while (result == 0) {
13. int i = randomNumber5();
14. int j = randomNumber5();
15. result = values[i-1][j-1];
16. }
17. return result;
18. }
20. public static int randomNumber5() {
21. // implemented for us
22. }
23. }
We need to make sure we maintain the same probability that we choose any number between 1 and 7. In order to accomplish this, we use our working random function to select two numbers between 1 and 5. This gives us 25 possibilities. Keeping the probabilities even, we can have 3 sets of possibilities between 1 and 7 (3*7 = 21 < 25). This means there are possible outcomes in which we need to try again. For the rest of the numbers, we simply assign 3 numbers that correspond with each number from 1 to 7. Programmatically, this can be achieved in the most straight forward fashion by creating a two dimensional array of values, and using the generated numbers to select a value in the array. If the selected value is one of the values that should be thrown away, we select another pair of random numbers.
Complexity:
Time: Worst case it runs forever, but the probability of this is infinitesimally small. The average
case is between 1 and 2 selections.
Space: O(1)
Random number shuffling #probability #random
Given an array of integers, write a function to shuffle the integers randomly, so that each permutation is equally likely.
1. public class Solution {
2. public static int[] shuffleArray(int[] input) {
3. for (int i = 0; i < input.length; i++) {
4. int swap = i + (int) (Math.random() * (input.length - i));
5. int temp = input[swap];
6. input[swap] = input[i];
7. input[i] = temp;
8. }
9. return input;
10. }
11. }
We have to be careful to not give one element a larger probability to be swapped than any other in order to make each possible permutation equally likely. In order to accomplish this we can iterate over the array in order, swapping each element with a random element that comes after the current element.
Complexity:
Time: O(n)
Space: O(1)
Coin flips to die rolls #probability #random
Given a function that gives us the result of a coin flip (1 or 2), write a function that gives us the result of a dice roll (1 to 6 inclusive).
1. public class Solution {
2. public static int dieRoll() {
3. int result = 0;
4. while (result < 1 || result > 6) {
5. result = 0;
6. if (coinFlip() == 1)
7. result |= 1;
8. if (coinFlip() == 1)
9. result |= 2;
10. if (coinFlip() == 1)
11. result |= 4;
12. }
13. return result;
14. }
16. private static int coinFlip() {
17. // implemented for us
18. }
19. }
There are many solutions to this problem. One solution is to flip the coin three times and use the results of the coin flips to decide whether or not to turn on each of the three lowest bits in an integer. This will give us a result between 0 and 7. If we get 0 or 7, we'll need to roll again and continue to do so until we get a valid die roll.
Complexity:
Time: This could run forever, but the chance of that is infinitesimally small
Space: O(1)
Optimization
Find nearest neighbors #sorting
Given array of people, each represented by their name (a string) and their position in line (an integer). Write a function that takes a name and returns their 3 nearest neighbors. We can assume for the sake of simplicity that there are at least 4 people in the list.
1. import java.util.Arrays;
3. public class Solution {
4. public static Person[] findNearestNeighbors(Person[] people,
5. String target) {
6. Person[] neighbors = new Person[3];
7. Arrays.sort(people);
8. for (int i = 0; i < people.length; i++) {
9. if (people[i].name.equals(target)) {
10. int before = i - 1;
11. int after = i + 1;
12. int index = 0;
13. while (index < 3) {
14. if (after < people.length && (before < 0 ||
Math.abs(people[before].position - people[i].position) >
Math.abs(people[after].position - people[i].position))) {
neighbors[index] = people[after];
after++;
19. } else {
neighbors[index] = people[before];
before--;
22. }
23. index++;
24. }
25. }
26. }
27. return neighbors;
28. }
30. private static class Person implements Comparable<Person> {
31. public String name;
32. public int position;
33. @Override
34. public int compareTo(Person other) {
35. return ((Person) other).position - this.position;
36. }
37. }
38. }
We can solve this quite easily by first sorting the array by each person's position. The 3 nearest neighbors will then be located in either in the three positions immediately before or immediately after the target.
Complexity:
Time: O(n log n)
Space: O(1)
Stock market timing #stock market #optimization
Given an array of integers, where each element represents the stock price on consecutive days. Write a function to find the maximum profit if we're allowed to buy exactly once and sell exactly once over the time period.
1. public class Solution {
2. public static int findBiggestProfit(int[] days) {
3. int minPrice = days[0];
4. int maxProfit = 0;
5. for (int i = 1; i < days.length; i++) {
6. if (days[i] < minPrice)
7. minPrice = days[i];
8. int currentProfit = days[i] - minPrice;
9. if (currentProfit > maxProfit)
10. maxProfit = currentProfit;
11. }
12. return maxProfit;
13. }
14. }
We can go over the stock price data day by day keeping track of the lowest price we've seen so far, and the best profit we've seen so far. Best profit is updated when we find a stock price that, when the min price is subtracted, is greater than the old max profit.
Complexity:
Time: O(n)
Space: O(1)
Maximal subarray #optimization
Given an array, describe an algorithm to identify the subarray with the maximum sum. For example, if the input is [1, -3, 5, 2, 9, -8, -6, 4], the output would be [5, 2, 9].
1. public class Solution {
2. public static int maxSubarray(int[] input) {
3. int maxSoFar = 0;
4. int maxEndingHere = 0;
5. for(int i = 0; i < input.length; i++) {
6. maxEndingHere = Math.max(0, maxEndingHere + input[i]);
7. maxSoFar = Math.max(maxSoFar, maxEndingHere);
8. }
9. return maxSoFar;
10. }
11. }
While this may seem like a dynamic programming problem, we can further optimize the memory usage by only keeping track of the maximum we've seen so far and the maximum ending at the current position instead of memoizing these values across the entire array. For the max ending here value, we add the current value to the last max ending value if the sum is greater than zero, otherwise we reset the value to zero. We then use this value and check it against the maximum we've seen so far, and update it if the current value is greater.
Complexity:
Time: O(n)
Space: O(1)
Path finding #a star, path finding
Given a two dimensional grid with weights representing the cost of moving through each square, write a function that finds the minimum path between a given start and end cell.
1. import java.util.ArrayList;
2. import java.util.HashSet;
3. import java.util.List;
4. import java.util.Set;
6. public class AStar {
7. public class Node {
8. List<Node> neighbors = new ArrayList<Node>();
9. Node parent;
10. int xPos;
11. int yPos;
12. int fCost;
13. int gCost;
14. int hCost;
15. int cost;
16. }
18. public List<Node> aStar(Node start, Node goal) {
19. Set<Node> open = new HashSet<Node>();
20. Set<Node> closed = new HashSet<Node>();
22. start.gCost = 0;
23. start.hCost = estimateDistance(start, goal);
24. start.fCost = start.hCost;
26. open.add(start);
27. while (true) {
28. Node current = null;
29. if (open.size() == 0)
30. throw new RuntimeException("No path exists");
31. for (Node node : open) {
32. if (current == null || node.fCost < current.fCost)
33. current = node;
34. }
36. if (current == goal)
37. break;
39. open.remove(current);
40. closed.add(current);
41.
42. for (Node neighbor : current.neighbors) {
43. if (neighbor == null)
44. continue;
45. int nextG = current.gCost + neighbor.cost;
46. if (nextG < neighbor.gCost) {
47. open.remove(neighbor);
48. closed.remove(neighbor);
49. }
51. if (!open.contains(neighbor) && !closed.contains(neighbor)) {
52. neighbor.gCost = nextG;
53. neighbor.hCost = estimateDistance(neighbor, goal);
54. neighbor.fCost = neighbor.gCost + neighbor.hCost;
55. neighbor.parent = current;
56. open.add(neighbor);
57. }
58. }
59. }
61. List<Node> nodes = new ArrayList<Node>();
62. Node current = goal;
63. while (current.parent != null) {
64. nodes.add(current);
65. current = current.parent;
66. }
67. nodes.add(start);
69. return nodes;
70. }
72. public int estimateDistance(Node node1, Node node2) {
73. return Math.abs(node1.xPos - node2.xPos) +
74. Math.abs(node1.yPos - node2.yPos);
75. }
76. }
This question is a set up for us to use the A* path finding algorithm.
Complexity:
Time: O(N) where N is the number of cells in the grid
Design Patterns
Listener design pattern
#design patterns #listener #explanation
Explain the listener design pattern.
1. public class Listener {
2. public static void listener() {
3. EventSource eventSource = new EventSource();
4. EventListener eventListener = new EventListener();
5.
6. eventSource.addListener(eventListener);
7. }
8. }
This is a design pattern that is often used when handling user interface actions. The idea is that there are a group of "listeners" who are interested in a certain event happening. These listeners register themselves as listeners with the event source. When the event occurs, the event source knows to go through its list of listeners for that event, and notify them that the event has occurred. An example of this would be if we had a button on a page that was supposed to make a ball bounce on the page when clicked. The object controlling the ball would subscribe to an "onClick" event for the button. When the object receives a click event from the button, it knows to make the ball bounce. This is a very flexible design pattern that can be used in many situations.
Model view controller #model view controller #mvc #design pattern #explanation
Explain the model view controller design pattern.
1. public class Model {
2. // Contains program state, variables, etc
3. }
5. public class View {
6. // Contains user interface, text fields, buttons, etc.
7. }
9. public class Controller {
10. // Listens for inputs from view and makes changes to model
11. // Listens for model changes and makes changes to view
12. }
The model view controller (MVC) design pattern is used when developing user facing applications in order to separate the application's data from the user interface. The idea is that the user interface should be able the change without affecting the underlying data model and vice versa. The model contains the application state, the view contains the application's user interface, and the controller handles communication between the two.
Singleton pattern
#singleton #design patterns #explanation
Explain the singleton design pattern.
1. public class Singleton {
2. private static final Singleton instance;
3.
4. static {
5. instance = new Singleton();
6. }
8. public static Singleton getInstance() {
9. return instance;
10. }
12. private Singleton() {
13. }
14. }
The singleton pattern is used in order to maintain a single instance of an object in our program. Singletons contain private constructors that are never called externally. Instead, the "getInstance()" method is called when an instance of the singleton object is needed. Singletons can be initialized either lazily (when the getInstance method is first called) or eagerly (when the object is created).
Parallelism & Concurrency
Threads and processes #parallelism #explanation
Explain threads and processes.
1. public class MyThread extends Thread {
3. public void run() {
4. // Code that we want to execute on the thread
5. }
7. public static void main(String args[]) {
8. (new MyThread()).start();
9. }
10. }
Threads and processes are both paradigms that allow computers to run more than one piece of code at the same time. If our computer has multiple cores it can actually execute them at the same time, while single core machines only simulate this simultaneous execution using context switching. A process is a program that is run by a user. Our web browser runs on one processes, while our text editor runs on another. This makes it appear as if both are running at the same time. Each process can have one or more threads. Our web browser may run each window on a separate thread, so if we have two windows open at once, we can see each one functioning at the same time. Likewise, a program that has a user interface and is performing some heavy computation at the same time (like rendering graphics) will likely take user input and perform the processing on different threads. This allows clicks and key presses to be registered very quickly, without having to wait for the heavy computation to finish. Threads can share memory, while processes have separate chunks of memory allocated to them.
Mutex vs semaphore #parallelism #explanation
Explain the difference between a mutex and a semaphore.
1. import java.util.concurrent.Semaphore;
3. class UseSemaphore {
4. private static final int NUM_RESOURCES = 100;
5. private final Semaphore semaphore = new Semaphore(NUM_RESOURCES, true);
6.
7. public void useSemaphore() throws InterruptedException {
8. semaphore.acquire();
9. // Do something that requires one of the resources
10. semaphore.release();
11. }
12. }
Both mutexes and semaphores are used in parallel programming to prevent multiple threads from accessing a shared resource at the same time. A semaphore is used when we have a limited pool of resources. Let's say for example we don't want to have more than 5 connections open to a server at one time. We can create a semaphore with the limit of 5. Each time a thread wants to open a connection, it must acquire a resource from the semaphore, and then release it when it is done. A mutex is like a semaphore with only a single resource. Mutexes are like locks and are used to prevent concurrent access on a single object or resource.
Synchronized methods #parallelism #java
Explain Java synchronized methods.
1. public class SynchronizedCounter {
2. private int count = 0;
4. public synchronized void increment() {
5. count++;
6. }
8. public synchronized void decrement() {
9. count--;
10. }
12. public synchronized int value() {
13. return count;
14. }
15. }
Objects in Java have their own mutexes, or locks. When a method is called that is synchronized, the object's mutex is locked. When the method is finished, the mutex is unlocked. This ensures only one synchronized method can be called on an object at a time.
Preventing deadlocks #parallelism #deadlocks
Explain one way to prevent deadlocks.
1. public class Deadlock {
2. public static void deadLockThreadOne() {
3. lockA();
4. lockB();
5. }
7. public static void deadLockThreadTwo() {
8. lockB();
9. lockA();
10. }
11. }
Deadlocks can be prevented by having a well defined access order when accessing multiple resources that require locks. This prevents the case where two threads are competing for the same resources, and one thread obtains a lock for resource A at the same time as another thread obtains a lock for resource B. Now thread one needs to obtain a lock for B, while the other thread is waiting to obtain the lock for A. The two threads will wait forever. If both threads obtained lock A first, then lock B, this situation would not happen.
Matrix manipulation
Matrix rotation in place #matrix manipulation #tricky
Write a function that rotates an two dimensional square matrix 90 degrees using O(1) additional memory.
1. public class Solution {
2. public static void rotateMatrix(int input[][]) {
3. int n = input.length;
4. if (n <= 1)
5. return;
7. for (int i = 0; i < n / 2; i++) {
8. for (int j = i; j < n - i - 1; j++) {
9. int temp = input[i][j];
10. input[i][j] = input[n - j - 1][i];
11. input[n - j - 1][i] = input[n - 1 - i][n - 1 - j];
12. input[n - 1 - i][n - 1 - j] = input[j][n - 1 - i];
13. input[j][n - 1 - i] = temp;
14. }
15. }
16. }
17. }
The key to this problem is that we have to rotate 4 numbers at once, storing the first value that is overwritten as a temporary variable and then restoring it in the end. We work our way from the outside to the inside in "layers" performing these four way swaps until we reach the center.
Complexity:
Time: O(n)
Space: O(1)
