《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,你要不要来?
把贵司招聘信息放这里
查看: 3486|回复: 27
收起左侧

口袋宝石公司终极onsite面经

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

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

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

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

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;
2. LCA in a Binary Tree. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
followup: LCA in a BST;
Onsite:. 鍥磋鎴戜滑@1point 3 acres
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; . from: 1point3acres.com/bbs
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 , 类的借口不能被破坏) . more info on 1point3acres.com
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
return (1,2)(0,3)(4,4)(0,4)
Round 4. Waral 鍗氬鏈夋洿澶氭枃绔,
design a string class , with implementation of charAt() and substring(b,e), with substring() requires O(1) time and O(1) space complexity
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了

评分

3

查看全部评分

 楼主| mwang29 发表于 2015-3-22 01:22:13 | 显示全部楼层
yuruofeifei 发表于 2015-3-19 15:36
恭喜楼主offer都拿到手软啊!!  
可不可以分享下,achievement system design的思路啊?

没有没有

那题主要的design其实就是设计requirement 接口和reward 接口, 然后每个achievement 都有两个list, 一个存的是所有requirement 一个存的是所有reward. 有一个函数叫satisfied(), 每次调用就把requirement list 遍历一遍看是否都满足了, 都满足了就把所有reward 挨个给一遍. requirement和reward是相似的,这里只说requirement接口

interface Requirement{
    public boolean isSatisfied(Player player);
}
接下来对player里的每个属性写一个requirement类就可以了, 比如lvl值
class ReachLvlReq implements Requirement{. 1point3acres.com/bbs
   int lvl;
   public ReachLvlReq (int lvl){
       this.lvl = lvl;
   }
   public boolean isSatisfied(Player player){
       return player.lvl >= this.lvl;
   }
}
这样写之后不管requirement是lvl2还是lvl5都不用改框架的code
.鏈枃鍘熷垱鑷1point3acres璁哄潧假设多了一个connect on FB, 那自然player里会多一个boolean 属性叫 connectFB
自己新写一个requirement类就可以了. From 1point 3acres bbs

class connectOnFBReq implements Requirement{ . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  public connectOnFBReq  (){
   }
   public boolean isSatisfied(Player player){
       return player.connectOnFB;
   }. 1point 3acres 璁哄潧
}. From 1point 3acres bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这样就保证即使出现了全新的req, 加的code也是minimum
回复 支持 1 反对 0

使用道具 举报

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那道题么。。

第一问就是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. From 1point 3acres bbs
是把整个屋子途上?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 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
去搜搜看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的思路啊?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-18 01:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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