## Facebook Interview Question for SDE1s

• 4

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Hi Miraan, what happened if we have task with dependency on subtask. How the problem are then optimized?

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
for(i=0; i< workers; i++)
{
var moveNext = false;
{
else
moveNext = true;
}

}
console.log(allocation.sort(function(a,b){return b-a;}));
}

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
for(i=0; i< workers; i++)
{
var moveNext = false;
{
else
moveNext = true;
}

}
console.log(allocation.sort(function(a,b){return b-a;}));
}

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.append(a)

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

Comment hidden because of low score. Click to expand.
0

Instead of find_loc() being O(n) (in number of workers), you can maintain a min priority_queue to find the minimum loaded worker in O(1). Remove this from queue, update its time and re-insert (O(log(n))

Overall then the algo becomes O(mlog(n)) with n workers and m tasks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.append(a)

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 w = wheap.Remove(); // get worker with minimum end time
wheap.Insert(w+time); // update worker
}
return heap.Max();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

// 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);
}

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 += val;
min_heapify(0, m_last + 1);
}

int min()
{
int min = INT_MIN;
if (m_heap && m_last >= 0) {
min = m_heap;
}
return min;
}

int max()
{
int max = INT_MIN;
if (m_heap && m_last >= 0)
{
max = m_heap;
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;
};

{
int tasks[] = { 2, 2, 3, 7, 1 };

HeapMin heap;

const int SIZE = sizeof(tasks) / sizeof(int);

for (int i = SIZE - 1; i >= 0; --i) {
}
EXPECT_EQ(heap.min(), 7);
EXPECT_EQ(heap.max(), 8);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import heapq
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 = *worker
heapq.heapify(times)
t=heapq.heappop(times)
heapq.heappush(times,(t+i))
return max(times)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
for (int i = tasks.size() - 1; i >= 0; --i) {
int top = pq.top();
pq.pop();
}

while (pq.size() > 1)
pq.pop();

int res = pq.top();
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````ruby
def get_list(a, n)
buckets = Hash.new
n.times do |b|
buckets[b] = []
end
sorted = a.sort.reverse
sorted.each do |s|
bucket = buckets.sort_by{|k,v| v.inject(0, :+)}.to_h.keys.first
buckets[bucket] << s
end
return buckets
end

print(get_list([2, 2, 3, 7, 1], 2))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Console.WriteLine("number of workers vs number of tasks");
int[] listOfTaksWithHoursValue = new int;
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]);

}

Console.WriteLine("with {0} minium hours needed to compelte these tasks {1}", 2, totalHours);

{
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
{
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Console.WriteLine("number of workers vs number of tasks");
int[] listOfTaksWithHoursValue = new int;
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]);

}

Console.WriteLine("with {0} minium hours needed to compelte these tasks {1}", 2, totalHours);

{
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
{
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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):
assign =  * workers
# 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
print assign
return max(assign)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
import java.io.*;
import java.util.*;

class Solution {
public static void main(String[] args) {
int k = 2;
int[] worker = new int[k];

//reverse array
int i = 0;
int j = tasks.length - 1;
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
}

System.out.println(getMaxValue(worker));
}//main

public static int findMin(int[] array) {
int minValue = array;
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;
for (int i = 1; i < array.length; i++) {
if (array[i] > maxValue) {
maxValue = array[i];
}
}
return maxValue;
}

}//solution

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sum the total work hours.
Divide by the number of workers.

you can deal with odd number of workers/work hours by incrementing the work hours until workhours%#ofworkers is zero and then divide by #ofworkers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
break;
}
}
}

{
vector<int> worker_time;
worker_time.resize(workers_count, 0);
int max_time = 0;
for (int i = 0; i < tasks.size(); ++i) {
max_time = max(max_time, worker_time[worker]);
}
return max_time;
}

int Balance(vector<int> const &tasks, int workers_count)
{
int min_time = numeric_limits<int>::max();
do {
min_time = min(min_time, time);

return min_time;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
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".

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
for(i=0; i< workers; i++)
{
var moveNext = false;
{
else
moveNext = true;
}

}
console.log(allocation.sort(function(a,b){return b-a;}));
}

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````function getMini(tasks, workers)
{
var total = tasks.reduce(function(a,b){return a+b;}, 0);
var mean = total/workers;
var allocation = [];
for(i=0; i< workers; i++)
{
var moveNext = false;
{
else
moveNext = true;
}

}
console.log(allocation.sort(function(a,b){return b-a;}));
}

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.