一亩三分地论坛

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

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

Linkedin二面面经

[复制链接] |试试Instant~ |关注本帖
NANA1123 发表于 2014-10-17 07:48:19 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Other

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

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

x
第一个题是很简单的pow,第二题题目很长,加上面试官大姐的东南亚口音听得不太习惯,花了挺长时间理解题意,其实就是BFS,虽然大姐说track是对的但是最后没有写出完整的代码,感觉已跪,发出来给之后的面试攒点RP吧. 1point3acres.com/bbs

[img=0,1]file:///C:\Users\xinjie\AppData\Roaming\Tencent\Users\280861202\QQ\WinTemp\RichOle\546_XYTNXX8K[5YJTS)WUQX.jpg[/img] QQ图片20141016194710.jpg


. 1point 3acres 璁哄潧
补充内容 (2014-10-18 00:00):
为看不到图的同学补充下第二题题意:Given  a root of a tree. The tree may be of any depth and width. Transform it in a way that each node(except probably one) would either have N or 0 children

补充内容 (2014-10-18 00:02):
还有一个条件:父子关系不能颠倒(但可以为sibling)

评分

4

查看全部评分

lixiang.xjtu 发表于 2014-11-4 00:58:09 | 显示全部楼层
赞面经。第二题,可以把所有的节点先放到一个数组里面。然后把这些点连成一个N叉树。连起来的时候需要注意,因为你可以连成一个完全树,所以A[i]的N个儿子分别是i*N+1到i*N+N。这样一个个连起来就好了,连起来很方便。所以就是1.按level 遍历存到数组里面,preorder应该也可以。这样保证不违反那个sibling的条件。2.在数组里面连出一个full N tree. 主要考察的是遍历和完全树的trick.1point3acres缃

如果实在要优化的话,可以把数组变成一个queue。然后用按level遍历。如果把A[i]和N个儿子连起来之后,可以从队列里面pop出A[i]。只是一点小优化而已。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

eecsece 发表于 2014-10-17 08:05:13 | 显示全部楼层
为啥没有权限下载。。
回复 支持 反对

使用道具 举报

csgtc 发表于 2014-10-17 08:19:49 | 显示全部楼层
就用BFS走一下咯,copy过去的tree也用一个queue存,满了就dequeue这样,这题应该不难吧
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-17 08:32:00 | 显示全部楼层
lz可以更新下第二题么?好像看不到哎。
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-17 08:32:24 | 显示全部楼层
不知道大神们对难的定义是什么,不过我估计我面的这么多公司的题目都没有能被称的上难的吧

因为Linkedin非常明显是有题库的,所以发发面经希望能造福下之后面试的小伙伴们

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-17 08:34:07 | 显示全部楼层
wjl2525 发表于 2014-10-17 08:32. visit 1point3acres.com for more.
lz可以更新下第二题么?好像看不到哎。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
不知道为什么我没办法复制文本,所以贴的截图,没有设置权限应该能点开?
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-17 08:38:13 | 显示全部楼层
NANA1123 发表于 2014-10-17 08:34. From 1point 3acres bbs
不知道为什么我没办法复制文本,所以贴的截图,没有设置权限应该能点开?

不知道哎,反正我打开链接的时候提示是:抱歉,您没有权限下载本附件
回复 支持 反对

使用道具 举报

