一亩三分地论坛

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

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

Pocket gems onsite面经,有新题

[复制链接] |试试Instant~ |关注本帖
lovexinxu 发表于 2015-9-26 06:33:04 | 显示全部楼层 |阅读模式

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

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

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

x
昨天三番一日游了,但是面满了四轮,中午没来得及吃饭,后两轮已经饿的没力气了,连续4小时不停写不停讲还是很累人的。. 1point3acres.com/bbs
开始面经
第一轮: 印度哥哥
1.
2. 拓扑排序那题
鏉ユ簮涓浜.涓夊垎鍦拌鍧. . more info on 1point3acres.com
第二轮: 亚裔小哥
1. 给了一个m*n格子,每个格子不是0就是1,在每一行里面,0后面不一定是1,但1后面肯定是1,举个例子
m=3, n=4:

0 0 0 0
0 1 1 1
0 0 1 1

然后让你返回第一个出现1的列。说了三个方法,最后给出O(m+n)的,他说应该是最佳了,就是每行从右往左查看,遇到0就开始查看下一行,但从刚才的位置继续,不断更新output值。很简单的题,不过个人很喜欢这种小心思的题目。.鏈枃鍘熷垱鑷1point3acres璁哄潧

2. top down view of binary tree.我用的object方法,网上可以查到。

第三轮:白人小哥
经典的成就系统,设计好了以后反反复复的讨论和改,那时候已经很累了,脑子跟不上了基本。建议大家吃好饭休息好。

第四轮: 白人小哥,传说中的只穿袜子到处跑的。。。
写string类那个题,要求charAt substr和构造函数都是O(1);. 鍥磋鎴戜滑@1point 3 acres

面试官人都很nice,也学到不少东西,觉得答得还行但是他们家品位实在不好捉摸。。。今天收到拒信,move on了。
附上对我帮助很大的面经集合,原帖是:[整理]pocket gems onsite 面经整理(截至20150707)
http://www.1point3acres.com/bbs/ ... &fromuid=172165. From 1point 3acres bbs
(出处: 一亩三分地论坛)

祝各位去试这家奇葩品位公司的各位好运~~~



补充内容 (2015-9-26 06:34):
刚开始忘了,第一轮第一题是max product of substr

补充内容 (2015-9-26 06:59):
string是space O(1)

评分

3

查看全部评分

ye.li.ming 发表于 2015-9-27 03:54:13 | 显示全部楼层
感谢楼主分享面经哈,第二轮第一题是不是能用一个binary search找到第一个1呢。。这样应该可以达到m+logn。
回复 支持 1 反对 0

使用道具 举报

cbwcs 发表于 2015-9-26 06:38:19 | 显示全部楼层
感谢楼主的分享,加油!!
回复 支持 反对

使用道具 举报

 楼主| lovexinxu 发表于 2015-9-26 06:58:18 | 显示全部楼层
cbwcs 发表于 2015-9-26 06:38
感谢楼主的分享,加油!!

谢谢你的大米~加油~
回复 支持 反对

使用道具 举报

 楼主| lovexinxu 发表于 2015-9-26 06:58:56 | 显示全部楼层
string是space O(1)
回复 支持 反对

使用道具 举报

hardworking 发表于 2015-9-26 09:48:43 | 显示全部楼层
第2跟第4个都是pg的大神喔,楼主有幸跟他们过招
回复 支持 反对

使用道具 举报

 楼主| lovexinxu 发表于 2015-9-26 10:33:34 | 显示全部楼层
hardworking 发表于 2015-9-26 09:48
第2跟第4个都是pg的大神喔,楼主有幸跟他们过招

感受到了大神的气息……不过他们真的人都是非常nice的!也学到了许多~
回复 支持 反对

使用道具 举报

hardworking 发表于 2015-9-26 10:38:39 | 显示全部楼层
lovexinxu 发表于 2015-9-26 10:33
感受到了大神的气息……不过他们真的人都是非常nice的!也学到了许多~

我知道,第2个亚裔小哥是不是挺帅的
回复 支持 反对

使用道具 举报

 楼主| lovexinxu 发表于 2015-9-26 12:36:18 | 显示全部楼层
hardworking 发表于 2015-9-26 10:38
我知道,第2个亚裔小哥是不是挺帅的
. more info on 1point3acres.com
是啊是啊!伯克利毕业牛人!
回复 支持 反对

使用道具 举报

 楼主| lovexinxu 发表于 2015-9-27 04:52:59 | 显示全部楼层
ye.li.ming 发表于 2015-9-27 03:54
感谢楼主分享面经哈,第二轮第一题是不是能用一个binary search找到第一个1呢。。这样应该可以达到m+logn。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我的方法worse case也就m+n(从右上角搜到左下角,只会往左往下搜)。
但binary search的话,遇到这种情况,
00000000
00001111
00001111. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
00001111
00001111
worse case 会变成 m + (m - 1) * log(n/2)
或者
00000000. From 1point 3acres bbs
00000001
00000011
00000111
00001111
每次都要把左边binarysearch一下找最左边的1,就是完全多出来的,当m和n非常大的时候,worse case表现就很差。
但想到binary search思路还是极好的!
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-2-29 11:28:42 | 显示全部楼层
楼主你好 想问下那个string class 要你实现setCharAt了么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 01:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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