一亩三分地论坛

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

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

Pocket Gems跪经 全程电面+onsite 尽量写的详细了

[复制链接] |试试Instant~ |关注本帖
shenhualong 发表于 2016-2-2 14:01:29 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@PoketGem - 内推 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
今天onsite两轮被赶走,已跪无疑。。。其实第一轮就已经跪了只是Ona没来得及过来轰人。。电面+onsite面经希望能帮助以后的小伙伴们。. 1point3acres.com/bbs

第一轮电面
都是经典老题strstr和k top. more info on 1point3acres.com
1. strstr没什么说的,双循环写出来就好了,让写了主函数和test case测试一下,问了一句循环的终止条件,time complexity(O(两个字符串长度相乘)),worst case并举例就是aaaaaaaaa和aaaab的例子。
follow up :有啥更好的方法没? 答曰:KMP。 赞曰:OK,good。就没了。

2. ktop也还行吧,只是我不知死活的问了一句如果有频率一样的怎么办,让都输出来。比如A = [2, 3, 5, 3, 2, 5, 1, 5, 6], k = 2,最多的是5有3次,其次是2和3各有两次,这样k=2就输出[5, 2, 3]顺序不重要。楼主发现之前想的瞬间不对了,于是灵机一动想了个解决方法。俩hashmap + minheap。
先扫一遍用一个hashmap<Integer, Integer>计数,上面的例子就是:[2:2, 3:2, 5:3, 1:1, 6:1]。然后把第一个hashmap里边的信息放第二个hashmap<Integer, Set<Integer>>里,key是频率,set里是所有出现这个频率的数,比如:[2:<2, 3>, 3:<5>, 1:<1, 6>]。然后再把第二个hashmap里的entry扔到size = 2的minheap里,剩下的再慢慢输出。
也让写了主函数测试,出现了几个没compile过的,改了改,过了。问了复杂度O(nlogk),解释了半天第二个hashmap干啥用的。并没有stream的那个followup。


第二轮电面
也是地里出现过的题
1. input 一个array A一个数x,找出A里边的一个index k使a1 = A[0~k-1]里边等于x的元素个数 等于 a2=A[k ~ n-1]里不等于x的元素的个数,如果没有符合的返回-1。注意a1和a2不能为空,也就是0和n-1都不符合要求。
好找。扫一遍数出一共x多少个xTotal。再扫一遍,边扫边数出已经遇到的x个数xMet。这样在每个index都能随时直接算出a2里不等于x的元素的个数了。
然后让人工过一个test case。
follow up :可不可能有多个符合的index.。答曰:不能。追问:请证。
之前没看见有人报这个followup,一开始虽然直觉觉得不能,但是还是没想清楚,只想到在第二遍扫的时候有四个相关的变量:xMet,nonXMet, xNotMet, nonXNotMet。其中xMet和nonXMet组成了扫过的部分,xNotMet和nonXNotMet组成了未扫过的部分。符合的条件则是:xMet = nonXNotMet。而这两个变量一个只能递增(xMet),一个只能递减(nonXNotMet),而且并不能同时不变,因为如果当前index值是x,index++之后xMet也+1;如果当前的index值不是x,index++之后nonXNotMet就-1。所以不能同时不变,就不能有多个符合的。

2. bst next largest node with/without parent pointer. 鍥磋鎴戜滑@1point 3 acres
注意的是两种情况都不能访问node里的值,所以任何比较值的解法都是不对的,之前看有人贴出来的代码有比较值的方法,大家就不要参考了。
1) 有parent pointer
有右孩子的话就是右孩子最小的,就是有孩子使劲儿往左走到头的那个。没有有孩子就是沿着parent pointer往上走,知道某个node是他的parent的左孩子时,就找到了。
follow up:为啥有右孩子就是右子树里最小的,凭啥不能在别处啊?根据bst性质解释解释清楚就行了。
2) 没有parent pointer,但是给了root 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
有右孩子情况一样。由于楼主之前看的比较值的方法,当时又是一懵。然后想想只能inorder traverse了没别的办法了。问了performance,答曰:时间O(n),recursion的话空间O(height),moris的话空间O(1)。追问:moris有啥不好啊。这个也是问的楼主一愣,居然说出不好编。。。然后弱弱的回答需要修改左右子树的reference,如果遇到不能修改的情况,就不行了。然后她说嗯不能修改,如果多线程的时候就麻烦了。我说对对对。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

