一亩三分地论坛

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

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

PocketGems一面二面(二面老题变形)

[复制链接] |试试Instant~ |关注本帖
zhumeng900906 发表于 2015-8-25 12:48:14 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
上周二面的,二面两个都是老题变形,发上来给大家作参考,攒人品,求大米
一面:
是个英国小哥,去年10月份刚来的公司,先是介绍了一下自己在公司负责的部分,英国口音,没太听清。。。之后问了why pocket gem,然后差不多就开始做题了,都是最常见的两道题
1. strStr. 1point3acres.com/bbs
写完后让自己写了test case,然后问了worst time complexity,并让举了个例子
2. find most K frequent number in an array.1point3acres缃
问了一下具体的代码,就过了
最后让我问他几个问题后就结束了。一面结束后没多久就给了二面的通知

二面:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是一个native speaker,上来就差不多开始做题
1. sort color的变形, 原题是三个颜色进行排序,我这次碰到的是四种object,只能通过getNum()来获取他们的数值,数值包括1,2,3,4,对object数组进行排序。做法其实和三个差不多,类似quick sort的partition。这道题问了worst case time complexity
2. BST找next larger node的变形,变形后是让找下k个nodes。我的做法是先写findNext函数,然后循环k次,每次将新找到的点作为findNext的参数传进去。写完代码后,问findNext的worst case time complexity,因为可能不是平衡树,所以是O(n),然后又问整个方法的worst case time complexity,这时候就有点懵了,不知道是不是kn, 然后就耽搁了几分钟,估计就是挂在这了,在这也问一下各位大神,我这个方法的worst case time complexity是多少呢,O(Kn)? 要是k = n,是O(n^2)吗

评分

2

查看全部评分

cleverley 发表于 2015-8-27 01:09:34 | 显示全部楼层
请问lz是怎么投的?直接去官网投还是找内推的?大概多久能收到面试邀请?谢谢!
回复 支持 1 反对 0

使用道具 举报

naige 发表于 2015-8-25 13:42:05 | 显示全部楼层
我觉得bst找下k个最大,worst case time complexity 就是O(n), 因为这个其实就是 inorder traversal, 找到了第一个点,顺着就找到了剩下的,是linear time的。
回复 支持 1 反对 0

使用道具 举报

 楼主| zhumeng900906 发表于 2015-8-26 14:11:43 | 显示全部楼层
naige 发表于 2015-8-25 13:42. more info on 1point3acres.com
我觉得bst找下k个最大,worst case time complexity 就是O(n), 因为这个其实就是 inorder traversal, 找到 ...

要是用inorder traversal的方法确实是是O(n),但是我当时写的方法是用找下一个大的点,循环k次,每次传进去的参数为上一次找到的点,感觉这样写应该就不是O(n)了
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 14:27:50 | 显示全部楼层
楼主,第一题strstr你用的是最简单的那个方法嘛?
回复 支持 反对

使用道具 举报

 楼主| zhumeng900906 发表于 2015-8-26 14:38:36 | 显示全部楼层
jiebour 发表于 2015-8-26 14:27. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主,第一题strstr你用的是最简单的那个方法嘛?

对,暴力法解的,没有用KMP
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-27 01:00:08 | 显示全部楼层
zhumeng900906 发表于 2015-8-26 14:38
对,暴力法解的,没有用KMP
. 鍥磋鎴戜滑@1point 3 acres
他也没有expect你用KMP?这么爽。。。。

补充内容 (2015-8-27 07:00):. From 1point 3acres bbs
楼主,求个靠谱的内推。。。。
回复 支持 反对

使用道具 举报

jokebill 发表于 2015-8-27 07:29:00 | 显示全部楼层
LZ BST这题,输入是给的current node和root node,然后找下k个node吗?

我的想法是,先在当前node的右子树找,如果找不够k个,再从root node开始先找到current node的parent node,这样stack是建好的,可以很容易的从parent node往后把剩下的node走完
回复 支持 反对

使用道具 举报

 楼主| zhumeng900906 发表于 2015-8-27 07:33:41 | 显示全部楼层
jiebour 发表于 2015-8-27 01:00
他也没有expect你用KMP?这么爽。。。。. From 1point 3acres bbs

补充内容 (2015-8-27 07:00):

我是网投的,没找内推,而且这家回复其实挺快的,感觉不用内推也可以
回复 支持 反对

使用道具 举报

 楼主| zhumeng900906 发表于 2015-8-27 07:35:43 | 显示全部楼层
jokebill 发表于 2015-8-27 07:29
LZ BST这题,输入是给的current node和root node,然后找下k个node吗?.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我的想法是,先在当前node的右子 ...
. from: 1point3acres.com/bbs
BST这题没有给root node,但是每个点都有parent node
回复 支持 反对

使用道具 举报

jokebill 发表于 2015-8-27 07:47:38 | 显示全部楼层
zhumeng900906 发表于 2015-8-27 07:35
BST这题没有给root node,但是每个点都有parent node

啊,那更好搞了啊,对当前node右子树inorder,不够K个跳到当前node的parent,再inorder ...,O(n) worst case啊

补充内容 (2015-8-27 08:10):
跳到parent的时候应该还需要查当前node是不是比parent大,是的话,继续跳再上一级parent
回复 支持 反对

使用道具 举报

 楼主| zhumeng900906 发表于 2015-8-28 07:47:30 | 显示全部楼层
cleverley 发表于 2015-8-27 01:09
请问lz是怎么投的?直接去官网投还是找内推的?大概多久能收到面试邀请?谢谢!

直接在官网投的,大概一周之内收到的面试邀请
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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