Skip to content

Instantly share code, notes, and snippets.

View chouclee's full-sized avatar

Zhoucheng Li chouclee

14 followers · 13 following
View GitHub Profile
@chouclee
chouclee / LinkedList.java
Created June 18, 2014 16:31
[CC150][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?
import java.util.Random;
//* without temporary buffer
//* time O(N^2)
public class LinkedList<Item> {
private class Node {
Item item;
Node next;
@chouclee
chouclee / nthToLast.java
Created June 19, 2014 06:15
[CC150][2.2] Implement an algorithm to find the nth to last element of a singly linked list
import java.util.LinkedList;
public class nthToLast {
public static<Item> Item find(LinkedList<Item> list, int n) {
int N = list.size();
if ( n < 1 || n > N) return null;
int idx = N - n;
return list.get(idx);
}
@chouclee
chouclee / LinkedList.java
Last active August 29, 2015 14:02
[CC150][2.3] Implement an algorithm to delete a node in the middle of a single 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
public class LinkedList<Item> {
private Node<Item> first;
private Node<Item> last;
private int N;
public LinkedList() {
this.N = 0;
}
public void add(Node<Item> node) {
@chouclee
chouclee / add.java
Last active August 29, 2015 14:02
[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 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: (3 -> 1 -> 5) + (5 -> 9 -> 2) Output: 8 -> 0 -> 8
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;
public class add {
public static LinkedList<Integer> addList(LinkedList<Integer> a,
LinkedList<Integer> b) {
LinkedList<Integer> result = new LinkedList<Integer>();
ListIterator<Integer> iterA = a.listIterator();
ListIterator<Integer> iterB = b.listIterator();
@chouclee
chouclee / CircularList.java
Created June 19, 2014 14:08
[CC150][2.6] Given a circular linked list, implement an algorithm which returns 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 [the same C as earlier] output: C
import java.util.Random;
import java.util.HashSet;
public class CircularList<Item> {
private Node first;
private Node last;
private class Node {
private Item item;
private Node next;
@chouclee
chouclee / TripleStack.java
Created June 20, 2014 04:32
[CC150][3.1] Describe how you could use a single array to implement three stacks
//* http://algs4.cs.princeton.edu/13stacks/
//* [statck1 element, statck2 element, statck3 element, statck1 element,statck2 element,...,statck3 element]
//* double the array size when one stack is full
//* shrink the array size to half when all three stacks are one-quarter size full
//* time complexity: average O(1) for push() and pop()
import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class TripleStack<Item> {
@chouclee
chouclee / minStack.java
Created June 20, 2014 05:50
[CC150][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;
import java.util.Random;
public class minStack<T extends Comparable<? super T>> {
Stack<T> data;
Stack<T> min;
T minimum;
int N;
public minStack() {
@chouclee
chouclee / partition.java
Created June 23, 2014 06:44
[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.
import java.util.LinkedList;
public class partition {
public static<T extends Comparable<? super T>> LinkedList<T> parti(LinkedList<T> list, T pivot) {
LinkedList<T> lessThan = new LinkedList<T>();
LinkedList<T> equal = new LinkedList<T>();
LinkedList<T> largerThan = new LinkedList<T>();
int cmp;
for (T element : list) {
cmp = element.compareTo(pivot);
@chouclee
chouclee / solution.java
Created June 23, 2014 09:05
[CC150][2.7] Implement a function to check if a linked list is a palindrome.
import java.util.LinkedList; //LinkedList in Java is double-linked list
import java.util.ListIterator;
import java.util.Stack;
public class solution {
public static<T> boolean isPalindrome(LinkedList<T> list) {
if (list == null) throw new IllegalArgumentException();
Stack<T> reverse = new Stack<T>();
int N = 0;
for (T element : list) {
@chouclee
chouclee / SetOfStacks.java
Created June 23, 2014 09:35
[CC150][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 once the pre…
import java.util.Stack;
import java.util.ArrayList;
public class SetOfStacks<T> {
private ArrayList<myStack> stacks;
private int threshold;
private int currIdx;
private class myStack {
Stack<T> stack;