一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2855|回复: 16
收起左侧

Facebook 电面

[复制链接] |试试Instant~ |关注本帖
南若冲 发表于 2015-3-11 05:18:24 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚面完的一个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
. From 1point 3acres bbs
这是面试官指正以后的代码
int task(vector<int> v,int N){
    int n=v.size();
    if(n==0) return 0;
    if(n==1) return 1;
    unordered_map<int,int> m;
    int count=0;
    for(int i=0;i<n;i++){
        if(m.find(v)==m.end()){
            m[v]=count;
            count++;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.         }else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            if(count-m[v]>=N+1){
               m[v]=count;
               count++;
            }
            else{
                count+=N+1-(count-m[v]);
                m[v]=count;
                count++;
            }

        }-google 1point3acres
    }
    return count;.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

我的错误是在于 每次更新已经出现的task的index时 我用的是input里面的index 而不是输出以后的index 这个他最后指出来了
比如第一个例子中的第二个1出现时,我是用input中第二个1的下标(2)去更新map的,而不是他在假象的新的第二个1的下标(4)去更新map
按照以往f的要求 我觉得我的面试发挥得不好 一开始以为是一些常规的二叉树和链表的题和dfs的题 这些我准备的多一点
后来想想 其实也不难 可以参考leetcode上一些array移动下标的题比如remove element什么的

只能全职再战Facebook了 难过 .1point3acres缃
希望对大家有帮助
. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres
补充内容 (2015-3-11 05:21):
说漏了 假设是单核的系统 而且要保持input的task的顺序 比如第二个2要等待第二个1执行了才能执行.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

补充内容 (2015-3-24 15:55):
被拒啦 开开心心去亚马逊了 全职再战
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-3-24 15:55): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
被拒啦 开开心心去亚马逊了 全职再战 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

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

.1point3acres缃补充内容 (2015-3-24 15:56):.鐣欏璁哄潧-涓浜-涓夊垎鍦
被拒啦 开开心心去亚马逊了 全职再战

评分

3

查看全部评分

ZhiDong 发表于 2015-3-11 14:48:54 | 显示全部楼层
贴个自己的:

public static int  task(int [] input ,int N){
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(input[0], 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
        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);
            }
        }. 1point3acres.com/bbs
        return map.get(input[input.length - 1]);   
    }
回复 支持 3 反对 0

使用道具 举报

dennyrong 发表于 2015-3-20 12:19:46 | 显示全部楼层
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])) {. From 1point 3acres bbs
            map.put(task[i], i+res);
            i++;
        }else {
            int index = map.get(task[i]);
            if(i+res-index<=N) {
                res++;
            }else {. more info on 1point3acres.com
                map.put(task[i],i+res);
                i++;
            }
        }
    }
    return i+res;
}
回复 支持 1 反对 0

使用道具 举报

wcy1984123 发表于 2015-3-11 14:47:19 | 显示全部楼层
楼主能解释的详细一点么?为什么给定 [1,2,1,2], N=3 会出现下面两种情况?
// 1,2,1,2 --> 4,
// 1,2,_,_,1,_,_,2--> 6 这个难道不应该输出8 (4个元素加上4个'_')?谢谢啦。
回复 支持 反对

使用道具 举报

 楼主| 南若冲 发表于 2015-3-12 02:36:31 | 显示全部楼层
