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

import Swift
func ReconstructQueue(process: inout [[Int]]) -> [[Int]] {
    
    var temp: [(Int, Int)] = []
    var temp2: [(Int, Int)] = Array(repeating: (0, 0), count: process.count)
    var k: Int = 0
    while k < process.count
    {
        temp.append((process[k][0], process[k][1]))
        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 { ($0.0 == $1.0) ? $0.1 < $1.1 : $0.0 > $1.0 }
    var i: Int = 0
    while i < temp.count {
        temp2.insert(temp[i], at: temp[i].1)
        i += 1
    }
    var l: Int = 0
    // Place the result back in original 2d array
    while l < process.count {
        process[l][0] = temp2[l].0
        process[l][1] = temp2[l].1
        l += 1
    }
    return process
}
    var p: [[Int]] =  [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    var sol: [[Int]] = ReconstructQueue(process: &p)
    print("[", terminator: "")
    var i: Int = 0
    var j: Int = 0
    while i < sol.count {
        print("[", terminator: "")
        j = 0
        while j < sol[0].count {
            print(sol[i][j], terminator: "")
            if j == 0 {
                print(",", terminator: "")
            }
            
            j += 1
        }
        print("]", terminator: "")
        if i != sol.count-1 {
            print(",", terminator: "")
        }
        i += 1
    }
    print("]")
Queue reconstruction by priority
...