ads

WEEK-4///////////////////////////////////////////////////////////////////////////////////////////////////////
class ArrayStack {
  private Object[] elements;
  private int size;
  private int capacity;

  /**
   * Creates an empty ArrayStack with capacity 1.
   */
  public ArrayStack() {
    elements  = new Object[1];
    size = 0;
    capacity = 1;
  }

  /**
   * @return The size of this ArrayStack.
   */
  public int size() {
    return size;
  }

  /**
   * @return `true` iff this ArrayStack is empty, `false` otherwise.
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * @return `true` iff the size is equal to the capacity, `false` otherwise.
   */
  public boolean isFull() {
    return size == capacity;
  }

  /**
   * @return the top element of the stack without removing it
   */
  public Object peek() throws EmptyStackException {
    if(size == 0){
      throw new EmptyStackException();
    }
    else{
      return elements[size-1];
    }
  }

  /**
   * Adds `o` to the stack.
   * If capacity of stack was too small, capacity is doubled and `o` is added.
   *
   * @param o
   *     the element to add to the stack.
   */
  public void push(Object o) {
    if(size == capacity){
      Object[] newArr = new Object[capacity*2];
      for(int i=0; i<capacity; i++)
        newArr[i] = elements[i];
      elements = newArr;
      capacity *= 2;
    }

    elements[size++] = o;
  }

  /**
   * Removes the top element from the stack.
   * If removing top would make the stack use less than 25% of its capacity,
   * then the capacity is halved.
   *
   * @return the element which was at the top of the stack.
   * @throws EmptyStackException
   *     iff the queue is empty
   */
  public Object pop() throws EmptyStackException {
    if(size == 0){
      throw new EmptyStackException();
    }

    Object obj = elements[--size];

    if((size < capacity/4) && (capacity/2 >= 1)){
      Object[] eleArr = new Object[capacity/2];
      for(int i = 0; i<size; i++)
        eleArr[i] = elements[i];
      elements = eleArr;
      capacity /= 2;
    }

    return obj;
  }

  /**
   * @return a String representation of the ArrayStack
   * Example output for ArrayStack with 2 elements and capacity 5:
   * <ArrayStack[1,2]>(Size=2, Cap=5)
   */
  public String toString() {
    String str;
    if(size == 0){
      str = String.format("<ArrayStack[]>(Size=%d, Cap=%d)", size, capacity);
    }
    else{
      str = String.format("<ArrayStack[%s", elements[0].toString());
      for(int i=1; i<size; i++){
        str += String.format(",%s", elements[i].toString());
      }
      str += String.format("]>(Size=%d, Cap=%d)", size, capacity);
    }
    return str;
    }

  // For testing, do not remove or change.
  public Object[] getElements() {
    return elements;
  }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////

class Solution {
  /**
   * Computes whether the BinaryTree is complete.
   *
   * @param tree
   *     the BinaryTree to check.
   * @return true iff the BinaryTree is complete, else false.
   */
  public static boolean isTreeComplete(BinaryTree tree) {
    return isTreeComplete(tree, 0, totalNodes(tree));
  }

  private static int totalNodes(BinaryTree tree){
    if(tree == null){
      return 0;
    }

    return 1 + totalNodes(tree.getLeft()) + totalNodes(tree.getRight());
  }

  public static boolean isTreeComplete(BinaryTree tree, int index, int totalNodes){
    if(tree == null){
      return true;
    }

    if(index >= totalNodes){
      return false;
    }

    return isTreeComplete(tree.getLeft(), 2*index+1, totalNodes) && isTreeComplete(tree.getRight(), 2*index+2, totalNodes);
  }

}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
import java.util.*;

/**
 * Iterates lazily over a binary tree in a depth-first manner. For instance a tree
 * with 8 as it's root and 4 and 10 as it's children should be iterated as: 8 ->
 * 4 -> 10.
 */
class BinaryTreeIterator<V> implements Iterator<V> {
  BTree<V> tree;
  Stack<Position<V>> stack = new Stack<Position<V>>();
  /**
   * Constructor.
   * Should reset on a new tree.
   *
   * @param tree
   *     takes the tree
   */
  public BinaryTreeIterator(BTree<V> tree) {
    this.tree = tree;
    if(tree.getRoot() != null)
      stack.push(tree.getRoot());
  }

