一亩三分地论坛

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

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

LinkedIn 实习 一面+二面

[复制链接] |试试Instant~ |关注本帖
rexzhang 发表于 2016-11-23 01:46:31 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 实习@Linkedin - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
发一下昨天的二面和一周前的一面面经回馈地里,求好运

一面(一个烙印):-google 1point3acres
pow(m, n)
写了一个naive的O(n)方法和二分递归的O(logn)的方法

two sum data structure
两种场景,insertion多的和query多的
follow up是算k sum,不过只讲了下思路没写
. 1point 3acres 璁哄潧
二面(一个烙印+一个中国人):
level order traverse (print result)

。。。
用queue很快写完,结果那个面试官沉默了很久。。。不知道是在想什么。。。。反复和他check我哪里有问题,他并没有说什么。。。有点虚. from: 1point3acres.com/bbs

tournament tree (父节点是左右子节点中较小的)
找第二小的. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
思路就是第二小的一定是和最小的有一次比较,所以只遍历有最小值的那条路径,找到路径里面除了这个最小的之外,其他最小的就好了.1point3acres缃
follow up是找第三小的和找任意第k小的。-google 1point3acres

二面有点讲太快了。。。有些细节没讲。。。思路有点跳跃,不知道会不会有影响。。。

求好运求offer

评分

2

查看全部评分

say543 发表于 6 天前 | 显示全部楼层
rexzhang 发表于 2016-11-23 04:42
我的思路是不断调用之前写的找第二小的(find_sec_min),当找到一个第二小的之后,把这棵树里面所有最小值 ...

                  1
         3               1
     4     3       2        1
   5  4  6 3   7   2   8   1
. more info on 1point3acres.com
我猜楼主是意思是 栗子 这样 沿着1的一直判断左右找到一个比root 还小的left or right child 就是第二个 不过follow up 怎么recursion 找到第三个甚至第k个呢? 求指教教                                                                                                   
回复 支持 1 反对 0

使用道具 举报

iammajian 发表于 2016-11-23 11:16:24 | 显示全部楼层
求问第一题k sum 什么思路? 谢谢!
回复 支持 0 反对 1

使用道具 举报

1451427216 发表于 2016-11-23 03:50:27 | 显示全部楼层
第二题的follow up 如何做啊
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-23 04:42:51 | 显示全部楼层
1451427216 发表于 2016-11-22 14:50
第二题的follow up 如何做啊

我的思路是不断调用之前写的找第二小的(find_sec_min),当找到一个第二小的之后,把这棵树里面所有最小值改写成第二小的值,然后再调用find_sec_min,这时候找到的第二小值在原来的树里面就是第三小的值了,以此类推。当然其中还有一些判断细节要处理。。不过我觉得这样应该可以work,那个面试官好像也没什么意见。。
. more info on 1point3acres.com
补充内容 (2016-11-22 15:51):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我也不太确定。。。不知道其他人有没有别的想法。。
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-11-23 14:24:09 | 显示全部楼层
楼主请问tournament tree每个node的值唯一吗? 如果不唯一那么有可能平局,那咋办呐?
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-25 00:16:51 | 显示全部楼层
iammajian 发表于 2016-11-22 22:16
求问第一题k sum 什么思路? 谢谢!

基本思路就是递归的把k sum化成k-1 sum,直到变成trivial的2sum来做。leetcode里面4sum的discussion有具体的代码。https://discuss.leetcode.com/top ... works-for-n-sum-n-2
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-25 00:27:29 | 显示全部楼层
TheBlackMamba 发表于 2016-11-23 01:24
楼主请问tournament tree每个node的值唯一吗? 如果不唯一那么有可能平局,那咋办呐?

题目里说了两个子节点的值不同且唯一,然后一个节点(非叶子节点)要么有两个子节点,要么没有子节点(叶子节点),所以不用考虑这种~不过按照我那个找任意k小的做法可能会出现有子节点值相等的情况,那就可能要同时遍历两个子节点,这样就很啰嗦了。。。所以那个follow up的做法感觉不是特别优化。。
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-11-25 03:19:46 | 显示全部楼层
rexzhang 发表于 2016-11-25 00:27
题目里说了两个子节点的值不同且唯一,然后一个节点(非叶子节点)要么有两个子节点,要么没有子节点(叶 ...

感谢回复! 是啊你做的方法好像有可能退化成dfs。。但是确实是正确的。祝你好运啊!
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-11-25 03:21:28 | 显示全部楼层
rexzhang 发表于 2016-11-25 00:16-google 1point3acres
基本思路就是递归的把k sum化成k-1 sum,直到变成trivial的2sum来做。leetcode里面4sum的discussion有具 ...

那这样的复杂度不是和dfs也一样吗? 为何不用dfs?
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-25 04:00:21 | 显示全部楼层
TheBlackMamba 发表于 2016-11-24 14:21
那这样的复杂度不是和dfs也一样吗? 为何不用dfs?

我觉得这两者本质是一样的,表述方法不太一样
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-25 04:01:26 | 显示全部楼层
TheBlackMamba 发表于 2016-11-24 14:19
感谢回复! 是啊你做的方法好像有可能退化成dfs。。但是确实是正确的。祝你好运啊!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
谢谢!是的我当时也想到了,不过没时间仔细分析了。。
回复 支持 反对

使用道具 举报

yaozhengkun110 发表于 2016-11-29 09:35:53 | 显示全部楼层
请问楼主有消息了吗
回复 支持 反对

使用道具 举报

 楼主| rexzhang 发表于 2016-11-29 09:37:37 | 显示全部楼层
yaozhengkun110 发表于 2016-11-28 20:35. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问楼主有消息了吗
.鐣欏璁哄潧-涓浜-涓夊垎鍦
暂时还没有,recruiter告诉我最快这周内出结果。好揪心。。。
回复 支持 反对

使用道具 举报

yaozhengkun110 发表于 2016-11-29 09:39:58 | 显示全部楼层
rexzhang 发表于 2016-11-29 09:37
暂时还没有,recruiter告诉我最快这周内出结果。好揪心。。。

那很好啊,我15号面的到现在也是没消息
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 21:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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