Facebook 电面

刚刚面完的一个Facebook电面 感觉很不好 应该挂了 没有见过的题 面试官是个俄罗斯或者欧洲人 Site Integrity Infrastructure team
口音过得去 但是还是听了挺久问题

给一个vector 里面的元素表示task type，给一个N，表示执行相同task时要等上N个单位时间 例子中用‘_’表示
// [1,2,1,2], N=3
// 1,2,1,2 --> 4,
// 1,2,_,_,1,_,_,2--> 6


// [1,2,1,2], N=2
// 1,2,1,2 --> 4,
// 1, 2, _, 1,2--> 5

这是面试官指正以后的代码
int task(vector<int> v,int N){
    int n=v.size();
    if(n==0) ret

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

了 全职再战

补充内容 (2015-3-24 15:55):
被拒啦 开开心心去亚马逊了 全职再战

补充内容 (2015-3-24 15:56):
被拒啦 开开心心去亚马逊了 全职再战

补充内容 (2015-3-24 15:56):
被拒啦 开开心心去亚马逊了 全职再战

补充内容 (2015-3-24 15:56):
被拒啦 开开心心去亚马逊了 全职再战

贴个自己的：

public static int  task(int [] input ,int N){
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(input[0], 1);
        for(int i = 1 ; i < input.length; ++i){
            if(map.containsKey(input[i])){
               int maxNum = Math.max(map.get(input[i-1]) + 1, map.get(input[i]) + N + 1);
               map.put(input[i], maxNum);
            } else{
               map.put(input[i],map.get(input[i-1]) + 1);
            }
        }
        return map.get(input[input.length - 1]);   
    }

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

用一个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;
        }

楼主能解释的详细一点么？为什么给定 [1,2,1,2], N=3 会出现下面两种情况？
// 1,2,1,2 --> 4,
// 1,2,_,_,1,_,_,2--> 6 这个难道不应该输出8 （4个元素加上4个'_'）？谢谢啦。

wcy1984123 发表于 2015-3-11 14:47
楼主能解释的详细一点么？为什么给定 [1,2,1,2], N=3 会出现下面两种情况？
// 1,2,1,2 --> 4,
// 1,2,_ ...

不好意思 直接把和面试官讨论的贴了上来
应该是这样的
[1,2,1,2] N=3
1,2,_,_,1,2 得到len=6
因为要保持任务执行顺序一样
所以第二个任务1只能等上3个单位时间 才能执行 这三个单位时间 第一个被任务2占据 后两个是用'_'来表示单位时间
又比如
[1] N=4 无论N是多少 都只输出长度1
因为后面已经没有要继续执行的任务了，尤其是相同的任务
又比如
[1,2,1,2] N=2
[1,2,_,1,2] 长度应该是5

不知道这么解释 是否明白？

ZhiDong 发表于 2015-3-11 14:48
贴个自己的：

public static int  task(int [] input ,int N){

感觉应该是可以的吧？主要是在于 每次在map里更新上一个执行的任务的位置时，不能用输入中的下标，要用已经执行任务时的下标 我主要错在了这里 其实我想的时候是这么想的 没想到写的时候写太快 写错了

南若冲 发表于 2015-3-12 02:36
不好意思 直接把和面试官讨论的贴了上来
应该是这样的
[1,2,1,2] N=3

谢谢楼主 很清楚了 👍

我好像太弱了，题目都看不太懂。。是要我们返回什么呢

南若冲 发表于 2015-3-12 02:38
感觉应该是可以的吧？主要是在于 每次在map里更新上一个执行的任务的位置时，不能用输入中的下标，要用已 ...

也是想了老半天的才想懂，楼主面试这么短时间内想出来实属不易。

南若冲 发表于 2015-3-12 02:38
感觉应该是可以的吧？主要是在于 每次在map里更新上一个执行的任务的位置时，不能用输入中的下标，要用已 ...

也是想了老半天的才想懂，楼主面试这么短时间内想出来实属不易。

ZhiDong 发表于 2015-3-12 10:24
也是想了老半天的才想懂，楼主面试这么短时间内想出来实属不易。

您这是客气啦 其实是我基础不好 如果思路清楚的话应该不会犯我这个错误 之前心想能碰个linked list或者binary tree的问题就好了