nealhu

// Cracking the Coding Interview
// 2.4 Write code to partition a linked list around a value x, 
// such that all nodes less than x come before all nodes greater than or equal to x.

class Node {
	public Node next;
	public int val;
	Node(int _v) {
		val = _v;
		next = null;

nealhu

// Cracking the Coding Interview
// 2.5
// 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 Ts 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:(7-> 1 -> 6) + (5 -> 9 -> 2).Thatis,617 + 295.
// Output: 2 -> 1 -> 9.That is, 912.
// FOLLOW UP
// Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
// Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
// Output: 9 -> 1 -> 2.That is, 912.

nealhu

// Cracking the Coding Interview 
// 2.6
// Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
// DEFINITION
// Circular linked list: 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[thesameCasearlier] 
// Output:C

class Node {

nealhu

// Cracking the Coding Interview
// 2.7  Implement a function to check if a linked list is a palindrome.

class Node {
	public Node next;
	public int val;
	Node(int _v) {
		val = _v;
		next = null;
	}

nealhu

// Cracking the Coding Interview
// 3.1  Describe how you could use a single array to implement three stacks.

class ThreeStack {
	public static final int TOTAL_SIZE = 10;
	public static int[] buf = new int[TOTAL_SIZE];
	private static int[] offset = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] start = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] end = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] length = new int[3];

nealhu

// Cracking the Coding Interview
// 3.2 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.
import java.util.Stack;

class MinStack {
	private Stack<Integer> s;
	private Stack<Integer> minValues;

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.

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