Strategies

Random assorted notes from competitive programming problems - various strategies, etc.

Arrays and Strings

Hash tables

• Using a HashSet or HashMap in Java is a fast, O(1) way to look things up
• Use hash tables when you need to keep track of how many of X different things you have seen
• Internally, hash tables can use binary trees to stay balanced, and use less space

Array lists

• Internally resized array with O(1) access
• When array runs out of space, needs to double, which takes O(N)
• Doubling in size should happen infrequently, so ends up taking O(1) on average

StringBuffer

• Avoids the expensive/costly construction of a new string in a loop
• StringBuffer internally stores an array of Strings, does not concatenate them until it needs to return the result (when toString() method called)

public string joinWords(String[] words) {
  StringBuffer sentence = new StringBuffer();
  for(String w : words) { 
    sentence.append(w + " ");
  }
  return sentence.toString();
}