一亩三分地论坛

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

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

fb家新鲜电面面经

[复制链接] |试试Instant~ |关注本帖
oxfordjin11 发表于 2016-10-25 08:47:27 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
面试官首先自我介绍了一下,一个facebook infrasturcture组的小哥。
然后问了一下简历上的实习经历,问的most challenging part 和 most interesting part.
coding两道题
1.move zeros, 不要求非零元素的顺序
2.minimum substring window (lc76)的变形,给一个string然后一个alphabet(也是一个string,每个字母只出现一次),让你找一个最短的substring,要求里面出现alphabet里面所有的字母。
然后最后留了5分钟问问题。. From 1point 3acres bbs
第二题没答好,感觉要挂......
大米求大米. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

4

查看全部评分

weii 发表于 2016-10-25 10:20:42 | 显示全部楼层
momo 请问第二题LZ哪里没答好?感觉跟LC76那题还是一样的,能用LC67的方法解决
回复 支持 反对

使用道具 举报

tonymuu 发表于 2016-10-25 12:13:34 | 显示全部楼层
感觉如果他们问你简历的话就说明你以前经验很丰富的 所以算是加分项的吧!
回复 支持 反对

使用道具 举报

 楼主| oxfordjin11 发表于 2016-10-25 20:36:42 | 显示全部楼层
tonymuu 发表于 2016-10-25 12:13
感觉如果他们问你简历的话就说明你以前经验很丰富的 所以算是加分项的吧!

可能他们就对你的实习经历还感兴趣一点...其余的就什么都没问了
回复 支持 反对

使用道具 举报

 楼主| oxfordjin11 发表于 2016-10-25 20:38:44 | 显示全部楼层
weii 发表于 2016-10-25 10:20
momo 请问第二题LZ哪里没答好?感觉跟LC76那题还是一样的,能用LC67的方法解决

确实能用那题的方法解决...但我当时不记得那道题怎么做的了...就按照自己想的思路说了...中间还卡住了...code没写完
回复 支持 反对

使用道具 举报

tonymuu 发表于 2016-10-26 02:31:35 | 显示全部楼层
oxfordjin11 发表于 2016-10-25 20:36. 1point3acres.com/bbs
可能他们就对你的实习经历还感兴趣一点...其余的就什么都没问了

第二道题挺难的感觉 所以他们应该会考虑题目难度?反正要是我上肯定没有思路。。
回复 支持 反对

使用道具 举报

春山寒 发表于 2016-10-26 02:46:22 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-26 03:02:21 | 显示全部楼层
move zero那题不要求非0元素顺序,该怎么做?你是用的swap的方法?还是和LC一样的方法?
回复 支持 反对

使用道具 举报

 楼主| oxfordjin11 发表于 2016-10-26 06:10:10 | 显示全部楼层
iPhD 发表于 2016-10-26 03:02
move zero那题不要求非0元素顺序,该怎么做?你是用的swap的方法?还是和LC一样的方法?
. from: 1point3acres.com/bbs
我一上来直接写的lc的方法,然后小哥说这样可能会有不必要的操作,然后我就说的swap的方法,然后他说make sense.我觉得要的是swap的方法,要不然也不会强调不要求非零元素的顺序。
回复 支持 反对

使用道具 举报

youto 发表于 2016-10-29 09:31:11 | 显示全部楼层
请问楼主,第二题是说找一个substring是alphabet字符串的anagram形式?最短的话不就是和alphabet字符一样长的substring?不知道理解的对不对?
回复 支持 反对

使用道具 举报

 楼主| oxfordjin11 发表于 2016-10-30 02:25:25 | 显示全部楼层
youto 发表于 2016-10-29 09:31
请问楼主,第二题是说找一个substring是alphabet字符串的anagram形式?最短的话不就是和alphabet字符一样长 ...

最好的情况是每个字母在substring里只出现一次,而且没有其他字母,但是题目的意思是找一个包括alphabet里面所有字母的最短字符串,这个字符串不一定是anagram.
回复 支持 反对

使用道具 举报

