脸书家onsite

脸家效率很高， 两三天后就发了offer, 然后级别数字居然和目前的一模一样， 还不给加面。。。这和拒信有什么区别呢。。。只能锯掉了

1. behavior question。 最后问了道dot product的老题
2. given a list of words, find whether a given target word exists. Should support “.” which matches any character. Follow up: support “*” which matchs 0 or more char

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

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

coding是给一个数组和一个数N， 随机返回该数组中任意一个不大于N的数。

forestwn 发表于 2016-10-9 02:41
211 Add and Search Word - Data structure design, Follow up: support “*” which matchs 0 or more cha ...

这个应该就是LC211的扩展了，加上了support for '*'. 关键是当search word遇到'*'，要跳过所有可能连续的'*'继续寻找下一个非'*'的char。在字典数据结构的Trie中就对于找当前node的所有对应的子孙nodes（若是'.'就找所有子孙）。然后再循环每个子孙node递归。一个edge case就是若word以连续的'*'结尾的话就直接返回true，因为'*'之前的prefix在字典中已经找到了。
大家看看code有没有问题。

1. struct Nd { // Trie node for dictionary
   
2.     bool flag; // true if representing a word
   
3.     vector<Nd*> next;
   
4.     Nd():flag(false),next(vector<Nd*>(26)) {}
   
5. };
   
6.    
   
7. class WordDictionary {
   
8. private:   
   
9.     Nd* r; // dummy root for Trie
   
10.    
    
11.     // get all nodes from descendants of cur representing as char c;
    
12.     // if c is not alphabet, get all descendants
    
13.     void getNodes(Nd* cur, char c, vector<Nd*>& nodes) {
    
14.         if (!cur) return;
    
15.         int ic = c - 'a';
    
16.         for (int i = 0; i < 26; ++i) {
    
17.           if (!cur->next[i]) continue;
    
18.           if (ic == i || ic < 0 || ic >= 26)
    
19.              nodes.push_back(cur->next[i]);
    
20.           getNodes(cur->next[i], c, nodes);
    
21.         }
    
22.     }
    
23.    
    
24.     // search word w from index start
    
25.     bool mySearch(string w, int start, Nd* cur) {
    
26.         if (!cur) return false;
    
27.         int n = w.length();
    
28.         if (start == n) return cur->flag;
    
29.         else if (start > n) return false;
    
30.         
    
31.         char c = w[start];
    
32.         if (c >= 'a' && c <= 'z') { // c is alphabet
    
33.             return mySearch(w, start+1, cur->next[c-'a']);
    
34.         }else if (c == '.') { // c is '.'
    
35.             for (int i = 0; i < 26; i++) {
    
36.                if (mySearch(w, start+1, cur->next[i])) return true;
    
37.             }
    
38.             return false;
    
39.         }else { // c is '*'
    
40.            // find next non '*' char and store it in c
    
41.            while (++start < n && (c=w[start]) == '*') continue;
    
42.            if (start == n) return true; // all trailing '*''s
    
43.            // get all nodes from descendants of cur representing as char c;
    
44.            // otherwise c is '.', and so get all descendants
    
45.            vector<Nd*> nodes; getNodes(cur, c, nodes);
    
46.            for (auto node : nodes) {
    
47.                if (mySearch(w, start, node)) return true;
    
48.            }
    
49.            return false;
    
50.         }
    
51.     }
    
52.    
    
53. public:
    
54.     // constructor
    
55.     WordDictionary() { r = new Nd(); }
    
56. 
    
57.     // Adds a word into the data structure.
    
58.     void addWord(string word) {
    
59.         Nd* cur = r;
    
60.         for (char c:word) {
    
61.             int i = c-'a';
    
62.             if (!cur->next[i]) cur->next[i] = new Nd();
    
63.             cur = cur->next[i];
    
64.         }
    
65.         cur->flag = true;
    
66.     }
    
67. 
    
68.     // Returns if the word is in the data structure. Support '.' and '*'
    
69.     bool search(string word) { return mySearch(word, 0, r); }
    
70. };

复制代码

