Acceptable data structure in worst case scenario?

  • 0

    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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.