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.

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.

I have no idea about this initially…

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;
		}
	}
}

Comments after running:
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();
	}

	public void add(T value) {
		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).
FOLLOW UP
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);
				indices.add(newStack);
			}
		}

		public T pop() {
			MyStack<T> topStack = buffer.peek();
			if (size > 1) {
				return topStack.pop();
			} 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();
		}
	}

Comments after running:

  • 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 top.getData();
		}
		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);
			buffer.add(stack);
		} else {
			MyStack2<T> stack = buffer.get(buffer.size() - 1);
			if (stack.isFull()) {
				MyStack2<T> newStack = new MyStack2<T>(CAPACITY);
				newStack.push(data);
				buffer.add(newStack);
			} 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;
		return top.min();
	}
}

Comments:
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) {
		return tops[stackNum] == SIZE * stackNum;
	}

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

Comments after running:

  • 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;
		}
	}

Comments:

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

Previous Older Entries