Coding Exercises Day 27d (Problem #24)

Problem:

Implement Depth First Search for a Binary Tree

public <T> static boolean depthFirstSearch(Node<T extends Comparable<T>>  node, T value) {
  if (null == node) return false;

  if (value.compareTo(node.getValue()) == 0) {
    return true;
  }
  return depthFirstSearch(node.getLeft(), value) || 
         depthFirstSearch(node.getRight(), value);
}

Coding Exercises Day 27c (Problem #23)

Problem:

For a Binary Search Tree, insert a node.

class BinarySearchTree<T extends Comparable<T>> {

  Node<T> root;

  public BinarySearchTree(Node<T> root) {
    this.root = root;
  }
  
  public void insert(T value) {
    insert(root, value);
  }

  private void insert(Node<T> node, T value) {
    if (value.compareTo(node.getValue()) < 0) {
      if (node.getLeft() != null) {
        insert(node.getLeft(), value);
      }
      else {
        node.setLeft(new Node<T>(value));
      }
    }
    else if (value.compareTo(node.getValue()) > 0) {
      if (node.getRight() != null) {
        insert(node.getRight(), value);
      }
      else {
        node.setRight(new Node<T>(value));
      }
    }
  }
}

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;
}

Coding Exercises Day 11 (Problem #15)

Problem:
Given a circular linked list, implement and algorithm which returns the node at the beginning of the loop.

Definition:
Circular linked list: A corrupt linked list in which a nodes 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 (same C as earlier)
Ouput: C

Node * findLoopHead(Node *head) {
  if (NULL == head) {
    return NULL;
  }
  int listSize = 1;

  Node *node = head->next;

  while (node != NULL) {
    // Start at head and look at previous nodes
    int i;
    Node *previous = head;
    
    for (i = 0; i < listSize; i++) {
      if (node == previous) {
        return node;
      }
      previous = head->next;
    }
 
    listSize++;
    node = node->next;
  }
  // Not a circular linked list
  return NULL;
}

Coding Exercises Day 10 (Problem #14)

Problem:
Implement a function to check if a linked list is a palindrome

 boolean isPalindrome(List<T> list) {
  Stack<T> stack = new Stack<T>();

  int size = list.size();

  if (size < 2) return true;
  
  boolean sizeIsOdd = (size % 2 != 0) ? true : false;

  for (int i = 0; i < size; i++) {
    T element = list.get(i);
    
    if (i < size / 2) stack.push(element);
    
    // Ignore the middle element if the list size is odd.
    if ((!sizeIsOdd && i == size / 2) || i > size / 2) {
      if (stack.peek() == element) { 
        stack.pop();
      }
      else {
        return false;
      }
    }
  }
  return true;
}

Coding Exercises Day 9b (Problem #13)

Problem:
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.

 void partitionList(List<T> list, int pivot) {
  int elementsSeen = 0;
  int size = list.size();
  
  Iterator<T> iter = list.iterator();  

  while (elementsSeen < size && iter.hasNext()) {
    T element = iter.next();
    iter.remove();
    
    if (element < pivot) {
      list.add(0);  
    }
    else {
      list.add(size - 1);
    }
    elementsSeen++;
  }  
}

Coding Exercises Day 9 (Problem #12)

Problem

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees.  Can you do this in place?

void rotate90Degrees(byte[][] image) {
  // Run through rows 0 -> n/2 - 1 and rotate all bytes in that row
  for (int i = 0; i < n/2; i++) {
    for (int j = i; j < n - i; j++) {
      rotateByte90Degrees(image, i, j);
    }
  }  
}

// Rotate all four bytes corresponding to x,y.
void rotateByte90Degrees(byte[][] image, int x, int y) {
  int lastIndex = image.length - 1;
  
  byte nextByte = image[y][lastIndex - x];
  
  // Rotation 1
  image[y][lastIndex - x] = image[x][y];
  
  // Store the byte that was overwritten in x,y.
  // We are treating image[x][y] as an additional temp var.
  image[x][y] = nextByte;
  
  // Store the next byte that will be overwritten
  nextByte = image[lastIndex - x][lastIndex - y];
  
  // Rotation 2
  image[lastIndex - x][lastIndex - y] = image[x][y];

  image[x][y] = nextByte;
  nextByte = image[lastIndex - y][x];

  // Rotation 3
  image[lastIndex - y][x] = image[x][y];
  
  // Rotation 4
  image[x][y] = nextByte;
}

Coding Exercises Day 8c (Problem #11)

Problem:
Implement an algorithm in C to delete a node in the middle of a singly linked list.

void delete(Node *head, Node *nodeToDelete) {
  if (head == nodeToDelete) {
    head = head->next;
  }
  Node *current = head;
  Node *next = head->next;

  while (next != NULL) {
    if (next == nodeToDelete) {
      current->next = next->next;
      break;
    }
    current = next;
    next = next->next;
  }  
}

Followup:
Assume you only have access to that node and not the head of the list

void delete(Node *node) {
  if (node != NULL) {
    node->next = node->next->next;
    node->value = node->next->value;
  }
}

Coding Exercises Day 8b (Problem #10)

Problem:
Implement an algorithm to find the kth to last element of a singly linked list.

 T findKthToLast(List<T> list, k) {
  if (k = 0) return null;

  int size = 0;
  
  Map<Integer, T> elementMap = new HashMap<Integer, T>();

  for (T element : list) {
    size++;
    elementMap.put(size, element);
  }
  return elementMap.get(size - k + 1);
}

Coding Exercises Day 8a (Problem #9)

Problem:
Write code to remove duplicates from an unsorted linked list.

 void removeDuplicates(List list) {
  Set previousElements = new HashSet();
  
  Iterator iter = list.iterator();

  while (iter.hasNext()) {
    T current = iter.next();
    
    if (previousElements.contains(current)) {
      iter.remove();
    }
    else {
      previousElements.add(current);
    }
  } 
}

Followup:
How would you solve this problem if a temporary buffer is not allowed?

 void removeDuplicates(List list) {
  // Sort the list first.
  Collections.sort(list);

  T previous = null;'

  Iterator iter = list.iterator();
  
  while(iter.hasNext()) {
    T current = iter.next();
    
    if (null == previous) {
      previous = current;
    }
    else if (previous == current) {
      iter.remove();
    }
    else {
      previous = current;
    }
  }
}

Coding Exercises Day 7 (Problem #8)

Problem:
Assume you have a method isSubstring which checks if one word is a substring of another.  Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.  E.g., "waterbottle" is a rotation of "erbottlewat".

boolean isRotation(String s1, String s2) {
  try {
    if (s1.length() != s2.length()) {
      return false;
    }
    String concatString = s2 + s2;

    return s1.isSubstring(s2);
  }
  catch (NullPointerException npe) {
    npe.printStackTrace();
    return false;
  }
}

Coding Exercises Day 5 (Problem #7)

Problem:
Write an algorithm such that if an element in an MxN matrix is 0, it's entire row and column are set to 0.

void fillWithZeros(int[][] matrix) {

  int m = matrix[0].length; // num rows
  int n = matrix.length; // num columns

  Set rows = new HashSet(m);
  Set columns = new HashSet(n);
  
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (0 == matrix[i][j]) {
        rows.add(i);
        columns.add(j);
      }
    }
  }

  for (int i : rows) {
    for (int j = 0; j < n; j++) {
      matrix[i][j] = 0;
    }
  }

  for (int j : columns) {
    for (int i = 0; j < m; i++) {
      matrix[i][j] = 0;
    }  
  }
}

Coding Exercises Day 4 (Problem #6)

Problem:
Implement a method to perform basic string compression using the counts of repeated characters.  For example, the string aabcccccaaa would become a2b1c5a3.  If the compressed string is no smaller than the original string, the method should return the original string.

String compress(String s) {
  int length = s.length();
  
  if (length < 3) {
    return s;
  }  

  StringBuilder compressed = new StringBuilder();
  
  boolean isCompressed = false;

  char previousChar = s.charAt(0); 
  int charCount = 1;

  int index = 1;

  while (compressed.length() < length && index < length) {
    char currentChar = s.charAt(index);

    if(currentChar != previousChar) {
      compressed.append(previousChar).append(charCount);
      
      previousChar = currentChar;
      charCount = 1;
    }  
    else {
      charCount++;
    }
    index++;
  }

  if (index == length && compressed.length() < length) {
    return compressed.toString;
  }
  return s;
}

Coding Exercises Day 3 (Problem #5)

Problem:
Write a method to replace all spaces in a string with '%20'.  You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the true length of the string.  (Note: if implementing in Java, please use a character array so that you can perform this operation in place).

Example:
Input: "Mr. John Smith    "
Output: "Mr.%20John%20Smith"

  void replaceSpaces(char[] charArray, int length) {
    int delta = 0;

    for (int i = 0; i < length; i++) {
      if (' ' == charArray[i + delta]) {
        for (j = delta + length - 1); j > i + delta; j--) {
          charArray[j + 2] = charArray[j];
        }

        charArray[i] = '%';
        charArray[i + 1] = '2';
        charArray[i + 2] = '0';      
        delta += 2;            
      }
    }
  }

Best Comedy Standup Performances

Top Tier

These are some of the best standup performances I've ever seen.  Some of the links below may be outdated, but there are lots of alternative resources to view these clips.

• Bill Burr - Let it Go - IMDb
• David Chappelle - Rick James - YouTube Pt 1, YouTube Pt 2
• David Chappelle - HBO Comedy Half Hour - YouTube Full
• Kevin Hart - Def Comedy Jam - YouTube Pt 1, YouTube Pt 2, YouTube Pt 3, YouTube Pt 4, YouTube Pt 5
• Eddie Murphy - Delirious - YouTube Full

Second Tier

Good, worth watching, but not quite legendary status.

• David Chappelle - Killin' Them Softly - YouTube Full
• Chris Rock - Bringin' the Pain - YouTube Full
• Norm MacDonald - One Night Stand (HBO) - Daily Motion Full

Coding Exercises Day 2 (Problem #4)

Problem:
Given two strings, determine if one is a permutation of the other (i.e., the two strings are anagrams of each other)

static boolean areAnagrams(String s1, String s2) {
  if (null == s1 && null == s2) {
    return true;
  }
  else if (null == s1 ^ null == s2) {
    return false;
  }
  // Both strings are non-null and identical length
  else if (s1.length() == s2.length()) {
    // char are two-byte primitives in Java
    int numChars = Math.pow(2, 16);

    int[] s1CharCount = new int[numChars];
    int[] s2CharCount = new int[numChars];

    countChars(s1, s1CharCount);
    countChars(s2, s2CharCount);

    for (int i = 0; i < numChars; i++) {
      if (s1CharCount[i] != s2CharCount[i]) {
        return false;
      }
    }
    return true;
  }
  return false;
}

static void countChars(String s, int[] charCount) {
  for (int i = 0; i < s.length(); i++) {
    charCount[Character.numericValue(s.charAt(i))]++;    
  }
}

Coding Exercises Day 1c (Problem #3)

Problem:
Find the height of a binary tree given the root node

  int getHeight(Node node) {
    int rval = 0;

    if (node != null) {
      rval = 1;

      Node left = node.getLeft();
      Node right = node.getRight();
    
      if (left != null || right != null) {
        
        rval += Math.max(getHeight(left), getHeight(right));
      }
    }
    return rval;
  }

Coding Exercises Day 1b (Problem #2)

Problem:
Implement a function in C which reverses a null-terminated string.

void reverse(char* str) {
  
  int length = strlen(str);

  if (length > 1) {

    int startIdx = 0;
    int endIdx = length - 1;
    
    while (startIdx < endIdx) { 
      char temp = str[startIdx];
      str[startIdx] = str[endIdx];
      str[endIdx] = temp;

      endIdx--;
      startIdx++;
    }
  }
}

Coding Exercises Day 1 (Problem #1)

I've decided to start honing my skills by working on a coding problem every day. The code might not be correct and it might not even compile, but the important thing is to code something each day.

Day 1 (Problems completed: 1)

Problem:
Implement an algorithm to determine if a string has all unique characters.  What if you cannot use additional data structures?

boolean allUnique(String s) {
  boolean rval = true;

  // Java uses two-byte chars, so lets initialize an array of size 2^16
  boolean[] trackChars = new boolean[Math.pow(2, 16)];

  for (int i = 0; i < s.length; i++) {
    int charAsNum = Character.getNumericValue(s.charAt(i));
    
    if (!trackChars[charAsNum]) {
      trackChars[charAsNum] = true;
    }
    else {
      rval = false;
      break;    
    }
  }
  return rval;
}