推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2356|回复: 19
收起左侧

FB电面

[复制链接] |试试Instant~ |关注本帖
qqzhao18 发表于 2014-11-12 07:28:45 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Other

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

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

x
45min 面试
前10min讨论简历 以及对fb有兴趣和自己有兴趣的domain
technical : find average value for each level in binary tree
solution : level order traversal --- 一边写代码一边说 写完以后印度小哥解释一下。。然后一阵狂说 不知道那个时候感觉英语水平狂飙还是怎样 印度小哥说perfect 信心大增
剩下10min -- 转成recursion  -- 想了大概3min 小哥问我怎么做 我说了一下 小哥说 you are in the correct direction  就开始写 不过时间不等人 最后木有写完 小哥说you are in the correct direction 下面提问题吧
问了instagram为啥木有enable hashtag问题 (因为小哥是instagram组的). Waral 鍗氬鏈夋洿澶氭枃绔,
问了他的working experience 大牛啊 从google跳到facebook。。我等弱逼瞬间吓哭. Waral 鍗氬鏈夋洿澶氭枃绔,
最后next step move forward结束
很开心的说 起码没有问奇葩问题。。。希望好运!!!

评分

1

查看全部评分

west0428 发表于 2014-11-12 07:38:11 | 显示全部楼层
赞lz!祝lz onsite好运~~~ 啥时候给我个电面  ><

补充内容 (2014-11-12 07:38):
不过recursion的思路是什么呢?
回复 支持 反对

使用道具 举报

 楼主| qqzhao18 发表于 2014-11-12 08:42:26 | 显示全部楼层
west0428 发表于 2014-11-12 07:38
赞lz!祝lz onsite好运~~~ 啥时候给我个电面  ><

补充内容 (2014-11-12 07:38):

我当时也懵了。。后来想到一个很蹩脚的思路 他竟然说对。。
就是用个hashmap存level和这个level上的treenode return这个map 最后再求average。。。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-12 11:45:01 | 显示全部楼层
qqzhao18 发表于 2014-11-12 08:42
我当时也懵了。。后来想到一个很蹩脚的思路 他竟然说对。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就是用个hashmap存level和这个level上的tree ...

就是说你的recursive的parameter实际上就是一个HashMap<TreeNode>?
回复 支持 反对

使用道具 举报

west0428 发表于 2014-11-12 23:12:36 | 显示全部楼层
qqzhao18 发表于 2014-11-12 08:42
我当时也懵了。。后来想到一个很蹩脚的思路 他竟然说对。。
就是用个hashmap存level和这个level上的tree ...

这样!那就可以preorder遍历树,构造这个map喽?
回复 支持 反对

使用道具 举报

 楼主| qqzhao18 发表于 2014-11-13 01:00:32 | 显示全部楼层
west0428 发表于 2014-11-12 23:12
这样!那就可以preorder遍历树,构造这个map喽?

对的。。。觉得很蹩脚。。。
回复 支持 反对

使用道具 举报

 楼主| qqzhao18 发表于 2014-11-13 01:02:04 | 显示全部楼层
averillzheng 发表于 2014-11-12 11:45
就是说你的recursive的parameter实际上就是一个HashMap?

HashMap<Integer,ArrayList<TreeNode>> 然后进行recursion 其实我自己都不知道对不对。。。觉得应该是这样,key是level value是这个level上的node
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-13 01:14:39 | 显示全部楼层
qqzhao18 发表于 2014-11-13 01:02
HashMap 然后进行recursion 其实我自己都不知道对不对。。。觉得应该是这样,key是level value是这个leve ...
. 1point 3acres 璁哄潧
恩。这个问题问的有点怪。
回复 支持 反对

使用道具 举报

west0428 发表于 2014-11-13 04:29:22 | 显示全部楼层
qqzhao18 发表于 2014-11-13 01:00
对的。。。觉得很蹩脚。。。
. more info on 1point3acres.com
我觉得挺正常的,是个合理的解法~
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-11-13 04:34:28 | 显示全部楼层
recursive 就是dfs吧 一层层的打印
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2014-11-13 12:09:10 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

jyx1369 发表于 2014-11-18 08:07:27 | 显示全部楼层
额,你可以用一个arraylist来存level的sum(之后碰到一样level的,进行update就可以),然后level 就是arraylist的index。。。。这样简单些。。。
回复 支持 反对

