推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 9591|回复: 39
收起左侧

脸书家onsite

[复制链接] |试试Instant~ |关注本帖
kunzi 发表于 2016-7-2 13:23:56 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Pass在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x

脸家效率很高, 两三天后就发了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 characters
.1point3acres缃3. a. Minimum Size Subarray Sum. from: 1point3acres.com/bbs
    b. Check whether a string is Palindrom
    c. 忘了。。。
4. Design autocomplete in a search engine
5. behavior question. 最后的coding是给一个数组和一个数N, 随机返回该数组中任意一个不大于N的数。. visit 1point3acres.com for more.

. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

4

查看全部评分

zzgzzm 发表于 2016-11-6 12:56:14 | 显示全部楼层
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. visit 1point3acres.com for more.
  2.     bool flag; // true if representing a word
  3.     vector<Nd*> next;
  4.     Nd():flag(false),next(vector<Nd*>(26)) {}
  5. };.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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]); . From 1point 3acres bbs
  20.           getNodes(cur->next[i], c, nodes);
  21.         }
  22.     }. From 1point 3acres bbs
  23.     . visit 1point3acres.com for more.
  24.     // search word w from index start
  25.     bool mySearch(string w, int start, Nd* cur) {. 1point3acres.com/bbs
  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.             }.1point3acres缃
  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.     }. more info on 1point3acres.com
  52.    
  53. public:
  54.     // constructor
  55.     WordDictionary() { r = new Nd(); }
  56. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  57.     // Adds a word into the data structure.. visit 1point3acres.com for more.
  58.     void addWord(string word) {. 1point 3acres 璁哄潧
  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];. From 1point 3acres bbs
  64.         }
  65.         cur->flag = true;
  66.     }

  67.     // Returns if the word is in the data structure. Support '.' and '*'
  68.     bool search(string word) { return mySearch(word, 0, r); }.1point3acres缃
  69. };
复制代码
回复 支持 2 反对 0

使用道具 举报

liurudahai 发表于 2016-9-29 00:44:58 | 显示全部楼层
liurudahai 发表于 2016-9-29 00:39
. 鍥磋鎴戜滑@1point 3 acres第二题是LEETCODE原题吧,如果用*怎么做?是和.差不多,对所有的26个字符同时搜索,只是下去之后相当于又碰 ...

不对,应该是这样,分两种情况,因为他可以匹配0个字符,所以直接可以用*后面那个字符在当前层搜索,如果失败,因为*可以匹配任何多个字符,那么就对当前层不是NULL的CHILDREN进行递归,然后在下一层再对*后面那个字符进行搜索
回复 支持 1 反对 0

使用道具 举报

fubu 发表于 2016-11-6 13:36:44 | 显示全部楼层
贴我的代码,我这儿'*'是match 0个或多个前缀字符的 '*' Matches zero or more of the preceding element. visit 1point3acres.com for more.

  1. public class WordDictionary {
  2.     TrieNode root;
  3.     WordDictionary() {
  4.         root = new TrieNode();
  5.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.         }-google 1point3acres
  18.         cur.hasWord = true;
  19.     }

  20.     public boolean search(String word) {
  21.         TrieNode cur = root;
  22.         return search(root, word, 0);
  23.     }
  24.    
  25.     private boolean search(TrieNode cur, String word, int index) {. visit 1point3acres.com for more.
  26.         if(cur == null) {
  27.             return false;
  28.         }
  29.         if(index == word.length()) {. 鍥磋鎴戜滑@1point 3 acres
  30.             return cur.hasWord;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  31.         }
  32.         char c = word.charAt(index);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  33.         if(index == word.length() - 1 || word.charAt(index+1) != '*') {. 鍥磋鎴戜滑@1point 3 acres
  34.             if(c == '.') {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.                 for(TrieNode node : cur.children) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.                     if(search(node, word, index+1)) {
  37.                         return true;.1point3acres缃
  38.                     }
  39.                 }
  40.                 return false;-google 1point3acres
  41.             } else if(c == '*') {
  42.                 return false;. from: 1point3acres.com/bbs
  43.             } else {. 1point3acres.com/bbs
  44.                 return search(cur.children[c - 'a'], word, index+1);
  45.             }
  46.         } else {
  47.             if(search(cur, word, index+2)) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  48.                 return true;
  49.             }
  50.             if(c == '.') {
  51.                 for(TrieNode node : cur.children) {
  52.                     if(search(node, word, index)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  53.                         return true;
  54.                     }. 1point 3acres 璁哄潧
  55.                 }
  56.                 return false;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  57.             } else {
  58.                 return search(cur.children[c - 'a'], word, index);
  59.             }
  60.         }. 1point 3acres 璁哄潧

  61.     }. From 1point 3acres bbs
  62.    
  63.     class TrieNode {
  64.         TrieNode[] children;
  65.         char letter;
  66.         boolean hasWord;. Waral 鍗氬鏈夋洿澶氭枃绔,
  67.         TrieNode() {
  68.             children = new TrieNode[26];
  69.             hasWord = false;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  70.         }
  71.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  72. }
