RPN
public static int eval(String s) {
LinkedList<Integer> evalStack = new LinkedList<Integer>();
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 { // number.
evalStack.push(Integer.parseInt(symbol));
}
}
return evalStack.pop();
}
Search Postings List
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) {
searchPostingsListHelper(L, 0);
}
public static void searchPostingsList(PostingListNode L) {
LinkedList<PostingListNode> s = new LinkedList<PostingListNode>();
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());
}
}
}
TowerHanoi - todo: iterative version
private static void transfer(int n, ArrayList<LinkedList<Integer>> pegs,
int from, int to, int use) {
if (n > 0) {
transfer(n - 1, pegs, from, use, to);
pegs.get(to).push(pegs.get(from).pop());
System.out.println("Move from peg " + from + " to peg " + to);
transfer(n - 1, pegs, use, to, from);
}
}
public static void moveTowerHanoi(int n) {
ArrayList<LinkedList<Integer>> pegs = new ArrayList<LinkedList<Integer>>();
for (int i = 0; i < 3; i++) {
pegs.add(new LinkedList<Integer>());
}
// Initialize pegs.
for (int i = n; i >= 1; --i) {
pegs.get(0).push(i);
}
transfer(n, pegs, 0, 1, 2);
}
ViewSunset
Stream from East to West
public static <T extends Comparable<T>> LinkedList<Pair<Integer, T>>
examineBuildingsWithSunset( InputStream sin) {
int idx = 0; // building's index.
T height;
// Stores (building_idx, building_height) pair with sunset views.
LinkedList<Pair<Integer, T>> buildingsWithSunset = new LinkedList<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
while (true) {
height = (T) osin.readObject();
while (!buildingsWithSunset.isEmpty()
&& height.compareTo(buildingsWithSunset.getLast().getSecond()) >= 0) {
buildingsWithSunset.removeLast();
}
buildingsWithSunset.addLast(new Pair<Integer, T>(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
private static <T extends Comparable<T>> void insert(LinkedList<T> S, T e) {
if (S.isEmpty() || S.peek().compareTo(e) <= 0) {
S.push(e);
} else {
T f = S.pop();
insert(S, e);
S.push(f);
}
}
public static <T extends Comparable<T>> void sort(LinkedList<T> S) {
if (!S.isEmpty()) {
T e = S.pop();
sort(S);
insert(S, e);
}
}
Normalized Path names
public static String normalizedPathNames(String path) {
LinkedList<String> s = new LinkedList<String>(); // 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();
}
Binary TreeLevel Order -- Java Queue, better use ArrayQueue
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();
}
}
}
Circular Queue
public static class Queue<T> {
private int head = 0, tail = 0, count = 0;
private Object[] data;
public Queue(int cap) {
data = new Object[cap];
}
public void enqueue(T x) {
// Dynamically resize due to data_.size() limit.
if (count == data.length) {
// Rearrange elements.
Collections.rotate(Arrays.asList(data), -head);
head = 0;
tail = count;
data = Arrays.copyOf(data, count << 1);
}
// Perform enqueue
data[tail] = x;
tail = (tail + 1) % data.length;
++count;
}
public T dequeue() {
if (count != 0) {
--count;
T ret = (T) data[head];
head = (head + 1) % data.length;
return ret;
}
throw new RuntimeException("empty queue");
}
public int size() {
return count;
}
}
Queue Using Two Integers
public static class Queue {
private int val = 0;
private int size = 0, maxSize = (int) Math.floor(Math
.log10(Integer.MAX_VALUE));
public void enqueue(int x) {
if (size >= maxSize) {
throw new RuntimeException("queue overflow");
}
val = val * 10 + x;
++size;
}
public int dequeue() {
if (size != 0) {
int ret = 0, d = (int) Math.floor(Math.log10(val));
if (d + 1 == size) {
int powVal = (int) Math.pow(10, d);
ret = val / powVal;
val -= powVal * ret;
}
--size;
return ret;
}
throw new RuntimeException("empty queue");
}
}
Queue From Stacks
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");
}
}
Queue With Max Using Deque
public static class Queue<T extends Comparable<T>> {
private LinkedList<T> q = new LinkedList<T>();
private LinkedList<T> d = new LinkedList<T>();
public void enqueue(T x) {
q.addFirst(x);
while (!d.isEmpty() && d.getLast().compareTo(x) < 0) {
d.removeLast();
}
d.addLast(x);
}
public T dequeue() {
if (!q.isEmpty()) {
T ret = q.removeLast();
if (ret.equals(d.getFirst())) {
d.removeFirst();
}
return ret;
}
throw new RuntimeException("empty queue");
}
public T max() {
if (!d.isEmpty()) {
return d.getFirst();
}
throw new RuntimeException("empty queue");
}
Maximum of A Sliding Window - O(n)
public static void trafficVolumes(List<TrafficElement> A, int w) {
QueueWithMaxUsingDeque<TrafficElement> Q = new QueueWithMaxUsingDeque<TrafficElement>();
for (int i = 0; i < A.size(); i++) {
Q.enqueue(A.get(i));
while (A.get(i).getTime() - Q.head().getTime() > w) {
Q.dequeue();
}
System.out.println("Max after inserting " + i + " is "
+ Q.max().getVolume());
}
}
public static int eval(String s) {
LinkedList<Integer> evalStack = new LinkedList<Integer>();
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 { // number.
evalStack.push(Integer.parseInt(symbol));
}
}
return evalStack.pop();
}
Search Postings List
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) {
searchPostingsListHelper(L, 0);
}
public static void searchPostingsList(PostingListNode L) {
LinkedList<PostingListNode> s = new LinkedList<PostingListNode>();
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());
}
}
}
TowerHanoi - todo: iterative version
private static void transfer(int n, ArrayList<LinkedList<Integer>> pegs,
int from, int to, int use) {
if (n > 0) {
transfer(n - 1, pegs, from, use, to);
pegs.get(to).push(pegs.get(from).pop());
System.out.println("Move from peg " + from + " to peg " + to);
transfer(n - 1, pegs, use, to, from);
}
}
public static void moveTowerHanoi(int n) {
ArrayList<LinkedList<Integer>> pegs = new ArrayList<LinkedList<Integer>>();
for (int i = 0; i < 3; i++) {
pegs.add(new LinkedList<Integer>());
}
// Initialize pegs.
for (int i = n; i >= 1; --i) {
pegs.get(0).push(i);
}
transfer(n, pegs, 0, 1, 2);
}
ViewSunset
Stream from East to West
public static <T extends Comparable<T>> LinkedList<Pair<Integer, T>>
examineBuildingsWithSunset( InputStream sin) {
int idx = 0; // building's index.
T height;
// Stores (building_idx, building_height) pair with sunset views.
LinkedList<Pair<Integer, T>> buildingsWithSunset = new LinkedList<>();
try {
ObjectInputStream osin = new ObjectInputStream(sin);
while (true) {
height = (T) osin.readObject();
while (!buildingsWithSunset.isEmpty()
&& height.compareTo(buildingsWithSunset.getLast().getSecond()) >= 0) {
buildingsWithSunset.removeLast();
}
buildingsWithSunset.addLast(new Pair<Integer, T>(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
private static <T extends Comparable<T>> void insert(LinkedList<T> S, T e) {
if (S.isEmpty() || S.peek().compareTo(e) <= 0) {
S.push(e);
} else {
T f = S.pop();
insert(S, e);
S.push(f);
}
}
public static <T extends Comparable<T>> void sort(LinkedList<T> S) {
if (!S.isEmpty()) {
T e = S.pop();
sort(S);
insert(S, e);
}
}
Normalized Path names
public static String normalizedPathNames(String path) {
LinkedList<String> s = new LinkedList<String>(); // 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();
}
Binary TreeLevel Order -- Java Queue, better use ArrayQueue
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();
}
}
}
Circular Queue
public static class Queue<T> {
private int head = 0, tail = 0, count = 0;
private Object[] data;
public Queue(int cap) {
data = new Object[cap];
}
public void enqueue(T x) {
// Dynamically resize due to data_.size() limit.
if (count == data.length) {
// Rearrange elements.
Collections.rotate(Arrays.asList(data), -head);
head = 0;
tail = count;
data = Arrays.copyOf(data, count << 1);
}
// Perform enqueue
data[tail] = x;
tail = (tail + 1) % data.length;
++count;
}
public T dequeue() {
if (count != 0) {
--count;
T ret = (T) data[head];
head = (head + 1) % data.length;
return ret;
}
throw new RuntimeException("empty queue");
}
public int size() {
return count;
}
}
Queue Using Two Integers
public static class Queue {
private int val = 0;
private int size = 0, maxSize = (int) Math.floor(Math
.log10(Integer.MAX_VALUE));
public void enqueue(int x) {
if (size >= maxSize) {
throw new RuntimeException("queue overflow");
}
val = val * 10 + x;
++size;
}
public int dequeue() {
if (size != 0) {
int ret = 0, d = (int) Math.floor(Math.log10(val));
if (d + 1 == size) {
int powVal = (int) Math.pow(10, d);
ret = val / powVal;
val -= powVal * ret;
}
--size;
return ret;
}
throw new RuntimeException("empty queue");
}
}
Queue From Stacks
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");
}
}
Queue With Max Using Deque
public static class Queue<T extends Comparable<T>> {
private LinkedList<T> q = new LinkedList<T>();
private LinkedList<T> d = new LinkedList<T>();
public void enqueue(T x) {
q.addFirst(x);
while (!d.isEmpty() && d.getLast().compareTo(x) < 0) {
d.removeLast();
}
d.addLast(x);
}
public T dequeue() {
if (!q.isEmpty()) {
T ret = q.removeLast();
if (ret.equals(d.getFirst())) {
d.removeFirst();
}
return ret;
}
throw new RuntimeException("empty queue");
}
public T max() {
if (!d.isEmpty()) {
return d.getFirst();
}
throw new RuntimeException("empty queue");
}
Maximum of A Sliding Window - O(n)
public static void trafficVolumes(List<TrafficElement> A, int w) {
QueueWithMaxUsingDeque<TrafficElement> Q = new QueueWithMaxUsingDeque<TrafficElement>();
for (int i = 0; i < A.size(); i++) {
Q.enqueue(A.get(i));
while (A.get(i).getTime() - Q.head().getTime() > w) {
Q.dequeue();
}
System.out.println("Max after inserting " + i + " is "
+ Q.max().getVolume());
}
}