Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Feature #15: Queue Reconstruction by Priority

Explore how to reconstruct a process queue from priority and position information when the original order is lost. Learn the sorting and insertion method to reorder processes by priority and number of higher priority processes ahead. Understand the time and space complexity involved in this operating system feature.

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:

Go (1.16.5)
package main
import (
  "fmt"
  "sort"
)
type Tuple struct{
  a int
  b int
}
func ReconstructQueue(process [][]int) [][]int{
  temp := make([]Tuple, 0)
  temp2 := make([]Tuple, len(process))
  for i := 0; i < len(process); i++{
    t := Tuple{a : process[i][0], b : process[i][1]}
    temp = append(temp, t)
  }
  // First sort processes by priority and then by the k value.
  // priority in descending order and k value in ascending order.
  sort.SliceStable(temp, func(i, j int) bool {
    return temp[i].a > temp[j].a
  })
  sort.SliceStable(temp, func(i, j int) bool {
    return (temp[i].a == temp[j].a && temp[i].b < temp[j].b)
  })
  for i := 0; i < len(temp); i++ {
    index := temp[i].b
    temp2 = append(temp2[:index+1], temp2[index:]...)
    temp2[index] = temp[i]
  }
  // Place the result back in original 2d array
  for l := 0; l < len(process); l++ {
      process[l][0] = temp2[l].a
      process[l][1] = temp2[l].b
  }
  return process
}
func main() {
    p := [][]int{{7,0}, {4,4},{7,1},{5,0},{6,1},{5,2}}
    sol := ReconstructQueue(p);
    fmt.Print("[");
    for i := 0; i < len(sol) ; i++ {
        fmt.Print("[");
        for j := 0; j < len(sol[0]) ; j++ {
            fmt.Print(sol[i][j]);
            if(j==0) { fmt.Print(","); }        
        }
        fmt.Print("]");
        if i != len(sol) - 1 {  fmt.Print(",") }       
    }
    fmt.Print("]");
}
...