亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2405|回复: 19
收起左侧

FB电面

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

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

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

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

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组的)
问了他的working experience 大牛啊 从google跳到facebook。。我等弱逼瞬间吓哭
最后next step move forward结束 . 鍥磋鎴戜滑@1point 3 acres
很开心的说 起码没有问奇葩问题。。。希望好运!!!

评分

1

查看全部评分

west0428 发表于 2014-11-12 07:38:11 | 显示全部楼层
赞lz!祝lz onsite好运~~~ 啥时候给我个电面  ><.1point3acres缃
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2014-11-12 07:38):
不过recursion的思路是什么呢?
回复 支持 反对

使用道具 举报

 楼主| qqzhao18 发表于 2014-11-12 08:42:26 | 显示全部楼层
west0428 发表于 2014-11-12 07:38
赞lz!祝lz onsite好运~~~ 啥时候给我个电面  >< 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. more info on 1point3acres.com
补充内容 (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. 1point 3acres 璁哄潧
我当时也懵了。。后来想到一个很蹩脚的思路 他竟然说对。。
就是用个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 ...

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

使用道具 举报

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 ...

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个数
. from: 1point3acres.com/bbs
别暴露我身份。。。哼,
回复 支持 反对

使用道具 举报

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. };-google 1point3acres
  12. map<int, node> mhash;
  13. void preorder(Tree *root, int lev){
  14.     if(root == NULL)    return;. 鍥磋鎴戜滑@1point 3 acres
  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);. From 1point 3acres bbs
  19. }

  20. map<int, int> solve(Tree *root){
  21.     map<int, int> res;
  22.     if(root == NULL)    return res;
  23.     preorder(root, 1);
  24.     for(int i=1;i<=mhash.size();++i){-google 1point3acres
  25.         res[i] = mhash[i].sum/mhash[i].count;
  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);. 1point 3acres 璁哄潧
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.     t2->left = t4;
  40.     t2->right = t5;
  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]);
  46.     }. 1point 3acres 璁哄潧
  47. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  48. /*
  49.         1
  50.        /\
  51.       2 3
  52.      /\ /\
  53.     4 56 7
  54.     */. visit 1point3acres.com for more.
复制代码
回复 支持 反对

使用道具 举报

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-10-20 02:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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