Flipkart Interview Question
SDE1sCountry: India
Interview Type: In-Person
What's the point of a linked list here? Why not just use a HashSet and be done with it:
1. Create/Insert -> O(1)
2. Retrieve -> O(1)
3. Update -> O(1)
4. Delete -> O(1)
@Naveen: There may be a possibility of collision when you use hashMap so your retrieval and deletion will not be in O(1) in worst case.
And @jbaum517: Can you please elaborate how HashSet will give the result of all CRUD operations in O(1) ?
@Aman_Mittal: Operations on a HashMap are considered to be amortized O(1). Much like adding an element to an ArrayList is amortized O(1)
@Aman Mittal: A HashSet is essentially a HashMap without values that are mapped from the key set. HashSet has all of those same access functions and their worst case behavior since it's based on a constant time hash of the object.
Since we're talking about HashSet though which is part of java's util package, I should also note that HashSet is NOT synchronized. So we would need some sort of external locking mechanism in place if this data structure were to be used by multiple processes simultaneously.
@Naveen - if you are caring of collision, then you should ask that what data you are going to store, how you are going to make the key ? If you have right hash function, there is less chances of collision. Still if you want you can have multilevel of hash implementation where on collision, you can recalculate the key (obviously that object has some difference in some properties) and value would be hash table on basis of recalculated key. A variation of this is also known as cuckoo hashing.
Use LinkedList and HashMap, map is needed to keep the track of node in linkedlist.
- Naveen August 07, 20151. Create -> add node to both linkedlist and map O(1)
2. Retrieve -> get the reference of the node in list using map and return the node. O(1)
3. Update -> get the reference of the node in list using map and update it in the list O(1)
4. Delete -> get the reference of the node in list using map and delete it from the both linkedlist and map O(1)