check all that applies You are asked to design a data structure to store some ob

Question

check all that applies

You are asked to design a data structure to store some objects. Each object has a 32-bit integer timestamp field. Your container is expected to be used like this: 1. Objects are inserted into the container, not necessarily ordered by the timestamp. It's guaranteed that there will never be more than 1,000,000,000 (1 billion) objects at once. 2. Objects will never be removed from the 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 these requirements, which of the following designs would you consider acceptable with regards to worst case scenario performance? You may select multiple options. Pick the correct choices O Store all objects in an array; append to the end; perform quicksort before we need to iterate if needed. O Store all objects in an array; append to the end and perform in-place merge sort after each insertion if needed. O Store all objects in an array; keep it sorted by inserting any new object at the appropriate position. O Use a balanced tree with dynamic node allocation, using timestamp field as the comparison criterion. O Keep a linked list of dynamically allocated elements and append to the end of it: perform merge sort before iterating if needed. O Store elements in a hashmap (mapping from timestamp to the object) with reasonable number of buckets. O Preallocate an array and use timestamp as index in it. When we need to iterate, check all possible timestamps for associated objects. Clear selection

Explanation / Answer

Solution:

The correct choices are:

Use a balanced tree with dynamic node allocation, using timestamp field as the comparison criterion.

Explanation:

Because balanced tree will provide O(log n) time of search after the object is inserted.

Store elements in a hashmap (mapping from timestamp to the object) with reasonable number of buckets.

Explanation:

Hash maps will provide best searching time.

Preallocate an array and use timestamp as Index in It. When we need to iterate, check all possible timestamps for associated objects.

This is the optimal way of doing it.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.