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