复制代码



. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

.鏈枃鍘熷垱鑷1point3acres璁哄潧






. 鍥磋鎴戜滑@1point 3 acres
回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-6 10:02:00 | 显示全部楼层
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;. 1point 3acres 璁哄潧
  4.   return res;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  5. }
复制代码
回复 支持 1 反对 0

使用道具 举报

Fustang 发表于 2016-7-2 22:04:37 | 显示全部楼层
ccrjohn8787 发表于 2016-7-2 20:55. 1point 3acres 璁哄潧
多谢楼主!请问最后一题有什么要求吗?constant space?不然是不是扫一遍记一下不大于N的数,然后用个rand?

那题应该是FB常考题random max index的变种 可以用Reservoir Sampling 不需要额外space
回复 支持 0 反对 1

使用道具 举报

pustar 发表于 2016-7-2 16:45:09 | 显示全部楼层
Minimum Size Subarray Sum题目要求是什么啊?能细说下吗?
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-7-2 20:55:30 | 显示全部楼层
多谢楼主!请问最后一题有什么要求吗?constant space?不然是不是扫一遍记一下不大于N的数,然后用个rand?
回复 支持 反对

使用道具 举报

 楼主| kunzi 发表于 2016-7-2 22:52:53 来自手机 | 显示全部楼层
pustar 发表于 2016-7-2 16:45. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Minimum Size Subarray Sum题目要求是什么啊?能细说下吗?

leetcode原题啊
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-7-7 11:48:31 | 显示全部楼层
dot product 是什么题? 直接球dot product?
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-8 03:14:26 | 显示全部楼层
求问楼主 autocomplete 是怎么回答的
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-9 13:48:34 | 显示全部楼层
同问autocomplete怎么答的?谢谢
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2016-7-10 05:59:53 | 显示全部楼层
请问题2需要写代码么
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2016-7-10 06:02:44 | 显示全部楼层
ChrisGates23 发表于 2016-7-10 05:59
请问题2需要写代码么

I mean followup
回复 支持 反对

使用道具 举报

 楼主| kunzi 发表于 2016-7-10 06:28:11 | 显示全部楼层

需要的

字数字数
回复 支持 反对

使用道具 举报

hanabeast 发表于 2016-7-10 07:56:14 | 显示全部楼层
楼主本来是哪里的 G?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-10 10:31:39 来自手机 | 显示全部楼层
楼主几年经验?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-10 10:31:43 来自手机 | 显示全部楼层
楼主几年经验?
回复 支持 反对

使用道具 举报

 楼主| kunzi 发表于 2016-7-10 12:37:22 | 显示全部楼层
. 鍥磋鎴戜滑@1point 3 acres
三十多年马工经验了。。。
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-11 03:47:43 | 显示全部楼层
kunzi 发表于 2016-7-10 12:37
三十多年马工经验了。。。

我勒个去。。
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-8-31 13:57:56 | 显示全部楼层
kunzi 发表于 2016-7-10 12:37
三十多年马工经验了。。。

神马是三十多年马工经验。。求详情
回复 支持 反对

使用道具 举报

leyhzm 发表于 2016-8-31 23:28:10 | 显示全部楼层
请问楼主 面试完后一天有收到填面试feedback的邮件嘛?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-29 00:39:38 | 显示全部楼层
第二题是LEETCODE原题吧,如果用*怎么做?是和.差不多,对所有的26个字符同时搜索,只是下去之后相当于又碰到了一个*么,而不是直接MATCH下一位
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-18 03:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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