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