We learned more about different types of data structures and continued to work on the second sprint of data structures. We learned about:
– LinkedList (single or double linked). The single linked LinkedList is great for modeling the prototype chains. Constant in insertion time. Linear in look time.
– Constant in lookup time. Linear in insertion time if insertion is not in the end of the array.
– Similar to LinkedList except each node can have multiple children. It is good for modelling hierarchy; and it is good for finding an element if the tree is sorted.
– A collection of key-value pairs that satisfies the following constrains:
1. constant in lookup time.
2. constant in insertion time.
3. each key has to be unique.
Jake and I spent a lot of time time on HashTable and I think if I were an interviewer, I would ask my interviewee to implement a HashTable for me too.
The hash function is deterministic, stateless, and a upper limit. I can image those hash functions must come from the best mathematicians.
Rehash is also necessary when the current hash table becomes either too crowded or too sparse.
We end up implementing a HashTable with nested arrays. The approach is cool, just working with nesting arrays really requires a clear mind all the time.
-Marcus emphasized that optimization should focus on the # of steps, not how much time each step spend. That is a great point. We also learned about the notation of O(1), O(n), O(logn), O(n^2) and O(x^n, where x is a constant).