一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1759|回复: 19
收起左侧

FB电面

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

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

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

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

x
45min 面试. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
前10min讨论简历 以及对fb有兴趣和自己有兴趣的domain
. 鍥磋鎴戜滑@1point 3 acrestechnical : 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组的)
问了他的working experience 大牛啊 从google跳到facebook。。我等弱逼瞬间吓哭
最后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?
. Waral 鍗氬鏈夋洿澶氭枃绔,
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 ...

恩。这个问题问的有点怪。
回复 支持 反对

使用道具 举报

west0428 发表于 2014-11-13 04:29:22 | 显示全部楼层
qqzhao18 发表于 2014-11-13 01:00
对的。。。觉得很蹩脚。。。

.1point3acres缃我觉得挺正常的,是个合理的解法~
回复 支持 反对

使用道具 举报

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
.1point3acres缃额,你可以用一个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 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
yuxi 那你怎么求每个level的node个数
回复 支持 反对

使用道具 举报

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

使用道具 举报

jyx1369 发表于 2014-11-19 13:21:09 | 显示全部楼层
qqzhao18 发表于 2014-11-18 08:13. visit 1point3acres.com for more.
yuxi 那你怎么求每个level的node个数

别暴露我身份。。。哼,
回复 支持 反对

使用道具 举报

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){}
  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 3 acres
  23.     preorder(root, 1);
  24.     for(int i=1;i<=mhash.size();++i){
  25.         res[i] = mhash[i].sum/mhash[i].count;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.     }
  27.     return res;
  28. }

  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);. 1point3acres.com/bbs
  37.     t1->left = t2;
  38.     t1->right = t3;
  39.     t2->left = t4;
  40.     t2->right = t5;
  41.     t3->left = t6;. From 1point 3acres bbs
  42.     t3->right = t7;
  43.     map<int, int> res = solve(t1);. from: 1point3acres.com/bbs
  44.     for(int i=1;i<=res.size();++i){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  45.         printf("%d\t%d\n", i, res[i]);
  46.     }. 鍥磋鎴戜滑@1point 3 acres
  47. }

  48. /*
  49.         1
  50.        /\
  51.       2 3-google 1point3acres
  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 ...
. From 1point 3acres bbs
你思路很对啊,但数据结构麻烦了。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷我觉得这样:HashMap<int,  pair<int, int>>; 就是<层ID,pair<和值,个数>>, preorder traverse的时候按当前层ID更新对应的值就行
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 16:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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