一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5308|回复: 36
收起左侧

脸书家onsite

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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
3. a. Minimum Size Subarray Sum. 鍥磋鎴戜滑@1point 3 acres
    b. Check whether a string is Palindrom
    c. 忘了。。。
4. Design autocomplete in a search engine.鐣欏璁哄潧-涓浜-涓夊垎鍦
5. behavior question. 最后的coding是给一个数组和一个数N, 随机返回该数组中任意一个不大于N的数。


评分

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
  2.     bool flag; // true if representing a word
  3.     vector<Nd*> next;. 1point3acres.com/bbs
  4.     Nd():flag(false),next(vector<Nd*>(26)) {}. more info on 1point3acres.com
  5. };
  6.     . from: 1point3acres.com/bbs
  7. class WordDictionary {
  8. private:   
  9.     Nd* r; // dummy root for Trie. 鍥磋鎴戜滑@1point 3 acres
  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';. visit 1point3acres.com for more.
  16.         for (int i = 0; i < 26; ++i) {
  17.           if (!cur->next[i]) continue;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.           if (ic == i || ic < 0 || ic >= 26) . 鍥磋鎴戜滑@1point 3 acres
  19.              nodes.push_back(cur->next[i]);
  20.           getNodes(cur->next[i], c, nodes);. from: 1point3acres.com/bbs
  21.         }. From 1point 3acres bbs
  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. From 1point 3acres bbs
  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(); }-google 1point3acres

  56.     // Adds a word into the data structure.
  57.     void addWord(string word) {
  58.         Nd* cur = r;
  59.         for (char c:word) {
  60.             int i = c-'a';
  61.             if (!cur->next[i]) cur->next[i] = new Nd();
  62.             cur = cur->next[i];
  63.         }
  64.         cur->flag = true;. more info on 1point3acres.com
  65.     }

  66.     // Returns if the word is in the data structure. Support '.' and '*'
  67.     bool search(string word) { return mySearch(word, 0, r); }
  68. };
复制代码
回复 支持 2 反对 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;
  4.   return res;
  5. }
复制代码
回复 支持 1 反对 0

使用道具 举报

Fustang 发表于 2016-7-2 22:04:37 | 显示全部楼层
ccrjohn8787 发表于 2016-7-2 20:55
多谢楼主!请问最后一题有什么要求吗?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 | 显示全部楼层

三十多年马工经验了。。。
回复 支持 反对

使用道具 举报

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下一位
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 03:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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