Decode the Coding Interview in Elixir: 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
defmodule Solution do
  def reconstruct_queue(people) do
    output = []
    # Convert initial lists to tuples
    people = people |> Enum.map(fn x -> x |> List.to_tuple end)
    # First sort priorities by priority and then by the k value.
    # priority in descending order and k value in ascending order.
    people = people |> Enum.sort(&(elem(&1, 0) >= elem(&2, 0)))
    # Iterate over the sorted list people and add people[i] at index people[i][1] 
    # of output list.
    people = 
      people 
      |> Enum.reduce(output, fn(p, output) ->
        List.insert_at(output, elem(p, 1), p)
      end)
     # Convert initial tuples back to list
    people |> Enum.map(fn x -> x |> Tuple.to_list end)
  end
end
# Driver Code
IO.puts "-----------------------------"
IO.puts "PROGRAM OUTPUT:"
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
IO.inspect Solution.reconstruct_queue(people)
...