## Facebook Interview Question

SDE1s**Country:**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 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:

```
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();
}
}
```

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();
}
}
```

```
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)
```

1) First sort jobs according to finish time.

- scbase March 18, 20172) 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".