1. Data Structure Design for Timestamped Objects

Problem Description

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:

• 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.
• Objects will never be removed from the container.
• Occasionally, you will need to iterate over all stored objects in a sorted by timestamp order.
• The container is never shared among different threads.

Acceptable Designs (Pick ONE OR MORE 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; 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.

2. Concurrent Container Implementation Review

Problem Description

struct concurrent_container  
{  
    void construct(int N)  
    {  
        init_mutex(&lock);  
        resize(N);  
    }  

    int get(int index)  
    {  
        lock.acquire();  
        if (index < 0 || index >= size) {  
            return INT_MAX;  
        }  
        int result = data[index];  
        lock.release();  
        return result;  
    }  

    void set(int index, int value)  
    {  
        lock.acquire();  
        if (index < 0 || index >= size) {  
            return;  
        }  
        data[index] = value;  
        lock.release();  
    }  

    void resize(int N)  
    {  
        lock.acquire();  
        size = N;
        data = (int*) malloc(size);
        for (int i = 0; i < size; ++i)
            data[i] = 0;
        lock.release();  
    }  

    void destroy()  
    {  
        free(data);  
        data = NULL;
        size = 0;
        destroy_mutex(&lock);
    }  

    mutex lock;  
    int size;  
    int* data;  
};

Detected Problems (Pick ONE OR MORE options)

• The implementation can cause a resource leak.
• The implementation can cause a memory corruption.
• The implementation is not protected from integer overflow errors.

我们长期稳定承接各大科技公司如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.