From http://elementsofprogramminginterviews.com/solutions/
Compute all Valid IP Address
public static List<String> getValidIpAddress(String s) {
List<String> result = new ArrayList<>();
for (int i = 1; i < 4 && i < s.length(); ++i) {
String first = s.substring(0, i);
if (isValidPart(first)) {
for (int j = 1; i + j < s.length() && j < 4; ++j) {
String second = s.substring(i, i + j);
if (isValidPart(second)) {
for (int k = 1; i + j + k < s.length() && k < 4; ++k) {
String third = s.substring(i + j, i + j + k), fourth = s
.substring(i + j + k);
if (isValidPart(third) && isValidPart(fourth)) {
result.add(first + "." + second + "." + third + "." + fourth);
}
}
}
}
}
}
return result;
}
private static boolean isValidPart(String s) {
if (s.length() > 3) {
return false;
}
// "00", "000", "01", etc. are not valid, but "0" is valid.
if (s.startsWith("0") && s.length() > 1) {
return false;
}
int val = Integer.parseInt(s);
return val <= 255 && val >= 0;
}
Implement even-odd mergeEvenOddMergeLinkedListTemplate.java
public static <T> Node<T> evenOddMerge(Node<T> L) {
Node<T> odd = (L != null) ? L.next : null;
Node<T> oddCurr = odd;
Node<T> preEvenCurr = null, evenCurr = L;
while (evenCurr != null && oddCurr != null) {
evenCurr.next = oddCurr.next;
preEvenCurr = evenCurr;
evenCurr = evenCurr.next;
if (evenCurr != null) {
oddCurr.next = evenCurr.next;
oddCurr = oddCurr.next;
}
}
// Odd number of nodes.
if (evenCurr != null) {
preEvenCurr = evenCurr;
}
// Prevents empty list.
if (preEvenCurr != null) {
preEvenCurr.next = odd;
}
return L;
}
Test whether a singly linked list is palindromic
PalindromeLinkedListTemplate.java
public static <T> boolean isLinkedListAPalindrome(Node<T> L) {
// Find the middle point of L if L is odd length,
// and right-middle point if L is even length.
Node<T> slow = L, fast = L;
while (fast != null) {
fast = fast.next;
if (fast != null) {
fast = fast.next;
slow = slow.next;
}
}
// Compare the first half and reversed second half lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
while (reverse != null && L != null) {
if (reverse.data != L.data) {
return false;
}
reverse = reverse.next;
L = L.next;
}
return true;
}
public static double findMedianSortedCircularLinkedList(Node<Integer> rNode) {
if (rNode == null) {
// no node in this linked list.
throw new IllegalArgumentException("empty list");
}
// Checks all nodes are identical or not and identify the start of list.
Node<Integer> curr = rNode;
Node<Integer> start = rNode;
int count = 0;
do {
++count;
curr = curr.next;
// start will point to the largest element in the list.
if (start.data.compareTo(curr.data) <= 0) {
start = curr;
}
} while (curr != rNode);
// start's next is the begin of the list.
start = start.next;
// Traverses to the middle of the list and return the median.
for (int i = 0; i < ((count - 1) >> 1); ++i) {
start = start.next;
}
return (count & 1) != 0 ? start.data : 0.5 * (start.data + start.next.data);
}
Split original list and maintain multiple lists, and concat them at last. Use dummy head node for each list.
public static NodeT<Integer> listPivoting(NodeT<Integer> L, int x) {
NodeT<Integer> now = L;
NodeT<Integer> lessHead = new NodeT<>(0, null);
NodeT<Integer> equalHead = new NodeT<>(0, null);
NodeT<Integer> largerHead = new NodeT<>(0, null);
NodeT<Integer> lessTail = lessHead;
NodeT<Integer> equalTail = equalHead;
NodeT<Integer> largerTail = largerHead;
while (now != null) {
if (now.data < x) {
lessTail.next = now;
lessTail = now;
} else if (now.data == x) {
equalTail.next = now;
equalTail = now;
} else { // now->data > x.
largerTail.next = now;
largerTail = now;
}
now = now.next;
}
lessTail.next = equalTail.next = largerTail.next = null;
if (largerHead.next != null) {
equalTail.next = largerHead.next;
}
if (equalHead.next != null) {
lessTail.next = equalHead.next;
}
return lessHead.next;
}
Uses insertion sort on linked list.
public static NodeT<Integer> insertionSort(final NodeT<Integer> L) {
if (L == null) {
return L;
}
NodeT<Integer> dummyHead = new NodeT<>(0, L);
NodeT<Integer> now = L;
while (now != null && now.next != null) {
if (now.data > now.next.data) {
NodeT<Integer> target = now.next;
NodeT<Integer> pre = dummyHead;
while (pre.next.data < target.data) {
pre = pre.next;
}
NodeT<Integer> temp = pre.next;
pre.next = target;
now.next = target.next;
target.next = temp;
} else {
now = now.next;
}
}
return dummyHead.next;
}
Add list-based integers
add-two-number-list.cc AddTwoNumberList.java
public static NodeT<Integer> addTwoNumbers(NodeT<Integer> L1,
NodeT<Integer> L2) {
NodeT<Integer> dummyHead = new NodeT<>(0, null);
NodeT<Integer> digit = dummyHead;
int sum = 0;
while (L1 != null || L2 != null) {
if (L1 != null) {
sum += L1.data;
L1 = L1.next;
}
if (L2 != null) {
sum += L2.data;
L2 = L2.next;
}
digit.next = new NodeT<>(sum % 10, null);
sum /= 10;
digit = digit.next;
}
if (sum > 0) {
digit.next = new NodeT<>(sum, null);
}
return dummyHead.next;
}
Stack and Queue
public static class Stack {
private LinkedList<Integer> s = new LinkedList<>();
private LinkedList<Pair<Integer, Integer>> aux = new LinkedList<>();
public boolean empty() {
return s.isEmpty();
}
public Integer max() {
if (!empty()) {
return aux.peek().getFirst();
}
throw new RuntimeException("empty_stack");
}
public Integer pop() {
if (empty()) {
throw new RuntimeException("empty_stack");
}
Integer ret = s.pop();
if (ret.equals(aux.peek().getFirst())) {
aux.peek().setSecond(aux.peek().getSecond() - 1);
if (aux.peek().getSecond().equals(0)) {
aux.pop();
}
}
return ret;
}
public void push(Integer x) {
s.push(x);
if (!aux.isEmpty()) {
if (x.compareTo(aux.peek().getFirst()) == 0) {
aux.peek().setSecond(aux.peek().getSecond() + 1);
} else if (x.compareTo(aux.peek().getFirst()) > 0) {
aux.push(new Pair<>(x, 1));
}
} else {
aux.push(new Pair<>(x, 1));
}
}
}
public static class Stack<T extends Comparable<T>> {
private LinkedList<Pair<T, T>> s = new LinkedList<Pair<T, T>>();
public boolean empty() {
return s.isEmpty();
}
public T max() {
if (!empty()) {
return s.peek().getSecond();
}
throw new RuntimeException("empty stack");
}
public T pop() {
if (empty()) {
throw new RuntimeException("empty stack");
}
return s.pop().getFirst();
}
public void push(T x) {
s.push(new Pair<T, T>(x, Collections.max(Arrays.asList(x, empty() ? x : s
.peek().getSecond()))));
}
}
Evaluate RPN expressions RPN.java public static int eval(String s) {
LinkedList<Integer> evalStack = new LinkedList<>();
String[] symbols = s.split(",");
for (String symbol : symbols) {
if (symbol.length() == 1 && "+-*/".contains(symbol)) {
int y = evalStack.pop();
int x = evalStack.pop();
switch (symbol.charAt(0)) {
case '+':
evalStack.push(x + y);
break;
case '-':
evalStack.push(x - y);
break;
case '*':
evalStack.push(x * y);
break;
case '/':
evalStack.push(x / y);
break;
default:
throw new IllegalArgumentException("Malformed RPN at :" + symbol);
}
} else { // symbol is a number.
evalStack.push(Integer.parseInt(symbol));
}
}
return evalStack.pop();
}
public static boolean isValidParentheses(String s) {
LinkedList<Character> leftParens = new LinkedList<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
leftParens.push(s.charAt(i));
} else {
if (leftParens.isEmpty()) {
return false; // No left paren.
}
if ((s.charAt(i) == ')' && leftParens.peek() != '(')
|| (s.charAt(i) == '}' && leftParens.peek() != '{')
|| (s.charAt(i) == ']' && leftParens.peek() != '[')) {
return false; // Unmatched left paren.
}
leftParens.pop();
}
}
return leftParens.isEmpty();
}
LinkedList<String> s = new LinkedList<>(); // Use LinkedList as a stack.
// Special case: starts with "/", which is an absolute path.
if (path.startsWith("/")) {
s.push("/");
}
for (String token : path.split("/")) {
if (token.equals("..")) {
if (s.isEmpty() || s.peek().equals("..")) {
s.push(token);
} else {
if (s.peek().equals("/")) {
throw new RuntimeException("Path error");
}
s.pop();
}
} else if (!token.equals(".") && !token.isEmpty()) { // Name.
for (char c : token.toCharArray()) {
if (c != '.' && !Character.isDigit(c) && !Character.isLetter(c)) {
throw new RuntimeException("Invalid directory name");
}
}
s.push(token);
}
}
StringBuilder normalizedPath = new StringBuilder();
if (!s.isEmpty()) {
Iterator<String> it = s.descendingIterator();
String prev = it.next();
normalizedPath.append(prev);
while (it.hasNext()) {
if (!prev.equals("/")) {
normalizedPath.append("/");
}
prev = it.next();
normalizedPath.append(prev);
}
}
return normalizedPath.toString();
}
LinkedList<BinarySearchTree<T>> s = new LinkedList<BinarySearchTree<T>>();
BinarySearchTree<T> curr = n;
while (!s.isEmpty() || curr != null) {
if (curr != null) {
s.push(curr);
curr = curr.getLeft();
} else {
curr = s.pop();
System.out.println(curr.getData());
curr = curr.getRight();
}
}
}
searchPostingsListHelper(L, 0);
}
private static int searchPostingsListHelper(PostingListNode L, int order) {
if (L != null && L.getOrder() == -1) {
L.setOrder(order++);
order = searchPostingsListHelper(L.getJump(), order);
order = searchPostingsListHelper(L.getNext(), order);
}
return order;
}
public T data;
public BinaryTreeNode<T> left, right;
public int size;
}
// @include
public static BinaryTreeNode<Integer> findKthNodeBinaryTree(
BinaryTreeNode<Integer> root, int k) {
BinaryTreeNode<Integer> n = root;
while (n != null) {
int leftSize = n.left != null ? n.left.size : 0;
if (leftSize < k - 1) {
k -= (leftSize + 1);
n = n.right;
} else if (leftSize == k - 1) {
return n;
} else { // leftSize > k - 1.
n = n.left;
}
}
throw new RuntimeException("no k-th node in binary tree");
}
BinaryTree<Integer> n = node;
if (n.getRight() != null) {
// Find the leftmost element in n's right subtree.
n = n.getRight();
while (n.getLeft() != null) {
n = n.getLeft();
}
return n;
}
// Find the first parent whose left child contains n.
while (n.getParent() != null && n.getParent().getRight() == n) {
n = n.getParent();
}
// Return nullptr means n does not have successor.
return n.getParent();
}
public static List<Star> findClosestKStars(InputStream sin, int k) {
// Use maxHeap to find the closest k stars.
PriorityQueue<Star> maxHeap = new PriorityQueue<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Record the first k stars.
while (true) {
Star s = (Star) osin.readObject();
if (maxHeap.size() == k) {
// Compare the top of heap with the incoming star.
Star farStar = maxHeap.peek();
// compareTo() method compares the Euclidean distances
// of s and farStar to the origin (Earth).
if (s.compareTo(farStar) < 0) {
maxHeap.remove();
maxHeap.add(s);
}
} else {
maxHeap.add(s);
}
}
} catch (IOException e) {
// Do nothing, was read last element in stream.
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Store the closest k stars.
List<Star> closestStars = new ArrayList<>();
while (!maxHeap.isEmpty()) {
closestStars.add(maxHeap.remove());
}
return closestStars;
}
Collections.sort(A, c);
}
private static void nthElement(List<Integer> A, int n) {
nthElement(A, n, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
}
// @include
public static List<Integer> findKClosestToMedian(List<Integer> a, int k) {
// Find the element i where |a[i] - median| is k-th smallest.
final double m = findMedian(a);
nthElement(a, k - 1, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return Double.valueOf(Math.abs(a - m)).compareTo(Math.abs(b - m));
}
});
return new ArrayList<>(a.subList(0, k));
}
private static class Data {
public int larger;
public int equal;
}
public static int compareKthLargestHeap(List<Integer> maxHeap, int k, int x) {
Data data = new Data();
data.larger = 0;
data.equal = 0;
compareKthLargestHeapHelper(maxHeap, k, x, 0, data);
return data.larger >= k ? 1 : (data.larger + data.equal >= k ? 0 : -1);
}
private static void compareKthLargestHeapHelper(List<Integer> maxHeap, int k,
int x, int idx, Data data) {
if (data.larger >= k || idx >= maxHeap.size() || maxHeap.get(idx) < x) {
return;
} else if (maxHeap.get(idx) == x) {
if (++data.equal >= k) {
return;
}
} else { // max_heap[idx] > x.
++data.larger;
}
compareKthLargestHeapHelper(maxHeap, k, x, (idx * 2) + 1, data);
compareKthLargestHeapHelper(maxHeap, k, x, (idx * 2) + 2, data);
}
int[] counter = new int[1 << 16];
ifs.mark(Integer.MAX_VALUE);
Scanner s = new Scanner(ifs);
while (s.hasNextInt()) {
++counter[s.nextInt() >> 16];
}
for (int i = 0; i < counter.length; ++i) {
// Finds one bucket contains less than (1 << 16) elements.
if (counter[i] < (1 << 16)) {
BitSet bitVec = new BitSet(1 << 16);
ifs.reset();
s = new Scanner(ifs);
while (s.hasNext()) {
int x = s.nextInt();
if (i == (x >> 16)) {
bitVec.set(((1 << 16) - 1) & x); // Gets the lower 16 bits of x.
}
}
ifs.close();
for (int j = 0; j < (1 << 16); ++j) {
if (!bitVec.get(j)) {
return (i << 16) | j;
}
}
}
}
throw new RuntimeException("no missing element");
}
public static Pair<Integer, Integer> findDuplicateMissing(List<Integer> A) {
int sum = 0, squareSum = 0;
for (int i = 0; i < A.size(); ++i) {
sum += i - A.get(i);
squareSum += i * i - A.get(i) * A.get(i);
}
return new Pair<>((squareSum / sum - sum) / 2, (squareSum / sum + sum) / 2);
}
FindMissingAndDuplicateXOR.java
public static Pair<Integer, Integer> findDuplicateMissing(List<Integer> A) {
int missXORDup = 0;
for (int i = 0; i < A.size(); ++i) {
missXORDup ^= i ^ A.get(i);
}
// We need to find a bit that's set to 1 in missXORDup. This assignment
// sets all of bits in differBit to 0 except for the least significant
// bit in missXORDup that's 1.
int differBit = missXORDup & (~(missXORDup - 1));
int missOrDup = 0;
for (int i = 0; i < A.size(); ++i) {
if ((i & differBit) != 0) {
missOrDup ^= i;
}
if ((A.get(i) & differBit) != 0) {
missOrDup ^= A.get(i);
}
}
for (int ai : A) {
if (ai == missOrDup) { // Find duplicate.
return new Pair<>(missOrDup, missOrDup ^ missXORDup);
}
}
// missOrDup is the missing element.
return new Pair<>(missOrDup ^ missXORDup, missOrDup);
}
public static int findElementAppearsOnce(List<Integer> A) {
int ones = 0, twos = 0;
int nextOnes, nextTwos;
for (int i : A) {
nextOnes = (~i & ones) | (i & ~ones & ~twos);
nextTwos = (~i & twos) | (i & ones);
ones = nextOnes;
twos = nextTwos;
}
return ones;
}
Map<Character, Integer> hash = new HashMap<>();
// Inserts all chars in L into a hash table.
for (char c : L.toCharArray()) {
if (!hash.containsKey(c)) {
hash.put(c, 1);
} else {
hash.put(c, hash.get(c) + 1);
}
}
// Checks characters in M that could cover characters in a hash table.
for (char c : M.toCharArray()) {
if (hash.containsKey(c)) {
hash.put(c, hash.get(c) - 1);
if (hash.get(c) == 0) {
hash.remove(c);
if (hash.isEmpty()) {
return true;
}
}
}
}
// No entry in hash means L can be covered by M.
return hash.isEmpty();
}
Compute all Valid IP Address
public static List<String> getValidIpAddress(String s) {
List<String> result = new ArrayList<>();
for (int i = 1; i < 4 && i < s.length(); ++i) {
String first = s.substring(0, i);
if (isValidPart(first)) {
for (int j = 1; i + j < s.length() && j < 4; ++j) {
String second = s.substring(i, i + j);
if (isValidPart(second)) {
for (int k = 1; i + j + k < s.length() && k < 4; ++k) {
String third = s.substring(i + j, i + j + k), fourth = s
.substring(i + j + k);
if (isValidPart(third) && isValidPart(fourth)) {
result.add(first + "." + second + "." + third + "." + fourth);
}
}
}
}
}
}
return result;
}
private static boolean isValidPart(String s) {
if (s.length() > 3) {
return false;
}
// "00", "000", "01", etc. are not valid, but "0" is valid.
if (s.startsWith("0") && s.length() > 1) {
return false;
}
int val = Integer.parseInt(s);
return val <= 255 && val >= 0;
}
Implement even-odd mergeEvenOddMergeLinkedListTemplate.java
public static <T> Node<T> evenOddMerge(Node<T> L) {
Node<T> odd = (L != null) ? L.next : null;
Node<T> oddCurr = odd;
Node<T> preEvenCurr = null, evenCurr = L;
while (evenCurr != null && oddCurr != null) {
evenCurr.next = oddCurr.next;
preEvenCurr = evenCurr;
evenCurr = evenCurr.next;
if (evenCurr != null) {
oddCurr.next = evenCurr.next;
oddCurr = oddCurr.next;
}
}
// Odd number of nodes.
if (evenCurr != null) {
preEvenCurr = evenCurr;
}
// Prevents empty list.
if (preEvenCurr != null) {
preEvenCurr.next = odd;
}
return L;
}
Test whether a singly linked list is palindromic
PalindromeLinkedListTemplate.java
public static <T> boolean isLinkedListAPalindrome(Node<T> L) {
// Find the middle point of L if L is odd length,
// and right-middle point if L is even length.
Node<T> slow = L, fast = L;
while (fast != null) {
fast = fast.next;
if (fast != null) {
fast = fast.next;
slow = slow.next;
}
}
// Compare the first half and reversed second half lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
while (reverse != null && L != null) {
if (reverse.data != L.data) {
return false;
}
reverse = reverse.next;
L = L.next;
}
return true;
}
Compute the median of a sorted circular linked list
MedianSortedCircularLinkedListTemplate.javapublic static double findMedianSortedCircularLinkedList(Node<Integer> rNode) {
if (rNode == null) {
// no node in this linked list.
throw new IllegalArgumentException("empty list");
}
// Checks all nodes are identical or not and identify the start of list.
Node<Integer> curr = rNode;
Node<Integer> start = rNode;
int count = 0;
do {
++count;
curr = curr.next;
// start will point to the largest element in the list.
if (start.data.compareTo(curr.data) <= 0) {
start = curr;
}
} while (curr != rNode);
// start's next is the begin of the list.
start = start.next;
// Traverses to the middle of the list and return the median.
for (int i = 0; i < ((count - 1) >> 1); ++i) {
start = start.next;
}
return (count & 1) != 0 ? start.data : 0.5 * (start.data + start.next.data);
}
Implement list pivoting
ListPivoting.javaSplit original list and maintain multiple lists, and concat them at last. Use dummy head node for each list.
public static NodeT<Integer> listPivoting(NodeT<Integer> L, int x) {
NodeT<Integer> now = L;
NodeT<Integer> lessHead = new NodeT<>(0, null);
NodeT<Integer> equalHead = new NodeT<>(0, null);
NodeT<Integer> largerHead = new NodeT<>(0, null);
NodeT<Integer> lessTail = lessHead;
NodeT<Integer> equalTail = equalHead;
NodeT<Integer> largerTail = largerHead;
while (now != null) {
if (now.data < x) {
lessTail.next = now;
lessTail = now;
} else if (now.data == x) {
equalTail.next = now;
equalTail = now;
} else { // now->data > x.
largerTail.next = now;
largerTail = now;
}
now = now.next;
}
lessTail.next = equalTail.next = largerTail.next = null;
if (largerHead.next != null) {
equalTail.next = largerHead.next;
}
if (equalHead.next != null) {
lessTail.next = equalHead.next;
}
return lessHead.next;
}
Sort a list
InsertionSortList.javaUses insertion sort on linked list.
public static NodeT<Integer> insertionSort(final NodeT<Integer> L) {
if (L == null) {
return L;
}
NodeT<Integer> dummyHead = new NodeT<>(0, L);
NodeT<Integer> now = L;
while (now != null && now.next != null) {
if (now.data > now.next.data) {
NodeT<Integer> target = now.next;
NodeT<Integer> pre = dummyHead;
while (pre.next.data < target.data) {
pre = pre.next;
}
NodeT<Integer> temp = pre.next;
pre.next = target;
now.next = target.next;
target.next = temp;
} else {
now = now.next;
}
}
return dummyHead.next;
}
Add list-based integers
add-two-number-list.cc AddTwoNumberList.java
public static NodeT<Integer> addTwoNumbers(NodeT<Integer> L1,
NodeT<Integer> L2) {
NodeT<Integer> dummyHead = new NodeT<>(0, null);
NodeT<Integer> digit = dummyHead;
int sum = 0;
while (L1 != null || L2 != null) {
if (L1 != null) {
sum += L1.data;
L1 = L1.next;
}
if (L2 != null) {
sum += L2.data;
L2 = L2.next;
}
digit.next = new NodeT<>(sum % 10, null);
sum /= 10;
digit = digit.next;
}
if (sum > 0) {
digit.next = new NodeT<>(sum, null);
}
return dummyHead.next;
}
Stack and Queue
Implement a stack with max API
StackWithMaxTemplate.java StackWithMaxImproved.javapublic static class Stack {
private LinkedList<Integer> s = new LinkedList<>();
private LinkedList<Pair<Integer, Integer>> aux = new LinkedList<>();
public boolean empty() {
return s.isEmpty();
}
public Integer max() {
if (!empty()) {
return aux.peek().getFirst();
}
throw new RuntimeException("empty_stack");
}
public Integer pop() {
if (empty()) {
throw new RuntimeException("empty_stack");
}
Integer ret = s.pop();
if (ret.equals(aux.peek().getFirst())) {
aux.peek().setSecond(aux.peek().getSecond() - 1);
if (aux.peek().getSecond().equals(0)) {
aux.pop();
}
}
return ret;
}
public void push(Integer x) {
s.push(x);
if (!aux.isEmpty()) {
if (x.compareTo(aux.peek().getFirst()) == 0) {
aux.peek().setSecond(aux.peek().getSecond() + 1);
} else if (x.compareTo(aux.peek().getFirst()) > 0) {
aux.push(new Pair<>(x, 1));
}
} else {
aux.push(new Pair<>(x, 1));
}
}
}
public static class Stack<T extends Comparable<T>> {
private LinkedList<Pair<T, T>> s = new LinkedList<Pair<T, T>>();
public boolean empty() {
return s.isEmpty();
}
public T max() {
if (!empty()) {
return s.peek().getSecond();
}
throw new RuntimeException("empty stack");
}
public T pop() {
if (empty()) {
throw new RuntimeException("empty stack");
}
return s.pop().getFirst();
}
public void push(T x) {
s.push(new Pair<T, T>(x, Collections.max(Arrays.asList(x, empty() ? x : s
.peek().getSecond()))));
}
}
Evaluate RPN expressions RPN.java public static int eval(String s) {
LinkedList<Integer> evalStack = new LinkedList<>();
String[] symbols = s.split(",");
for (String symbol : symbols) {
if (symbol.length() == 1 && "+-*/".contains(symbol)) {
int y = evalStack.pop();
int x = evalStack.pop();
switch (symbol.charAt(0)) {
case '+':
evalStack.push(x + y);
break;
case '-':
evalStack.push(x - y);
break;
case '*':
evalStack.push(x * y);
break;
case '/':
evalStack.push(x / y);
break;
default:
throw new IllegalArgumentException("Malformed RPN at :" + symbol);
}
} else { // symbol is a number.
evalStack.push(Integer.parseInt(symbol));
}
}
return evalStack.pop();
}
Test if parens, brackets, and braces are matched
valid-parentheses.cc ValidParentheses.javapublic static boolean isValidParentheses(String s) {
LinkedList<Character> leftParens = new LinkedList<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
leftParens.push(s.charAt(i));
} else {
if (leftParens.isEmpty()) {
return false; // No left paren.
}
if ((s.charAt(i) == ')' && leftParens.peek() != '(')
|| (s.charAt(i) == '}' && leftParens.peek() != '{')
|| (s.charAt(i) == ']' && leftParens.peek() != '[')) {
return false; // Unmatched left paren.
}
leftParens.pop();
}
}
return leftParens.isEmpty();
}
Normalize pathnames NormalizedPathnames.java
public static String normalizedPathNames(String path) {LinkedList<String> s = new LinkedList<>(); // Use LinkedList as a stack.
// Special case: starts with "/", which is an absolute path.
if (path.startsWith("/")) {
s.push("/");
}
for (String token : path.split("/")) {
if (token.equals("..")) {
if (s.isEmpty() || s.peek().equals("..")) {
s.push(token);
} else {
if (s.peek().equals("/")) {
throw new RuntimeException("Path error");
}
s.pop();
}
} else if (!token.equals(".") && !token.isEmpty()) { // Name.
for (char c : token.toCharArray()) {
if (c != '.' && !Character.isDigit(c) && !Character.isLetter(c)) {
throw new RuntimeException("Invalid directory name");
}
}
s.push(token);
}
}
StringBuilder normalizedPath = new StringBuilder();
if (!s.isEmpty()) {
Iterator<String> it = s.descendingIterator();
String prev = it.next();
normalizedPath.append(prev);
while (it.hasNext()) {
if (!prev.equals("/")) {
normalizedPath.append("/");
}
prev = it.next();
normalizedPath.append(prev);
}
}
return normalizedPath.toString();
}
Print the keys in a BST BSTSortedOrderTemplate.java
public static <T> void printBSTInSortedOrder(BinarySearchTree<T> n) {LinkedList<BinarySearchTree<T>> s = new LinkedList<BinarySearchTree<T>>();
BinarySearchTree<T> curr = n;
while (!s.isEmpty() || curr != null) {
if (curr != null) {
s.push(curr);
curr = curr.getLeft();
} else {
curr = s.pop();
System.out.println(curr.getData());
curr = curr.getRight();
}
}
}
Search a postings list SearchPostingsListRecursive.java Iterative.java
public static void searchPostingsList(PostingListNode L) {searchPostingsListHelper(L, 0);
}
private static int searchPostingsListHelper(PostingListNode L, int order) {
if (L != null && L.getOrder() == -1) {
L.setOrder(order++);
order = searchPostingsListHelper(L.getJump(), order);
order = searchPostingsListHelper(L.getNext(), order);
}
return order;
}
public static void searchPostingsList(PostingListNode L) {
LinkedList<PostingListNode> s = new LinkedList<>();
int order = 0;
s.push(L);
while (!s.isEmpty()) {
PostingListNode curr = s.pop();
if (curr != null && curr.getOrder() == -1) {
curr.setOrder(order++);
s.push(curr.getNext());
s.push(curr.getJump());
}
}
}
Compute buildings with a sunset view ViewSunset.java
public static LinkedList<Pair<Integer, Integer>>
examineBuildingsWithSunset(InputStream sin) {
int idx = 0; // Building's index.
Integer height;
// Stores (building_idx, building_height) pair with sunset views.
LinkedList<Pair<Integer, Integer>> buildingsWithSunset = new LinkedList<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
while (true) {
height = (Integer) osin.readObject();
while (!buildingsWithSunset.isEmpty()
&& (height.
compareTo(buildingsWithSunset.getLast().getSecond()) >= 0)) {
buildingsWithSunset.removeLast();
}
buildingsWithSunset.addLast(new Pair<>(idx++, height));
}
} catch (ClassNotFoundException e) {
System.out.println(e.getMessage());
} catch (IOException e) {
// Catching when there no more objects in InputStream
}
return buildingsWithSunset;
}
Sort a stack StackSorting.java
public static void sort(LinkedList<Integer> S) {
if (!S.isEmpty()) {
Integer e = S.pop();
sort(S);
insert(S, e);
}
}
private static void insert(LinkedList<Integer> S, Integer e) {
if (S.isEmpty() || S.peek().compareTo(e) <= 0) {
S.push(e);
} else {
Integer f = S.pop();
insert(S, e);
S.push(f);
}
}
Print a binary tree in order of increasing depth BinaryTreeLevelOrderTemplate.java
public static <T> void printBinaryTreeLevelOrder(BinarySearchTree<T> n) {
// Prevent empty tree
if (n == null) {
return;
}
LinkedList<BinarySearchTree<T>> q = new LinkedList<BinarySearchTree<T>>();
q.push(n);
int count = q.size();
while (!q.isEmpty()) {
BinarySearchTree<T> front = q.pollLast();
System.out.print(front.getData() + " ");
if (front.getLeft() != null) {
q.push(front.getLeft());
}
if (front.getRight() != null) {
q.push(front.getRight());
}
if (--count == 0) {
System.out.println();
count = q.size();
}
}
}
Implement a circular queue CircularQueueTemplate.java
Implement a queue API using two stacks QueueFromStacksTemplate.java
public static class Queue<T> {
private LinkedList<T> a = new LinkedList<T>();
private LinkedList<T> b = new LinkedList<T>();
public void enqueue(T x) {
a.push(x);
}
public T dequeue() {
if (b.isEmpty()) {
while (!a.isEmpty()) {
b.push(a.pop());
}
}
if (!b.isEmpty()) {
return b.pop();
}
throw new RuntimeException("empty queue");
}
}
Test if a binary tree is balanced BalancedBinaryTreeTemplate.java
private static <T> int getHeight(BinaryTree<T> n) {
if (n == null) {
return -1;
}
int lHeight = getHeight(n.getLeft());
if (lHeight == -2) {
return -2; // left subtree is not balanced.
}
int rHeight = getHeight(n.getRight());
if (rHeight == -2) {
return -2; // right subtree is not balanced.
}
if (Math.abs(lHeight - rHeight) > 1) {
return -2; // current node n is not balanced.
}
return Math.max(lHeight, rHeight) + 1;
}
public static <T> boolean isBalancedBinaryTree(BinaryTree<T> n) {
return getHeight(n) != -2;
}
Sum the leaves in a binary tree encoding integers SumRootToLeafBinaryTree.java
public static int sumRootToLeaf(BinaryTree<Integer> root) {
return preOrderTraversal(root, 0);
}
private static int preOrderTraversal(BinaryTree<Integer> root, int num) {
if (root == null) {
return 0;
}
num = (num * 2) + root.getData();
if (root.getLeft() == null && root.getRight() == null) { // Leaf.
return num;
}
// Non-leaf.
return preOrderTraversal(root.getLeft(), num)
+ preOrderTraversal(root.getRight(), num);
}
Find a root to leaf path with specified sum PathSumBinaryTree.java
public static boolean hasPathSum(BinaryTree<Integer> root, int sum) {
return hasPathSumHelper(root, 0, sum);
}
private static boolean hasPathSumHelper(BinaryTree<Integer> root,
int pathsum, int sum) {
if (root != null) {
pathsum += root.getData();
if (root.getLeft() == null && root.getRight() == null) { // Leaf.
return pathsum == sum;
}
// Non-leaf.
return hasPathSumHelper(root.getLeft(), pathsum, sum)
|| hasPathSumHelper(root.getRight(), pathsum, sum);
}
return false;
}
Compute the k-th node in an inorder traversal KThNodeBinaryTree.java
public static class BinaryTreeNode<T> {public T data;
public BinaryTreeNode<T> left, right;
public int size;
}
// @include
public static BinaryTreeNode<Integer> findKthNodeBinaryTree(
BinaryTreeNode<Integer> root, int k) {
BinaryTreeNode<Integer> n = root;
while (n != null) {
int leftSize = n.left != null ? n.left.size : 0;
if (leftSize < k - 1) {
k -= (leftSize + 1);
n = n.right;
} else if (leftSize == k - 1) {
return n;
} else { // leftSize > k - 1.
n = n.left;
}
}
throw new RuntimeException("no k-th node in binary tree");
}
Compute the successor Successor.java
public static BinaryTree<Integer> findSuccessor(BinaryTree<Integer> node) {BinaryTree<Integer> n = node;
if (n.getRight() != null) {
// Find the leftmost element in n's right subtree.
n = n.getRight();
while (n.getLeft() != null) {
n = n.getLeft();
}
return n;
}
// Find the first parent whose left child contains n.
while (n.getParent() != null && n.getParent().getRight() == n) {
n = n.getParent();
}
// Return nullptr means n does not have successor.
return n.getParent();
}
Form a linked list from the leaves of a binary treeConnectLeavesBinaryTreeTemplate.java
private static <T> void connectLeavesHelper(BinaryTree<T> n,
ArrayList<BinaryTree<T>> L) {
if (n != null) {
if (n.getLeft() == null && n.getRight() == null) {
L.add(n);
} else {
connectLeavesHelper(n.getLeft(), L);
connectLeavesHelper(n.getRight(), L);
}
}
}
public static <T> ArrayList<BinaryTree<T>> connectLeaves(BinaryTree<T> n) {
ArrayList<BinaryTree<T>> L = new ArrayList<BinaryTree<T>>();
connectLeavesHelper(n, L);
return L;
}
ArrayList<BinaryTree<T>> L) {
if (n != null) {
if (n.getLeft() == null && n.getRight() == null) {
L.add(n);
} else {
connectLeavesHelper(n.getLeft(), L);
connectLeavesHelper(n.getRight(), L);
}
}
}
public static <T> ArrayList<BinaryTree<T>> connectLeaves(BinaryTree<T> n) {
ArrayList<BinaryTree<T>> L = new ArrayList<BinaryTree<T>>();
connectLeavesHelper(n, L);
return L;
}
Sort an almost-sorted array ApproximateSort.java
public static void approximateSort(InputStream sin, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Firstly pushes k elements into minHeap.
for (int i = 0; i < k; ++i) {
minHeap.add((Integer) osin.readObject());
}
// Extracts the minimum one for every incoming element.
while (true) {
minHeap.add((Integer) osin.readObject());
System.out.println(minHeap.remove());
}
} catch (IOException e) {
// Do nothing, was read last element in stream
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Extracts the remaining elements in minHeap.
while (!minHeap.isEmpty()) {
System.out.println(minHeap.remove());
}
}
Compute the k closest stars ClosestStars.java
// Use maxHeap to find the closest k stars.
PriorityQueue<Star> maxHeap = new PriorityQueue<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
// Record the first k stars.
while (true) {
Star s = (Star) osin.readObject();
if (maxHeap.size() == k) {
// Compare the top of heap with the incoming star.
Star farStar = maxHeap.peek();
// compareTo() method compares the Euclidean distances
// of s and farStar to the origin (Earth).
if (s.compareTo(farStar) < 0) {
maxHeap.remove();
maxHeap.add(s);
}
} else {
maxHeap.add(s);
}
}
} catch (IOException e) {
// Do nothing, was read last element in stream.
} catch (ClassNotFoundException e) {
System.out.println("ClassNotFoundException: " + e.getMessage());
}
// Store the closest k stars.
List<Star> closestStars = new ArrayList<>();
while (!maxHeap.isEmpty()) {
closestStars.add(maxHeap.remove());
}
return closestStars;
}
Find k elements closest to the median ClosestToMedian.java
private static void nthElement(List<Integer> A, int n, Comparator<Integer> c) {Collections.sort(A, c);
}
private static void nthElement(List<Integer> A, int n) {
nthElement(A, n, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
}
// @include
public static List<Integer> findKClosestToMedian(List<Integer> a, int k) {
// Find the element i where |a[i] - median| is k-th smallest.
final double m = findMedian(a);
nthElement(a, k - 1, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return Double.valueOf(Math.abs(a - m)).compareTo(Math.abs(b - m));
}
});
return new ArrayList<>(a.subList(0, k));
}
private static class Data {
public int larger;
public int equal;
}
Test if x is bigger than the k-th largest element CompareKthLargestInHeap.java
// -1 means smaller, 0 means equal, and 1 means larger.public static int compareKthLargestHeap(List<Integer> maxHeap, int k, int x) {
Data data = new Data();
data.larger = 0;
data.equal = 0;
compareKthLargestHeapHelper(maxHeap, k, x, 0, data);
return data.larger >= k ? 1 : (data.larger + data.equal >= k ? 0 : -1);
}
private static void compareKthLargestHeapHelper(List<Integer> maxHeap, int k,
int x, int idx, Data data) {
if (data.larger >= k || idx >= maxHeap.size() || maxHeap.get(idx) < x) {
return;
} else if (maxHeap.get(idx) == x) {
if (++data.equal >= k) {
return;
}
} else { // max_heap[idx] > x.
++data.larger;
}
compareKthLargestHeapHelper(maxHeap, k, x, (idx * 2) + 1, data);
compareKthLargestHeapHelper(maxHeap, k, x, (idx * 2) + 2, data);
}
Find the min and max simultaneously FindingMinMax.java
public static Pair<Integer, Integer> findMinMax(ArrayList<Integer> A) {
if (A.size() <= 1) {
return new Pair<>(A.get(0), A.get(0));
}
// Initializes the min and max pair.
Pair<Integer, Integer> minMaxPair = Pair.minmax(A.get(0), A.get(1));
for (int i = 2; i + 1 < A.size(); i += 2) {
Pair<Integer, Integer> localPair = Pair.minmax(A.get(i), A.get(i + 1));
minMaxPair = new Pair<>(
Math.min(minMaxPair.getFirst(), localPair.getFirst()),
Math.max(minMaxPair.getSecond(), localPair.getSecond()));
}
// Special case: If there is odd number of elements in the array, we still
// need to compare the last element with the existing answer.
if ((A.size() & 1) != 0) {
minMaxPair = new Pair<>(
Math.min(minMaxPair.getFirst(), A.get(A.size() - 1)),
Math.max(minMaxPair.getSecond(), A.get(A.size() - 1)));
}
return minMaxPair;
}
Find the missing IP address MissingElement.java
public static int findMissingElement(InputStream ifs) throws IOException {int[] counter = new int[1 << 16];
ifs.mark(Integer.MAX_VALUE);
Scanner s = new Scanner(ifs);
while (s.hasNextInt()) {
++counter[s.nextInt() >> 16];
}
for (int i = 0; i < counter.length; ++i) {
// Finds one bucket contains less than (1 << 16) elements.
if (counter[i] < (1 << 16)) {
BitSet bitVec = new BitSet(1 << 16);
ifs.reset();
s = new Scanner(ifs);
while (s.hasNext()) {
int x = s.nextInt();
if (i == (x >> 16)) {
bitVec.set(((1 << 16) - 1) & x); // Gets the lower 16 bits of x.
}
}
ifs.close();
for (int j = 0; j < (1 << 16); ++j) {
if (!bitVec.get(j)) {
return (i << 16) | j;
}
}
}
}
throw new RuntimeException("no missing element");
}
Find the duplicate and missing elements
FindMissingAndDuplicate.javapublic static Pair<Integer, Integer> findDuplicateMissing(List<Integer> A) {
int sum = 0, squareSum = 0;
for (int i = 0; i < A.size(); ++i) {
sum += i - A.get(i);
squareSum += i * i - A.get(i) * A.get(i);
}
return new Pair<>((squareSum / sum - sum) / 2, (squareSum / sum + sum) / 2);
}
FindMissingAndDuplicateXOR.java
public static Pair<Integer, Integer> findDuplicateMissing(List<Integer> A) {
int missXORDup = 0;
for (int i = 0; i < A.size(); ++i) {
missXORDup ^= i ^ A.get(i);
}
// We need to find a bit that's set to 1 in missXORDup. This assignment
// sets all of bits in differBit to 0 except for the least significant
// bit in missXORDup that's 1.
int differBit = missXORDup & (~(missXORDup - 1));
int missOrDup = 0;
for (int i = 0; i < A.size(); ++i) {
if ((i & differBit) != 0) {
missOrDup ^= i;
}
if ((A.get(i) & differBit) != 0) {
missOrDup ^= A.get(i);
}
}
for (int ai : A) {
if (ai == missOrDup) { // Find duplicate.
return new Pair<>(missOrDup, missOrDup ^ missXORDup);
}
}
// missOrDup is the missing element.
return new Pair<>(missOrDup ^ missXORDup, missOrDup);
}
Find an element that appears only once
FindElementAppearsOnce.javapublic static int findElementAppearsOnce(List<Integer> A) {
int ones = 0, twos = 0;
int nextOnes, nextTwos;
for (int i : A) {
nextOnes = (~i & ones) | (i & ~ones & ~twos);
nextTwos = (~i & twos) | (i & ones);
ones = nextOnes;
twos = nextTwos;
}
return ones;
}
Test if an anonymous letter is constructible AnonymousLetter.java
public static boolean anonymousLetter(String L, String M) {Map<Character, Integer> hash = new HashMap<>();
// Inserts all chars in L into a hash table.
for (char c : L.toCharArray()) {
if (!hash.containsKey(c)) {
hash.put(c, 1);
} else {
hash.put(c, hash.get(c) + 1);
}
}
// Checks characters in M that could cover characters in a hash table.
for (char c : M.toCharArray()) {
if (hash.containsKey(c)) {
hash.put(c, hash.get(c) - 1);
if (hash.get(c) == 0) {
hash.remove(c);
if (hash.isEmpty()) {
return true;
}
}
}
}
// No entry in hash means L can be covered by M.
return hash.isEmpty();
}
Implement mergesort in-place MergeTwoSortedArraysInPlace.java
public static void mergeTwoSortedArrays(int A[], int m, int B[], int n) {
int a = m - 1, b = n - 1, tar = m + n - 1;
while (a >= 0 && b >= 0) {
A[tar--] = (A[a] > B[b]) ? A[a--] : B[b--];
}
while (b >= 0) {
A[tar--] = B[b--];
}
}
Pre-Sort
Count the frequencies of characters in a sentence CountOccurrencesInSentence.java
public static void countOccurrences(String s) {
char[] a = s.toCharArray();
Arrays.sort(a);
int count = 1;
for (int i = 1; i < a.length; ++i) {
if (a[i] == a[i - 1]) {
++count;
} else {
System.out.print("(" + a[i - 1] + "," + count + "),");
count = 1;
}
}
System.out.println("(" + a[a.length - 1] + ',' + count + ")");
}
Find unique elements EliminateDuplicate.java
public static void eliminateDuplicate(ArrayList<Integer> a) {
Collections.sort(a); // makes identical elements become neighbors.
// C++ unique-like algorithm on indexes
if (a.size() < 2) {
return;
}
int result = 0;
for (int first = 1; first < a.size(); first++) {
if (!a.get(first).equals(a.get(result))) {
a.set(++result, a.get(first));
}
}
// shrink array size
a.subList(++result, a.size()).clear();
}
Compute an optimum assignment of tasks TaskAssignment.java
public static List<Pair<Integer, Integer>> taskAssignment(
List<Integer> A) {
Collections.sort(A);
List<Pair<Integer, Integer>> P = new ArrayList<>();
for (int i = 0, j = A.size() - 1; i < j; ++i, --j) {
P.add(new Pair<>(A.get(i), A.get(j)));
}
return P;
}
Team photo day---1 TeamPhoto1.java
Implement a fast sorting algorithm for listsSortList.java
public static Node<Integer> sortList(Node<Integer> L) {
// Base case. L has 0 or 1 node.
if (L == null || L.next == null) {
return L;
}
// Finds the middle point of L.
Node<Integer> preSlow = null, slow = L, fast = L;
while (fast != null && fast.next != null) {
preSlow = slow;
fast = fast.next.next;
slow = slow.next;
}
preSlow.next = null; // Splits the list into two lists.
return MergeSortedLists.mergeTwoSortedLinkedLists(sortList(L),
sortList(slow));
}
UnconstructableChange
public static int NonconstructibleChange(List<Integer> A) {
Collections.sort(A);
int sum = 0;
for (int a : A) {
if (a > sum + 1) {
break;
}
sum += a;
}
return sum + 1;
}
