facebook intern 面经

Jester_Z 发表于 2016-1-27 12:59
就怕是这个=  = 楼主能说说思路吗~~

我试着写了一下....

1. int printtask2(string tasks,int coldTime) {
   
2.   int n = tasks.size();

   
3.   if (n == 0)
   
4.     return 0;

   
5. 
   
6.   unordered_map<char, int> map;

   
7.   unordered_map<char, int> freq;
   
8.   for (int task:tasks)
   
9.     freq[task]++;
   
10. 
    
11.   priority_queue<pair<char, int>, vector<pair<char, int>>, cmp2> Q;
    
12.   for (auto it = freq.begin(); it != freq.end(); it++)
    
13.     Q.push({it->first, it->second});
    
14. 
    
15.   int mTime = 0;

    
16.   vector<int> order;
    
17.   while (!Q.empty()) {
    
18.     priority_queue<pair<char, int>, vector<pair<char, int>>, cmp2> tmp;
    
19.     auto task = Q.top();
    
20.     Q.pop();
    
21.     while (map.find(task.first) != map.end() && map[task.first] + coldTime > mTime &&!Q.empty())
    
22.     {
    
23.       tmp.push(task);
    
24.       task = Q.top();
    
25.       Q.pop();
    
26.     }
    
27.     if (map.find(task.first) == map.end() || map[task.first] + coldTime <= mTime)
    
28.     {
    
29.       map[task.first] = ++mTime;
    
30.       if (task.second-- > 1)
    
31.         Q.push(task);
    
32.       cout << task.first << " ";
    
33.     }
    
34.     else
    
35.     {
    
36.       tmp.push(task);
    
37.       task = tmp.top();
    
38.       tmp.pop();
    
39.       int prev = mTime;
    
40.       mTime = max(mTime,map[task.first]+coldTime);
    
41.       for(;prev<mTime;prev++)
    
42.         cout<<" _ ";
    
43.       map[task.first] = ++mTime;
    
44.       if(task.second-->1)
    
45.       Q.push(task);
    
46.       cout << task.first<<" ";
    
47.     }
    
48. 
    
49.     while (!tmp.empty()) {
    
50.       Q.push(tmp.top());
    
51.       tmp.pop();
    
52.     }
    
53. 
    
54.   }
    
55.   return mTime;
    
56. }

复制代码

用python写了一个不确定对不对，但是没用priority queue优化取频率最高的部分

1. def taskSchedule2(self, tasks, cd):
   
2.                 counter = collections.Counter(tasks)
   
3.                 print counter
   
4.                 cdHash = {}
   
5.                 i = 0
   
6.                 t = 0
   
7. 
   
8.                 while i < len(tasks):
   
9.                         flag = 0
   
10.                         for j,freq in counter.most_common():
    
11.                                 if (j not in cdHash or t - cdHash[j] > cd) and counter[j] > 0:
    
12.                                         cdHash[j] = t
    
13.                                         print str(j) + " ",
    
14.                                         counter[j] -= 1
    
15.                                         i += 1
    
16.                                         flag = 1
    
17.                                         break
    
18.                         if flag == 0:
    
19.                                 print "_ ",
    
20.                         t += 1
    
21. 
    
22.                 return t

复制代码

Augustus 发表于 2016-1-27 04:08
去年年末就有同学说fb没坑了啥的。。。。。。这些人真是谣言散播者。。。

那是全职。。。

內堆會收到確認信嗎？有的內推者好像是會forward resume給hr而已。

nickboy 发表于 2016-1-28 05:52
內堆會收到確認信嗎？有的內推者好像是會forward resume給hr而已。

不知道我找的小伙伴怎么推的，没有确认信，但是过了两三天就收到recruiter的联系邮件

楼主第二题能不能具体说下什么意思？
input: ABAABB
cooldown: 2 (don't repeat characters in this unit of time)
output: AB_AB
请问下cooldown这个2代表什么？为什么输出是AB_AB，这是下划线_是什么意思呢？
谢谢！

Huangxin 发表于 2016-1-28 11:39
楼主第二题能不能具体说下什么意思？
input: ABAABB
cooldown: 2 (don't repeat characters in this unit ...

那几句都是他当时写的，他没写完，output按他的要求应该是AB_AB_AB。cooldown就是相同task之间必须间隔的时间，所以对前三个task来说不可以ABA，只能AB_A，两个A之间要隔2，下划线就代表正在冷却(cool down)

songty11 发表于 2016-1-27 23:47
我试着写了一下....

What is your comparator cmp2?

请问哪位大神有task scheduling这道题的java版solution c++的看不懂。。。

有没有好心人 贴出java版的代码呀