Check if a tree is balanced

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one

My initial thoughts:
Do a DFS on the tree. Keep record of minimum level and maximum level. After DFS is done, check if max – min is less than or equal to one.

My initial codes:

	public static boolean isBalanced(TreeNode<Integer> root) {
Pair<Integer> pair = DFSwithLevel(root, 0, Integer.MAX_VALUE,
Integer.MIN_VALUE);
return pair.getY() - pair.getX() <= 1;
}

private static Pair<Integer> DFSwithLevel(TreeNode<Integer> current,
int level, int min, int max) {
if (current.isLeaf()) {
if (level < min)
min = level;
if (level > max)
max = level;
return new Pair<Integer>(min, max);
} else {
for (TreeNode<Integer> child : current.getChildren()) {
Pair<Integer> pair = DFSwithLevel(child, level + 1, min, max);
if (pair.getX() < min)
min = pair.getX();
if (pair.getY() > max)
max = pair.getY();
}
return new Pair<Integer>(min, max);
}
}

Solution:
private static int getMinLevel(TreeNode<Integer> root) {
if (root.isLeaf())
return 0;
else {
int min = Integer.MAX_VALUE;
for (TreeNode<Integer> child : root.getChildren()) {
min = Math.min(1 + getMinLevel(child), min);
}
return min;
}
}

private static int getMaxLevel(TreeNode<Integer> root) {
if (root.isLeaf())
return 0;
else {
int max = Integer.MIN_VALUE;
for (TreeNode<Integer> child : root.getChildren()) {
max = Math.max(1 + getMaxLevel(child), max);
}
return max;
}
}

public static boolean isBalanced2(TreeNode<Integer> root) {
int maxLevel = getMaxLevel(root);
int minLevel = getMinLevel(root);
return maxLevel - minLevel <= 1;
}

Comments: slightly more elegant than mine in that it utilizes the recursive structures of counting tree levels.

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy',

}
}
});
});


Sort a stack without assumptions of implementation

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution
The idea is simple enough: we use another stack as an auxiliary one. Then we pop items from the original stack and push into the auxiliary stack into the correct position. The time complexity is $O(N^{2})$. It’s similar as Insertion Sort.

	public static Stack<Integer> sort(Stack<Integer> stack) {
Stack<Integer> auxiliary = new Stack<Integer>();
while (!stack.isEmpty()) {
Integer value = stack.pop();
while (!auxiliary.isEmpty() && value < auxiliary.peek())
stack.push(auxiliary.pop());
auxiliary.push(value);
}
return auxiliary;
}



Implement queue using two stacks

Implement a MyQueue class which implements a queue using two stacks.

My initial thoughts:
The first stack keep pushing in new items as the enqueue function. When dequeue, stack1 pops element and stack2 push that element in. That will rearrange the order of FILO to FIFO. After the transfering, the first element will be on the top of stack2 so we just pop that out. Then we moving the elements in stack2 back to stack1.

My initial codes:

import java.util.Stack;
public class Q3_5 {

private Stack<Object> stack1 = new Stack<Object>();
private Stack<Object> stack2 = new Stack<Object>();

public void enqueue(Object item) {
stack1.push(item);
}

public Object dequeue() {
if(stack1.empty())
return null;
else {
while(!stack1.empty())
stack2.push(stack1.pop());
Object item = stack2.pop();
while(!stack2.empty())
stack1.push(stack2.pop());
return item;
}
}
}

Not quite efficient for dequeue.
Solution:
public class MyQueue<T> {
Stack<T> s1, s2;

public MyQueue() {
s1 = new Stack<T>();
s2 = new Stack<T>();
}

public int size() {
return s1.size() + s2.size();
}

s1.push(value);
}

public T peek() {
if (!s2.empty()) return s2.peek();
while (!s1.empty()) s2.push(s1.pop());
return s2.peek();
}

public T remove() {
if (!s2.empty()) return s2.pop();
while (!s1.empty()) s2.push(s1.pop());
return s2.pop();
}
}

Comments: lazy implementation for peek() and pop(). Only move elements from stack1 to stack2 when needed.


Solve Towers of Hanoi using stack

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.

My initial thoughts:
Let us denote the three rods, from left to right, as src, transfer and des.

• 1 disk only: move from src to des. done.
• 2 disks(top to bottom: 1->2): move 1 from src to transfer, move 2 from src to des, move 1 from transfer to des.
• 3 disks: ‘magically(recursively)’ move {1,2} from src to transfer, move 3 from src to des, ‘magically(recursively)’ move {1,2} from transfer to des.
• n disks: recursively move the top n-1 disks from src to transfer, move n from src to des, recursively move the n-1 disks from transfer to des.

For $n$ disks, we need $2^{n}-1$ steps at minimum to finish the game.

My codes:(solution)