Onsite 记错时间早到半小时也是醉了。。。
第一轮,某三哥。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
进来时候还是可以的,也是先扯皮了几句,并没有很冷漠,还问我东海岸下大雪了是不是很冷。
然后他以为自己是第二轮,不知道怎么回事。
然后正等着他出word break,room connection之类的呢,居然出了一个regex。。。。。没错就是leetcode原题regex。。
当时我内心狂奔着千万只草泥马。。。就好比你切了一晚上pizza,然后他抬头跟你说,呵呵我不饿。面经都白刷了。。。。
主要的是*的情况我真的想不起来了。。。最后勉强写了个n3的方法,他很不高兴的走了。当时我就知道必跪无疑了。自己坐着的时候希望Ona赶紧来把我轰走。。好在天黑之前逛逛sf的海边。。结果亚裔小哥进来时我居然内心还有点儿失望。。。。扯远了。
再多说两句这个三哥吧,其实他开始并不冷漠,我一开始分析的时候他还挺感兴趣并讨论有回应。但是只分析出n3算法之后,他就不理我自己玩儿手机了。。。这个不能怪别人,毕竟刷题不利必自毙。共勉。

第二轮,传说中的亚裔小哥,parse json to database
小哥进来同样以为自己是第三轮。。不知道怎么回事儿。.1point3acres缃
看版上有人报这题,但是找了很久都没有太多细节,我尽量多的回忆吧,希望能帮到后边的人。
json格式
[
{type:"session", data:{player_id:89757, session_id:66055, name:"ergou", date:"2016-1-1HHMMSS"}},. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
{type:"purchase", data:{player_id:89757, session_id:66055, state:"success", date:"2016-1-2HHMMSS"}},
{type:"battle", data:{player_id:...., session_id:...., result:....}},
.....
]
就是这类型的,长这样整体叫events,里边的每一条叫event,长的差不多,名字不一样,data也就相应的不一样。.鐣欏璁哄潧-涓浜-涓夊垎鍦

database格式
class Row {
      String tableName;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
      Map<String, String> map;
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是把json的格式parse了然后变成这样就行了,tableName就是对应上边的type(session,purchase,battle这种),map里就是每个event里data里所有的key value pair。

然后给了一个class
class JSONValue {
       String getAsString()
       Long getAsLong()
       Map getAsMap()
       List getAsList()
       ....
}
就是每个key value pair的value都是一个JSONValue,整个的list也是JSONValue,data也是,可以用这些method转换成java的的类型(别的语言也行,我是java),但是特定的类型只能call特定的函数,比如session对应的是数字,所以你提取session的值的时候只能call getAsLong(),如果你call了getAsMap()或其他的就不对。而data是Map,parse data时候只能call getAsMap()这个意思。

你要实现的method接口是
List<Row> parseToDB(List<JSONValue> events, Config c) {

}
.1point3acres缃类似这样表达
arg1 就是上面的JSON,是一堆events。Config是另一个类型也是需要设计的,具体功能差不多就是告诉你哪个类型需要调用JSONValue里的哪个method才能parse对,比如告诉你session里的name是string类型,那么你parse name这个field的时候就要call getAsString()这样。这里需要OOD,我设计了一个type的Interface然后就差不多那样我也不是很清楚楼主非常水的。。。。

这样由于我本身比较水也不是很会设计而且到最后的时候Ona已经在外面跟小哥招手要哄人了。。。。贴出来比较详细了希望面过并且比较了解怎么设计的同学们可以进一步讨论帮助后面的同学吧。

然后Ona就来送客了。。天还没黑,就去逛sf了。

评分

4

查看全部评分

faye_roll 发表于 2016-2-3 15:28:44 | 显示全部楼层
你说的是regular expression matching??
回复 支持 反对

使用道具 举报

 楼主| shenhualong 发表于 2016-2-4 07:02:12 | 显示全部楼层
faye_roll 发表于 2016-2-3 15:28
你说的是regular expression matching??

对啊,leetcode原题。只记得dp,状态方程实在想不起来了。
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-2-20 12:14:26 | 显示全部楼层
楼主 我下周要面了 想请教你一下切pizza那题 看地里有个回帖提了个二维dp的解法 感觉很难完整写出解法 不知道你有没有什么可行的解法?.鐣欏璁哄潧-涓浜-涓夊垎鍦
不知道可不可以加个联系方式 请教一下Onsite事宜-google 1point3acres
万分感谢!
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-2-20 12:24:52 | 显示全部楼层
另外不得不给影藏彩蛋89757好评!
回复 支持 反对

使用道具 举报

LBS 发表于 2016-2-27 08:28:21 | 显示全部楼层
请教一下LZ第二轮
1. 说json里面的type是string类,data是map类,那么我用JSONValue中的 Map getAsMap()去获取data得到的应该是MAP<string, JSONValue> 还是 得到一个新的JSONValue?

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴2. 这个event本身(list中的一行)是不是一个MAP, in other words, events就是一个list里面装满了MAP?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3.提取session的值的时候只能call getAsLong() - > 能写1~2行提取session里面数据,具体调用 getAslong()的代码吗?

非常感谢,祝OFFER多多!
回复 支持 反对

使用道具 举报

梳子爱安可 发表于 2016-4-23 04:39:50 | 显示全部楼层
楼主 room connection那道题有代码或是思路么,现在特别confuse 方便的话发我一份呗 lemonsherry1992@gmail.com 非常感谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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