## Facebook Interview Question

SDE1s**Country:**United States

```
public static void main(String[] args) throws Exception {
int[] nums = {1,1,1,2,2,2,3,4};
int k =2;
System.out.println(getMinTime(nums,k));
}
static int getMinTime(int[] nums, int k) {
Arrays.sort(nums);
StringBuilder slots = new StringBuilder();
slots.append(nums[0]);
for (int i = 1; i < nums.length; i++) {
int lastPos = slots.lastIndexOf(nums[i]+"");
if(lastPos == -1) {
int slotsPos = slots.indexOf("_");
if(slotsPos == -1)
slots.append(nums[i]);
else {
slots.deleteCharAt(slotsPos);
slots.insert(slotsPos,nums[i]);
}
} else {
int slotsPos = lastPos + k;
if(slots.length() <= slotsPos) {
for (int j = 0; j < k; j++) {
slots.append("_");
}
slots.append(nums[i]);
} else {
if(slots.charAt(slotsPos) == '_') {
slots.deleteCharAt(slotsPos);
slots.insert(slotsPos,nums[i]);
} else {
while(slotsPos < slots.length() && slots.charAt(slotsPos) != '_') {
slotsPos ++;
}
if(slots.length() <= slotsPos) {
slots.append(nums[i]);
} else {
slots.deleteCharAt(slotsPos);
slots.insert(slotsPos,nums[i]);
}
}
}
}
}
return slots.length();
}
```

Observations:

1. Minimum finish time will occur if the scheduler is work conserving (or as close to it as possible)

2. For this to happen, in a particular time slot out of all runnable tasks, pick one which has higher repeat count left. In case the counts are equal, ties can be broken arbitrarily using task id

To achieve the above,

struct task{

int id;

int cnt; //remaining repeats

int next_time; // value when the task can be re-executed

};

- Iterate the array of inputs and create an array(or unordered_map) of unique tasks.

For example, for 111222

create a map:

1 => id:1, cnt=3, next_time:0

2 => id:1, cnt=3, next_time:0

Create a priority queue which compares based on the following criterion:

Higher priority is given to tasks

- with lower next_time

- in case 2 tasks have same next_time, then prioritize the one with higher cnt

- in case both above conditions are the same, break ties based on smaller id first

```
set time = 0;
Enqueue all the tasks in this queue.
Now process while the queue is not empty:
- x <-- pop the top task
- update time as : time += max(time, x.time) + 1 // 1 is the duration for which a task runs
- x.cnt--
-if (x.cnt > 0)
- update x.time = time + k
- push x back into the queue
- return time as the final output
```

Given an array of task and k wait time for which a repeated task

needs to wait k time to execute again. please rearrange the task

sequences to minimize the total time to finish all the tasks.

Example

Tasks = 111222, k = 2,

One possible task sequence is

12_12_12,

another possible task sequence is 21_21_21

thus you shoud return 8

public int getMiniTime(int[] nums, int k){

}

follow up, output one of the sequence 12_12_12, or 21_21_21

```
using System;
using System.Collections.Generic;
using System.Linq;
namespace Permutation
{
class Program
{
int[] arr = new int[6] { 1, 1, 1, 1, 1, 1 };
Dictionary<int, int> runningProcess = new Dictionary<int, int>();
int[] visited;
public void GetMiniTime(int[] arr)
{
visited = new Int32[arr.Length];
int count =0;
while(count<arr.Length)
{
int tmp = NextElement(arr, visited);
if (tmp == Int32.MinValue)
{
DecrementWaitTime();
Console.Write("_");
}
else
{
Console.Write(tmp);
count++;
}
}
}
public int NextElement(int[] input, int[] visited)
{
for (int i = 0; i < input.Length;i++ )
{
if(visited[i]==0)
{
if(CheckStatus(input[i]))
{
visited[i] = -1;
return input[i];
}
}
}
return Int32.MinValue;
}
public bool CheckStatus(int tmp)
{
if (!runningProcess.ContainsKey(tmp))
{
DecrementWaitTime();
runningProcess.Add(tmp, 2);
return true;
}
return false;
}
public void DecrementWaitTime()
{
for (int i = 0; i < runningProcess.Count; i++)
{
int waittime = runningProcess.Values.ElementAt(i);
int key = runningProcess.Keys.ElementAt(i);
waittime--;
runningProcess[key] = waittime;
}
RemoveZeros();
}
public void RemoveZeros()
{
List<int> list = new List<int>();
foreach(int i in runningProcess.Keys)
{
int waittime = runningProcess[i];
if (waittime <= 0)
list.Add(i);
}
foreach (int i in list)
runningProcess.Remove(i);
}
static void Main(string[] args)
{
Program p = new Program();
p.GetMiniTime(p.arr);
Console.ReadLine();
}
}
}
```

import collections

import heapq

class Solution:

def getMinTime(self, tasks, interval):

counter = collections.Counter(tasks)

heap = [(0, key, count) for key, count in dict(counter).items()]

time = 0

while len(heap) > 0:

t, k, c = heap[0]

if t <= time:

t, k, c = heapq.heappop(heap)

if c > 1:

t = interval + time + 1

c -= 1

heapq.heappush(heap, (t, k, c))

time += 1

return time

```
import collections
import heapq
class Solution:
def getMinTime(self, tasks, interval):
counter = collections.Counter(tasks)
heap = [(0, key, count) for key, count in dict(counter).items()]
time = 0
while len(heap) > 0:
t, k, c = heap[0]
if t <= time:
t, k, c = heapq.heappop(heap)
if c > 1:
t = interval + time + 1
c -= 1
heapq.heappush(heap, (t, k, c))
time += 1
return time
```

- sudip.innovates April 06, 2017