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


一亩三分地论坛

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

求问两道fb面经题

[复制链接] |试试Instant~ |关注本帖
gundamkeroro 发表于 2017-11-12 08:38:10 | 显示全部楼层 |阅读模式

2019(4-6月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
求问fb的面经题 给定两个压缩表示的vector 比如[(3,2),(4,1),(2,3)] 就是[2, 2, 2, 1, 1, 1, 1, 3, 3]的缩写 现在给你两个这样压缩好的vetcor 让你求和 当两个长度不同的时候 按最小一个的长度算
. Waral 鍗氬鏈夋洿澶氭枃绔,
trie的搜索, 和李口儿妖妖有些不同。搜索返回所有符合wildcard的词
比如
add("car"). 1point3acres.com/bbs
add("caw")
add("cauw"). 1point3acres.com/bbs
search("c*w") 返回 "caw" 和 "cauw".
. Waral 鍗氬鏈夋洿澶氭枃绔,


还有一道给定 一个字符串和一个切分长度k 比如:
"This is a good day" k=10
切分为:
"This (1/4)"
"is a (2/4)". more info on 1point3acres.com
"good (3/4)". more info on 1point3acres.com
"day (4/4)"
也就是说每个切分后面还要带上一个后缀 而且这个后缀还是算长度的 最后返回的切分最小需要多少下



补充内容 (2017-11-12 08:39):
修正一下 第一个不是求和 是求vector点乘

本帖被以下淘专辑推荐:

ccwei1001 发表于 6 天前 | 显示全部楼层
跟原提想法很像 加一些改編
  1. void Main() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. {
  3.         var wordDict = new WordDictionary();
  4.         wordDict.AddWord("car");
  5.         wordDict.AddWord("caaw");
  6.         wordDict.AddWord("cauw");
  7.         wordDict.AddWord("cw");
  8.         Console.WriteLine(wordDict.Search("c*w"));. 鍥磋鎴戜滑@1point 3 acres
  9. }

  10. public class WordDictionary {
  11.     private TrieNode root;
  12.    
  13.     /** Initialize your data structure here. */
  14.     public WordDictionary() {
  15.         this.root = new TrieNode();
  16.     }
  17.    
  18.     /** Adds a word into the data structure. */
  19.     public void AddWord(string word) {
  20.         TrieNode node = this.root;
  21.         foreach(char c in word) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.             if(!node.ContainsChild(c)) {
  23.                 node.SetChild(c, new TrieNode());
  24.             }
  25.             node = node.GetChild(c);
  26.         }
  27.         node.MarkWord();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.     }
  29.     . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.     public HashSet<string> Search(string word) {
  31.                 var result = new HashSet<string>();
  32.         Search(word, this.root, "", result);
  33.                 return result;
  34.     }
  35.    
  36.     private void Search(string word, TrieNode node, string soFar, HashSet<string> result) {-google 1point3acres
  37.         if(node == null && string.IsNullOrEmpty(word)) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.             result.Add(soFar);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.                         return;
  40.         }
  41.         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.         TrieNode current = node;
  43.         
  44.         for(int i = 0; i < word.Length; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  45.             char c = word[i];
  46.             if(c != '*') {
  47.                 // If c != '*', regular search
  48.                 if(current.ContainsChild(c)){
  49.                                         soFar += c;
  50.                     current = current.GetChild(c);
  51.                 } else {
  52.                     return;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  53.                 }   
  54.             } else {
  55.                                 // Skip the * to check the scenario where * matches nothing
  56.                                 Search(word.Substring(i + 1), current, soFar, result);
  57.                         .1point3acres缃
  58.                 // Search for all children
  59.                 foreach(var key in current.GetChildrenKeys()) {
  60.                                         //Check if * matches any current char
  61.                     Search(word.Substring(i + 1), current.GetChild(key), soFar + key, result);
  62.                                        
  63.                                         //Check if * matches any current char, and possibly more char later
  64.                                         Search(word.Substring(i), current.GetChild(key), soFar + key, result);.1point3acres缃
  65.                 }
  66.                 return;
  67.             }
  68.             
  69.         }
  70.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  71.                 // All chars match, make sure this is a word
  72.          if(current != null && current.IsWord) {
  73.                          result.Add(soFar);
  74.                  }
  75.     }
  76. }
  77. . more info on 1point3acres.com
  78. class TrieNode
  79. {
  80.     private IDictionary<char, TrieNode> children;
  81.     public bool IsWord { get; private set; }
  82.     // Initialize your data structure here.
  83.     public TrieNode() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  84.     {
  85.         this.children = new Dictionary<char, TrieNode>();.1point3acres缃
  86.     }
  87.     . 1point 3acres 璁哄潧
  88.     public ICollection<char> GetChildrenKeys() {
  89.         return children.Keys;
  90.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  91.    
    -google 1point3acres
  92.     public bool ContainsChild(char c) {
  93.         return children.ContainsKey(c);
  94.     }.1point3acres缃
  95.    
  96.     public TrieNode GetChild(char c) {
  97.         return children[c];. visit 1point3acres.com for more.
  98.     }
  99.    
  100.     public TrieNode SetChild(char c, TrieNode node) {. 鍥磋鎴戜滑@1point 3 acres
  101.         return children[c] = node;
  102.     }
  103.    
  104.     public void MarkWord() {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  105.         this.IsWord = true;
  106.     }
  107. }
复制代码
回复 支持 1 反对 0

使用道具 举报

zachzuogwu 发表于 2017-11-13 01:58:22 | 显示全部楼层
gundamkeroro 发表于 2017-11-12 13:04
嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理

sorry 理解错题了。这样的话,因为leaf存在才算找到了,那string从后向前,树从下往上,同时开始。如果遇到string里的star,直接从trie的当前层找star前面的字母直到找到为止。search成功的条件就是同时到达最前面。有些corner case需要注意。也不知道对不对,错了的话还请谅解。
回复 支持 0 反对 1

使用道具 举报

chengshuangdao 发表于 2017-11-12 08:59:12 | 显示全部楼层
这是实习题目吗,感觉路子很野啊,第一题可以顺序比较两个vector内的每个tuple的第一位,比如两个(a1, b1), (a2, b2),可以算Min(a1, a2)*b1*b2,较小的a所在的tuple过掉,较大的a所在的tuple更新a值为Math.abs(a1-a2),然后每一次都这么比较,直到某一个vector到达最后
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 11:18:02 | 显示全部楼层
chengshuangdao 发表于 2017-11-12 08:59
这是实习题目吗,感觉路子很野啊,第一题可以顺序比较两个vector内的每个tuple的第一位,比如两个(a1, b1), ...

后两道确实有点野
回复 支持 反对

使用道具 举报

zachzuogwu 发表于 2017-11-12 11:27:59 | 显示全部楼层
第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 11:44:08 | 显示全部楼层
zachzuogwu 发表于 2017-11-12 11:27
第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串

没有明白 你的意思是在节点额外存单词的后缀?
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-11-12 11:57:25 | 显示全部楼层
"字符串和一个切分长度k "没看懂啊
回复 支持 反对

使用道具 举报

prince123 发表于 2017-11-12 12:01:08 | 显示全部楼层
edyyy 发表于 2017-11-12 11:57
"字符串和一个切分长度k "没看懂啊

同没看明白。。关注一下。。这是楼主看的面经还是楼主被面倒的题目?
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 12:34:09 | 显示全部楼层
prince123 发表于 2017-11-12 12:01. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
同没看明白。。关注一下。。这是楼主看的面经还是楼主被面倒的题目?

别人的 别人被面倒了
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 12:35:37 | 显示全部楼层
edyyy 发表于 2017-11-12 11:57
"字符串和一个切分长度k "没看懂啊
. Waral 鍗氬鏈夋洿澶氭枃绔,
就是每行的长度除了最后一行 都是k 然后不足的长度用空格补齐 具体规则和text justification 差不多 但是现在后面加了一个(i/n)的后缀 而且这个后缀还要占字符
回复 支持 反对

使用道具 举报

zachzuogwu 发表于 2017-11-12 12:52:53 | 显示全部楼层
gundamkeroro 发表于 2017-11-12 11:44
没有明白 你的意思是在节点额外存单词的后缀?

你看下trie tree的建造就知道了 我说的莉蔻那道题只用search存在与否 所以当add到最后一个字母的时候 将boolean改为true即可…如果你要返回字符串的话 那么当add到最后一个字母的时候 将字符串存在leaf里…
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 13:04:38 | 显示全部楼层
zachzuogwu 发表于 2017-11-12 12:52
你看下trie tree的建造就知道了 我说的莉蔻那道题只用search存在与否 所以当add到最后一个字母的时候 将b ...

嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理
回复 支持 反对

使用道具 举报

say543 发表于 2017-11-12 14:52:00 | 显示全部楼层
gundamkeroro 发表于 2017-11-12 13:04
嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理
. From 1point 3acres bbs

暴力做行吗? * 有两种选择 一种继续 move on to next level tries 另一 种skip ?
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-12 19:19:25 | 显示全部楼层
say543 发表于 2017-11-12 14:52
暴力做行吗? * 有两种选择 一种继续 move on to next level tries 另一 种skip ?

听面试人说 考官说这种不够smart...
回复 支持 反对

使用道具 举报

qq274880049 发表于 2017-11-13 01:53:36 | 显示全部楼层
那个trie的题目去年的面经看到过,但是那个是给在职跳槽的题目, 你确定实习也被面了这题? 而且当时在职跳槽面的也只是判断‘c*a’ 是否存在,而不是打印出所有结果。。
回复 支持 反对

使用道具 举报

 楼主| gundamkeroro 发表于 2017-11-13 02:37:01 | 显示全部楼层
qq274880049 发表于 2017-11-13 01:53
那个trie的题目去年的面经看到过,但是那个是给在职跳槽的题目, 你确定实习也被面了这题? 而且当时在职跳 ...

不确定是不是实习面的 但是说这道题的人是在实习群说的 打印倒是不是主要难点
回复 支持 反对

使用道具 举报

cathylan2016 发表于 2017-11-13 03:27:03 | 显示全部楼层
gundamkeroro 发表于 2017-11-12 12:35
就是每行的长度除了最后一行 都是k 然后不足的长度用空格补齐 具体规则和text justification 差不多 但是 ...
.1point3acres缃
典型binary search 的方法,,,,,值位于len(string)/k 和len(string) 之间。。加一个helper函数
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 05:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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