Facebook Interview Question Software Engineer Interns
Country: United States
use a priority queue with frequency as priority. Given n, each time extract top n elements from the queue and put into scheduler queue (output). Now, decrease the frequency of the elements extracted and put it back to priority queue if new frequency is grater than zero. If queue is left with less than n elements then put (n-queue_size) numbers of idle jobs in the out put. Overall complexity is O(Nlgm) where N = length of input string. m = total number of unique tasks.
I am not sure that I properly understand the problem but we could sort tasks by task frequences - most frequent first and than execute the largest group of different taks till it is possible and wait between them - this is greedy approach. for example we have AAAAAABBBBCCCD - > we produce ABCD_ABC_ABC_AB_A_A -> 10
Assuming coldtime is 2 in your example wouldn't the output task be like this instead?
ABCDABCABCAB_A__A ?
You don't really need the first wait times because, for example, there are at least 2 tasks between the first A and second A (A"BCD"A) so there is enough wait between two same tasks that we do not have to add a "NO OP" between them.
Once you are down to 2 tasks though (After the C's and D's are finished) then we need to add coldtime to ensure enough wait time between two tasks.
My approach uses a dictionary to classify these tasks into bin with certain counts in each bins. We place the most common tasks into the list first.
At each iteration, we check the bins again and see which tasks has the most occurences left, we place this task in our task list in the next "legal" position, until the bins are all empty.
here is the code:
public static char[] DistributeTask(Dictionary<char, int> dict, int coolTime)
{
char c = GetLongest(dict);
int length = Math.Max(dict[c] * coolTime, dict[c] * dict.Count());
char[] tasks = new char[length];
while (!DictIsEmpty(dict))
{
char ch= GetLongest(dict);
int ind = NextVacantValidPosition(tasks, ch, coolTime);
tasks[ind] = ch;
dict[ch]--;
}
return tasks;
}
public static bool DictIsEmpty(Dictionary<char, int> dict)
{
foreach (KeyValuePair<char, int> kvp in dict)
{
if (kvp.Value > 0)
{
return false;
}
}
return true;
}
public static bool IsValidLocation(char[] task, int ind, char c, int coolTime)
{
for (int i = Math.Max(0, ind - coolTime); i <= Math.Min(ind + coolTime, task.Length-1); i++)
{
if (task[i] == c)
return false;
}
return true;
}
public static int NextVacantValidPosition(char[] task, char c, int coolTime)
{
for (int i = 0; i < task.Length; i++)
{
if (task[i] == 0)
{
if (IsValidLocation(task, i, c, coolTime))
{
return i;
}
}
}
return -1;
}
public static char GetLongest(Dictionary<char, int> dict)
{
int length = 0;
char c = '\0';
foreach (KeyValuePair<char, int> kvp in dict)
{
if (kvp.Value > length)
{
c = kvp.Key;
length = kvp.Value;
}
}
return c;
}
public static <K, V extends Comparable<? super V>> Map<K, V>
sortByValue( Map<K, V> map )
{
List<Map.Entry<K, V>> list =
new LinkedList<Map.Entry<K, V>>( map.entrySet() );
Collections.sort( list, new Comparator<Map.Entry<K, V>>()
{
public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
{
return (o2.getValue()).compareTo( o1.getValue() );
}
} );
Map<K, V> result = new LinkedHashMap<K, V>();
for (Map.Entry<K, V> entry : list)
{
result.put( entry.getKey(), entry.getValue() );
}
return result;
}
////AABD
//ABDA
String taskSchedule(String str,int k){
StringBuilder result=new StringBuilder();
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0; i <str.length();i++){
char curr = str.charAt(i);
if( map.containsKey(curr)){
Integer val =map.get(curr);
map.put(curr, val+1);
}else{
map.put(curr, 1);
}
}
Map<Character,Integer> sortedMap =sortByValue(map);
int consumed =0;
char prevc = '-';
int j=k+1;
while(consumed < str.length()){
for(Character c : sortedMap.keySet()){
if( j==0){
j=k+1;
prevc = '-';
break;
}
if(map.get(c)> 0){
if( prevc == c ){
result.append("_");
}else{
result.append(c);
Integer val =map.get(c);
map.put(c,val-1);
consumed++;
prevc=c;
}
j--;
}
if(consumed ==str.length()){
break;
}
}
}
return result.toString();
}
public static <K, V extends Comparable<? super V>> Map<K, V>
sortByValue( Map<K, V> map )
{
List<Map.Entry<K, V>> list =
new LinkedList<Map.Entry<K, V>>( map.entrySet() );
Collections.sort( list, new Comparator<Map.Entry<K, V>>()
{
public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
{
return (o2.getValue()).compareTo( o1.getValue() );
}
} );
Map<K, V> result = new LinkedHashMap<K, V>();
for (Map.Entry<K, V> entry : list)
{
result.put( entry.getKey(), entry.getValue() );
}
return result;
}
////AABD
//ABDA
String taskSchedule(String str,int k){
StringBuilder result=new StringBuilder();
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0; i <str.length();i++){
char curr = str.charAt(i);
if( map.containsKey(curr)){
Integer val =map.get(curr);
map.put(curr, val+1);
}else{
map.put(curr, 1);
}
}
Map<Character,Integer> sortedMap =sortByValue(map);
int consumed =0;
char prevc = '-';
int j=k+1;
while(consumed < str.length()){
for(Character c : sortedMap.keySet()){
if( j==0){
j=k+1;
prevc = '-';
break;
}
if(map.get(c)> 0){
if( prevc == c ){
result.append("_");
}else{
result.append(c);
Integer val =map.get(c);
map.put(c,val-1);
consumed++;
prevc=c;
}
j--;
}
if(consumed ==str.length()){
break;
}
}
}
return result.toString();
}
I don't think it can get simpler than this
from collections import Counter
def schedule(tasks, n):
#Gives us the tasks in the descending order of frequency
tasks = Counter(tasks)
tasks = sorted(tasks.items(), key=lambda x: x[1], reverse=True)
#Keeps track of the last time a task was performed
check_last = {}
i = 0
while len(tasks) != 0:
current_task = findNextPossibleTask(tasks, check_last, i)
if current_task:
tasks.remove(current_task)
print(current_task[0])
remaining_count = current_task[1] - 1
check_last[current_task[0]] = i
#If we still have more of the current task to complete, add it to
#the end of the list
if remaining_count > 0:
tasks.append((current_task[0], remaining_count))
else:
print("_")
i += 1
def findNextPossibleTask(tasks, check_last, i):
for task in tasks:
current_task = task[0]
last_time_of_task = check_last.get(current_task, -n-1)
#If we have satisfied the criteria of waiting for time n, we can now
#do this task
if i - last_time_of_task > n:
return task
return None
public class SequenceTask {
private static void taskSequence(String input) {
char[] arr = input.toCharArray();
Map<String, Integer> unsortedMap = new TreeMap<String, Integer>();
Arrays.sort(arr);
char s = arr[0];
int count = 1;
int total_count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == s) {
count++;
} else {
unsortedMap.put(String.valueOf(s), count);
s = arr[i];
count = 1;
}
total_count++;
}
if (total_count < arr.length) {
unsortedMap.put(String.valueOf(s), count);
}
// this is how you sort a map
List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>(unsortedMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});
// System.out.println(unsortedMap);
Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
for (Iterator<Map.Entry<String, Integer>> it = list.iterator(); it.hasNext();) {
Map.Entry<String, Integer> entry = it.next();
sortedMap.put(entry.getKey(), entry.getValue());
}
// System.out.println(sortedMap);
total_count = 0;
System.out.print("for input: " + input + " result is: ");
while (true) {
for (Map.Entry<String, Integer> element : sortedMap.entrySet()) {
if (element.getValue() != 0) {
System.out.print(element.getKey() + "");
int value = element.getValue();
value--;
sortedMap.put(element.getKey(), value);
total_count++;
}
}
if (total_count >= input.length()) {
break;
}
System.out.print("_");
}
System.out.println();
}
public static void main(String[] args) {
taskSequence("ABDCCCCBBBBA");
taskSequence("ABBBAA");
}
}
public class SequenceTask {
private static void taskSequence(String input) {
char[] arr = input.toCharArray();
Map<String, Integer> unsortedMap = new TreeMap<String, Integer>();
Arrays.sort(arr);
char s = arr[0];
int count = 1;
int total_count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == s) {
count++;
} else {
unsortedMap.put(String.valueOf(s), count);
s = arr[i];
count = 1;
}
total_count++;
}
if (total_count < arr.length) {
unsortedMap.put(String.valueOf(s), count);
}
// this is how you sort a map
List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>(unsortedMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});
// System.out.println(unsortedMap);
Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
for (Iterator<Map.Entry<String, Integer>> it = list.iterator(); it.hasNext();) {
Map.Entry<String, Integer> entry = it.next();
sortedMap.put(entry.getKey(), entry.getValue());
}
// System.out.println(sortedMap);
total_count = 0;
System.out.print("for input: " + input + " result is: ");
while (true) {
for (Map.Entry<String, Integer> element : sortedMap.entrySet()) {
if (element.getValue() != 0) {
System.out.print(element.getKey() + "");
int value = element.getValue();
value--;
sortedMap.put(element.getKey(), value);
total_count++;
}
}
if (total_count >= input.length()) {
break;
}
System.out.print("_");
}
System.out.println();
}
public static void main(String[] args) {
taskSequence("ABDCCCCBBBBA");
taskSequence("ABBBAA");
}
}
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void ScheduleTaskWithColdTime(char *sequence, int sizeSeq, int coldTime)
{
char wait = '_';
int j = 0, count = 0;
char matchChar;
// Create an empty queue of strings
queue<char> q;
for (int i = 1; i < sizeSeq; i++)
{
matchChar = sequence[j];
if (sequence[i] != sequence[j])
{
swap((sequence + i), (sequence + ++j));
j++;
}
}
for (int j = 0; j <= sizeSeq; j++)
{
q.push(sequence[j]);
count++;
if (count == coldTime && j < sizeSeq)
{
q.push(wait);
count = 0;
}
}
while (!q.empty())
{
cout << q.front();
q.pop();
}
cout<<"\nModified Sequence is - "<<sequence<<endl;
}
/* Driver program to test above functions */
int main()
{
char str[] = "AAABBB";
int n = strlen(str);
ScheduleTaskWithColdTime(str, n - 1, 2);
return 0;
}
{{
public class TaskScheduler {
static class Task implements Comparable<Task>{
int freq;
char name;
public Task(int freq, char name) {
this.freq=freq;
this.name=name;
}
@Override
public int compareTo(Task o) {
return o.freq-this.freq;
}
}
public static void schedule(String s, int t){
String ans="";
HashMap<Character, Integer> freqMap=new HashMap<>();
for(int i=0;i<s.length();i++) {
int freq=freqMap.getOrDefault(s.charAt(i), 0);
freqMap.put(s.charAt(i), freq+1);
}
PriorityQueue<Task> queue=new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
Character key = entry.getKey();
Integer value = entry.getValue();
queue.add(new Task(value, key));
}
while(!queue.isEmpty()){
ArrayList<Task> list=new ArrayList<>();
for(int i=0;i<t+1;i++){
if(!queue.isEmpty()) {
Task task=queue.poll();
ans+=task.name;
task.freq--;
list.add(task);
} else
break;
}
int len=list.size();
while(list.size()>0){
Task tt=list.remove(0);
if(tt.freq>0)
queue.add(tt);
}
if(len>0 && !queue.isEmpty()){
for(int i=0;i<t+1-len;i++)
ans+="_";
}
}
System.out.println("ans="+ans);
}
public static void main(String[] args) {
schedule("AAABBB", 2);
schedule("AAABBBCCDD", 2);
}
}}
public class TaskScheduler {
static class Task implements Comparable<Task>{
int freq;
char name;
public Task(int freq, char name) {
this.freq=freq;
this.name=name;
}
@Override
public int compareTo(Task o) {
return o.freq-this.freq;
}
}
public static void schedule(String s, int t){
String ans="";
HashMap<Character, Integer> freqMap=new HashMap<>();
for(int i=0;i<s.length();i++) {
int freq=freqMap.getOrDefault(s.charAt(i), 0);
freqMap.put(s.charAt(i), freq+1);
}
PriorityQueue<Task> queue=new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
Character key = entry.getKey();
Integer value = entry.getValue();
queue.add(new Task(value, key));
}
while(!queue.isEmpty()){
ArrayList<Task> list=new ArrayList<>();
for(int i=0;i<t+1;i++){
if(!queue.isEmpty()) {
Task task=queue.poll();
ans+=task.name;
task.freq--;
list.add(task);
} else
break;
}
int len=list.size();
while(list.size()>0){
Task tt=list.remove(0);
if(tt.freq>0)
queue.add(tt);
}
if(len>0 && !queue.isEmpty()){
for(int i=0;i<t+1-len;i++)
ans+="_";
}
}
System.out.println("ans="+ans);
}
public static void main(String[] args) {
schedule("AAABBB", 2);
schedule("AAABBBCCDD", 2);
}
First sort tasks by task frequency. like AAAABBBCCDD.
Try fill it with A first, get A_ _ A_ _ A_ _ A
then fill B,get AB_AB_AB_A
then fill C, get ABCABCAB_A
then fill D, get ABCABCABDAD
In your last case, should it be ABCABCABDA_D, since D needs to wait for 2 slots, but the optimal solution is ABCABDACBAD
Use a maxheap with the frequency of each task being the key, everytime pop n item from the heap, and put in the result and update the keys. if there is less than n item in the heap then we should fill the gap with '_'
- nima February 05, 2016