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