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.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
// 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 
// 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.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.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.3
// Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
// EXAMPLE
// Input: the node c from the linked list a->b->c->d->e
// Result: nothing isreturned, but the new linked list looks like a- >b- >d->e

class Node {
	public Node next;
	public int val;

nealhu

// Cracking the Coding Interview
// 2.2 Implement an algorithm to find the kth to last element of a singly linked list.

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

nealhu

// CC_2_1
// Write code to remove duplicates from an unsorted linked list.
// FOLLOW UP
// How would you solve this problem if a temporary buffer is not allowed?


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

nealhu

// Cracking the Coding Interview
// 1.7  Write an algorithm such that if an element in an MxN matrix is 0, 
// its entire row and column are set to 0.
import java.util.Arrays;
class MatrixZeros {
	public static void setZeros(int[][] m) {
		if (m.length <= 1 && m[0].length <= 1) return;
		boolean zeroAtFirstRow = false;
		boolean zeroAtFirstColumn = false;
		// check first row