使用道具 举报

jyx1369 发表于 2014-11-18 08:12:47 | 显示全部楼层
jyx1369 发表于 2014-11-18 08:07
额,你可以用一个arraylist来存level的sum(之后碰到一样level的,进行update就可以),然后level 就是arra ...

啊,想错了。这样算不出每个level的node counts,还是要用hashmap
回复 支持 反对

使用道具 举报

 楼主| qqzhao18 发表于 2014-11-18 08:13:44 | 显示全部楼层
jyx1369 发表于 2014-11-18 08:07
额,你可以用一个arraylist来存level的sum(之后碰到一样level的,进行update就可以),然后level 就是arra ...

yuxi 那你怎么求每个level的node个数
回复 支持 反对

使用道具 举报

austurela 发表于 2014-11-18 08:24:08 | 显示全部楼层
难道不用BFS?
回复 支持 反对

使用道具 举报

jyx1369 发表于 2014-11-19 13:21:09 | 显示全部楼层
qqzhao18 发表于 2014-11-18 08:13
yuxi 那你怎么求每个level的node个数
.鏈枃鍘熷垱鑷1point3acres璁哄潧
别暴露我身份。。。哼,
回复 支持 反对

使用道具 举报

Neal_kks 发表于 2014-11-22 15:03:07 | 显示全部楼层
感觉用先序遍历先把hashmap建起来最简单,只要保存每一层的sum和count就行了。我用c++写了一个,附简单的测试用例。
  1. #include <map>
  2. using namespace std;

  3. struct node{
  4.     int sum, count;
  5.     node():sum(0), count(0){}
  6. };

  7. struct Tree{
  8.     int val;
  9.     Tree *left, *right;
  10.     Tree(int mval):val(mval), left(NULL), right(NULL){}. From 1point 3acres bbs
  11. };
  12. map<int, node> mhash;
  13. void preorder(Tree *root, int lev){
  14.     if(root == NULL)    return;
  15.     mhash[lev].sum += root->val;
  16.     mhash[lev].count += 1;
  17.     if(root->left)  preorder(root->left, lev+1);
  18.     if(root->right) preorder(root->right, lev+1);
  19. }

  20. map<int, int> solve(Tree *root){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.     map<int, int> res;
  22.     if(root == NULL)    return res;. 1point 3acres 璁哄潧
  23.     preorder(root, 1);
  24.     for(int i=1;i<=mhash.size();++i){
  25.         res[i] = mhash[i].sum/mhash[i].count;
  26.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.     return res;
  28. }. 鍥磋鎴戜滑@1point 3 acres

  29. int main(){
  30.     Tree *t1 = new Tree(1);
  31.     Tree *t2 = new Tree(2);
  32.     Tree *t3 = new Tree(3);
  33.     Tree *t4 = new Tree(4);
  34.     Tree *t5 = new Tree(5);
  35.     Tree *t6 = new Tree(6);
  36.     Tree *t7 = new Tree(7);
  37.     t1->left = t2;
  38.     t1->right = t3;
  39.     t2->left = t4;
  40.     t2->right = t5;
    -google 1point3acres
  41.     t3->left = t6;
  42.     t3->right = t7;
  43.     map<int, int> res = solve(t1);
  44.     for(int i=1;i<=res.size();++i){
  45.         printf("%d\t%d\n", i, res[i]);. more info on 1point3acres.com
  46.     }
  47. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  48. /*
  49.         1
  50.        /\. from: 1point3acres.com/bbs
  51.       2 3. Waral 鍗氬鏈夋洿澶氭枃绔,
  52.      /\ /\
  53.     4 56 7
  54.     */
复制代码
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-1-31 11:17:54 | 显示全部楼层
就是DFS不行吗?
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-2-1 23:33:56 | 显示全部楼层
qqzhao18 发表于 2014-11-13 01:02
HashMap 然后进行recursion 其实我自己都不知道对不对。。。觉得应该是这样,key是level value是这个leve ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你思路很对啊,但数据结构麻烦了。。
我觉得这样:HashMap<int,  pair<int, int>>; 就是<层ID,pair<和值,个数>>, preorder traverse的时候按当前层ID更新对应的值就行
回复 支持 反对

使用道具 举报

peace 发表于 2015-2-2 03:57:20 | 显示全部楼层
这跟leetcode上的level order traversal一样吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-24 13:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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