  /**
   * @return True if there is a next element in the iterator, else False
   */
  @Override
  public boolean hasNext() {
    return !stack.isEmpty();
  }

  /**
   * Get the next element of the iterator and shift
   * iterator by one.
   *
   * @return current element value
   * @post iterator is moved to next element
   */
  @Override
  public V next() {

    if(stack.isEmpty()) return null;

    Position<V> temp = stack.pop();
    try{
      if(tree.hasRight(temp)){
        stack.push(tree.getRight(temp));
      }
      if(tree.hasLeft(temp)){
        stack.push(tree.getLeft(temp));
      }
    }
    catch(InvalidPositionException e){
      //hmm
    }

    return temp.getValue();
  }

  /**
   * Skip a single element of the iterator.
   *
   * @post iterator is moved to next element.
   */
  @Override
  public void remove() {
    next();
  }
}

/**
 * DO NOT MODIFY
 */
interface Position<V> {
  /**
   * @return the key of this position.
   */
  public int getKey();

  /**
   * @return the value of the position.
   */
  public V getValue();
}

interface BTree<V> {
  /**
   * @return the root of the tree
   */
  public Position<V> getRoot();

  /**
   * Get the left child of a position.
   *
   * @param v
   *     the position to get the child of.
   * @return the child of the position iff hasLeft(v) is true.
   * @throws InvalidPositionException
   *     else
   */
  public Position<V> getLeft(Position<V> v) throws InvalidPositionException;

  /**
   * Get the right child of a position.
   *
   * @param v
   *     the position to get the child of.
   * @return the child of the position iff hasRight(v) is true.
   * @throws InvalidPositionException
   *     else
   */
  public Position<V> getRight(Position<V> v) throws InvalidPositionException;

  /**
   * Check if a position has a left child.
   *
   * @param v
   *     position to check.
   * @return true iff v has a left child.
   * @throws InvalidPositionException
   *     if v is not valid (e.g. null)
   */
  public boolean hasLeft(Position<V> v) throws InvalidPositionException;

  /**
   * Check if a position has a right child.
   *
   * @param v
   *     position to check.
   * @return true iff v has a right child.
   * @throws InvalidPositionException
   *     if v is not valid (e.g. null)
   */
  public boolean hasRight(Position<V> v) throws InvalidPositionException;

  /**
   * Adds a new entry to the tree.
   *
   * @param key
   *     to use.
   * @param value
   *     to add.
   */
  public void add(int key, V value);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
WEEK-5

class Solution {
  /**
   * @param elements
   *     Array of integers to be sorted.
   */
  public static void selectionSort(int[] elements) {
    for(int i=0; i<elements.length-1; i++){
      int min = i;
      for(int j=i+1; j<elements.length; j++){
        if(elements[min]>elements[j])
          min = j;
      }
      int swap = elements[i];
      elements[i] = elements[min];
      elements[min] = swap;
    }
  }
}
//////////////////////////////////////////////////////////////////////////////////////////////////
class Solution {
  /**
   * @param elements
   *     Array of integers to be sorted.
   */
  public static void quickSort(int[] elements) {
    quickSort(elements, 0, elements.length-1);
  }

