michaelniu

package cc150;
/*
 * 3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in,
first out" basis. People must adopt either the "oldest" (based on arrival time) of
all animals at the shelter, or they can select whether they would prefer a dog or
a cat (and will receive the oldest animal of that type). They cannot select which
specificanimal they would like. Create the data structures to maintain this system
and implement operations such as enqueue, dequeueAny, dequeueDog and
dequeueCat.You may use the built-in LinkedList data structure.
Algorithm:

michaelniu

package cc150;
/*
 * 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.

Algorithm:
 set  two stacks  mainStack and  helpStack
  the helpStack  store the  data  that bigger then pushed data;

michaelniu

/*
 * 3.5 Implement a MyQueue class which implements a queue using two stacks
 * Algorithm
 * use one Stack for  Enqueue -----EnQueueStack
 * use another Stack for Dequeue----DeQueueStack.
 * if DeQueueStack is  empty  then  pop  from EnqueueStack and  push to  DequeueStac one by one.
 * O(N) and O(N)
 */
public class MyQueueByTwoStacks {

michaelniu

/*
 * 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 SetOf Stacks that mimics
this. SetOf Stacks should be composed of several stacks and should create a
new stack once the previous one exceeds capacity. SetOf Stacks. push() and
SetOf Stacks. pop() should behave identically to a single stack (that is, popO
should return the same values as it would if there were just a single stack).

FOLLOW UP

michaelniu

/*
 * 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.
* Algorithm:
* use a stack to store the  minum value of the   stack,   
* if push  data  < minstack.top   then push the data to minstack
* if pop() =  minstack.top  then pop  data from minstack
* 

michaelniu

package cc150;
/*
 * 2.7 Implement a function to check if a linked list is a palindrome
 * Algorithm
 * 1, use slow and fast pointers ;
 * 2. slow move one step , fast move two steps
 * 3.fast reach the last node  the first reach the  central node
 * 4. create a new linked list , reverse to save the second half of the list
 * 5. compare two  lists from begin   until second list to end , 
 * 6. if the data doens't match , it is not  palindrome   

michaelniu

package cc150;

import java.util.Hashtable;

/*
 * 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.

michaelniu

package cc150;
/*
 * 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).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP

michaelniu

package cc150;
/*
 *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.
Algorithm
pretty straight forward  
 iterate the  original list  
 if  the data  >=x  
      thenode.next = x.next  and  x.next= thenode
 else

michaelniu

package cc150;
/*
 *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
 Algorithm
 set c.data = c.next.data   and  c.next= c.next .next
 O(1) and O(1)