1. Question 1

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.

---

Question

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.

---

Options

• [ ] Store all objects in an array; append to the end; perform quicksort before we need to iterate if needed.
• [ ] Store all objects in an array; append to the end and perform in-place merge sort after each insertion if needed.
• [ ] Store all objects in an array; keep it sorted by inserting any new object at the appropriate position.
• [ ] Use a balanced tree with dynamic node allocation, using timestamp field as the comparison criterion.
• [ ] Keep a linked list of dynamically allocated elements and append to the end of it; perform merge sort before iterating if needed.
• [ ] Store elements in a hashmap (mapping from timestamp to the object) with a reasonable number of buckets.
• [ ] Preallocate an array and use timestamp as index in it. When we need to iterate, check all possible timestamps for associated objects.

---

3. Question 3

Complete the blanks in the following question with the appropriate answer.

Suppose you want to store the following properties per each memory page:

1. Page status - one of:
   • a) In use (has some useful data)
   • b) Dirty (stored data previously, ready to be reused)
   • c) Free (never stored any data)
2. Page index - an integer in range [0, 368447]
3. Access mode - one of:
   • a) Read-only
   • b) Write-only
   • c) Execute only
   • d) Can read and write
   • e) Can read and execute
   • f) Can read, write, and execute
4. Process ID - an integer in range [0, 37337], storing the process ID the page is allocated to

---

Question:

Assuming we need to keep the direct field access API as simple as possible (e.g., we can’t have an additional compression layer), what is the minimal number of bytes we need to store a single record?

---

Bit Calculation:

• Page Status (3 values) → Needs 2 bits (since 2² = 4, which covers 3 values).
• Page Index (0 to 368447) → Needs 19 bits (since 2¹⁹ = 524288, which covers 368447).
• Access Mode (6 values) → Needs 3 bits (since 2³ = 8, which covers 6 values).
• Process ID (0 to 37337) → Needs 16 bits (since 2¹⁶ = 65536, which covers 37337).

Total bits required:
2 + 19 + 3 + 16 = 40 bits

Since storage is typically done in bytes, we round up:
40 bits = 5 bytes

---

Final Answer:

5 bytes

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.