Facebook 电面

wyni18 发表于 2015-3-12 04:45
我好像太弱了，题目都看不太懂。。是要我们返回什么呢

应该是我表达不清楚 要我们返回执行任务的时间 或者就是那个按照这个规则输出的数组的长度

南若冲 发表于 2015-3-12 13:41
应该是我表达不清楚 要我们返回执行任务的时间 或者就是那个按照这个规则输出的数组的长度

谢谢楼主

lz， 我看到另一个帖子也报的这题说还有一个follow up，如果N不是fixed，是variable怎么办，你被问了这个follow up吗？不知是怎么答的？

不知道怎么顶贴啊.. 只能在这里回复了..刚刚面完的这道题.. 感谢楼主的分享.. 也就不单独发帖了
之前看到的这道题, 但是没有动手做, 只是大概想了一下思路, 但是面到见过的题目,心里还是一稳
面试过程就是随便聊两句简历,问问我为毛对Facebook感兴趣,然后就开始直接做题
我写完基本大框架之后,他让我进一步优化自己的code, 然后我就跟他讲这个code还能怎么优化,优化到最后会只有一个case, 剩下的情况都会是一样的..
自己的code就不贴出来丢人了, 但是我感觉最重要的部分是communication和思路的清晰, 然后code写出来要clean, 同时要写得快
全程当玩了一个小时了,也不求onsite, 祝大家面试goodluck了

public int execTime(int[] task, int N) {
    if(task==null || task.length==0)
        return 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int res = 0;
    int i =0;
    while(i<task.length) {
        if(!map.containsKey(task[i])) {
            map.put(task[i], i+res);
            i++;
        }else {
            int index = map.get(task[i]);
            if(i+res-index<=N) {
                res++;
            }else {
                map.put(task[i],i+res);
                i++;
            }
        }
    }
    return i+res;
}

写了一下

1. #include <vector>
   
2. #include <iostream>
   
3. #include <unordered_map>
   
4. #include <cassert>
   
5. using namespace std;
   
6. 
   
7. int runTask(vector<int> tasks, int n) {
   
8.   int len = tasks.size();
   
9.   if (len < 2) return len;
   
10. 
    
11.   int time = 0;
    
12.   unordered_map<int, int> mp;
    
13.   for (int i = 0; i < len; i++) {
    
14.     time++;
    
15.     if (mp.find(tasks[i]) == mp.end()) {
    
16.       mp[tasks[i]] = time;
    
17.     } else {
    
18.       if (time - mp[tasks[i]] < n + 1) {
    
19.         time = mp[tasks[i]] + n + 1;
    
20.         mp[tasks[i]] = time;
    
21.       }
    
22.     }
    
23.   }
    
24. 
    
25.   return time;
    
26. }
    
27. 
    
28. int main(int argc, char const *argv[]) {
    
29.   assert(runTask(vector<int>{}, 3) == 0);
    
30.   assert(runTask(vector<int>{1}, 3) == 1);
    
31.   assert(runTask(vector<int>{1, 2, 1, 2}, 3) == 6);
    
32.   assert(runTask(vector<int>{1, 2, 1, 2}, 2) == 5);
    
33.   assert(runTask(vector<int>{1, 1, 1, 1}, 3) == 13);
    
34.   assert(runTask(vector<int>{1, 1, 1, 1}, 1) == 7);
    
35.   assert(runTask(vector<int>{1, 2, 1, 2}, 1) == 4);
    
36. }

复制代码

用一个map来存 task_id -> last finishing time

public int getExecTime(int[] tasks, int N) {
            if (tasks == null || tasks.length == 0) {
                return 0;
            }

            Map<Integer, Integer> map = new HashMap<>();

            int i = 0; // # of tasks finished
            int timeStamp = 0;

            while (i < tasks.length) {
                if (!map.containsKey(tasks[i])
                        || timeStamp - map.get(tasks[i]) > N) {

                    map.put(tasks[i], timeStamp);
                    i++;
                }
                timeStamp++;
            }
            return timeStamp;
        }