jingz8804

import java.util.Random;

public class RandomItem{
    private int[] numbers;
    private double[] probs;
    private Random rand;
    
    public RandomItem(int[] numbers, double[] probs){
        this.numbers = numbers;
        this.probs = probs;

jingz8804

public class SuccessorDelete{
    private int[] id;
    private int[] sz;
    private int[] maximum;
    
    public SuccessorDelete(int N){
        id = new int[N];
        sz = new int[N];
        maximum = new int[N];
        for (int i = 0; i < N; i++){

jingz8804

public class WeightedQuickUnionFind{
    private int[] id;
    private int[] sz;
    private int[] height; // this is for union-by-height
    private int count; // the number of connected components
    private int[] maximum; // keep track of the maximum object in each connected component
    
    public WeightedQuickUnionFind(int N){
      id = new int[N];
      sz = new int[N];

jingz8804

// Given a singly linked list, modify the value of first half nodes such that 
// 1st node’s new value is equal to the last node’s value minus first node’s current value, 
// 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes. 
// (No extra memory to be used)

// public class Node{
// 	int val;
// 	Node next;
// }

jingz8804

package lecture1;

public class App{
    
    public static void main(String[] args){
        Runner1 r1 = new Runner1();
        Runner2 r2 = new Runner2();
        
        r1.start();
        r2.start();

jingz8804

public class BitonicArraySearch{
    private int[] numbers;
    private int len;
    private int turningPointIndex = -1;
    
    public BitonicArraySearch(int[] numbers){
        this.numbers = numbers;
        len = numbers.length;
    }
    

jingz8804

/**
 * This is in fact a question about shuffle sort. First of all, what does shuffle even mean?
 * Well, it means generate a uniformly random permutation of the original array.
 * To do that, there are two ways:
 * 1. Shuffle sort: we generate a random number (uniformly distributed) for each entry in the array. 
 *    We sort the array according to the value of the random number.
 * 
 * 2. Knuth shuffle: In iteration i, pick an integer r between 0 and i uniformly at random. Swap a[i] and a[r]. 
 *    Proof?
 */ 

jingz8804

public Set<Integer> pickDistinctNumbers(int k, int[] numbers){
	if(numbers == null || numbers.length == 0) return null;
	int len = numebrs.length;
	if(k <= 0 || k > len) return null; // ask about these situations. this is just an example

	Set<Integer> result = new HashSet<Integer>(); // Sets.newHashSet() if you use Google Guava
    int size = 0;
    while(size < k){
        int picked = (int) (Math.random() * len);
        if(result.add(numbers[picked])) size++;

jingz8804

public class App{
    
    public static void main(String[] args){
        DaemonThread dt = new DaemonThread();
        
        dt.setDaemon(true); // must be set before thread starting;
        dt.start(); // spawning the thread
        
        try{
            Thread.sleep(3000); // wait for 3 seconds. This actually let the daemon thread to print out some messages.

jingz8804

package lecture2;

public class App{
    
    public static void main(String[] args){
        Processor prc = new Processor();
        
        prc.start();
        
        System.out.println("Press Return to stop");