Session 3 of the CodeU exercises

CollatzGraph.java

import com.google.gson.Gson;
import com.oracle.javafx.jmx.json.JSONWriter;
import jdk.nashorn.api.scripting.JSObject;

import java.io.*;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class CollatzGraph {

    HashMap<Integer, Integer> graph;
    int maxInteger = 1;
    int minInteger = -1;

    public CollatzGraph() {
        graph = new HashMap<Integer, Integer>();
    }

    public HashMap<Integer, Integer> getGraph() {
        return graph;
    }

    public int getNumNodes() {
        return graph.size();
    }

    public int getMaxInteger() {
        return maxInteger;
    }

    public int getMinInteger() {

        int counter = 1;
        while (true) {
            if(graph.containsKey(counter)) {
                counter++;
            } else {
                break;
            }
        }
        minInteger = counter;
        return minInteger;
    }

    int loopCount(int x) {
        if(graph.containsKey(x)) {
            return graph.get(x);
        }
        int b = 0;
        if (x % 2 == 0) {
            b =  1 + loopCount(x >> 1);
        } else {
            b  = 1 + loopCount((3 * x) + 1);
        }

        graph.put(x, b);
        maxInteger = Math.max(x, maxInteger);
        return b;
    }

    void initialize() {
        graph.put(1, 1);
    }

    int maxLoop(int x, int y) {
        // STUDENTS: FILL IN CODE HERE!
        int maxCount = loopCount(x);

        for(int i = x + 1; i <= y; i++) {
            int t = loopCount(i);
            maxCount = Math.max(maxCount, t);
        }

        return maxCount;
    }

    public void save(String fileName) throws IOException {
        PrintWriter pw = new PrintWriter(new FileOutputStream(new File(fileName)));
        Gson gson = new Gson();
        String s = gson.toJson(this);
        pw.write(s);
        pw.flush();
        pw.close();
    }

    public static CollatzGraph load(String fileName) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(new File(fileName))));
        Gson gson = new Gson();
        return gson.fromJson(reader, CollatzGraph.class);
    }

    public static void testCollatz(CollatzGraph graph, int n) {
        long starTime, endTime;
        starTime = System.nanoTime();
        int result = graph.maxLoop(1, n);
        endTime = System.nanoTime();
        System.out.println("Collatz with " + n + " elements: " + (endTime - starTime) + " nsec with result " + result);
    }

    public static void printMap(Map mp) {
        Iterator it = mp.entrySet().iterator();

        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            System.out.println(pair.getKey() + " = " + pair.getValue());
        }
    }

    public static void main(String[] args) {
        CollatzGraph graph = new CollatzGraph();
        graph.initialize();
        System.out.println("Starting tests...");

        testCollatz(graph, 100000);
        testCollatz(graph, 100000);
        testCollatz(graph, 100000);
        testCollatz(graph, 100000);

        System.out.println("the graph contain " + graph.getNumNodes() + " nodes");
        System.out.println("The maximum integer is: " + graph.getMaxInteger());
        System.out.println("The minimum integer that is not in the graph is: " + graph.getMinInteger());
//        printMap(graph.getGraph());

        try {
            graph.save("savedFile.json");
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        try {
            CollatzGraph graph2 = CollatzGraph.load("savedFile.json");
            System.out.println("The maximum integer is: " + graph2.getMaxInteger());
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

Dictionary.iava

import java.util.HashSet;

// How does the class TrivialDictionary looks like?
// How are the words stored inside TrivialDictionary?
// Are those words in memory or in a Database?

// 05:24 mins
public class Dictionary {

    HashSet<String> previousWords;

    public boolean isInDictionary(String word) {

        if(previousWords.contains(word)) {
            return true;
        }
        // Assume the words are stored in a List<String>
        int index = TrivialDictionary.getWords().indexOf(word);
        return TrivialDictionary.wordAt(index) != null;
    }
}

Majority.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

// I decided to not sort this because that would require the
// Solution to be O(nlog(n))
// By using a HashMap makes the solution O(n)
// 07:12 mins
public class Majority {

    // Can be an array, LinkedList, etc.. don't matter really
    public Integer hasMajority(ArrayList<Integer> numbers) {

        // Number, Count
        HashMap<Integer, Integer> countNumbers = new HashMap<Integer, Integer>();
        for(Integer i : numbers) {
            if(countNumbers.containsKey(i)) {
                countNumbers.put(i, countNumbers.get(i) + 1);
            } else {
                countNumbers.put(i, 1);
            }
        }

        for(Map.Entry<Integer, Integer> entry : countNumbers.entrySet()) {

            // Checks if the value is bigger than 50%
            // >> 1 is the same as /2
            if(entry.getValue() > numbers.size() >> 1) {
                return entry.getKey();
            }
        }
        return null;
    }
}

MyClass.java

import java.util.Arrays;

// 9:11 Mins
// Wanted to do it without a sort but I couldn't figure it out
public class MyClass {

    int[] numbers;

    public MyClass(int[] numbers) {
        this.numbers = numbers;
        Arrays.sort(numbers);
    }

    public int nthLargest(int n) {
        if(n == 0) {
            throw new RuntimeException("n cannot be 0.");
        }

        if(n > numbers.length) {
            throw new RuntimeException("n cannot be bigger than the input size.");
        }
        return numbers[n-1];
    }
}

Query.java

/**
 * Created by marcus on 5/1/15.
 */
public class Query {

    long timeStamp;
    String values;

    public Query(long timeStamp, String values) {
        this.timeStamp = timeStamp;
        this.values = values;
    }

    public long getTimeStamp() {
        return timeStamp;
    }

    public void setTimeStamp(long timeStamp) {
        this.timeStamp = timeStamp;
    }

    public String getValues() {
        return values;
    }

    public void setValues(String values) {
        this.values = values;
    }
}

QueryStream.java

import java.util.*;

/**
 * Created by marcus on 5/1/15.
 */
public class QueryStream {

    LinkedList<Query> stream;
    Query currentQuery;
    LinkedList<String> currentQueryList;
    ListIterator<Query> streamIterator;
    ListIterator<String> queryIterator;
    long previousQuery;

    public QueryStream(List<Query> stream) {
        this.stream = new LinkedList<Query>(stream);
        streamIterator = stream.listIterator();
        setNextQuery();
        previousQuery = currentQuery.getTimeStamp();
    }

    public void setNextQuery() {
        currentQuery = streamIterator.next();
        currentQueryList = new LinkedList<String>(Arrays.asList(currentQuery.getValues().split(" ")));
        queryIterator = currentQueryList.listIterator();
    }

    public String next() {
        if(queryIterator.hasNext()) {
            return queryIterator.next();
        }
        setNextQuery();
        String s = String.valueOf(currentQuery.getTimeStamp() - previousQuery);
        previousQuery = currentQuery.getTimeStamp();
        return s;
    }

    public boolean hasNext() {
        return queryIterator.hasNext() || streamIterator.hasNext();
    }

    public static void main(String[] args) {

        Query q1 = new Query(System.nanoTime(), "hello world this is a query");
        Query q2 = new Query(System.nanoTime(), "second query string");
        Query q3 = new Query(System.nanoTime(), "another query");

        List<Query> qs = new ArrayList<Query>(Arrays.asList(q1, q2, q3));
        QueryStream stream = new QueryStream(qs);

        while(stream.hasNext()) {
            System.out.println(stream.next());
        }
    }
}