Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
L1 and L2 tasks can be scheduled in a straight forward way. But you cant schedule the tasks in L3 directly because there is a cycle.
So, you will have to use some strategy (like bankers algo) to break this deadlock and proceed to schedule the tasks in L3 as well.
Not clear to schedule a Job if there is a cycle. In this case job C can be completed only after completion of B and B can be completed only after completion of C.
If the tasks were all of the same duration, the strategy is straightforward. Take the next task from the list and execute it on a machine if there's enough time left for that day.
For uneven durations, strategy: keep machines free for long tasks.
First, schedule ready tasks on one machine, say T1, then on T2, then on T3 (when available)
First i assume that task L is missing and doesn't play in game
I think over a strategy when all machine are maximal loaded all the time, taking into account their constraints (some greedy approach, don't leave idle machine). As short observation of the given task sequences I came upon the following schedule which in my view is optimal.
I noticed that before each 8 h taks there are 2 tasks by 4 hours on the schedule.
So my algorithm is the following.
While all 8 hours taks are not executed do:
I take maximum tasks by 8 hours. This could be :
For 24 hours day:
2 tasks by 8 hours and 2 by 4 hours or 1 tasks by 8 hours 4 taks by 4 hours
For 16 hours day:
1 task by 8 hour and 2 by 4 hours.
When there are not available 8 hours taks and I distribute all available 4 hours tasks on available machines.
This is example:
W ----------------Thr------Fr----Mon----Th-----Wed
M1 - M,K--------E-----A,N---n/a-----S,T-----J,D
M2 - R-----------G,V-----C,B---n/a -----P-------Y
M3 - Z,H--------n/a-------W-----n/a---------------F,C
So it takes 6 days to complete all tasks because Monday is all - down
AFAIK, Banker's Algorithm is used to prevent deadlocks where there isn't enough resources so that all the processes can use them simultaneously. The main idea is that a process with higher need of resources should not be given resources at the first place. But the whole point here is prevent deadlock when processes depend on resources. In the question, a process depends on another process. How can then Bankers algorithm be applied here?
If the dependencies are based upon resources, we can solve it by droping a process to not execute, in the cycle case, but if it is functional, then i think we will not be able to reach to any particular solution.
If it is resource related dependency, then one should break the c -> f link.
here is the solution in this case
W-> We Th Fr Sa Su Mo Tu We Thr Fr
T1 CB W ST P JD Y F
T2 MK E VG AN
T3 ZH R
If a list is such that L1 = A->R->K->M (eg A can be completed if R is completed, R can be completed only if K is completed etc.)
- Sugarcane_farmer May 14, 2014Then L3 can never be completed because of the cycle?
What am i missing?