fb家新鲜电面面经

面试官首先自我介绍了一下，一个facebook infrasturcture组的小哥。
然后问了一下简历上的实习经历，问的most challenging part 和

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

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

母。
然后最后留了5分钟问问题。
第二题没答好，感觉要挂......
求大米求大米

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;
   
5.   int i = 0, j = -1, minlen = n;
   
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);  
    
19.       }
    
20.       i++; // drop first char in substring
    
21.       if (--freq[s[i]] == 0) {
    
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

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;
   
4.   int i = 0; // first index of zero value
   
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. 
    
17. // unstable O(n)
    
18. void moveZerosToEnd2(vector<int>& a) {
    
19.   int n = a.size(); if (n < 2) return;
    
20.   int i = 0; // first index of zero value
    
21.   int j = n-1; // last index of non-zero value
    
22.   while (i < n) {
    
23.     if (a[i] == 0) {
    
24.       while (j > i && a[j] == 0) j--;
    
25.       if (j == i) return;
    
26.       swap(a[i], a[j]);
    
27.     }
    
28.     i++;
    
29.   }
    
30. }

复制代码

oxfordjin11 发表于 2016-10-30 02:25
最好的情况是每个字母在substring里只出现一次，而且没有其他字母，但是题目的意思是找一个包括alphabet ...

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

momo 请问第二题LZ哪里没答好？感觉跟LC76那题还是一样的，能用LC67的方法解决

感觉如果他们问你简历的话就说明你以前经验很丰富的 所以算是加分项的吧！

tonymuu 发表于 2016-10-25 12:13
感觉如果他们问你简历的话就说明你以前经验很丰富的 所以算是加分项的吧！

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

weii 发表于 2016-10-25 10:20
momo 请问第二题LZ哪里没答好？感觉跟LC76那题还是一样的，能用LC67的方法解决

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

oxfordjin11 发表于 2016-10-25 20:36
可能他们就对你的实习经历还感兴趣一点...其余的就什么都没问了

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

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

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

move zero那题不要求非0元素顺序，该怎么做？你是用的swap的方法？还是和LC一样的方法？

iPhD 发表于 2016-10-26 03:02
move zero那题不要求非0元素顺序，该怎么做？你是用的swap的方法？还是和LC一样的方法？

我一上来直接写的lc的方法，然后小哥说这样可能会有不必要的操作，然后我就说的swap的方法，然后他说make sense.我觉得要的是swap的方法，要不然也不会强调不要求非零元素的顺序。

请问楼主，第二题是说找一个substring是alphabet字符串的anagram形式？最短的话不就是和alphabet字符一样长的substring？不知道理解的对不对？