  public static void quickSort(int [] elements, int l, int r)
  {
    if(l>=r)
    return;

    int left=l;
    int right=r-1;
    int pivot=r;

    while(left<=right)
    {
      while(left<=right && elements[left]<=elements[pivot])
      left++;

      while(left<=right && elements[right]>=elements[pivot])
      right--;

      if(left<= right){
        int temp=elements[left];
        elements[left]=elements[right];
        elements[right]=temp;
        left++;
        right--;
      }
    }
     int temp=elements[left];
      elements[left]=elements[pivot];
      elements[pivot]=temp;

      quickSort(elements, l, left-1);
      quickSort(elements, left+1, r);

  }
}
///////////////////////////////////////////////////////////////////////////////////////////

WEEK-6

import java.util.*;

class Solution {
  @SuppressWarnings("unchecked")
  public static Queue<Integer>[] fillBuckets(int[] array) {
    if(array == null) return null;
    if(array.length == 0) return new LinkedList[0];

    int vmin = array[0];
    int vmax = array[0];
    if(array.length > 1){
      for(int i=1; i<array.length; i++){
        if(array[i] < vmin)
          vmin = array[i];
        else if(array[i] > vmax)
          vmax = array[i];
      }
    }

    Queue<Integer>[] buckets = new LinkedList[vmax - vmin + 1];

    for(int i=0; i<array.length; i++){
      if(buckets[array[i]-vmin] == null){
        buckets[array[i]-vmin] = new LinkedList<Integer>();
      }
      buckets[array[i]-vmin].add(array[i]);
    }
    return buckets;
  }

  public static int[] readBuckets(Queue<Integer>[] buckets) {
    if(buckets == null) return null;

    int[] array = new int[buckets.length];
    int k=0;

    for(int i=0; i<buckets.length; i++){
      while(buckets[i] != null && buckets[i].size()>0){
        array[k++]=buckets[i].remove();
      }
    }

    int[] sorted_array = new int[k];
    for(int i=0; i<k; i++){
      sorted_array[i] = array[i];
    }

    return sorted_array;
  }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
class Solution {
  public static void stableSort(String[][] table, int column) {
    if(table==null) return;

    int len = table.length;
    for(int i=1; i<len; i++){
      String key = table[i][column];
      String[] key_row = table[i];

      int j=i-1;
      while(j>=0 && table[j][column].compareTo(key)>0){
        table[j+1] = table[j];
        j--;
      }
      table[j+1] = key_row;
    }
  }
}
////////////////////////////////////////////////////////////////////////////////////////////////////
WEEK-7

import java.util.*;

class MySet extends HashSet<String> {
  private static final long serialVersionUID = 1L;

  public MySet() {
    super();
  }

  /**
   * @return the union of the elements of this and that
   */
  public MySet union(MySet that) {
    MySet result = new MySet();
    Iterator<String> this_set = this.iterator();
    while(this_set.hasNext()){
      result.add(this_set.next());
    }

    if(that != null){
      Iterator<String> that_set = that.iterator();
      while(that_set.hasNext()){
        String elem = that_set.next();
        if(!result.contains(elem)){
          result.add(elem);
        }
      }
    }
    return result;
  }

  /**
   * @return the intersection of the elements of this and that
   */
  public MySet intersection(MySet that) {
    MySet result = new MySet();

    if(that != null){
      Iterator<String> that_set = that.iterator();
      while(that_set.hasNext()){
        String elem = that_set.next();
        if(this.contains(elem)){
          result.add(elem);
        }
      }
    }
    return result;
  }

  /**
   * @return the difference of the elements of this and that
   */
  public MySet difference(MySet that) {
    MySet result = new MySet();
    Iterator<String> this_set = this.iterator();
    while(this_set.hasNext()){
      result.add(this_set.next());
    }

    if(that != null){
      Iterator<String> that_set = that.iterator();
      while(that_set.hasNext()){
        String elem = that_set.next();
        if(result.contains(elem)){
          result.remove(elem);
        }
      }
    }
    return result;
  }

  /**
   * @return the exclusive or (XOR) of the elements of this and that
   */
  public MySet exclusiveOr(MySet that) {
    MySet result = new MySet();
    Iterator<String> this_set = this.iterator();
    while(this_set.hasNext()){
      result.add(this_set.next());
    }

    if(that != null){
      Iterator<String> that_set = that.iterator();
      while(that_set.hasNext()){
        String elem = that_set.next();
        if(result.contains(elem)){
          result.remove(elem);
        }
        else{
          result.add(elem);
        }
      }
    }
    return result;
  }

