一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1463|回复: 10
收起左侧

PoketGem 电面

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

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

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

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

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

一面:native speaker
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 1, strstr
我说我写个KMP吧(反正是练手,好久没写了看看还能写出来不),非让我写个naive的。-google 1point3acres
2, 求 top k
写了个quick select算法。问复杂度说是average O(n), worst case O(n^2)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我说用median of medians可以保证worst case时候O(n),那哥们好像没听说过。.鐣欏璁哄潧-涓浜-涓夊垎鍦
.鐣欏璁哄潧-涓浜-涓夊垎鍦
二面:native speaker
先问问什么pocket gem,由于完全没准备他们家背景,所以瞎扯。
我说我以前玩过你们家的一个游戏,挺好玩,名字就叫 ‘pocket gem’ (老婆给我说的)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
结果这哥们说我在这呆了4年都不知道有这么个游戏。
然后解释名字记错了,但是是一个貌似连连看的游戏,结果被告知他们家没有这样的游戏。。。
事后证明老婆记错了。。那个游戏是宝石工厂,不是他们家的。。。
然后在这种诡异气氛下就开始做题了
1,sort color, 要求O(n)时间,常数空间. 1point3acres.com/bbs
个人觉得那个3个指针one pass的做法有点tricky,不好装是现想出来的。
所以用两次partition来做。
结果这哥们没听过partition,解释了半天quicksort 中的 partition什么的都不懂。
然后就先开写,但他看不懂我写的。。。
后来在各种演示下终于将信将疑的move到下一题了
2, 有parent指针的BST,找next larger元素。
没啥好说的,解释了几种情况后3分钟搞定。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

======
估计挂在culture问题或partition上了。
练手也算得到了一个不错的经验,以后还是用最常见的写法来写,免得看不懂。


mglldjim 发表于 2015-7-17 06:37:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我也刚刚挂了,我擦!
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-18 04:47:28 | 显示全部楼层
关注一亩三分地微博:
Warald
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. from: 1point3acres.com/bbs
应该就是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更好

你是说 quick sort么? 平均o(n)
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-19 12:33:24 | 显示全部楼层
eko910817 发表于 2016-9-19 11:27
如果不要求排序,quick select更好
. more info on 1point3acres.com
哦 我好像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, 2017-4-29 04:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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