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:

using System;
using System.Collections.Generic;
public class Solution {
    public static int[][] ReconstructQueue(int[][] process) {
        
        List<Tuple<int, int>> temp = new List<Tuple<int, int>>();
        List<Tuple<int, int>> temp2 = new List<Tuple<int, int>>(process.GetLength(0));
        for (int k = 0; k < process.GetLength(0); k++)
        {
            temp.Add(new Tuple<int, int>(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.
        temp.Sort((x, y) => { 
            int result = y.Item1.CompareTo(x.Item1); 
            return result == 0 ? x.Item2.CompareTo(y.Item2) : result; 
        });
        for (int i = 0; i < temp.Count; i++){
            temp2.Insert(temp[i].Item2, temp[i]);
        }
        // Place the result back in original 2d array
        for (int l = 0; l < process.GetLength(0); l++){
            process[l][0] = temp2[l].Item1;
            process[l][1] = temp2[l].Item2;
        }
        return process;
    }
    static void Main(){
        int[][] p =  new int[6][]{new []{7,0}, new []{4,4},new []{7,1},new []{5,0},new []{6,1},new []{5,2}};
        var sol = ReconstructQueue(p);
        System.Console.Write("[");
        for(int i = 0; i < sol.Length ; i++){
            System.Console.Write("[");
            for(int j = 0; j < sol[0].Length ; j++){
                System.Console.Write(sol[i][j]);
                if(j==0)
                    System.Console.Write(",");
            }
            System.Console.Write("]");
            if(i!=(sol.Length-1))
                System.Console.Write(",");
        }
        System.Console.Write("]");
    }
}
Queue Reconstruction by Priority
...