  /**
   * @return a String representation of a MySet object
   */
  public String toString() {
    String str = "<MySet{";
    Iterator<String> this_set = this.iterator();
    while(this_set.hasNext()){
      str += this_set.next();
    }
    str += "}>";

    return str;
  }
}
//////////////////////////////////////////////////////////////////////////////////////////////
import java.util.*;

/**
 * Entry objects are used to represent "Key-Value" pairs.
 * An entry can be created by using new Entry(String key, Integer Value)
 * The .equals() method of Entry will compare the keys only.
 */
class Entry {
  public final String key;
  public final Integer value;

  public Entry(String s, Integer v) {
    key = s;
    value = v;
  }

  public boolean equals(String s) {
    return s == null && key == null || key.equals(s);
  }

  @Override
  public boolean equals(Object o) {
    return this == o || o != null && getClass() == o.getClass() && this.equals(((Entry) o).key);
  }

  public String getKey() {
    return key;
  }

  public int getValue() {
    return value;
  }
}

abstract class HashTable {
  protected LinkedList<Entry>[] myTable;

  /**
   * Constructs a new HashTable.
   *
   * @param capacity
   *     to be used as capacity of the table.
   * @throws IllegalArgumentException
   *     if the input capacity is invalid.
   */
  @SuppressWarnings("unchecked")
  public HashTable(int capacity) {
    if(capacity <= 0)
      throw new IllegalArgumentException();

    myTable = new LinkedList[capacity];
  }

  /**
   * Add a key value pair to the HashTable.
   *
   * @param key
   *     to identify the value.
   * @param value
   *     that is identified by the key.
   */
  public void put(String key, Integer value) {
    if(myTable == null) return;

    int hash = hash(key);
    if(myTable[hash] == null){
      myTable[hash] = new LinkedList<Entry>();
    }

    if(containsKey(key)){
      for(int i=0; i<myTable[hash].size(); i++){
        Entry entry = myTable[hash].get(i);
        if(entry.equals(key)){
          myTable[hash].set(i, new Entry(key, value));
          break;
        }
      }
    }
    else{
      myTable[hash].add(new Entry(key, value));
    }
  }

