推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

发个口袋宝石OA+电1电2面经

[复制链接] |试试Instant~ |关注本帖
jili 发表于 2017-7-9 01:29:12 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@PoketGem - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
OA: Zombie cluster, 不多说啦
. 1point3acres.com/bbs
Phone1:
题是小哥口述的,让自己take notes. visit 1point3acres.com for more.
http://www.1point3acres.com/bbs/thread-217589-1-1.html

. Waral 鍗氬鏈夋洿澶氭枃绔,
后来才发现和地里发过的的这题类似,不过也有一些区别,
每一种item不再有value属性, 只有cost属性
最终目标也改为求 尽可能装满所有stack的情况下,让cost最低.1point3acres缃



Phone2:
出了很诡异的一道新题,count the partition of strings that occur, 我当场懵逼,题意不太好理解, 下面有她给的test case大家自己体会吧 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

input: list of strings
output: integer/ count
count the partition of strings that occur
"abc" "bc" ---> 1     (abc, bc)
"string" "str" "ing" ---> 2  (string, str) (string, ing)
"string" "ringo" "ri" ---> 2 (string, ri)  (ringo, ri)
"string" "tring" "ring" ---> 1 (string, tring, ring)


一面华人小哥,二面华裔姐姐,两位口音都很纯正,人也很好很耐心,一时没有思路也不会催你,讲到正确的思路他们也会予以肯定,面试体验还是很好的,就是自己水平不够,二面那个题卡壳太久估计跪了

BTW,我连续两轮都没有遇到高频题,苦练的许久的strstr+ topk也没有发挥出来,也许是口袋宝石意识到题库泄露,有意的加新题或是改条件,最近面的小伙伴要注意啦, 最后求个大米. more info on 1point3acres.com


评分

2

查看全部评分

siren01 发表于 2017-7-13 07:49:54 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
其实就是按长度排好序,然后建一个Map<String, Set<String>>, 这里Set<String>是所有该string能组合成的parent string, 好拗口,这么写parentString.indexOf(string) != -1大家就懂了..1point3acres缃
然后每次除了更新自己的parent string,还要回过头去更新所以以自己为parent string的 string,把祖先string从它那里移除, 举例, ring可以到tring和string, 发现tring能到string,然后回过头把ring里的string去掉. visit 1point3acres.com for more.
最后用一个visited set来过一遍所有string,看有多少条path(有向). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

回复 支持 1 反对 0

使用道具 举报

siren01 发表于 2017-7-12 04:31:56 | 显示全部楼层
关注一亩三分地微博:
Warald
这个电话面试没有懂,能再讲解一下么

补充内容 (2017-7-12 04:32):
电面2
回复 支持 反对

使用道具 举报

 楼主| jili 发表于 2017-7-12 04:40:05 | 显示全部楼层
siren01 发表于 2017-7-12 04:31
这个电话面试没有懂,能再讲解一下么

补充内容 (2017-7-12 04:32):

case 1:   bc 是 abc 子串,  算一个partition 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
case 2:   str 是 string子串 组成 (string, str)
             ing 是 string 子串 组成 (string, ing)
             str ing 之间没有子串关系, 返回2
             返回2

case 3:  ri 是 string 子串 , 组成 (string, ri)
            ri 是 ringo 子串,  组成  (ringo, ri)
            string ringo 之间没有子串关系, 返回 2

case 4:  ring 是 tring 子串, tring是 string 子串, 组成 (string, tring, ring), 返回1.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

 楼主| jili 发表于 2017-7-12 04:42:57 | 显示全部楼层
今天刚收到正式拒信,主要就坑在二面这个题,3楼作了更详细的说明,有人再遇到这题的时候一定要把它秒掉啊
回复 支持 反对

使用道具 举报

siren01 发表于 2017-7-12 04:47:44 | 显示全部楼层
jili 发表于 2017-7-12 04:42
今天刚收到正式拒信,主要就坑在二面这个题,3楼作了更详细的说明,有人再遇到这题的时候一定要把它秒掉啊

谢了,就当练练手用,不要太在意。move on
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-7-12 05:25:47 | 显示全部楼层
jili 发表于 2017-7-12 04:42
今天刚收到正式拒信,主要就坑在二面这个题,3楼作了更详细的说明,有人再遇到这题的时候一定要把它秒掉啊
.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉电面2和strStr有点像....算是变形?!
回复 支持 反对

使用道具 举报

 楼主| jili 发表于 2017-7-12 05:51:30 | 显示全部楼层
newgod2500 发表于 2017-7-12 05:25
. visit 1point3acres.com for more.感觉电面2和strStr有点像....算是变形?!

比strstr复杂些,我为了思考求partition个数的算法,判断是否为子串直接调了 indexOf, 面试官也没说啥
回复 支持 反对

使用道具 举报

lj910817 发表于 2017-7-12 06:42:45 | 显示全部楼层
jili 发表于 2017-7-12 05:51
比strstr复杂些,我为了思考求partition个数的算法,判断是否为子串直接调了 indexOf, 面试官也没说啥

想请教下楼主,先排序,然后strstr+union-find?
回复 支持 反对

使用道具 举报

 楼主| jili 发表于 2017-7-12 06:59:37 | 显示全部楼层
lj910817 发表于 2017-7-12 06:42
想请教下楼主,先排序,然后strstr+union-find?

我也想到过,但这题规定的这种关系还不具有传递性,你看 case2: "string" "str" "ing" , union_find 是一个cluster 返回1,  但实际上应返回2。
回复 支持 反对

使用道具 举报

lj910817 发表于 2017-7-12 07:07:36 | 显示全部楼层
jili 发表于 2017-7-12 06:59
我也想到过,但这题规定的这种关系还不具有传递性,你看 case2: "string" "str" "ing" , union_find 是一 ...

要先排序把,每次往前扫,str和string是一组,ing和string是一组
回复 支持 反对

使用道具 举报

 楼主| jili 发表于 2017-7-12 07:18:31 | 显示全部楼层
lj910817 发表于 2017-7-12 07:07
要先排序把,每次往前扫,str和string是一组,ing和string是一组
. from: 1point3acres.com/bbs
对的要排序,我之前想了一个图的方法,每个String 看做一个Vertex, 建立一个邻接矩阵记录两两间是否为子串, 单向图,


                               
登录/注册后可看大图




最后数单向最长的路径数, 如上图依次是 1,2,2,1, 大家帮我看看这个思路有没有问题
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 07:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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