youto 发表于 2016-10-30 02:40:28 | 显示全部楼层
oxfordjin11 发表于 2016-10-30 02:25
最好的情况是每个字母在substring里只出现一次,而且没有其他字母,但是题目的意思是找一个包括alphabet ...

那就是说minimum substring window分两种情况,如果有substring只包含了alphbet的,那就是结果;没有的话,就是lc上的那种做法,找到最短的substring能够包含alphbet,但是可能还有其他字符,比如alphbet是abc,但是结果是bnac
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-30 04:30:05 | 显示全部楼层
1. Move zeros 我就假设是要求把数组中zero in place移到末尾。对于是否要求非零元素的相对位置不变(stable vs unstable),就是时间O(2n) vs O(n)的区别。关键是当前遇到0时,是和后面第一个非零元素交换(O(2n))还是最后一个非零元素交换(O(n)):
  1. // stable O(2n)
  2. void moveZerosToEnd1(vector<int>& a) {
  3.   int n = a.size(); if (n < 2) return;. 鍥磋鎴戜滑@1point 3 acres
  4.   int i = 0; // first index of zero value. 1point3acres.com/bbs
  5.   while (i < n) {
  6.     if (a[i] != 0) i++;
  7.     else {
  8.       int j = i+1; // first index of non-zero value after i
  9.       while (j < n && a[j] == 0) j++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.       if (j == n) return;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.       swap(a[i], a[j]);
  12.       i = j;
  13.     }
  14.   }
  15. }

  16. // unstable O(n)
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17. void moveZerosToEnd2(vector<int>& a) {
  18.   int n = a.size(); if (n < 2) return;
  19.   int i = 0; // first index of zero value
  20.   int j = n-1; // last index of non-zero value .鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.   while (i < n) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.     if (a[i] == 0) {
  23.       while (j > i && a[j] == 0) j--;
  24.       if (j == i) return;
  25.       swap(a[i], a[j]);
  26.     }
  27.     i++;
  28.   }
  29. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-30 05:40:42 | 显示全部楼层
2.minimum substring window. 这个题和求longest substr with at most k distinct chars类似。我用two pointers i, j 指向substring的头尾,让j向前进,同时保持substring字符频率统计,直到当所有要求字符都出现时记录当前长度及substring。然后移动i, 同时减小字符频率统计直到有一个要求字符被丢掉时停止,再前进j, 不断重复。这个题我觉得思路不难,但实现起来不容易写。(真正要是在interview时我写得还是慢。。。)
因为给定的alphabet是个string, 我需要转化成unordered_set<char> (hashset)提高时间效率。整体i, j至多扫描string一遍O(N) + 转化alphabet为hashset的O(M)时间。
大家还有什么办法?
  1. string minSubstr(string& s, string& alphabet) {
  2.   int n = s.length(), m = alphabet.size();
  3.   string res; // result to hold required min substring
  4.   if (n < m || n == 0) return res;. from: 1point3acres.com/bbs
  5.   int i = 0, j = -1, minlen = n;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.   unordered_map<char, int> freq; // char frequency of substring
  7.   unordered_set<char> chars; // all chars in alphabet
  8.   for (char& c:alphabet) chars.insert(c); // O(m)
  9.   
  10.   while (++j < n) { // O(n)
  11.     // if a new char in alphabet encountered.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.     if (chars.count(s[j]) && !freq.count(s[j])) m--;
  13.     freq[s[j]]++;
  14.    
  15.     // have all chars in alphabet
  16.     while (m == 0) {
  17.       if (j-i+1 < minlen) { // better substring found
  18.         minlen = j-i+1; res = s.substr(i, j-i+1);  .1point3acres缃
  19.       }. 鍥磋鎴戜滑@1point 3 acres
  20.       i++; // drop first char in substring. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.       if (--freq[s[i]] == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.         freq.erase(s[i]); . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.         if (chars.count(s[i])) m++; // miss a char in alphabet
  24.       }
  25.     }
  26.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.   return res;
  28. }
复制代码

补充内容 (2016-10-30 05:41):
若根本找不到要求的substring我的算法就返回空string
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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