贴我的代码，我这儿'*'是match 0个或多个前缀字符的 '*' Matches zero or more of the preceding element

1. public class WordDictionary {
   
2.     TrieNode root;
   
3.     WordDictionary() {
   
4.         root = new TrieNode();
   
5.     }
   
6.     // Adds a word into the data structure.
   
7.     public void addWord(String word) {
   
8.         TrieNode cur = root;
   
9.         for(int i=0; i<word.length(); i++) {
   
10.             char c = word.charAt(i);
    
11.             int index = c - 'a';
    
12.             if(cur.children[index] == null) {
    
13.                 cur.children[index] = new TrieNode();
    
14.             }
    
15.             cur = cur.children[index];
    
16.             cur.letter = c;
    
17.         }
    
18.         cur.hasWord = true;
    
19.     }
    
20. 
    
21.     public boolean search(String word) {
    
22.         TrieNode cur = root;
    
23.         return search(root, word, 0);
    
24.     }
    
25.    
    
26.     private boolean search(TrieNode cur, String word, int index) {
    
27.         if(cur == null) {
    
28.             return false;
    
29.         }
    
30.         if(index == word.length()) {
    
31.             return cur.hasWord;
    
32.         }
    
33.         char c = word.charAt(index);
    
34.         if(index == word.length() - 1 || word.charAt(index+1) != '*') {
    
35.             if(c == '.') {
    
36.                 for(TrieNode node : cur.children) {
    
37.                     if(search(node, word, index+1)) {
    
38.                         return true;
    
39.                     }
    
40.                 }
    
41.                 return false;
    
42.             } else if(c == '*') {
    
43.                 return false;
    
44.             } else {
    
45.                 return search(cur.children[c - 'a'], word, index+1);
    
46.             }
    
47.         } else {
    
48.             if(search(cur, word, index+2)) {
    
49.                 return true;
    
50.             }
    
51.             if(c == '.') {
    
52.                 for(TrieNode node : cur.children) {
    
53.                     if(search(node, word, index)) {
    
54.                         return true;
    
55.                     }
    
56.                 }
    
57.                 return false;
    
58.             } else {
    
59.                 return search(cur.children[c - 'a'], word, index);
    
60.             }
    
61.         }
    
62. 
    
63.     }
    
64.    
    
65.     class TrieNode {
    
66.         TrieNode[] children;
    
67.         char letter;
    
68.         boolean hasWord;
    
69.         TrieNode() {
    
70.             children = new TrieNode[26];
    
71.             hasWord = false;
    
72.         }
    
73.     }
    
74. }

复制代码

ccrjohn8787 发表于 2016-7-2 20:55
多谢楼主！请问最后一题有什么要求吗？constant space?不然是不是扫一遍记一下不大于N的数，然后用个rand?

只需要O(1)，不要存<=max的值，对<=max的直接做reservoir sampling即可。O(N) one pass 时间复杂度。

1. int getRand(const vector<int>& a, int high) {
   
2.   int res = INT_MIN, count = 0;
   
3.   for (int x:a) if (x <= high && rand()%(++count) == 0) res = x;
   
4.   return res;
   
5. }

复制代码

Minimum Size Subarray Sum题目要求是什么啊？能细说下吗？

多谢楼主！请问最后一题有什么要求吗？constant space?不然是不是扫一遍记一下不大于N的数，然后用个rand?

ccrjohn8787 发表于 2016-7-2 20:55
多谢楼主！请问最后一题有什么要求吗？constant space?不然是不是扫一遍记一下不大于N的数，然后用个rand?

那题应该是FB常考题random max index的变种 可以用Reservoir Sampling 不需要额外space

pustar 发表于 2016-7-2 16:45
Minimum Size Subarray Sum题目要求是什么啊？能细说下吗？

leetcode原题啊

dot product 是什么题？ 直接球dot product？

求问楼主 autocomplete 是怎么回答的

同问autocomplete怎么答的？谢谢

请问题2需要写代码么

ChrisGates23 发表于 2016-7-10 05:59
请问题2需要写代码么

I mean followup