Suppose we have to design a data structure to store some objects. Each object has a 32 bit integer timestamp field. Your container to be used like this: 1. Objects are inserted into the container, not necessarily ordered by the timestamp. Its guaranteed that there will never be 1 billion objects at once. 2. Objects will never be removed from container. 3. Occasionally you will need to iterate over all stored objects in a sorted by timestamp order. 4. The container is never shared among different threads.
Based on the above requirements, which of the foll designs would you consider acceptable with regards to worst case scenario performance?
Option1: Store all objects in an array; append to the end, perform quicksort before we need to iterate if needed.
Option2: Store all objects in an array; append to the end, perform in-place mergesort after each iteration if needed.
Option3: Store all objects in an array; keep it sorted by inserting any new object at the appropriate position.
Option4: Use a balanced tree with dynamic node allocation, using timestamp field as the comparison criterion.
Option5: Keep a linked list of dynamic allocated elements and append to the end of it; perform merge before iterating if needed.
Option6: Store elements in hashmap(mapping from timestamp to the object) with reasonable number of buckets.
Option 7: Preallocate an array and use timestamp as an index in it. When we need to iterate, check all possible timestamps for associated objects.
@solankirahul848 use a balanced tree with dynamic node allocation, using timestamp field as the comparison criterion.
@ssubbiah would you like to elaborate your answer?
Option 7. Because doing this will allow you to iterate in a sort by time manner easily as compared to other data structures. About using arrays and lists, All the merge and quick and insertion sorts will run in nlog(n) or quadratic time. About maps. Insertion and Access is constant time but sorting will take much more time. Couldnt say about using trees
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.