Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Assuming the tasks need to be run in the order given, as per the example, we can keep a map to remember the last time slot where a task was executed and advance the time slot until we can execute the current task in the list. Below is the Java code for this solution.
However, there's no need to keep remembering the last time slot for a task after it's farther away than the cooldown from the current time slot, so in order to save memory and avoid collisions in the map, an alternative solution would make use of a PriorityQueue to detect when it's no longer necesary to remember a time slot and remove it from the map.
public static int timeSlots(List<Integer> tasks, int cooldown) {
if ( cooldown <= 0 ) { return tasks.size(); }
Map<Integer, Integer> lastTimeSlot = new HashMap<>();
int result = 0;
int taskIndex = 0;
while ( taskIndex < tasks.size() ) {
Integer task = tasks.get(taskIndex);
Integer last = lastTimeSlot.get(task);
if ( last == null || result - last > cooldown ) {
lastTimeSlot.put(task, result);
taskIndex++;
}
result++;
}
return result;
}
This seems like a modification of the assembly line scheduling problem, typically done using dynamic programming.
At each task, the previous task can be task 1 or task 2. Accordingly add the cool_off time to same tasks (this corresponds to the penalty for switching assembly lines, only inverted logic)
The code would be something like:
t1[0] = time_1; // time_1 is the time taken to execute task 1
for(int i=1; i<N; i++)
{
if (cnt1 > 0 && cnt2 > 0)
{
// the below case is if current task is scheduled as task_1
// similar code should be written for curr task as task_2
// so you have 2 arrays t1 and t2
// final answer will be min(t1[N-1], t2[N-1])
int t1_prev1 = cool_1 + t1[i-1] + time_1;
int t1_prev2 = t1[i-1] + time_1;
if(t1_prev_1 < t1_prev_2)
{
cnt1--;
t1[i] = t1_prev1;
}
else
{
cnt2--;
t1[i] = t1_prev2;
}
}
else
{
//schedule that task whose cnt > 0 till it goes to 0 and break out
}
}
Here is the C++ version of this solution:
#define COOLDOWN_INTERVAL 2
void print_task_time_slots()
{
std::vector<int> tasks{ 1, 1, 2, 1, 2 }; // initial tasks list
std::unordered_map<int, int> timers; // keep track of all the timers per task type
size_t timeSlots = 0;
while(!tasks.empty()) {
// Execute the tasks if there is no timer for it
int taskType = tasks[0];
if(timers.count(taskType) == 0) {
// we can execute this task, since we have no timer for it
// add timer for this task type and remove the task from the queue
timers.insert(
std::make_pair(taskType, COOLDOWN_INTERVAL + 1)); // +1 we will decrease it by one few lines below
tasks.erase(tasks.begin());
}
// always increase the timeslots counter
timeSlots++;
// reduce the counters for all the task types. If a counter hits 0 we remove it from the map
std::unordered_map<int, int> tmpTimers;
std::for_each(timers.begin(), timers.end(), [&](std::unordered_map<int, int>::value_type& p) {
int type = p.first;
int counter_value = p.second;
--counter_value;
if(counter_value > 0) {
tmpTimers.insert(std::make_pair(type, counter_value));
}
});
timers.swap(tmpTimers);
}
std::cout << "we need " << timeSlots << " time units to run this tasks list" << std::endl;
}
What? What's the list of tasks? Start times, dependencies, ... Start and end times? Please clarify the question, it's too much guessing.
- Chris July 27, 2017