《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 10027|回复: 39
收起左侧

脸书家onsite

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

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

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

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

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
    b. Check whether a string is Palindrom
    c. 忘了。。。
4. Design autocomplete in a search engine.1point3acres缃
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;
  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.     }. 鍥磋鎴戜滑@1point 3 acres
  23.     -google 1point3acres
  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;.1point3acres缃
  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;. 1point3acres.com/bbs
  50.         }
  51.     }
  52.    
  53. public:
  54.     // constructor
  55.     WordDictionary() { r = new Nd(); }

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

使用道具 举报

liurudahai 发表于 2016-9-29 00:44:58 | 显示全部楼层
liurudahai 发表于 2016-9-29 00:39-google 1point3acres
第二题是LEETCODE原题吧,如果用*怎么做?是和.差不多,对所有的26个字符同时搜索,只是下去之后相当于又碰 ...
. more info on 1point3acres.com
不对,应该是这样,分两种情况,因为他可以匹配0个字符,所以直接可以用*后面那个字符在当前层搜索,如果失败,因为*可以匹配任何多个字符,那么就对当前层不是NULL的CHILDREN进行递归,然后在下一层再对*后面那个字符进行搜索
回复 支持 1 反对 0

使用道具 举报

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

  1. public class WordDictionary {. 1point3acres.com/bbs
  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();. 1point3acres.com/bbs
  14.             }
  15.             cur = cur.children[index];
  16.             cur.letter = c;
  17.         }
  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) {
  26.         if(cur == null) {
  27.             return false;
  28.         }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  29.         if(index == word.length()) {
  30.             return cur.hasWord;
  31.         }.1point3acres缃
  32.         char c = word.charAt(index);
  33.         if(index == word.length() - 1 || word.charAt(index+1) != '*') {
  34.             if(c == '.') {. 1point3acres.com/bbs
  35.                 for(TrieNode node : cur.children) {
    .1point3acres缃
  36.                     if(search(node, word, index+1)) {
  37.                         return true;
  38.                     }
  39.                 }
  40.                 return false;
  41.             } else if(c == '*') {
  42.                 return false;
  43.             } else {
  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.                     }
  55.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  56.                 return false;
  57.             } else {
  58.                 return search(cur.children[c - 'a'], word, index);
  59.             }
  60.         }

  61.     }
  62.    
  63.     class TrieNode {. Waral 鍗氬鏈夋洿澶氭枃绔,
  64.         TrieNode[] children;
    . more info on 1point3acres.com
  65.         char letter;
  66.         boolean hasWord;
  67.         TrieNode() {.1point3acres缃
  68.             children = new TrieNode[26];
  69.             hasWord = false;
  70.         }
  71.     }
  72. }
复制代码
. more info on 1point3acres.com


.鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs








回复 支持 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;
  4.   return res;
  5. }
复制代码
回复 支持 1 反对 0

使用道具 举报

Fustang 发表于 2016-7-2 22:04:37 | 显示全部楼层
ccrjohn8787 发表于 2016-7-2 20:55. Waral 鍗氬鏈夋洿澶氭枃绔,
多谢楼主!请问最后一题有什么要求吗?constant space?不然是不是扫一遍记一下不大于N的数,然后用个rand?
. Waral 鍗氬鏈夋洿澶氭枃绔,
那题应该是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 | 显示全部楼层
ChrisGates23 发表于 2016-7-10 06:02. more info on 1point3acres.com
I mean followup

需要的
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
字数字数
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
. 1point3acres.com/bbs
三十多年马工经验了。。。
回复 支持 反对

使用道具 举报

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

我勒个去。。
.1point3acres缃
回复 支持 反对

使用道具 举报

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-11-20 03:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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