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, 2017public class GetMinTimeForAssignedTask { public static void main(String[] args) { int[] nums = new int[]{1,1,1,2,2,2}; int k = 2; System.out.println(getMiniTime(nums, k)); } static int getMiniTime(int[] nums, int k){ int max = 0; for (int i = 0; i < nums.length; i++) { max = Math.max(max, nums[i]); } int[] arr = new int[max+1]; int t = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { t = Math.min(t, allocate(nums, arr, k, i, new Time(), 0).minTime); } return t; } //111222 static Time allocate(int[] nums, int[] arr, int k, int task, Time time, int st){ if(null == nums && null == arr) return time; boolean done = true; for (int i = 0; i < nums.length; i++) { if(nums[i] > 0){ done = false; break; } } if(done) { time.minTime = Math.min(time.minTime, time.time); return time; } boolean assigned = false; for (int i = st; i < nums.length; i++) { if(arr[nums[i]] == 0 && nums[i] > 0){ for (int j = 0; j < arr.length; j++) { if(arr[j] > 0) arr[j]--; } assigned = true; int u = nums[i]; arr[nums[i]] = k; nums[i] = 0; time.time += 1; if(st == nums.length-1) st = 0; time = allocate(nums, arr, k, i, time, st+1); nums[i] = u; time.time -= 1; } } if(!assigned){ for (int j = 0; j < arr.length; j++) { if(arr[j] > 0) arr[j]--; } time.time += 1; time = allocate(nums, arr, k, 0, time, 0); } return time; } } class Time{ int time; int minTime = Integer.MAX_VALUE; }