wcy1984123 发表于 2015-3-11 14:47. 1point 3acres 璁哄潧
楼主能解释的详细一点么?为什么给定 [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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

不知道这么解释 是否明白?
回复 支持 反对

使用道具 举报

 楼主| 南若冲 发表于 2015-3-12 02:38:27 | 显示全部楼层
ZhiDong 发表于 2015-3-11 14:48 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
贴个自己的:

public static int  task(int [] input ,int N){
. more info on 1point3acres.com
感觉应该是可以的吧?主要是在于 每次在map里更新上一个执行的任务的位置时,不能用输入中的下标,要用已经执行任务时的下标 我主要错在了这里 其实我想的时候是这么想的 没想到写的时候写太快 写错了
回复 支持 反对

使用道具 举报

wcy1984123 发表于 2015-3-12 02:42:43 | 显示全部楼层
南若冲 发表于 2015-3-12 02:36.鐣欏璁哄潧-涓浜-涓夊垎鍦
不好意思 直接把和面试官讨论的贴了上来
应该是这样的 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[1,2,1,2] N=3

谢谢楼主 很清楚了 &#128077;
回复 支持 反对

使用道具 举报

wyni18 发表于 2015-3-12 04:45:09 | 显示全部楼层
我好像太弱了,题目都看不太懂。。是要我们返回什么呢
回复 支持 反对

使用道具 举报

ZhiDong 发表于 2015-3-12 10:23:58 | 显示全部楼层
南若冲 发表于 2015-3-12 02:38
感觉应该是可以的吧?主要是在于 每次在map里更新上一个执行的任务的位置时,不能用输入中的下标,要用已 ...

也是想了老半天的才想懂,楼主面试这么短时间内想出来实属不易。
回复 支持 反对

使用道具 举报

ZhiDong 发表于 2015-3-12 10:24:04 | 显示全部楼层
南若冲 发表于 2015-3-12 02:38
感觉应该是可以的吧?主要是在于 每次在map里更新上一个执行的任务的位置时,不能用输入中的下标,要用已 ...

也是想了老半天的才想懂,楼主面试这么短时间内想出来实属不易。
回复 支持 反对

使用道具 举报

 楼主| 南若冲 发表于 2015-3-12 13:41:03 | 显示全部楼层
ZhiDong 发表于 2015-3-12 10:24
也是想了老半天的才想懂,楼主面试这么短时间内想出来实属不易。

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

使用道具 举报

 楼主| 南若冲 发表于 2015-3-12 13:41:59 | 显示全部楼层
wyni18 发表于 2015-3-12 04:45. Waral 鍗氬鏈夋洿澶氭枃绔,
我好像太弱了,题目都看不太懂。。是要我们返回什么呢

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

使用道具 举报

wyni18 发表于 2015-3-13 09:00:29 | 显示全部楼层
南若冲 发表于 2015-3-12 13:41.1point3acres缃
应该是我表达不清楚 要我们返回执行任务的时间 或者就是那个按照这个规则输出的数组的长度

谢谢楼主
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-16 14:16:27 | 显示全部楼层
lz, 我看到另一个帖子也报的这题说还有一个follow up,如果N不是fixed,是variable怎么办,你被问了这个follow up吗?不知是怎么答的?
回复 支持 反对

使用道具 举报

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

使用道具 举报

yanguango 发表于 2015-5-2 08:07:26 | 显示全部楼层
写了一下
  1. #include <vector>
  2. #include <iostream>
  3. #include <unordered_map>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4. #include <cassert>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5. using namespace std;

  6. int runTask(vector<int> tasks, int n) {. 1point 3acres 璁哄潧
  7.   int len = tasks.size();
  8.   if (len < 2) return len;

  9.   int time = 0;
  10.   unordered_map<int, int> mp;. more info on 1point3acres.com
  11.   for (int i = 0; i < len; i++) {.1point3acres缃
  12.     time++;
  13.     if (mp.find(tasks[i]) == mp.end()) {
  14.       mp[tasks[i]] = time;
  15.     } else {
  16.       if (time - mp[tasks[i]] < n + 1) {
  17.         time = mp[tasks[i]] + n + 1;
  18.         mp[tasks[i]] = time;
  19.       }
  20.     }
  21.   }. Waral 鍗氬鏈夋洿澶氭枃绔,

  22.   return time;
  23. }. more info on 1point3acres.com

  24. int main(int argc, char const *argv[]) {
  25.   assert(runTask(vector<int>{}, 3) == 0);. more info on 1point3acres.com
  26.   assert(runTask(vector<int>{1}, 3) == 1);
  27.   assert(runTask(vector<int>{1, 2, 1, 2}, 3) == 6);
  28.   assert(runTask(vector<int>{1, 2, 1, 2}, 2) == 5);
  29.   assert(runTask(vector<int>{1, 1, 1, 1}, 3) == 13);
  30.   assert(runTask(vector<int>{1, 1, 1, 1}, 1) == 7);
  31.   assert(runTask(vector<int>{1, 2, 1, 2}, 1) == 4);
  32. }
复制代码
回复 支持 反对

使用道具 举报

海岸线 发表于 2015-8-6 17:54:28 | 显示全部楼层
用一个map来存 task_id -> last finishing time.1point3acres缃

public int getExecTime(int[] tasks, int N) {. 1point3acres.com/bbs
            if (tasks == null || tasks.length == 0) {
                return 0;
            }
.1point3acres缃
            Map<Integer, Integer> map = new HashMap<>();. from: 1point3acres.com/bbs

            int i = 0; // # of tasks finished. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int timeStamp = 0;. more info on 1point3acres.com

            while (i < tasks.length) {
                if (!map.containsKey(tasks[i]).鏈枃鍘熷垱鑷1point3acres璁哄潧
                        || timeStamp - map.get(tasks[i]) > N) {. 1point3acres.com/bbs

                    map.put(tasks[i], timeStamp);
                    i++;. 1point3acres.com/bbs
                }
                timeStamp++;
            }
            return timeStamp;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表