FB店面面经

FB店面，杯具了。。。。发个面经，攒攒以后的人品。
1. 字符串匹配，最原始的那种：一个s，一个p，在s里面找p，返回第一个匹配字串的开头下标

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

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

多次的。只不过不是4 bytes，而是4KB。

面完了，整个人都不好了。还是基本功太差啊。

zyoppy008 发表于 2016-8-20 05:12
找出所有你的朋友的朋友，但不是你的朋友，按你们共同好友的数量排序

能不能用BFS做？只找到第二层就停止，并且对于每个第二层的节点，在BFS的过程中就记录有多少个第一层的节点能够到达它。这样就能排序了。BFS的时间复杂度是O（n），排序的时间复杂度是O(nlogn)。总共是O(nlogn)

楼主打回去好好刷题！

hezhifeng850207 发表于 2016-9-19 06:17
恩，我的意思是，window size=pattern size的时候，不就是保护所有pattern的字符，并且不包含其他非patte ...

能否贴个代码交流一下？我的代码如下:

1. 
   
2. public class Solution {
   
3.     public int strstrp(String s, String p) {
   
4.         if(s==null || p==null || s.length()<p.length()) {
   
5.             return -1;
   
6.         } else {
   
7.             int first = -1;
   
8.             int cntUnique = 0;
   
9.             int[] cnts = new int[ 256 ];
   
10. 
    
11.             Arrays.fill(cnts, Integer.MAX_VALUE);
    
12.             for(int idx = 0; idx < p.length(); idx++) {
    
13.                 if(cnts[ p.charAt(idx) ] == Integer.MAX_VALUE) {
    
14.                     cntUnique++;
    
15.                     cnts[ p.charAt(idx) ] = 1;
    
16.                 } else {
    
17.                     cnts[ p.charAt(idx) ]++;
    
18.                 }
    
19.             }
    
20. 
    
21.             for(int idx = 0; idx < p.length(); idx++) {
    
22.                 if(cnts[ s.charAt(idx) ] < Integer.MAX_VALUE) {
    
23.                     cnts[ s.charAt(idx) ]--;
    
24.                     if(cnts[ s.charAt(idx) ] == 0) {
    
25.                         cntUnique--;
    
26.                     } else if(cnts[ s.charAt(idx) ] == -1) {
    
27.                         cntUnique++;
    
28.                     }
    
29.                 }
    
30.             }
    
31.             if(cntUnique == 0) {
    
32.                 return 0;
    
33.             }
    
34. 
    
35.             for(int idx = p.length(); idx < s.length(); idx++) {
    
36.                 if(cnts[ s.charAt(idx-p.length()) ] < Integer.MAX_VALUE) {
    
37.                     cnts[ s.charAt(idx-p.length()) ]++;
    
38.                     if(cnts[ s.charAt(idx-p.length()) ] == 0) {
    
39.                         cntUnique--;
    
40.                     } else if(cnts[ s.charAt(idx-p.length()) ] == 1) {
    
41.                         cntUnique++;
    
42.                     }
    
43.                 }
    
44.                 if(cnts[ s.charAt(idx) ] < Integer.MAX_VALUE) {
    
45.                     cnts[ s.charAt(idx) ]--;
    
46.                     if(cnts[ s.charAt(idx) ] == 0) {
    
47.                         cntUnique--;
    
48.                     } else if(cnts[ s.charAt(idx) ] == -1) {
    
49.                         cntUnique++;
    
50.                     }
    
51.                 }
    
52. 
    
53.                 if(cntUnique == 0) {
    
54.                     return idx-p.length()+1;
    
55.                 }
    
56.             }
    
57. 
    
58.             return first;
    
59.         }
    
60.     }
    
61. }
    

复制代码

哎 加油吧

店面这么多题还不过？这个面试官在想啥？

sooorrr 发表于 2016-8-20 04:23
店面这么多题还不过？这个面试官在想啥？

但都不是难题。。。。而且我答的不太好，尤其是最后一题，虽然以前写过一次，但是没参考过答案，可能代码不够简洁，还有漏洞。

第一题的follow up我觉得可以用哈希表记录pattern里每个字符的出现次数，然后在string里维持一个pattern大小的窗口，窗口不断后移，如果遇到一个pattern里的字符就把他的频次-1，移除一个字符就+1。同时维持一个变量记录频次为0的字符的个数。这个值一开始等于pattern里的不同的字符的数量。在移动窗口的时候，一旦有字符的频次被减为0，则将这个变量的值减一。当该变量在某个时候变为0的时候，则找到了一个permutation。

第一题是implement strstr

第一题是implement strstr.
第二题是Minimum Depth of Binary Tree,
第三题是read4k.   Given API: int Read4096(char* buf);  It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file. The return is the number of chars read.   Todo: Use above API to Implement API  "int Read(char* buf, int n)" which reads any number of chars from the file.

都是原题，人品不错啦。。我昨天才面的，都是见到没见过的，连面经都没有的题，还是傻逼烙印给我面的，也挂了。 不过你好歹面了3个题，竟然也挂你？

zyoppy008 发表于 2016-8-20 04:52
都是原题，人品不错啦。。我昨天才面的，都是见到没见过的，连面经都没有的题，还是傻逼烙印给我面的，也挂 ...

你烤了啥题？
等你有了工作也去黑烙印啊