Coding Exercises Day 27b (Problem #22)

Problem:
Traverse a Binary Tree in InOrder, PreOrder, and PostOrder

class Tree <T> {
  Node<T> root;

  public <T> Tree(Node<T> root) {
    this.root = root;
  }

  public void inOrder() {
    inOrder(root);
  }
 
  private void inOrder(Node node) {
    if (node != null) {
      inOrder(node.getLeft());
      System.out.print(node.getValue());
      inOrder(node.getRight());
    }
  }

  public void preOrder() {
    preOrder(root);
  }
  
  private void preOrder(Node node) {
    if (node != null) {
      System.out.print(node.getValue());
      preOrder(node.getLeft());
      preOrder(node.getRight());
    }
  }

  public void postOrder() {
    postOrder(root);
  }

  private void postOrder(Node node) {
    if (node != null) {
      postOrder(node.getLeft());
      postOrder(node.getRight());
      System.out.print(node.getValue());
  } 
}

Coding Exercises Day 27 (Problem #21)

Problem:

Describe how you could use a single array to implement three stacks.

class ThreeStacks {
  private static final String STACK_ID_ERROR_MSG = "Stack Id must be 0, 1, or 2";
  
  int[] stackSize = new int[3];

  T[] dataArray;

  public ThreeStacks(int initialSize) {
    dataArray = new T[initialSize];
  }

  public push(int stackId, T element) throws IllegalArgumentException {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    // if data array is too small, triple it and copy over contents
    if (dataArray.length < (stackSize[stackId] + 1) * 3) {
      increaseDataArray();
    }    

    for (int i = stackSize[stackId]; i > 0; i--) {
      int index = i * 3 + stackId;
      dataArray[index] = dataArray[index - 3];      
    }

    stackSize[stackId]++;
    dataArray[stackId] = element;
  }

  public pop(int stackId) {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    if (stackSize[stackId] == 0) return null;

    T rval = dataArray[stackId];

    int index = stackId;

    for (int i = 0; i < stackSize[stackId]; i++) {
      dataArray[index] = dataArray[index + 3];      
    }    

    stackSize[stackId]--;

    return rval;
  }

  private increaseDataArray() {
    T[] biggerDataArray = new T[dataArray.length * 3];

    for (int i = 0; i < dataArray.length; i++) {
      biggerDataArray[i] = dataArray[i];
    }
  }
}

Coding Exercises Day 25b (Problem #20)

Problem:

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 previous one exceeds capacity.SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Follow up:

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

class SetOfStacks {
  int threshold;
  int size;

  List<Stack<Node>> stackList = new ArrayList<Stack<Node>>();

  public SetOfStacks(int threshold) {
    this.threshold = threshold;
  }

  public void push(Node node) {
    size++;
    if ((threshold * stackList.size()) < size) {
      stackList.add(0, new Stack<Node>);
    }
    stackList.get(0).push(node);
  }

  public Node pop() {
    if (0 == size) return null;

    size--;

    Stack topStack = stackList.get(0);

    Node rval = topStack.pop();

    if (topStack.empty()) {
      stackList.remove(0);
    }

    return rval; 
  }  

  public Node popAt(int index) {
    Stack<Node> stack = stackList.get(index);
    Node rval = stack.pop();

    Stack temp = new Stack();

    // Rebalance stacks
    for (int i = index - 1; i <= 0; i--) {
      Stack<Node> previousStack = stackList.get(i);
      
      while(!previousStack.empty()) {
        temp.push(previousStack.pop());
      }

      // Fill the empty slot with an element from the previous stack.
      stackList.get(i + 1).push(temp.pop());
      
      while (!temp.empty()) {
        previousStack.push(temp.pop());
      }
    }

    if (stack.empty()) {
      stackList.remove(index);
    }

    return rval;
  }
}

Coding Exercises Day 25 (Problem #19)

Problem:
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 all operate in O(1) time.

class Stack {
  List<Node> minList = new LinkedList<Node>();

  Node top = null;

  public void push(Node node) {
    if (null == top) {
      top = node;
      node.setNext(null);

      minList.add(0, node);
    }    
    else {
      node.setNext(top);
      top = node;

      // This is the new minimum
      if (node.getValue() < minList.get(0).getValue()) {
        minList.add(0, node);
      }
      else {
        // previous minimum node is still the minimum
        minList.add(0, minList.get(0));
      }
    }
  } 

  public Node pop() {
    rval = top;

    top = top.getNext();

    minList.remove(0);

    return rval;
  }

  public Node min() {
    return minList.get(0);
  }
}

Coding Exercises Day 24b (Problem #18)

Problem:
Write a program to sort a stack in ascending order.  You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

public void sortStack(Stack<Node> stack) {
  List<Node> tempList = new ArrayList<Node>();

  while(!stack.isEmpty()) {
    tempList.add(stack.pop());  
  }
  
  Comparator comparator = new Comparator( {
    public int compare(Node nodeOne, Node nodeTwo) {
      if (nodeOne.getValue() == nodeTwo.getValue()) return 0;
      
      // Sort in Descending Order
      if (nodeOne.getValue() > nodeTwo.getValue())  {
        return -1;
      }
      else {
        return 1;
      }
    } 
  });

  Collections.sort(tempList, comparator);

  for (Node node : tempList) {
    stack.push(node);
  }
}

Coding Exercises Day 24 (Problem #17)

Problem:

Implement a MyQueue class which implements a queue using two stacks.

class MyQueue {
  Stack<Node> stackLIFO = new Stack<Node>(); 
  Stack<Node> stackFIFO = new Stack<Node>();
  
  public void enqueue(Node node) {
    stackLIFO.push(node);
  }

  public Node dequeue() {
    if (stackFIFO.isEmpty() && stackLIFO.isEmpty()) return null;

    if (!stackFIFO.isEmpty()) {
      return stackFIFO.pop();
    }
    else {
      while(!stackLIFO.isEmpty()) {
        Node temp = stackLIFO.pop();
        stackFIFO.push(temp);
      }
      return stackFIFO.pop();
    }
  }
}

Coding Exercises Day 12 (Problem #16)

Problem:
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: (7 -> 1 -> 6) + (5 -> 9 -> 2).  Translates to 617 + 295.
Output: 2 -> 1 -> 9.  Translates to 912.

Follow Up:
Suppose the digits are stored in forward order.  Repeat the above problem.

Example:
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).  Translates to 617 + 295.
Output: 9 -> 1 -> 2.  Translates to 912.

List sum(List<Integer> numOneList, List<Integer> numTwoList, boolean isReversed) {
  StringBuilder numOneString = new StringBuilder();
  StringBuilder numTwoString = new StringBuilder();
   
  for (Integer digit : numOneList) {
    numOneString.append(digit);
  }

  for (Integer digit : numTwoList) {
    numOneString.append(digit);
  }

  if (isReversed) {
    numOneString.reverse();
    numTwoString.reverse();
  }

  int sum = Integer.parseInt(numOneString.toString()) 
         + Integer.parseInt(numTwoString.toString());

  List<Integer> rval = new LinkedList<Integer>();
  
  String sumString = String.valueOf(sum);

  for (int i = 0; i < sumString.length(); i++) {
    int j = i;
    if (isReversed) {
      j = sumString.length() - 1 - i;  
    }
    rval.add(sumString.charAt(j));
  }
  return rval;
}