Decode the Coding Interview in Rust: 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:

Press + to interact
fn reconstruct_queue(process:&mut Vec<Vec<i32>>)-> Vec<Vec<i32>> {
        
        let mut temp: Vec<(i32,i32)> = Vec::new();
        let mut temp2: Vec<(i32,i32)> = vec![(0,0);process.len()];
        
        for k in 0..process.len()
        {
            temp.push((process[k][0], process[k][1]));
        }
        // First sort priorities by priority and then by the k value.
        // priority in descending order and k value in ascending order.
         temp.sort();
         temp.reverse();
        for i in 0..temp.len()-1
        {
            if temp[i].0 == temp[i+1].0
            {
                if temp[i].1 >temp[i+1].1
                {
                    let t =temp[i];
                    temp[i] = temp[i+1];
                    temp[i+1] =t;
                }
            }
        }
        for i in 0..temp.len(){
            temp2.insert(temp[i].1 as usize, temp[i]);
        }
        // Place the result back in original 2d array
        for l in 0..process.len(){
            process[l][0] = temp2[l].0;
            process[l][1] = temp2[l].1;
        }
        return process.to_vec();
    }
fn main(){
  let mut p: Vec<Vec<i32>> =  vec![vec![7,0], vec![4,4],vec![7,1],vec![5,0],vec![6,1],vec![5,2]];
  let sol = reconstruct_queue(&mut p);
    println!("{:?}",sol);
}
...