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

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("]");
}
...