  /**
   * @param key
   *     to look for in the HashTable.
   * @return true iff the key is in the HashTable.
   */
  public boolean containsKey(String key) {
    if(myTable == null) return false;

    int hash = hash(key);

    if(myTable[hash] != null){
      for(Entry entry : myTable[hash]){
        if(entry.equals(key)){
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Get a value from the HashTable.
   *
   * @param key
   *     that identifies the value.
   * @return the value associated with the key or `null` if the key is not in the HashTable.
   */
  public Integer get(String key) {
    if(containsKey(key)){
      int hash = hash(key);
      for(Entry entry: myTable[hash]){
        if(entry.equals(key)){
          return entry.getValue();
        }
      }
    }
    return null;
  }

  /**
   * @return the capacity of the HashTable.
   */
  public int getCapacity() {
    return myTable.length;
  }

  /**
   * Hashes a string/key.
   *
   * @param item
   *     to hash.
   * @return the hashcode of the string, modulo the capacity of the HashTable.
   */
  public abstract int hash(String item);
}
//////////////////////////////////////////////////////////////////////////////////////////////////

class ETHHash extends HashTable {
  public ETHHash(int size) {
    super(size);
  }

  @Override
  public int hash(String item) {
    if(item == null)  return 0;

    int b = 1;

    for(int i=1; i <= item.length(); i++){
      char currentChar = item.charAt(i-1);

      int bi = currentChar * ((b % 257) + 1);
      b = bi;
    }

    return b % getCapacity();
  }
}

class GNUCPPHash extends HashTable {
  public GNUCPPHash(int size) {
    super(size);
  }

  @Override
  public int hash(String item) {
    if(item == null) return 0;

    int b = 0;

    for(int i=1; i <= item.length(); i++){
      int c = item.charAt(i-1);

      int bi = 4 * b + c;
      b = bi;
    }

    return ( ((1 << 31)-1) & b ) % getCapacity();
  }
}

class GNUCC1Hash extends HashTable {
  public GNUCC1Hash(int size) {
    super(size);
  }

  @Override
  public int hash(String item) {
    if(item == null)  return 0;

    int b = item.length();

    for(int i=1; i <= item.length(); i++){
      char c = item.charAt(i-1);

      int bi = 613 * b + c;
      b = bi;
    }

    return ((1 << 31)-1 & b) % getCapacity();
  }
}

class HashCodeHash extends HashTable {
  public HashCodeHash(int size) {
    super(size);
  }

  @Override
  public int hash(String item) {
    if (item == null) return 0;

    return Math.abs(item.hashCode()) % getCapacity();
  }
}
///////////////////////////////////////////////////////////////////////////////////////////////////
WEEK-8

import java.util.*;

/**
 * Implements a Depth first traversal of the Graph, starting at contructor vertex v. It
 * should return nodes at most once. If there is a choice between multiple next nodes,
 * always pick the lowest id node.
 */
class GraphIterator implements Iterator<Vertex> {
  private Graph g;
  private Vertex v;
  private Stack<Vertex> stack;
  private Set<Vertex> colored;
  private int graphSize;

  public GraphIterator(Graph g, Vertex v) {
    this.graphSize = 0;
    this.g = g;
    this.v = v;
  }

  @Override
  public boolean hasNext() {
    if(this.g == null || this.v == null)  return false;

    return this.g.getAllVertices().size() != this.graphSize;
  }

  @Override
  public Vertex next() {
    this.stack = new Stack<Vertex>();
    this.colored = new TreeSet<Vertex>();
    this.stack.push(v);

    Vertex current = null;

    for(int i=0; i<=this.graphSize; i++){

      do{
        current = this.stack.pop();
      }while(this.colored.contains(current));

      List<Vertex> neighbours = this.g.getNeighbours(current);
      Collections.sort(neighbours, (a,b) -> b.getId()-a.getId());

      for(Vertex v : neighbours){
        if(!this.colored.contains(v))
          this.stack.push(v);
      }

      this.colored.add(current);
    }
    this.graphSize++;
    return current;
  }
}
/////////////////////////////////////////////////////////////////////////////////////////
class Solution {
  public static int numberOfConnectedComponents(Graph g) {

    Collection<Vertex> unexplored = g.getAllVertices();

    for(int count=0; ; count++){
      Iterator<Vertex> un_iter = unexplored.iterator();

      if(!un_iter.hasNext())  return count;

      Vertex v = un_iter.next();
      Iterator<Vertex> iter = new GraphIterator(g, v);
      List<Vertex> explored = new ArrayList<>();

      while(iter.hasNext()){
        explored.add(iter.next());
      }

      unexplored.removeAll(explored);
    }
  }
}
/////////////////////////////////////////////////////////////////////////////////////////////////
import java.util.*;

class Solution {
  /**
   * Find the shortest path between v and u in the graph g.
   *
   * @param g
   *     graph to search in.
   * @param v
   *     node to start from.
   * @param u
   *     node to reach.
   * @return the nodes you that form the shortest path, including v and u. An
   * empty list iff there is no path between v and u.
   */
  public static List<Vertex> shortestPath(Graph g, Vertex v, Vertex u) {
    LinkedList<Vertex> slowPath = new LinkedList<Vertex>();
    Iterator<Vertex> iter = new GraphIterator(g,v);

    while(iter.hasNext()){
      Vertex x = iter.next();

      slowPath.add(x);

      if(x == u){
        break;
      }
    }

    if(slowPath.get(slowPath.size()-1) != u){
      return new ArrayList<>();
    }

    List<Vertex> fastRevPath = new ArrayList<>();
    int i = slowPath.size() - 1;

    while(true){
      Vertex c = slowPath.get(i);

      List<Vertex> connected = g.getNeighbours(c);

      fastRevPath.add(c);

      if(c == v){
        Collections.reverse(fastRevPath);
        return fastRevPath;
      }

      int index=0;

      for(Vertex vertex : slowPath){
        if(!fastRevPath.contains(vertex) && connected.contains(vertex)){
          i = index;
          break;
        }

        index++;
      }
    }

  }
}
///////////////////////////////////////////////////////////////////////////////////