spininertia

package chapter3;

import java.util.Stack;

/*
 * Career Cup 3.6
 * 
 * Write a program to sort a stack in ascending order (with biggest items on top).
 * You may use additional stacks 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.

spininertia

package chapter3;

import java.util.Stack;

/*
 * Career Cup 3.5
 * Implement a MyQueue class which implements a queue using two stacks.
 */
public class C3P5 {

spininertia

package chapter3;
/*
 * Career Cup 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 structure SetOfStacks that mimics this. SetOfStacks 
 * should be composed of several stacks and should create a new stack 

spininertia

package chapter3;

/*
 * Career Cup 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.
 */
public class C3P2 {

spininertia

package chapter3;

/*
 * Career Cup 3.1
 * Describe how you could use a single array to implement three stacks.
 */
public class C3P1 {

  /*
	 * Partition the array averagely to three stacks, use three integers to record the 3 top indexes

spininertia

package chapter2;

import java.util.LinkedList;

/*
 * Career Cup 2.7
 * Implement a function to check if a linked list is a palindrome.
 */
public class C2p7 {
  

spininertia

package chapter2;

public class C2P6 {

  /*
	 * p1: slower pointer which moves 1 step each time, p2: faster pointer which moves 2 steps each time
	 * k: number of steps from the head to the node, n:the number of steps taken when two pointers meets
	 * l: number of steps in the loop
	 * p1 and p2 start at the head, when they first meet, we have 2n - k - (n - k) = l --> n = l
	 * thus, they meet in the position where is l - k steps from the corrupt node(i.e. k steps to the corrupt node)

spininertia

package chapter2;

/*
 * Career Cup 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 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: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295

spininertia

package chapter2;

/*
 * Write code to partition a linked list around a value x, 
 * such that all nodes less than x come before all nodes greater than of equal to x.
 */
public class C2P4 {

  //use two linked list to contain the nodes in two partitions, then concatenate these two
	//time: O(n),  space:O(1)

spininertia

package chapter2;

/*
 * Career Cup 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 is returned, but the new linked list looks like a->b->d->e
 */