Amazon Interview Question
Software Engineer / Developersin case of hashtable solution, if we consider uniformly distributing hashing, then lookup time surely will come down to O(1)
Ran is absolutely right about insertion in linked list, as insertion is done at the begining of linked list which just takes creation of new node and making it head of the linked list.
But, in case of deletion in linked list, lookup itself will take O(N) in the worst case, that is traversing time in linked list.
- Give two data structures you could use
1. HashMap using hash table (unsorted map)
2. TreeMap using Red-Black Tree (sorted map)
- What is average and worst case insert time, delete time, look up time
1. for HashMap: average O(1) worst O(N)
2. for TreeMap: average O(log N) worst (unbalanced) O(N)
- What are pros/cons of each
1. for HashMap: speed
2. for TreeMap: sorted
The simplist one to use is an array.
lookup: O(1)
delete: O(n) due to shifting
insert: O(n) due to shifting
avg: O(n)
Cons:
Too many mem writes when shifting.
Pros:
Least mem overhead for lookup.
Hashmap and Treemap are good ones too.
For linked list, why does deletion and insertion need O(n)? It should be
O(1). For example, When i do deletion on a given element, I can just copy the next node info to the memory of the delete element, and free the mem of the next node. It is O(1).
- hashtable(an unsorted linked list is used for handling collision.
- someone September 30, 2005)
insert: O(1)
delete: O(n)
lookup: O(n)
- linked list
insert: O(n)
delete: O(n)
lookup: O(n)