nealhu

// 4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. 
// Avoid storing additional nodes in a data structure. 
// NOTE: This is not necessarily a binary search tree.
class Node {
	public int val;
	public Node left;
	public Node right;
	public Node(int val) {
		this.val = val;
		left = null;

nealhu

// Cracking the Coding Interview
// 4.5 Implement a function to check if a binary tree is a binary search tree.

class Node {
	public int val;
	public Node left;
	public Node right;
	Node(int v) {
		val = v;
		left = null;

nealhu

// Cracking the Coding Interview
// Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth 
// (e.g., if you have a tree with depth D,you'll have D linked lists).
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;

class Node {
	public int val;
	public Node left;

nealhu

// Cracking the Coding Interview
// 4.3 Given a sorted (increasing order) array with unique integer elements, 
// write an algorithm to create a binary search tree with minimal height.

class Node {
	public int val;
	public Node left;
	public Node right;
	Node(int v) {
		val = v;

nealhu

// Cracking the Coding Interview
// 4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;

class Node {
	public int val;

nealhu

// Cracking the Coding Interview
// 4.1 Implement a function to check if a binary tree is balanced. 
// For the purposes of this question, a balanced tree is defined to be a tree such that 
// the heights of the two subtrees of any node never differ by more than one.
class Node {
	public Node left;
	public Node right;
	public int val;
	Node(int v) {
		val = v;

nealhu

// Cracking the Coding Interview
// 3.6 Write a program to sort a stack in ascending order (with biggest items on top). 
// You may use at most one additional stack to hold items, 
// but you may not copy the elements into any other data structure (such as an array).
// The stack supports the following operations: push, pop, peek, and isEmpty.

import java.util.Stack;
class StackSort {
	public static void sortStack(Stack<Integer> s) {
		if (s.isEmpty()) return;

nealhu

// Cracking the Coding Interview
// 3.5 Implement a MyQueue class which implements a queue using two stacks.

import java.util.Stack;

class MyQueue<T> {
	// push stack
	private Stack<T> s0;
	// poll stack
	private Stack<T> s1;

nealhu

// Cracking the Coding Interview
// 3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and Ndisks of different sizes which can slide onto any tower.The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints:
// (1) Only one disk can be moved at a time.
// (2) A disk is slid off the top of one tower onto the next tower.
// (3) A disk can only be placed on top of a larger disk.
// Write a program to move the disks from the first tower to the last using stacks.
import java.util.Stack;

class HanoiTowers {
	public static void move(int num, Stack<Integer> ori, Stack<Integer> dest, Stack<Integer> buf) {

nealhu

// Cracking the Coding Interview
// 3.3 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 structureSetOf Stacks that mimics this. 
// SetOf Stacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. 
// SetOfStacks.push() and SetOfStacks.pop() should be have 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.