FB店面面经

zhuhai_ZFC 发表于 2016-8-20 04:33
第一题的follow up我觉得可以用哈希表记录pattern里每个字符的出现次数，然后在string里维持一个pattern大 ...

直接用window, 然后 sorted(window) == sorted(pattern)
提起和面试官商量下能否用 built-in sorted.

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

烙印 是不是  故意 难为 华人？

第一题的follow up就是minimum window substring? window size=pattern size

hezhifeng850207 发表于 2016-9-18 23:04
第一题的follow up就是minimum window substring? window size=pattern size

不是的。要找一个字串，里面的所有字符正好是pattern的一个排列。min window substring是找一个最短字串，包含所有pattern的字符，但同时也可以包含其他非pattern的字符。这里的followup仍然要求字符数量上严格匹配，只是顺序随意。有O(n+k)的方法，不过我的代码比较长。

zhuhai_ZFC 发表于 2016-9-19 05:32
不是的。要找一个字串，里面的所有字符正好是pattern的一个排列。min window substring是找一个最短字串 ...

恩，我的意思是，window size=pattern size的时候，不就是保护所有pattern的字符，并且不包含其他非pattern的字符了么？如果string中存在这么一个window的话，那么这个window size刚好就是pattern size。所以我们找到第一个满足条件的window的时候，直接返回就可以了

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

哦 对对对。

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

复制代码

zhuhai_ZFC 发表于 2016-9-20 02:14
能否贴个代码交流一下？我的代码如下:

没有写test case，不知道对不对，求大神莫喷
t是要找的pattern
public class Solution {
    public int minWindow(String s, String t) {
        int[] count=new int[256];
        for (int i=0;i<t.length();i++) count[t.charAt(i)]++;
        int k=0;
        int start=0, end=0;
        while (end<s.length()){
            //k+1 when we find a character in s which is also in t
            if (count[s.charAt(end)]>0) k++;
            count[s.charAt(end)]--;
            while (k==t.length()){
                //return directly when the size of window equals the size of pattern
                if (end-start+1==t.length()) return start;
                if (count[s.charAt(start)]==0) k--;
                count[s.charAt(start)]++;
                start++;
            }
            end++;
        }
        if (minlen==Integer.MAX_VALUE) -1;
        return start;
    }
}

第二题BFS， 不过电面这么搞也太难了吧。。。