一亩三分地论坛

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

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

口袋宝石公司终极onsite面经

[复制链接] |试试Instant~ |关注本帖
mwang29 发表于 2015-3-18 02:48:04 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@口袋宝石 - 网上海投 - Onsite |Pass

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

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

x
一周前面的口袋宝石公司的sde职位,今天来offer了, 补上全套面筋
P1:
1. sort color
2. next node in BST
followup: no parent pointer avaluable;
P2:
1. top k frequent numbers in an array;. 鍥磋鎴戜滑@1point 3 acres
2. LCA in a Binary Tree
followup: LCA in a BST;
. 1point 3acres 璁哄潧Onsite:
Round 0:
HR Screening;
Round 1:
1 sliding windows (given an array of n numbers and a window width of k , return a new array with the minimum value in each window)
ex: a = 1,2,3,-1,5,6,7 k = 3 return : 1, -1,-1,-1,5,6,7;
follow up: O(n) complexity;
2. maximum product in an array
3. Neighboring classroom, given a map of m * m, and n classrooms, determine if every classroom belongs to one single component; . more info on 1point3acres.com
bounds: (1)classroom is at most 3 * 3 in area (2) no overlapping classrooms (3) classrooms are at least 5% of m * m in total area (4) isConnected returns true only when two classroom shares a common EDGE
这轮完了的档口收到了一封"congratulations from amazon", 瞬间不想面了, 不过还是很负责任的继续面完了
Round 2
Achievement System Design, requirement:
(1)no new codes should be added when adding similar achievements/requirements( 原来有个achievement 叫reachLVL2 , 新加一个reachLVL5 , 不能新写一个类)
(2) new codes can be added with minimum amount when adding brand new achivements(新加一个connectOnFB achievement , 类的借口不能被破坏)
Round 3
1.  word search 1
2. given an array, return the starting and ending index of all subarrays that sums to 0;
ex: 1 , -2, 2, -1, 0 , 5. 1point 3acres 璁哄潧
return (1,2)(0,3)(4,4)(0,4). more info on 1point3acres.com
Round 4
design a string class , with implementation of charAt() and substring(b,e), with substring() requires O(1) time and O(1) space complexity-google 1point3acres
followup:
a new method setCharat(index, char) is added, a substring must keep the changes of parrent string that are made before its creation, but both the parrent string and the substring will not affect each other after the creation of the substring, requires O(1) space complexity

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 回家就开始做reference check了
. 1point3acres.com/bbs

评分

3

查看全部评分

lijl900805 发表于 2015-3-18 03:39:01 | 显示全部楼层
碉堡了呀王老J~
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-18 06:38:14 | 显示全部楼层
楼主好牛掰
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-18 06:39:02 | 显示全部楼层
第一轮的classroom能不能给我讲讲?
回复 支持 反对

使用道具 举报

头像被屏蔽
kinslayer 发表于 2015-3-18 06:42:26 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-18 06:42:37 | 显示全部楼层
就你了,口袋妖怪王老J,出击!
回复 支持 反对

使用道具 举报

唯一 发表于 2015-3-18 08:21:17 | 显示全部楼层
LZ能提示一下string那道题么。。
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-3-18 09:45:45 | 显示全部楼层
楼主能讲下教室那个题怎么搞吗?
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-3-18 09:53:01 | 显示全部楼层
kinslayer 发表于 2015-3-18 06:42
口袋宝石?!难道是Nintendo?

应该是pocket gem,做游戏的公司
回复 支持 反对

使用道具 举报

77777777 发表于 2015-3-18 10:03:35 | 显示全部楼层
真棒!zishuzishu
回复 支持 反对

使用道具 举报

 楼主| mwang29 发表于 2015-3-18 10:26:43 | 显示全部楼层
唯一 发表于 2015-3-18 08:21
LZ能提示一下string那道题么。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一问就是java 6 string的实现方式, 上网查下就好,第二问我用的是 arraylist of map存每次setCharAt改变的值.
回复 支持 反对

使用道具 举报

 楼主| mwang29 发表于 2015-3-18 10:28:42 | 显示全部楼层
liokumo 发表于 2015-3-18 06:39
第一轮的classroom能不能给我讲讲?

因为non-overlap, 直接在一个matrix 里把所有room所占的坐标涂满, 然后随便找一个顶点bfs看是不是经过的点的数量等于总面积就好了
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-18 22:21:07 | 显示全部楼层
mwang29 发表于 2015-3-18 10:28
因为non-overlap, 直接在一个matrix 里把所有room所占的坐标涂满, 然后随便找一个顶点bfs看是不是经过的 ...

是把整个屋子途上?non-overlap是指包括回字形的这种屋子嵌套屋子都不可能出现的意思吗?
回复 支持 反对

使用道具 举报

 楼主| mwang29 发表于 2015-3-18 22:24:33 来自手机 | 显示全部楼层
liokumo 发表于 2015-3-18 22:21
是把整个屋子途上?non-overlap是指包括回字形的这种屋子嵌套屋子都不可能出现的意思吗?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
会出现,但是这种屋子嵌套屋子按照定义就不是一个联通体,所以也不影响
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-19 00:45:36 | 显示全部楼层
谢谢楼主解答,还有一个问题,String的那个substring怎么设计成O(1)啊?难不成用hashtable把所有可能的substring都存起来么?
回复 支持 反对

使用道具 举报

 楼主| mwang29 发表于 2015-3-19 00:48:20 来自手机 | 显示全部楼层
liokumo 发表于 2015-3-19 00:45
谢谢楼主解答,还有一个问题,String的那个substring怎么设计成O(1)啊?难不成用hashtable把所有可能的su ...

去搜搜看Java jdk 6的源代码,你就明白了,注意,原题是要求时间和空间都是o(1),所以只可能是传reference
回复 支持 反对

使用道具 举报

 楼主| mwang29 发表于 2015-3-19 00:49:23 来自手机 | 显示全部楼层
liokumo 发表于 2015-3-19 00:45
谢谢楼主解答,还有一个问题,String的那个substring怎么设计成O(1)啊?难不成用hashtable把所有可能的su ...

jdk 6 Java.lang.String.java文件
回复 支持 反对

使用道具 举报

yuruofeifei 发表于 2015-3-19 15:36:14 | 显示全部楼层
恭喜楼主offer都拿到手软啊!!  
可不可以分享下,achievement system design的思路啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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