工业界资深数据科学家现场教你修改求职简历
小K现场教你修改求职简历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 2739|回复: 25
收起左侧

求问两道fb面经题

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

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的词
比如.留学论坛-一亩-三分地
add("car")
add("caw")
add("cauw")
search("c*w") 返回 "caw" 和 "cauw".

. 1point 3acres 论坛

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



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

评分

参与人数 1大米 +5 收起 理由
i563214f + 5 给你点个赞!

查看全部评分


上一篇:LinkedIn HR面
下一篇:求面经 a9 computer vision/ visual search

本帖被以下淘专辑推荐:

我的人缘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");
  5.         wordDict.AddWord("caaw");
  6.         wordDict.AddWord("cauw");
  7.         wordDict.AddWord("cw");
  8.         Console.WriteLine(wordDict.Search("c*w"));
  9. }

  10. public class WordDictionary {. 围观我们@1point 3 acres
  11.     private TrieNode root;. 1point3acres
  12.    
  13.     /** Initialize your data structure here. */
  14.     public WordDictionary() {
  15.         this.root = new TrieNode();. 留学申请论坛-一亩三分地
  16.     }. visit 1point3acres for more.
  17.     . 围观我们@1point 3 acres
  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);.1point3acres网
  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) {
  37.         if(node == null && string.IsNullOrEmpty(word)) {. 留学申请论坛-一亩三分地
  38.             result.Add(soFar);. visit 1point3acres for more.
  39.                         return;
  40.         }
  41.         
  42.         TrieNode current = node;
  43.         
  44.         for(int i = 0; i < word.Length; i++) {. Waral 博客有更多文章,
  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.                 }    . 围观我们@1point 3 acres
  54.             } else {
  55.                                 // Skip the * to check the scenario where * matches nothing
  56.                                 Search(word.Substring(i + 1), current, soFar, result);
  57.                         . from: 1point3acres
  58.                 // Search for all children
  59.                 foreach(var key in current.GetChildrenKeys()) {
  60.                                         //Check if * matches any current char. Waral 博客有更多文章,
  61.                     Search(word.Substring(i + 1), current.GetChild(key), soFar + key, result);. from: 1point3acres
  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.                 }
  66.                 return;
  67.             }. visit 1point3acres for more.
  68.             
  69.         }
  70.         . more info on 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;.本文原创自1point3acres论坛
  80.     public bool IsWord { get; private set; }.1point3acres网
  81.     // Initialize your data structure here.
  82.     public TrieNode()
  83.     {
  84.         this.children = new Dictionary<char, TrieNode>();
  85.     }
  86.    
  87.     public ICollection<char> GetChildrenKeys() {. 1point 3acres 论坛
  88.         return children.Keys; 来源一亩.三分地论坛.
  89.     }
  90.     . more info on 1point3acres
  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) {. visit 1point3acres for more.
  100.         return children[c] = node;
  101.     }. Waral 博客有更多文章,
  102.    
    来源一亩.三分地论坛.
  103.     public void MarkWord() {
  104.         this.IsWord = true;. Waral 博客有更多文章,
  105.     }
  106. }
复制代码
回复

使用道具 举报

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

使用道具 举报

我的人缘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)   【踩】
全局: 顶  90% (37)
 
 
9% (4)  踩
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)   【踩】
全局: 顶  90% (37)
 
 
9% (4)  踩
zachzuogwu 发表于 2017-11-12 11:27
第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串

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

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-12 11:57:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (165)
 
 
9% (17)  踩
"字符串和一个切分长度k "没看懂啊
回复

使用道具 举报

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

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

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

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

别人的 别人被面倒了
回复

使用道具 举报

我的人缘0
 楼主| gundamkeroro 发表于 2017-11-12 12:35:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (37)
 
 
9% (4)  踩
edyyy 发表于 2017-11-12 11:57. visit 1point3acres for more.
"字符串和一个切分长度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里…
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-22 08:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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