Facebook Interview Question for SDE1s


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

- Miraan March 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ratneshtr09 June 15, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Krishna March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous March 19, 2017 | Flag Reply
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[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

- Anonymous March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- axg April 13, 2017 | Flag
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[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

- j March 19, 2017 | Flag Reply
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 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();
}

- Anon March 19, 2017 | Flag Reply
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
    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

- nk March 20, 2017 | Flag Reply
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[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);
        }

- yura.gunko March 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- zyjdxtc March 20, 2017 | Flag Reply
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);
	}
	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;
}

- EAVIV March 22, 2017 | Flag Reply
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))

- drubin March 22, 2017 | Flag Reply
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;
                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();
    }
}

- Miraan March 26, 2017 | Flag Reply
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[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;
                }                  
            }

- Anonymous March 27, 2017 | Flag Reply
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[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;
                }

}

- Anonymous March 27, 2017 | Flag Reply
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):
    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)

- agarwal.raunak April 09, 2017 | Flag Reply
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[] 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

}}

- jessdesigntan April 16, 2017 | Flag Reply
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.

- Orion arm, Laniakea April 22, 2017 | Flag Reply
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++) {
		++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;
}

- Alex May 17, 2017 | Flag Reply
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[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".

- scbase March 18, 2017 | Flag Reply
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 = [];
	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)

- Krishna March 19, 2017 | Flag Reply
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 = [];
	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)

- Krishna March 19, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More