Decode the Coding Interview in C++: Real-World Examples/

...

/

Feature #15: Queue Reconstruction by Priority

Feature #15: Queue Reconstruction by Priority

Implement the "Queue Reconstruction by Priority" feature for our "Operating System" project.

We'll cover the following...

Description

A process queue contains the process priority. It also contains the number of processes ahead of a process in the queue that has a priority not less than its own. Suppose that the OS crashed and now we only have an array of processes, with each process at a random position in the array. In this feature, we’ll reconstruct the process queue from the information available to us.

Each element in the 2D array consists of a process’s priority and the number of processes with a higher or equal priority that are ahead of it in the queue. An entry [pi, ki] represents that a process with priority pi has ki other processes, with a priority of at least pi, ahead of it in the queue.

Our task is to reconstruct and return the process queue.

Let’s look at a few examples of this:

Solution

A process with a lower priority does not affect the placement of k processes with a higher priority. So, we will first insert the processes with a higher priority, into the output array. We will start by sorting the input array in descending order of process priority, and then in ascending order of the k-value. We will:

  • Sort the processes by priority, in a descending order.
  • Sort the processes with the same priority in ascending order of k.

We will pick elements from the sorted array, starting at index 0. If the element picked is [pi, ki], it will be inserted at index k in the output array. The following slides demonstrate this procedure:

Let’s take a look at an example of this:

std::vector<std::vector<int>> reconstructQueue(std::vector<std::vector<int>>& process) {
    
    std::vector<std::pair<int, int>> temp;
    std::vector<std::pair<int, int>> temp2(process.size());
    for (int k = 0; k < process.size(); k++)
    {
        temp.push_back({process[k][0], process[k][1]});
    }
    // First sort processes by priority and then by the k value.
    // priority in descending order and k value in ascending order.
    std::sort(temp.begin(), temp.end(), [](std::pair<int, int> p1, std::pair<int, int> p2){
        return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
    });
    for (int i = 0; i < temp.size(); i++){
        temp2.insert(temp2.begin() + temp[i].second, temp[i]);
    }
    // Place the result back in original 2d array
    for (int l = 0; l < process.size(); l++){
        process[l][0] = temp2[l].first;
        process[l][1] = temp2[l].second;
    }
    return process;
}
int main() {
    // Driver Code
    std::vector<std::vector<int>> p =  {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    auto sol = reconstructQueue(p);
    print(sol);
    return 0;
}
Queue reconstruction by priority

Complexity

...