import java.util.Stack;
public class Q3_4 {

private Stack<Object>[] stacks = new Stack[3];
private Object[] disks;

public Q3_4(Object[] disks) {
stacks[0] = new Stack<Object>();
stacks[1] = new Stack<Object>();
stacks[2] = new Stack<Object>();
this.disks = disks;
for (Object o : disks)
stacks[0].push(o);
}

public void solve() {
solveRecursively(0, 2, 1, disks);
}

public void solveRecursively(int sourceIndex, int desIndex,
int transferIndex, Object[] disks) {
Stack<Object> source = stacks[sourceIndex];
Stack<Object> des = stacks[desIndex];

Object[] sub_disks = null;
if (disks.length > 1) {
sub_disks = new Object[disks.length - 1];
System.arraycopy(disks, 0, sub_disks, 0,
disks.length - 1);
solveRecursively(sourceIndex, transferIndex,
desIndex, sub_disks);
}
Object t = source.pop();
des.push(t);
System.out.println("Move " + t + " from " +
sourceIndex + " to " + desIndex);

if (disks.length > 1)
solveRecursively(transferIndex, desIndex,
sourceIndex, sub_disks);
}
}



Set of stacks with capacity

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

My initial thoughts:
Use stack of stacks. Push to the top sub-stack. Pop from the top sub-stack. If the top sub-stack becomes empty, remove it. Keep a array list of all the sub-stacks.

My initial codes:

	public class MyStackOfStack<T> {

private MyStack<MyStack<T>> buffer = new MyStack<MyStack<T>>();
private static final int THRESHOLD = 10;
private int size = 0;
private List<MyStack<T>> indices = new ArrayList<MyStack<T>>();

public void push(T data) {
if (size < THRESHOLD && size > 1) {
buffer.peek().push(data);
size++;
} else { // size == 0 || size == THRESHOLD
MyStack<T> newStack = new MyStack<T>();
newStack.push(data);
size = 1;
buffer.push(newStack);
}
}

public T pop() {
MyStack<T> topStack = buffer.peek();
if (size > 1) {
} else { // size == 1
T data = topStack.pop();
buffer.pop();
indices.remove(indices.size() - 1);
size = THRESHOLD;
return data;
}
}

public T popAt(int index) {
return indices.get(index).pop();
}
}

popAt(int index) removes the bottom element of the sub-stack.
If one of the middle sub-stack is poped, its above sub=stack is supposed to pad down one element. This behavior is not supported.

Solution:
public class StackNode2<T> {
private T data = null;
private StackNode2<T> below = null;
private StackNode2<T> above = null;
// getters and setters are omitted.
}

public class MyStack2<T> {

private StackNode2<T> top = null;
private final int CAPACITY;
private StackNode2<T> bottom = null;
private int size = 0;

public MyStack2(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
StackNode2<T> item = new StackNode2<T>(data);
if (size == 0) {
top = item;
bottom = top;
size++;
} else if (size < CAPACITY) {
top.setAbove(item);
item.setBelow(top);
top = item;
size++;
}
}

public T pop() {
if (size > 0) {
size--;
StackNode2<T> item = top;
top = item.getBelow();
// top.setAbove(null);
return item.getData();
}
return null;
}

public T peek() {
if (size > 0) {
}
return null;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean isFull() {
return size == CAPACITY;
}

public T getBottom() {
if (size > 0)
return bottom.getData();
else
return null;
}

public T removeFromBottom() {
if (size > 0) {
size--;
StackNode2<T> item = bottom;
bottom = item.getAbove();
bottom.setBelow(null);
return item.getData();
} else {
return null;
}
}
}

public class SetOfStack<T> {

private ArrayList<MyStack2<T>> buffer =
new ArrayList<MyStack2<T>>();
private final int CAPACITY;

public SetOfStack(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
if (buffer.isEmpty()) {
MyStack2<T> stack = new MyStack2<T>(CAPACITY);
stack.push(data);
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
if (stack.isFull()) {
MyStack2<T> newStack = new MyStack2<T>(CAPACITY);
newStack.push(data);
} else {
stack.push(data);
}
}
}

public T pop() {
if (buffer.isEmpty()) {
return null;
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
T data = stack.pop();
if (stack.isEmpty())
buffer.remove(buffer.size() - 1);
return data;
}
}

public T popAt(int index) {
return leftShift(index, true);
}

public T leftShift(int index, boolean removeTop) {
MyStack2<T> stack = buffer.get(index);
T removedItem = null;
if (removeTop)
removedItem = stack.pop();
else
removedItem = stack.removeFromBottom();
if (stack.isEmpty())
buffer.remove(index);
else if (buffer.size() > index + 1) {
stack.push(leftShift(index + 1, false));
}
return removedItem;
}
}



Stack with function min in O(1) time

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

My initial thoughts:
We can keep an record of the current minimum element and dynamically update it when doing the push. However, the update cannot be kept when poping. Therefore I can only implement a O(1) push(), min() but O(n) pop() data structure.

My initial codes:

public class Q3_2 {

private StackNode<Integer> top = null;
private Integer min = Integer.MAX_VALUE;

public void push(Integer item) {
StackNode<Integer> t = new StackNode<Integer>(item);
t.setUnderneath(top);
top = t;

if (item < min)
min = item;
}

public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();

if (data == min) {
min = Integer.MAX_VALUE;
StackNode<Integer> curr = top;
while (curr != null) {
if (curr.getData() < min)
min = curr.getData();
curr = curr.getUnderneath();
}
}

return data;
}

public Integer min() {
return min;
}
}

