Sources

• Cracking the Coding interview by Gayle Laakman McDowell 3ed

Hash table

public HashMap<Integer, Student> buildMap(Student[] students) {
    HashMap<Integer, Student> map = new HashMap<Integer, Student>();
    for (Student s : students) map.put(s.getId(), s);
    return map;
}

When to use?

ArrayList (Dynamically Resizing Array)

• resizes itself as needed, but keeps O(1) access time
• typical: if array full, double it in size. Doubling takes O(n) time
  • But amortized run time is O(1)

    public ArrayList<String> merge(String[] words, String[] more) {
      ArrayList<String> sentence = new ArrayList<String>();
      for (String w : words) sentence.add(w);
      for (String w : more) sentence.add(w);
      return sentence;
    }
    

StringBuffer

public String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}