Airbnb 2018年春季E6 package

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2318|回复: 25
收起左侧

求问两道fb面经题

[复制链接] |试试Instant~ |关注本帖
我的人缘0
gundamkeroro 发表于 2017-11-12 08:38:10 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩

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

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

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

x
求问fb的面经题 给定两个压缩表示的vector 比如[(3,2),(4,1),(2,3)] 就是[2, 2, 2, 1, 1, 1, 1, 3, 3]的缩写 现在给你两个这样压缩好的vetcor 让你求和 当两个长度不同的时候 按最小一个的长度算

trie的搜索, 和李口儿妖妖有些不同。搜索返回所有符合wildcard的词
比如. From 1point 3acres bbs
add("car")
add("caw")
add("cauw")
search("c*w") 返回 "caw" 和 "cauw"..留学论坛-一亩-三分地



还有一道给定 一个字符串和一个切分长度k 比如:
"This is a good day" k=10
切分为:. visit 1point3acres for more.
"This (1/4)"
"is a (2/4)"
"good (3/4)".本文原创自1point3acres论坛
"day (4/4)"
也就是说每个切分后面还要带上一个后缀 而且这个后缀还是算长度的 最后返回的切分最小需要多少下. Waral 博客有更多文章,



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

上一篇:LinkedIn HR面
下一篇:drive.ai OA

本帖被以下淘专辑推荐:

我的人缘0
ccwei1001 发表于 2017-11-15 11:17:02 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
跟原提想法很像 加一些改編. 牛人云集,一亩三分地
  1. void Main()
  2. {
  3.         var wordDict = new WordDictionary();
  4.         wordDict.AddWord("car");. visit 1point3acres for more.
  5.         wordDict.AddWord("caaw");
  6.         wordDict.AddWord("cauw");
  7.         wordDict.AddWord("cw");
  8.         Console.WriteLine(wordDict.Search("c*w"));
  9. }

  10. public class WordDictionary {
  11.     private TrieNode root;
  12.     . 1point3acres
  13.     /** Initialize your data structure here. */
  14.     public WordDictionary() {
  15.         this.root = new TrieNode();.本文原创自1point3acres论坛
  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>();-google 1point3acres
  32.         Search(word, this.root, "", result);
  33.                 return result;
  34.     }
  35.    
  36.     private void Search(string word, TrieNode node, string soFar, HashSet<string> result) {
  37.         if(node == null && string.IsNullOrEmpty(word)) {
  38.             result.Add(soFar);. Waral 博客有更多文章,
  39.                         return;.1point3acres网
  40.         }
  41.         
    . 1point 3acres 论坛
  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 {.本文原创自1point3acres论坛
  55.                                 // Skip the * to check the scenario where * matches nothing. Waral 博客有更多文章,
  56.                                 Search(word.Substring(i + 1), current, soFar, result);
    . 一亩-三分-地,独家发布
  57.                        
  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);
  65.                 }. Waral 博客有更多文章,
  66.                 return;
  67.             }
  68.             
  69.         }
  70.         .本文原创自1point3acres论坛
  71.                 // All chars match, make sure this is a word
  72.          if(current != null && current.IsWord) {
    .留学论坛-一亩-三分地
  73.                          result.Add(soFar);
  74.                  }
  75.     }
  76. }
    来源一亩.三分地论坛.

  77. class TrieNode
  78. {
  79.     private IDictionary<char, TrieNode> children;
  80.     public bool IsWord { get; private set; }
  81.     // Initialize your data structure here.
  82.     public TrieNode()
  83.     {
  84.         this.children = new Dictionary<char, TrieNode>();
  85.     }
  86.    
  87.     public ICollection<char> GetChildrenKeys() {
  88.         return children.Keys;
  89.     }
  90.    
  91.     public bool ContainsChild(char c) {
  92.         return children.ContainsKey(c);
  93.     } 来源一亩.三分地论坛.
  94.    
  95.     public TrieNode GetChild(char c) {
  96.         return children[c];
  97.     }
  98.    
  99.     public TrieNode SetChild(char c, TrieNode node) {
  100.         return children[c] = node;
  101.     }
  102.     .1point3acres网
  103.     public void MarkWord() {
  104.         this.IsWord = true;
  105.     }
  106. }