Solution:
public class StackWithMinNode<T> extends StackNode<T> {

private Integer min = null;
private StackWithMinNode<T> underneath = null;

public StackWithMinNode(T item) {
super(item);
}

public Integer min() {
return min;
}

public void setMin(Integer min) {
this.min = min;
}

@Override
public StackWithMinNode<T> getUnderneath() {
return underneath;
}

public void setUnderneath(StackWithMinNode<T> underneath) {
this.underneath = underneath;
}

}

public class StackWithMin extends MyStack<Integer> {

StackWithMinNode<Integer> top = null;

@Override
public void push(Integer data) {
StackWithMinNode<Integer> item =
new StackWithMinNode<Integer>(data);
if (top != null)
item.setMin(Math.min(data, top.min()));
else
item.setMin(data);
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (top == null)
return null;
}
}

The idea is similar as my initial thought, only that we keep a local minimum for each node.
Another solution is implemented using an auxiliary stack to keep track of the local minimum, therefore potentially saving spaces taken by keep track local min for each single node.
public class StackWithMinStack extends MyStack<Integer> {

MyStack<Integer> minStack = new MyStack<Integer>();

@Override
public void push(Integer data) {
StackNode<Integer> item = new StackNode<Integer>(data);
if (minStack.isEmpty())
minStack.push(data);
else {
if (data.compareTo(minStack.peek()) <= 0)
minStack.push(data);
}
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
if (data.compareTo(minStack.peek()) == 0)
minStack.pop();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (minStack.isEmpty())
return null;
return minStack.peek();
}
}

Comment: Be careful about line 11. We push into the auxiliary stack if we have found element less OR equal to the local min. We have to keep duplicates in order to further deal with the case where one duplicate is poped. Think about this stack from top to bottom (on the right is its auxiliary stack, storing the local min):
5
2
4 2
2 2
7 7
If we only store one 2 in the auxiliary stack, then when 5 and 2 are poped from the original stack, the auxiliary stack will only be left with 7, resulting in a wrong global min.


Implement 3 stacks using a single array

Describe how you could use a single array to implement three stacks.

My initial thoughts:
If size of the array is n, we can allocate [0,n/3) to the first stack, [n/3,2n/3) to the second stack and [2n/3,n) to the third stack. We also need to maintain an array of pointers to the positions of the top for each stack.

My initial codes:

public class Q3_1 {

private final int SIZE = 10;
private Integer[] data = new Integer[SIZE * 3];
private int[] tops = { 0, 0, 0 };

public void push(int stackNum, Integer item) {
data[tops[stackNum] + SIZE * stackNum] = item;
tops[stackNum]++;
}

public Integer pop(int stackNum) {
if (tops[stackNum] == SIZE * stackNum)
return null;
tops[stackNum]--;
Integer element = data[tops[stackNum] + SIZE * stackNum];
data[tops[stackNum] + SIZE * stackNum] = null;
return element;
}

public boolean isEmpty(int stackNum) {
}

@Override
public String toString() {
String result = new String();
for (int i = 0; i < data.length; ++i)
result += data[i] + " ";
return result;
}
}

It works well but if we can also dynamically increase the size, that would be more practically realistic.

Solution:
int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = { -1, -1, -1 };
StackNode[] buffer = new StackNode[stackSize * 3];

void push(int stackNum, int value) {
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = indexUsed;
indexUsed++;
buffer[stackPointer[stackNum]] = new StackNode(lastIndex, value);
}

int pop(int stackNum) {
int value = buffer[stackPointer[stackNum]].value;
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
buffer[lastIndex] = null;
indexUsed--;
return value;
}

int peek(int stack) {
return buffer[stackPointer[stack]].value;
}

boolean isEmpty(int stackNum) {
return stackPointer[stackNum] == -1;
}

class StackNode {
public int previous;
public int value;
public StackNode(int p, int v) {
value = v;
previous = p;
}
}

The solution utilize a linked-list approach which allow each element in the stack to remember its previous node.



Find loop starting point in a circular linked list

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

