Here are a list of questions that I use as a reference cheat sheet.
- Level order traversal
- Inorder traversal
- Post order traversal
- Pre order traversal
- Breadth First Search
- Depth First Search
- Implement Signly Linked-List Stack
- Implement Signly Linked-List Queue
- Implement Doubly Linked-List
- Reverse a Linked-List
- Remove node from a Linked-List
- Insert at in a Linked-List
- Remove duplicates from a Linked-List
- Balance a BST
- Binary Search
- Merge Sort
- Shuffle Array
- Implement Comparator
- Implement Hashmap
- Stacks using queues
- Queues using stacks
- Validate a BST
- Decimals to romans
- Calculator using stacks
- Fibonacci Series
- String palindrome
At each node we print the left -> right
Worst case: O(n) - this happens when we have a one side leaning tree.
public void levelOrderTraversal(Node n) {
if (n == null) return;
Queue<Node> qu = new Queue<>();
qu.enque(n.root);
while (!qu.isEmpty()) {
Node current = qu.deque();
System.out.print.out(current);
if (current.left != null) {
qu.enque(current.left);
}
if (current.right != null) {
qu.enque(current.right);
}
}
}At each node we print the left -> root -> right
Worst case: O(n) - this happens when we have a one side leaning tree.
public void inOderTraversal(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
while (true) {
while (root != null) {
stack.push(root);
root = root.left;
}
if (stack.isEmpty()) break;
root = stack.pop();
System.out.print(root.data);
root = root.right;
}
}At each node we print the left -> right -> root
Worst case: O(n) - this happens when we have a one side leaning tree.
public void postOrderTraversal(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node current = stack.pop();
stack2.push(current);
if (current.left != null) stack.push(current.left);
if (current.right != null) stack.push(current.right);
}
while (!stack2.isEmpty()) {
System.out.println(stack2.pop());
}
}At each node we print the root -> left -> right
Worst case: O(n) - this happens when we have a one side leaning tree.
public void postOrderTraversal(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
while (true) {
while (root != null) {
System.out.print(root);
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) break;
root = stack.pop();
root = root.right;
}
}This algorithm is used to find items in a graph. At each level we search the left and right tree to see if we can find key Unlike trees, graphs can have cycles. We use the Queue data structure when implementing a queue
Worst case: O(E + V)
Best case: O(1)
public boolean bfs(Node start, Node goalNode) {
if (start == goal) return true;
Queue<Node> queue = new LinkedList<>();
ArrayList<Node> explored = new ArrayList<>();
queue.add(start);
explored.add(start);
while (!queue.isEmpty()) {
Node current = queue.deque();
if (current == goalNode) return true;
else if (current.getChildren().isEmpty(), explored) {
return false;
} else {
queue.addAll(current.getChildren(), explored);
}
explored.add(current);
}
return false;
}
public ArrayList<Node> getChildren(Node n, ArrayList<Node> explored) {
ArrayList<Node> result = new ArrayList<>();
Node left = n.left;
Node right = n.right;
if (left != null && !expored.contains(left)) result.add(left);
if (right != null && !expored.contains(right)) result.add(right);
return result;
}Another graph/tree travesal algorithm for finding items. We solve this by using a stack data structure
Worst case: O(n + m) - We get this complexity considering the fact that we are visiting each node only once and in the case of a tree (no cycles) we are crossing all the edges once.
Best case: O(1)
public boolean dfs(Node startNode, Node goalNode) {
if (startNode == goalNode) return true;
Stack<Node> stack = new Stack<>();
ArrayList<Node> visited = new ArrayList<>();
while (!stack.isEmpty()) {
Node current = stack.pop();
if (current == goalNode) {
visited.add(current);
return true;
} else {
visited.add(current);
node.addAll(curret.getChildren());
}
}
return false;
}Singly linked list is a list where the current node contains some data and a pointer to the next node. Travesal is only allowed in one way. This implementation is ideal for anyone who needs to use a stack
Complexity
Instertion at head: O(1)
Remove at head: O(1)
Instertion at specified place: O(n)
Remove at specified place: O(n)
public class LinkedList<T> {
Node first = null;
public void push(T item) {
if (first == null) {
first = new Node(item, null);
} else {
Node oldFirst = first;
Node newFirst = new Node(item, oldFirst);
}
}
public T pop() {
if (first == null) throw new NoSuchElementException("Empty");
T result = first.item;
first = first.next;
return result;
}
}
public class Node<T> {
T item;
Node next;
Node(T item, Node next) {
this.T = T;
this.next = next;
}
}Same as above with a subtle difference in the enque method
public class LinkedList<T> {
Node first = null;
Node last = null;
public void enque(T item) {
Node oldLast = last;
last = new Node(item, null);
first = oldLast;
if (first == null) first = last;
else oldLast.next = last;
}
public T deque() {
if (first == null) throw new NoSuchElementException("Empty");
T result = first.item;
first = first.next;
return result;
}
}
public class Node<T> {
T item;
Node next;
Node(T item, Node next) {
this.T = T;
this.next = next;
}
}A doubly linked list is a type of that allows the insertion of data at the head and tail of the list.
public class DoublyLikedList<T> {
Node head;
Node tail;
public addFirst(T item) {
Node tmp = new Node(item, head, null);
if (head != null) {
head.previous = tmp;
}
head = tmp;
if (tail == null) {
tail = tmp;
}
}
public addLast(T item) {
Node tmp = new Node(item, null, tail);
if (tail != null) {
tail.next = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
}
public T removeFirst() {
if (head == null) throw new NoSuchElementException();
Node oldHead = head;
head = head.next;
head.previous = null;
return oldHead.item;
}
public T removeLast() {
if (tail == null) throw new NoSuchElementException();
Node oldTail = tail;
tail = tail.previous;
tail.next = null;
return oldTail.item;
}
public void iterateForward() {
while (head != null) {
System.out.print(head);
head = head.next();
}
}
public void iterateBackwards() {
while (tail != null) {
System.out.print(head);
tail = head.previous();
}
}
}
public class Node<T> {
Node next;
Node previous;
T item;
Node(T item, Node next, Node previous) {
this.T = T;
this.previous = previous;
this.next = next;
}
}Given A-B-C-D-E-F return F-E-D-C-B-A
Complexity: O(n)
public void reverseList() {
Node current = first;
Node reversedList = null;
while (current != null) {
Node next = current.next;
current.next = reversedList;
reversedList = current;
current = first;
}
first = reversedList;
}Complexity: O(1)
public void deleteNode(Node node) {
node.item = node.next.item;
node.next = node.next.next;
}When we want to insert after a given node. If you are asked to insert after a position, you can just use a while loop and keep a counter
Complexity: O(1)
public void insertAt(Node whereToInsert, Node newNode) {
newNode.next = whereToInsert.next;
whereToInsert.next = newNode;
}The solution provided here is assuming that the list is sorted. If the list is un-sorted, you would need to have a Map and a new LinkedList to make it possible. The map would just contain list of things added to the new list
Complexity: O(n) where n is number of nodes in the given linked list.
public void removeDuplicates(Node root) {
while (root.next != null) {
Node curret = root;
Node next = root.next;
if (current.item == next.item) {
current.next = next.next;
} else {
current = current.next;
}
}
}By definition a balanced tree is type of tree where the heights of the two child subtrees of any node differ by at most one
Insert, Search, delete: O(n log n)
public void insertNode(Node node, int key) {
if (node == null) {
root = new Node(key);
}
if (key < node.key) {
node.left = insertNode(node.left, key);
} else if (key > node.key) {
node.right = insertNode(node.right, key);
}
// Update node height
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get the balance factor
int balanceFactor = getBalanceFactor(node);
// left left
if (balance > 1 && key < node.left.key) rightRotate(node);
// right right
if (balance < -1 && key > node.right.key) leftRotate(node);
// left right
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
rightRotate(node);
}
// right left
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
leftRotate(node);
}
}
private int getBalanceFactor(Node n) {
return n.left.height - n.right.height;
}
private void rightRotate(Node node) {
Node left = node.left;
Node T2 = node.right;
// Perform rotations
right.right = node;
node.left = T2;
node.height = Math.max(node.left.height, node.right.height);
left.height = Math.max(left.left.height, left.right.height);
}
private void leftRotate(Node node) {
Node y = node.right;
Node T2 = y.left;
// Perform rotation
y.left = node;
node.right = T2;
// Update heights
node.height = Math.max(node.left.height, node.right.height) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
}Uses a divide and conquer approach to search a given list
Complexity: O(log n)
public boolean binarySearch(int[] data, int n) {
int lo = 0;
int hi = data.length;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (n < data[mid]) hi = mid - 1
else if (m > data[mid]) lo = mid + 1;
else return true;
}
return false
}Sort left half, followed by sorting of right half and then merge the two sorted list together
Complexity: O(n log n)
TBDWe can shuffle an array using the Fisher Yates & Knuth shuffling algorithm in O(n) time. At each ith iteration we generate a random number from the start of the array to i and then do the swap
Complexity: O(n)
public void shuffle(int[] array) {
for (int i = 0; i < array.length; i++) {
// choose index uniformly in [0, i]
int randomNumber = i + Math.random() * (i + 1);
// perform the swap
int temp = a[i];
a[i] = a[randomNumber];
a[randomNumber] = temp;
}
}The task at hand is to convert a given decimal number n say 20 to its roman numeral equivalence.
See here for chart