3652ltc 发表于 2014-10-17 13:07:35 | 显示全部楼层
我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来,有点浪费空间,可以满了的话就添加在新树上,不过worst case都一样,因为假如是原来的每层node比transform的大的话,必须要把整个树存下来。. from: 1point3acres.com/bbs
下面是代码,大家帮忙看一下,看看有没有什么bug。。。
  1. TreeNode *compact(TreeNode *root, int n) {
  2.         queue<TreeNode *> q;
  3.         q.push(root);
  4.         queue <TreeNode *> new_q;
  5.         TreeNode *new_root = new TreeNode(root->val)
  6.         new_q.push(new_root);
  7.         while (!root->adj.empty()) {. 鍥磋鎴戜滑@1point 3 acres
  8.                 q.push(root->adj.pop_front());
  9.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.         while (!q.empty()) {
  11.                 while (q.size() >= n) {
  12.                         TreeNode *new_node = new_q.pop();
  13.                         for (int i = 0; i < n; i++) {
  14.                                 TreeNode *temp = q.pop();
  15.                                 new_node->adj.push_back(new TreeNode(temp->val));
  16.                                 while (!temp->adj.empty()) {
  17.                                         q.push(temp->adj.pop_first());
  18.                                 }
  19.                         }
  20.                 }
  21.                 TreeNode *node = q.peek();
  22.                 while (!node->adj.empty()) {. 1point3acres.com/bbs
  23.                         q.push(node->adj.pop_first());
  24.                 }
  25.         }-google 1point3acres
  26.         return new_root;
  27. }
复制代码
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-17 13:09:57 | 显示全部楼层
3652ltc 发表于 2014-10-17 13:07
我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来,有点浪费空间,可以满了的话就添加在新树上,不 ...

我看不到题目,层主能麻烦你简单复述下题目要求吗?谢谢啦。
回复 支持 反对

使用道具 举报

shirleywwww 发表于 2014-10-17 13:33:49 | 显示全部楼层
NANA1123 发表于 2014-10-17 08:32
不知道大神们对难的定义是什么,不过我估计我面的这么多公司的题目都没有能被称的上难的吧

因为Linkedin ...

我怎么感觉这题挺难的。。。
回复 支持 反对

使用道具 举报

3652ltc 发表于 2014-10-17 13:42:09 | 显示全部楼层
wjl2525 发表于 2014-10-17 13:09
我看不到题目,层主能麻烦你简单复述下题目要求吗?谢谢啦。
. 1point 3acres 璁哄潧
我的理解就是原来这棵树是任意的树,现在transform成满n叉树,然后新的树要保持原来的parent/children的关系,children最多变为parent的sibling,不能成为parent的parent,太绕了,希望你明白了,不过这也是我对这题的理解,哈哈
回复 支持 反对

使用道具 举报

冰冷剃度 发表于 2014-10-17 17:50:37 | 显示全部楼层
应该就是任意树转满N叉树,父子关系不准颠倒,但是可以变成同辈。建一个长为N的队列,从根到叶广度优先跑一遍就可以了吧。
回复 支持 反对

使用道具 举报

billupus 发表于 2014-10-18 05:05:53 | 显示全部楼层
我点不开姐姐。不过看上面的评论应该2叉转满N叉没错?N是给定的还是自己找?
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2014-10-19 16:11:51 | 显示全部楼层
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还是说节点个数在n范围内就可以。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 00:37:35 | 显示全部楼层
traceroute_su 发表于 2014-10-19 03:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...

这个问题如果首先就问清楚, 在面试官那肯定是加分的。
回复 支持 反对

使用道具 举报

kinslover 发表于 2014-10-20 01:07:34 | 显示全部楼层
traceroute_su 发表于 2014-10-19 16:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...

题里说了,只有一个点可以是例外,其儿子数目介于0到N之间。所以我觉得跑一遍BFS把新树尽量堆满就行了……
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-20 01:19:46 | 显示全部楼层
3652ltc 发表于 2014-10-17 13:07
我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来,有点浪费空间,可以满了的话就添加在新树上,不 ...

谢谢解答,想问下你这里开两个queue的用途?你的new_q进入循环后只有pop没有push操作(pop一次就空了吧),不知道我有没有看错?
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-20 01:22:59 | 显示全部楼层
traceroute_su 发表于 2014-10-19 16:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可以有一个exception
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-20 01:24:17 | 显示全部楼层
billupus 发表于 2014-10-18 05:05
. 1point3acres.com/bbs我点不开姐姐。不过看上面的评论应该2叉转满N叉没错?N是给定的还是自己找?

N是给定的,我补充了文字说明你可以看看
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-20 01:24:25 | 显示全部楼层
billupus 发表于 2014-10-18 05:05
我点不开姐姐。不过看上面的评论应该2叉转满N叉没错?N是给定的还是自己找?

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷N是给定的,我补充了文字说明你可以看看
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 04:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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