My initial thoughts:
Initialize with two pointers to the head, the slow pointer and fast pointer. Each time, slow pointer moves one step while the fast pointer moves two steps. If they meet in the some point, then that node must be the starting point of the loop.

My initial codes:

	public static LLNode findLoopBeginningPoint(

fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();

while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();
}

return slowPointer;
}

The testing input yields out ‘E’ instead of the expected result ‘C’. Walk through the code:

fastPointer: ‘C’; slowPointer: ‘A’
fastPointer: ‘E’; slowPointer: ‘B’
fastPointer: ‘D’; slowPointer: ‘C’
fastPointer: ‘C’; slowPointer: ‘D’
fastPointer: ‘E’; slowPointer: ‘E’

The catch point of this algorithm is that when the fast pointer meets the slow pointer, the distance between their meeting point and the starting point of the loop, is equal to the distance between the head of the list and the starting point of the loop.
Let us denote the length of non-loop list as $m$, i.e., the distance between the head of the list to the starting point of the loop is $m$. Let’s also have the size of the loop as $L$. When the two pointer meets, let us denote the distance between the meeting point of the starting of the loop as $d$. So, at the time of their meet, the fast pointer would have travelled $m+nL-d$ and the slow pointer only travelled $m+L-d$. Therefore we have $m+nL-d=2(m+L-d) \Leftrightarrow d\equiv m \pmod L$.
Therefore, when the two pointer meets, we can move one pointer to the head, and then move them one step at each time, when they meet again, they will meet at the starting pointer of the loop.
public static LLNode<Character> findLoopBeginningPoint(

do {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
} while (slowPointer != fastPointer);

if (slowPointer == null)
return null;

while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}

return slowPointer;
}

If the linked list has no loop, the highlighted line will raise an null-pointer exception under some circumstances.
Solution
public static LLNode<Character> FindBeginning(LLNode<Character> head) {

// find meeting point
while (n2.getNext() != null) {
n1 = n1.getNext();
n2 = n2.getNext().getNext();
if (n1 == n2)
break;
}

// Error check - there is no meeting point, and therefore no loop
if (n2.getNext() == null)
return null;

/*
* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps from the
* Loop Start. If they move at the same pace, they must meet at Loop
* Start.
*/
while (n1 != n2) {
n1 = n1.getNext();
n2 = n2.getNext();
}

return n2;
}



You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

My initial thoughts:
Add up numbers nodes by nodes. Take care of carries. In each summation of two digits:
sum digit = (digit1 + digit2 + carry_from_previous) % 10;
carry = (digit1 + digit2 + carry_from_previous) – 10;
There are generally three cases needed to be handled:

• digit1 and digit2 are neigher null
• digit1 is null
• digit2 is null

My initial codes:

	public static LLNode<Integer> addWithCarry(LLNode<Integer> head1,
LLNode<Integer> node = carry ? new LLNode<Integer>(1) : null;
return node;
}
int sum = carry ? (number1 + number2 + 1) % 10
: (number1 + number2) % 10;
boolean carryNext = carry ? number1 + number2 + 1 >= 10
: (number1 + number2) >= 10;
LLNode<Integer> node = new LLNode<Integer>(sum);
carryNext));
else
return node;
}

Solution
LLNode<Integer> l2, int carry) {
if (l1 == null && l2 == null)
return null;
LLNode<Integer> result = new LLNode<Integer>(carry);
int value = carry;
if (l1 != null)
value += l1.getData();
if (l2 != null)
value += l2.getData();
result.setData(value % 10);
LLNode<Integer> more = addList(l1 == null ? null : l1.getNext(),
l2 == null ? null : l2.getNext(), value > 10 ? 1 : 1);
result.setNext(more);
return result;
}

There are two mistakes in this solution. Highlighted line 4. If l1 and l2 are both null, you still need to consider the carry: 1 + 9->1 = 0->0->1 but this solution will output 0->0. Highlighted line 13: should be:
value >= 10 ? 1 : 0



Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

My initial thoughts:
We need to consider two cases: if that node is the head, then we need to update head pointer to the next one. If that node is in the middle, then we need to update the previous pointer.

My initial codes:


public static void deleteANode(LLNode head, LLNode item) {
item.setNext(null);
return;
}
while (current != null) {
if (current == item) {
previous.setNext(current.getNext());
current.setNext(null);
return;
} else {
previous = current;
current = current.getNext();
}
}
return;
}

It works fine with O(n) time complexity and O(1) space complexity.
After reading the solution, I found out that the question explicitly specifies that only the access to that node is given therefore you don’t know the head pointer.

Solution:
public static void deleteNode(LLNode node) {
if (node == null || node.getNext() == null)
return;
LLNode nextNode = node.getNext();
node.setData(nextNode.getData());
node.setNext(nextNode.getNext());
nextNode.setNext(null);
}