复制代码
回复

使用道具 举报

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

使用道具 举报

我的人缘0
zachzuogwu 发表于 2017-11-13 01:58:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
gundamkeroro 发表于 2017-11-12 13:04
嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理

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

使用道具 举报

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

后两道确实有点野
回复

使用道具 举报

我的人缘0
zachzuogwu 发表于 2017-11-12 11:27:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串
回复

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-12 11:44:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
zachzuogwu 发表于 2017-11-12 11:27
第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串

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

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-12 11:57:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (79)
 
 
15% (15)  踩
"字符串和一个切分长度k "没看懂啊
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
prince123 发表于 2017-11-12 12:01:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (216)
 
 
11% (27)  踩
edyyy 发表于 2017-11-12 11:57
"字符串和一个切分长度k "没看懂啊

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

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-12 12:34:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
prince123 发表于 2017-11-12 12:01
同没看明白。。关注一下。。这是楼主看的面经还是楼主被面倒的题目?

别人的 别人被面倒了
回复

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-12 12:35:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
edyyy 发表于 2017-11-12 11:57
"字符串和一个切分长度k "没看懂啊

就是每行的长度除了最后一行 都是k 然后不足的长度用空格补齐 具体规则和text justification 差不多 但是现在后面加了一个(i/n)的后缀 而且这个后缀还要占字符
回复

使用道具 举报

我的人缘0
zachzuogwu 发表于 2017-11-12 12:52:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
gundamkeroro 发表于 2017-11-12 11:44
没有明白 你的意思是在节点额外存单词的后缀?
. 一亩-三分-地,独家发布
你看下trie tree的建造就知道了 我说的莉蔻那道题只用search存在与否 所以当add到最后一个字母的时候 将boolean改为true即可…如果你要返回字符串的话 那么当add到最后一个字母的时候 将字符串存在leaf里…
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
say543 发表于 2017-11-12 14:52:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (31)
 
 
16% (6)  踩
gundamkeroro 发表于 2017-11-12 13:04
嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理

来源一亩.三分地论坛.
暴力做行吗? * 有两种选择 一种继续 move on to next level tries 另一 种skip ?
回复

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-12 19:19:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
say543 发表于 2017-11-12 14:52
暴力做行吗? * 有两种选择 一种继续 move on to next level tries 另一 种skip ?

听面试人说 考官说这种不够smart...
回复

使用道具 举报

我的人缘0
qq274880049 发表于 2017-11-13 01:53:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (279)
 
 
31% (131)  踩
那个trie的题目去年的面经看到过,但是那个是给在职跳槽的题目, 你确定实习也被面了这题? 而且当时在职跳槽面的也只是判断‘c*a’ 是否存在,而不是打印出所有结果。。
回复

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-13 02:37:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
qq274880049 发表于 2017-11-13 01:53
那个trie的题目去年的面经看到过,但是那个是给在职跳槽的题目, 你确定实习也被面了这题? 而且当时在职跳 ...

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

使用道具 举报

我的人缘0
cathylan2016 发表于 2017-11-13 03:27:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
gundamkeroro 发表于 2017-11-12 12:35. Waral 博客有更多文章,
就是每行的长度除了最后一行 都是k 然后不足的长度用空格补齐 具体规则和text justification 差不多 但是 ...

典型binary search 的方法,,,,,值位于len(string)/k 和len(string) 之间。。加一个helper函数
回复

使用道具 举报

我的人缘0
ARUI35 发表于 2017-11-26 06:22:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (73)
 
 
2% (2)  踩
帮顶一下,最后那个切分长度为k的,感觉难点在于首先要算出一共有多少行吗?毕竟(1/10)的长度是6, 但是(10/10)的长度又变成7了,感觉应该是有些tricks没有想到。 楼主有思路了吗?
回复

使用道具 举报

我的人缘0
douch 发表于 2017-11-27 08:01:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (17)
 
 
10% (2)  踩
有wildcard的这种search必须要用trie么?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-17 16:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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