Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

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

- funk July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A priority queue implementation with
Enqueue - put task with priority = epoch time + cool time
De queue - get task with priority <= now epoch time

- Sud July 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nharryp August 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PenChief September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getTimeSlots($tasks,$cooldown=2) {
$i =0;
$taksMap = [];
foreach($tasks as $value ) {

if(isset($taskMap[$value])) {
$diff = $i-$taskMap[$value];

if($diff<=$cooldown+1) {
$i = $i+($cooldown+1-$diff);
}

}

$taskMap[$value] = $i;
$i++;


}
return $i;
}

- Rahul November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getTimeSlots($tasks,$cooldown=2) {
	$i =0;
	$taksMap = [];
	foreach($tasks as $value )  {
		
		if(isset($taskMap[$value])) {
			$diff = $i-$taskMap[$value];

			if($diff<=$cooldown+1) {
				$i = $i+($cooldown+1-$diff);
			} 
			
		} 

		$taskMap[$value] = $i;
		$i++;
			

	}
	return $i;
}

- Rahul November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getTimeSlots($tasks,$cooldown=2) {
	$i =0;
	$taksMap = [];
	foreach($tasks as $value )  {
		
		if(isset($taskMap[$value])) {
			$diff = $i-$taskMap[$value];

			if($diff<=$cooldown+1) {
				$i = $i+($cooldown+1-$diff);
			} 
			
		} 

		$taskMap[$value] = $i;
		$i++;
			

	}
	return $i;
}

- rahul November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

@funk :
===
Assuming the tasks need to be run in the order given, as per the example
==
No, not really. This is variant of task scheduling problem, and you can use any permutation of the tasks, such that when applied - the slots are minimal.
That would be the precise formulation.

- NoOne July 27, 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