Facebook Interview Question
SDE1sCountry: United States
function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
var taskCounter =0;
for(i=0; i< workers; i++)
{
var moveNext = false;
var currentLoad = 0;
while(!moveNext && taskCounter < tasks.length)
{
if((currentLoad ==0 || i == workers -1 || (currentLoad + tasks[taskCounter]) < mean))
currentLoad += tasks[taskCounter++];
else
moveNext = true;
}
allocation.push(currentLoad);
}
console.log(allocation.sort(function(a,b){return b-a;})[0]);
}
getMini([2,2,36,3,5,2,4,46,76,4,23,12,41,63,34,1,13,7,3,21,4,7,1],5)
function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
var taskCounter =0;
for(i=0; i< workers; i++)
{
var moveNext = false;
var currentLoad = 0;
while(!moveNext && taskCounter < tasks.length)
{
if((currentLoad ==0 || i == workers -1 || (currentLoad + tasks[taskCounter]) < mean))
currentLoad += tasks[taskCounter++];
else
moveNext = true;
}
allocation.push(currentLoad);
}
console.log(allocation.sort(function(a,b){return b-a;})[0]);
}
getMini([2,2,36,3,5,2,4,46,76,4,23,12,41,63,34,1,13,7,3,21,4,7,1],5)
def find_loc(scheduler, task):
w_times = []
for wrkr in scheduler:
w_times.append(sum(wrkr))
max_time = max(w_times)
avail_time = 0
loc = 0
for i in range(len(scheduler)):
if max_time-w_times[i] > avail_time:
avail_time = max_time-w_times[i]
loc = i
return loc
def get_min_time(a, n):
a.sort(reverse=True)
print a
scheduler = [[] for i in range(n)]
scheduler[0].append(a[0])
i = 1
while i < len(a):
loc = find_loc(scheduler, a[i])
scheduler[loc].append(a[i])
i+=1
return scheduler
if __name__ == '__main__':
scheduler = get_min_time([2, 2, 3, 7, 1], 3)
print scheduler
def find_loc(scheduler, task):
w_times = []
for wrkr in scheduler:
w_times.append(sum(wrkr))
max_time = max(w_times)
avail_time = 0
loc = 0
for i in range(len(scheduler)):
if max_time-w_times[i] > avail_time:
avail_time = max_time-w_times[i]
loc = i
return loc
def get_min_time(a, n):
a.sort(reverse=True)
print a
scheduler = [[] for i in range(n)]
scheduler[0].append(a[0])
i = 1
while i < len(a):
loc = find_loc(scheduler, a[i])
scheduler[loc].append(a[i])
i+=1
return scheduler
if __name__ == '__main__':
scheduler = get_min_time([2, 2, 3, 7, 1], 3)
print scheduler
This looks like a greedy algorithm problem since task with longest running time cannot be scheduled later as it would increase the time.
public int getMini(int[] tasks, int k){
if(tasks == null || k <= 0){
return -1;
}
Heap<int> heap = heapify(tasks); // max heap
int[] workers = new int[k];
Heap<int> wHeap = heapify(workers); //min heap
while(heap.Count != 0){
int taskTime = heap.Remove(); // get max task time
int w = wheap.Remove(); // get worker with minimum end time
wheap.Insert(w+time); // update worker
}
return heap.Max();
}
This problem looks like a modification of partition problem which is a NP-complete problem i.e. exponential time. Like any NPC problem this can also be done in exponential however since we are worried about reducing the time we can probably do this as below in polynomial time.
The solution below runs in O(NLogN) + O(n*k):
public class TasksAndWorkers {
public int getMini(int[] tasks, int k) {
if(tasks == null || tasks.length == 0 || k <= 0) {
return 0; // error condition
}
int[] workers = new int[k];
// NlogN time
Arrays.sort(tasks);
// Takes n*k time, we are going in desc order so we know the i task will always take less than i+1 task
for(int i = tasks.length - 1; i >= 0 ; i--) {
int index = getCurrentMinWorker(workers);
workers[index] += tasks[i];
}
int minWorker = getCurrentMinWorker(workers);
return workers[minWorker];
}
public int getCurrentMinWorker(int[] workers) {
int index = 0;
for(int i = 0; i <= workers.length - 1; i++) {
if(workers[index] <= workers[i]) {
index = i;
}
}
return index;
}
}
I could have removed the sorting time by not sorting the array and that would have given me the same max time needed by the most time consuming worker but other workers may not ave been ideally utilitized i.e. it could result in:
W1- 300
W2 - 15+2+1
W3- 7
Sorting helps us use all workers to max capacity
Possible solution is to use binary min heap to distribute all tasks payload.
First we create min heap with N nodes (workers)
Sort task array to distribute tasks evenly from most expensive to lowers
increase key of most low task. O(1) for localize min and O(log(n)) to increase
get max node in heap O(n)
class HeapMin
{
public:
HeapMin()
: m_heap(nullptr)
, m_last(-1)
, m_size(0)
{ m_size = reallocate();}
~HeapMin() { delete m_heap;}
void insert(int value)
{
if (m_last == m_size - 1){
m_size = reallocate();
}
m_heap[++m_last] = value;
insert_impl(m_last);
}
void increase_min(int val)
{
if (!m_heap){
return;
}
m_heap[0] += val;
min_heapify(0, m_last + 1);
}
int min()
{
int min = INT_MIN;
if (m_heap && m_last >= 0) {
min = m_heap[0];
}
return min;
}
int max()
{
int max = INT_MIN;
if (m_heap && m_last >= 0)
{
max = m_heap[0];
for (int i = 1; i < m_last + 1; ++i) {
if (m_heap[i] > max) {
max = m_heap[i];
}
}
}
return max;
}
static int LEFT(int i) { return 2 * i + 1; }
static int RIGHT(int i) { return 2 * i + 2; }
static int PARENT(int i) { return (i - 1) / 2; }
protected:
void min_heapify(int i, int len)
{
int lowest = i;
int lhs = LEFT(i);
if (lhs < len && m_heap[lhs] < m_heap[i]){
lowest = lhs;
}
int rhs = RIGHT(i);
if (rhs < len && m_heap[rhs] < m_heap[lowest]) {
lowest = lhs;
}
if (i != lowest)
{
std::swap(m_heap[i], m_heap[lowest]);
min_heapify(lowest, len);
}
}
void insert_impl(int i)
{
if (i == 0){
return;
}
int parent = PARENT(i);
if (m_heap[parent] > m_heap[i])
{
std::swap(m_heap[parent], m_heap[i]);
insert_impl(parent);
}
}
int reallocate()
{
int size = m_size;
if (!m_heap)
{
size = m_size == 0 ? 127 : m_size;
m_heap = new int [size];
}
else
{
size = size * 2 + 1;
int *new_alloc = new int[size];
memcpy(static_cast<void*>(new_alloc), static_cast<void*>(m_heap), sizeof(m_heap) * sizeof(int));
delete m_heap;
m_heap = new_alloc;
}
return size;
}
private:
int *m_heap;
int m_size;
int m_last;
};
TEST(Heap, MinHeap_calc_task_max_min)
{
int tasks[] = { 2, 2, 3, 7, 1 };
HeapMin heap;
heap.insert(0); // add worker 1
heap.insert(0); // add worker 2
const int SIZE = sizeof(tasks) / sizeof(int);
std::sort(tasks, tasks + SIZE);
for (int i = SIZE - 1; i >= 0; --i) {
heap.increase_min(tasks[i]);
}
EXPECT_EQ(heap.min(), 7);
EXPECT_EQ(heap.max(), 8);
}
import heapq
def getMini(tasks,worker):
tot = sum(tasks)
#sort tasks
tasks.sort(reverse=True) # put in the largest time first
# the idea is to get as averaged as possible,
# every iteration we add the smallest value to the currently smallest worker
times = [0]*worker
heapq.heapify(times)
for i in tasks:
t=heapq.heappop(times)
heapq.heappush(times,(t+i))
return max(times)
int getMinimum(vector<int> tasks, int workers) {
priority_queue<int, std::vector<int>, std::greater<int>> pq;
for (int i = 0; i < workers; i++) {
pq.push(0);
}
sort(tasks.begin(), tasks.end());
for (int i = tasks.size() - 1; i >= 0; --i) {
int top = pq.top();
pq.pop();
pq.push(top + tasks[i]);
}
while (pq.size() > 1)
pq.pop();
int res = pq.top();
return res;
}
This is the optimal solution with complexity O(m^n) where m is the number of workers, and n is the number of jobs.
public class WorkerJobAllocation {
public static ArrayList<int[]> getArrangements(int[] jobTimes, int currentJob, int k) {
ArrayList<int[]> arrangements = new ArrayList<int[]>();
if (currentJob == jobTimes.length - 1) {
// for each worker, we create a partial arrangement with the last job allocated to that worker
for (int w = 0; w < k; ++w) {
int[] arrangement = new int[jobTimes.length];
arrangement[currentJob] = w;
arrangements.add(arrangement);
}
return arrangements;
}
for (int w = 0; w < k; ++w) {
// for each worker, we get the partial arrangements that allocate all jobs > currentJob
// then create a new partial arrangement with the currentJob allocated to that worker
ArrayList<int[]> partial = getArrangements(jobTimes, currentJob + 1, k);
for (int[] arrangement : partial) {
int[] newArrangement = arrangement.clone();
newArrangement[currentJob] = w;
arrangements.add(newArrangement);
}
}
return arrangements;
}
public static int getMinimum(int[] jobTimes, int k) {
if (jobTimes.length < 1) return 0;
ArrayList<int[]> arrangements = getArrangements(jobTimes, 0, k);
System.out.println("All arrangements:");
for (int[] arrangement : arrangements) {
printArrangement(arrangement, jobTimes, k);
}
System.out.println();
int minimum = Integer.MAX_VALUE;
int[] bestArrangement = null;
for (int[] arrangement : arrangements) {
int[] workerTimes = new int[k];
for (int job = 0; job < arrangement.length; ++job) {
workerTimes[arrangement[job]] += jobTimes[job];
}
int arrangementTime = Integer.MIN_VALUE;
for (int time : workerTimes) {
if (time > arrangementTime) arrangementTime = time;
}
if (arrangementTime < minimum) {
minimum = arrangementTime;
bestArrangement = arrangement;
}
}
System.out.println("Best arrangement:");
printArrangement(bestArrangement, jobTimes, k);
return minimum;
}
public static void main(String[] args) {
int[] jobTimes = new int[] {2, 2, 3, 3, 1};
int k = 4;
int min = getMinimum(jobTimes, k);
System.out.println(min);
}
public static void printArrangement(int[] arrangement, int[] jobTimes, int k) {
HashMap<Integer, ArrayList<Integer>> workerToJobs = new HashMap<Integer, ArrayList<Integer>>();
for (int w = 0; w < k; ++w) {
workerToJobs.put(w, new ArrayList<Integer>());
}
for (int j = 0; j < arrangement.length; ++j) {
workerToJobs.get(arrangement[j]).add(j);
}
int charactersAvailable = 30;
for (int w = 0; w < k; ++w) {
String s = "W" + w + ": { ";
for (int j : workerToJobs.get(w)) {
s += jobTimes[j] + " ";
}
s += "}";
int remaining = charactersAvailable - s.length();
for (int i = 0; i < remaining; ++i) s += " ";
System.out.print(s);
}
System.out.println();
}
}
Console.WriteLine("number of workers vs number of tasks");
int[] listOfTaksWithHoursValue = new int[9];
intRand = new Random();
for (int i = 0; i < 9; i++)
{
listOfTaksWithHoursValue[i] = intRand.Next(1, 8);
Console.WriteLine("Hours to complete for task " + i + " is:" + listOfTaksWithHoursValue[i]);
}
var totalHours = TasksForNumberOfWorkers(listOfTaksWithHoursValue, 2);
Console.WriteLine("with {0} minium hours needed to compelte these tasks {1}", 2, totalHours);
int TasksForNumberOfWorkers(int[] inputArray, int numberOfWorkers)
{
int totalHoursNeed = 0;
int maxHoursNeededForOneDay = 0;
for (int i = 0; i < inputArray.Length; i++)
{
totalHoursNeed = totalHoursNeed + inputArray[i];
if(maxHoursNeededForOneDay < 9)
{
maxHoursNeededForOneDay = maxHoursNeededForOneDay + inputArray[i];
}
}
if(totalHoursNeed/numberOfWorkers <= maxHoursNeededForOneDay)
{
return maxHoursNeededForOneDay;
}
else
{
return totalHoursNeed / numberOfWorkers;
}
}
Console.WriteLine("number of workers vs number of tasks");
int[] listOfTaksWithHoursValue = new int[9];
intRand = new Random();
for (int i = 0; i < 9; i++)
{
listOfTaksWithHoursValue[i] = intRand.Next(1, 8);
Console.WriteLine("Hours to complete for task " + i + " is:" + listOfTaksWithHoursValue[i]);
}
var totalHours = TasksForNumberOfWorkers(listOfTaksWithHoursValue, 2);
Console.WriteLine("with {0} minium hours needed to compelte these tasks {1}", 2, totalHours);
int TasksForNumberOfWorkers(int[] inputArray, int numberOfWorkers)
{
int totalHoursNeed = 0;
int maxHoursNeededForOneDay = 0;
for (int i = 0; i < inputArray.Length; i++)
{
totalHoursNeed = totalHoursNeed + inputArray[i];
if(maxHoursNeededForOneDay < 9)
{
maxHoursNeededForOneDay = maxHoursNeededForOneDay + inputArray[i];
}
}
if(totalHoursNeed/numberOfWorkers <= maxHoursNeededForOneDay)
{
return maxHoursNeededForOneDay;
}
else
{
return totalHoursNeed / numberOfWorkers;
}
}
Python solution: Follows Greedy approach by picking the most time consuming task and assigning to the most vacant worker. Complexity to sort the task nlogn and searching for least vacant labor n*m. Overall, time complexity (nlogn + nm)
def tassign(tasks, workers):
tasks = sorted(tasks, reverse=True)
assign = [0] * workers
for task in tasks:
# find the worker with min assignment
current, last, lidx = None, None, None
for idx in range(len(assign)):
a = assign[idx]
current = a
if last is None or last > current:
last = current
lidx = idx
assign[lidx] += task
print assign
return max(assign)
{{
import java.io.*;
import java.util.*;
class Solution {
public static void main(String[] args) {
int[] tasks = {2,2,3,7,1};
int[] taskDesc = new int[tasks.length];
int k = 2;
int[] worker = new int[k];
Arrays.sort(tasks);
//reverse array
int i = 0;
int j = tasks.length - 1;
while (i < tasks.length) {
taskDesc[j] = tasks[i];
i++;
j--;
}
//maintain an array of numbers which correspond to the workers
for(int n = 0; n < tasks.length; n++) {
int minWorker = findMin(worker);
//assign the next task to the minworker
worker[minWorker] += taskDesc[n];
}
System.out.println(getMaxValue(worker));
}//main
public static int findMin(int[] array) {
int minValue = array[0];
int minId = 0;
for (int i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
minId = i;
}
}
return minId;
}
public static int getMaxValue(int[] array) {
int maxValue = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > maxValue) {
maxValue = array[i];
}
}
return maxValue;
}
}//solution
}}
The greedy algorithm (sorting tasks in descending order and filling the least loaded worker so far) doesn't guarantee the optimal solution. E.g. 2 workers and these tasks: 9,8,7,5,3.
Looks like it's needed to iterate through all combinations of assignment a task to a worker:
bool BalanceSetNewComb(vector<int> &task_worker, int workers_count)
{
int i = 0;
for (; i < task_worker.size(); i++) {
++task_worker[i];
if (task_worker[i] < workers_count) {
break;
}
task_worker[i] = 0;
}
return i < task_worker.size();
}
int BalanceGetCombTime(vector<int> const &tasks, vector<int> const &task_worker, int workers_count)
{
vector<int> worker_time;
worker_time.resize(workers_count, 0);
int max_time = 0;
for (int i = 0; i < tasks.size(); ++i) {
int worker = task_worker[i];
worker_time[worker] += tasks[i];
max_time = max(max_time, worker_time[worker]);
}
return max_time;
}
int Balance(vector<int> const &tasks, int workers_count)
{
vector<int> task_worker;
task_worker.resize(tasks.size(), 0);
int min_time = numeric_limits<int>::max();
do {
int time = BalanceGetCombTime(tasks, task_worker, workers_count);
min_time = min(min_time, time);
} while (BalanceSetNewComb(task_worker, workers_count));
return min_time;
}
1) First sort jobs according to finish time.
2) Now apply following recursive process.
// Here arr[] is array of n jobs
findMaximumProfit(arr[], n)
{
a) if (n == 1) return arr[0];
b) Return the maximum of following two profits.
(i) Maximum profit by excluding current job, i.e.,
findMaximumProfit(arr, n-1)
(ii) Maximum profit by including the current job
}
How to find the profit including current job?
The idea is to find the latest job before the current job (in
sorted array) that doesn't conflict with current job 'arr[n-1]'.
Once we find such a job, we recur for all jobs till that job and
add profit of current job to result.
In the above example, "job 1" is the latest non-conflicting
for "job 4" and "job 2" is the latest non-conflicting for "job 3".
function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
var taskCounter =0;
for(i=0; i< workers; i++)
{
var moveNext = false;
var currentLoad = 0;
while(!moveNext && taskCounter < tasks.length)
{
if((currentLoad ==0 || i == workers -1 || (currentLoad + tasks[taskCounter]) < mean))
currentLoad += tasks[taskCounter++];
else
moveNext = true;
}
allocation.push(currentLoad);
}
console.log(allocation.sort(function(a,b){return b-a;})[0]);
}
getMini([2,2,36,3,5,2,4,46,76,4,23,12,41,63,34,1,13,7,3,21,4,7,1],5)
function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
var taskCounter =0;
for(i=0; i< workers; i++)
{
var moveNext = false;
var currentLoad = 0;
while(!moveNext && taskCounter < tasks.length)
{
if((currentLoad ==0 || i == workers -1 || (currentLoad + tasks[taskCounter]) < mean))
currentLoad += tasks[taskCounter++];
else
moveNext = true;
}
allocation.push(currentLoad);
}
console.log(allocation.sort(function(a,b){return b-a;})[0]);
}
getMini([2,2,36,3,5,2,4,46,76,4,23,12,41,63,34,1,13,7,3,21,4,7,1],5)
This problem is similar to the combinatorial NP-hard bin packing problem. A greedy solution which is not guaranteed to be optimal is to sort the jobs into decreasing order of size, and then add the jobs in that order, to the worker with the smallest size so far. You can keep track of the smallest worker using a min-heap.
The optimal solution is to build up all the possible arrangements of jobs to workers. You can do this by considering the jobs in order from job 1 to job n. For each job i, try allocating job i to each worker (worker 1 through worker m). This constructs m partial arrangements. For each of these partial arrangements, repeat the above procedure on job (i+1). For each job (for each stage of the recursion), we pick among m workers. Since there are n jobs, there are m^n possible arrangements of jobs to workers. The below algorithm (Java) finds these arrangements, then finds the arrangement that gives the minimum time:
- Miraan March 26, 2017