一亩三分地论坛

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

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

PoketGem 电面

[复制链接] |试试Instant~ |关注本帖
zhaishaodan 发表于 2015-7-17 03:35:17 | 显示全部楼层 |阅读模式

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

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

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

x
练手公司,背景什么的完全不符。本想着给onsite的话就推了,结果2面的时候把我拒了呵呵. From 1point 3acres bbs

一面:native speaker
1, strstr
我说我写个KMP吧(反正是练手,好久没写了看看还能写出来不),非让我写个naive的。
2, 求 top k
写了个quick select算法。问复杂度说是average O(n), worst case O(n^2)。
我说用median of medians可以保证worst case时候O(n),那哥们好像没听说过。

二面:native speaker
先问问什么pocket gem,由于完全没准备他们家背景,所以瞎扯。. 鍥磋鎴戜滑@1point 3 acres
我说我以前玩过你们家的一个游戏,挺好玩,名字就叫 ‘pocket gem’ (老婆给我说的)。
结果这哥们说我在这呆了4年都不知道有这么个游戏。
然后解释名字记错了,但是是一个貌似连连看的游戏,结果被告知他们家没有这样的游戏。。。.1point3acres缃
事后证明老婆记错了。。那个游戏是宝石工厂,不是他们家的。。。
然后在这种诡异气氛下就开始做题了
1,sort color, 要求O(n)时间,常数空间
个人觉得那个3个指针one pass的做法有点tricky,不好装是现想出来的。
所以用两次partition来做。
结果这哥们没听过partition,解释了半天quicksort 中的 partition什么的都不懂。. Waral 鍗氬鏈夋洿澶氭枃绔,
然后就先开写,但他看不懂我写的。。。
后来在各种演示下终于将信将疑的move到下一题了
2, 有parent指针的BST,找next larger元素。
没啥好说的,解释了几种情况后3分钟搞定。
. more info on 1point3acres.com
======
估计挂在culture问题或partition上了。
练手也算得到了一个不错的经验,以后还是用最常见的写法来写,免得看不懂。
. from: 1point3acres.com/bbs

mglldjim 发表于 2015-7-17 06:37:01 | 显示全部楼层
我也刚刚挂了,我擦!
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-18 04:47:28 | 显示全部楼层
top k的经典做法不是用heap么
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-18 05:52:25 来自手机 | 显示全部楼层
那个next larger是什么意思,怎么做的?
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-18 06:27:23 | 显示全部楼层
yangmyfly 发表于 2016-9-18 05:52
那个next larger是什么意思,怎么做的?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
应该就是int next_large(TreeNode* root, TreeNode* node), 返回BST里面比node小的最大的一个值吧 如果node有左儿子的话肯定就是左儿子的value 如果node 没有左儿子 要从root下一路找下来
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-18 08:02:27 | 显示全部楼层
shiloh00 发表于 2016-9-18 06:27
应该就是int next_large(TreeNode* root, TreeNode* node), 返回BST里面比node小的最大的一个值吧 如果no ...

嗯嗯,题目大概懂了
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-9-19 11:27:10 | 显示全部楼层
shiloh00 发表于 2016-9-17 12:47
top k的经典做法不是用heap么

如果不要求排序,quick select更好
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-19 12:31:03 | 显示全部楼层
eko910817 发表于 2016-9-19 11:27
如果不要求排序,quick select更好
. from: 1point3acres.com/bbs
你是说 quick sort么? 平均o(n)
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-19 12:33:24 | 显示全部楼层
eko910817 发表于 2016-9-19 11:27
如果不要求排序,quick select更好

哦 我好像quick sort和quick select搞混了- -
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-19 17:50:47 | 显示全部楼层
宝石工厂哈哈哈哈
回复 支持 反对

使用道具 举报

diodeBucks 发表于 2016-9-27 04:43:23 | 显示全部楼层
楼主你太有才了,简直像是说相声
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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