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.

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 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; 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.

---

2. Question 2

Use the HTTP GET method to retrieve information from a database of restaurant information. Query
https://jsonmock.hackerrank.com/api/food_outlets?city=<city>
to find all the records. The query result is paginated and can be further accessed by appending to the query string &page=<num> where num is the page number.

The response is a JSON object with the following five fields:

• page: The current page of the results. (Number)
• per_page: The maximum number of results returned per page. (Number)
• total: The total number of results. (Number)
• total_pages: The total number of pages with results. (Number)
• data: Either an empty array or one that contains the food outlet records.

In data, each food outlet has the following schema:

• id: outlet id (Number)
• name: The name of the outlet (String)
• city: The city in which the outlet is located (String)
• estimated_cost: The estimated cost of the food in the particular outlet (Number)
• user_rating: An object containing the user ratings in the following schema:
  • average_rating: The average user rating for the outlet (Number)
  • votes: The number of people who voted for the outlet (Number)

Given the function arguments city and cost, find the food outlet in the city that has the highest rating and whose estimated_cost is at most cost. If there are multiple restaurants that tie for the highest rating, return the one with the lowest expected cost.

Function Description

Complete the function bestRestaurant in the editor below.

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.

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 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; 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.

---

2. Question 2

Consider the following implementation of a container that will be used in a concurrent environment. The container is supposed to be used like an indexed array, but provide thread-safe access to elements.

struct concurrent_container  
{  
    // assume it's called for any new instance once before it's ever used  
    void construct(int N)  
    {  
        init_mutex(&lock);  
        resize(N);  
    }  

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

        return result;  
    }  

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

    // extend maximum capacity of the container so we can add more elements  
    void resize(int N)  
    {  
        lock.acquire();  
        size = N;  

(Truncated code)

---

3. Question 3

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

Jim wrote the following program to perform a depth-first search (DFS) in a binary tree:

struct Node  
{  
    int value;  
    Node * parent;  
    Node * left_child;  
    Node * right_child;  
    bool visited;  
};  

Node * dfs(Node * node, int target)  
{  
    printf("%d ", node->value);  
    node->visited = true;  

    if (node->value == target) {  
        return node;  
    }  

    Node * nodes[3] = {node->right_child,  
                       node->parent,  
                       node->left_child};  

    for (int i = 0; i < 3; ++i)  
        if (nodes[i] && !nodes[i]->visited)  
        {  
            Node * result = dfs(nodes[i], target);  
            if (result) {  
                return result;  
            }  
        }  

    return NULL;  
}  

---

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