一亩三分地论坛

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

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

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

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

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

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

x
OA: Zombie cluster, 不多说啦

Phone1:
题是小哥口述的,让自己take notes
http://www.1point3acres.com/bbs/thread-217589-1-1.html
.鏈枃鍘熷垱鑷1point3acres璁哄潧

后来才发现和地里发过的的这题类似,不过也有一些区别,
每一种item不再有value属性, 只有cost属性
最终目标也改为求 尽可能装满所有stack的情况下,让cost最低. visit 1point3acres.com for more.



Phone2:-google 1point3acres
出了很诡异的一道新题,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).鏈枃鍘熷垱鑷1point3acres璁哄潧
"string" "str" "ing" ---> 2  (string, str) (string, ing)
"string" "ringo" "ri" ---> 2 (string, ri)  (ringo, ri)
"string" "tring" "ring" ---> 1 (string, tring, ring). From 1point 3acres bbs


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

BTW,我连续两轮都没有遇到高频题,苦练的许久的strstr+ topk也没有发挥出来,也许是口袋宝石意识到题库泄露,有意的加新题或是改条件,最近面的小伙伴要注意啦, 最后求个大米
.鐣欏璁哄潧-涓浜-涓夊垎鍦
.1point3acres缃

评分

3

查看全部评分

siren01 发表于 2017-7-13 07:49:54 | 显示全部楼层
其实就是按长度排好序,然后建一个Map<String, Set<String>>, 这里Set<String>是所有该string能组合成的parent string, 好拗口,这么写parentString.indexOf(string) != -1大家就懂了.
然后每次除了更新自己的parent string,还要回过头去更新所以以自己为parent string的 string,把祖先string从它那里移除, 举例, ring可以到tring和string, 发现tring能到string,然后回过头把ring里的string去掉
最后用一个visited set来过一遍所有string,看有多少条path(有向)

回复 支持 1 反对 0

使用道具 举报

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

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

使用道具 举报

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

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

case 1:   bc 是 abc 子串,  算一个partition
case 2:   str 是 string子串 组成 (string, str)
             ing 是 string 子串 组成 (string, ing)
             str ing 之间没有子串关系, 返回2-google 1point3acres
             返回2. From 1point 3acres bbs

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
感觉电面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. visit 1point3acres.com for more.
要先排序把,每次往前扫,str和string是一组,ing和string是一组

对的要排序,我之前想了一个图的方法,每个String 看做一个Vertex, 建立一个邻接矩阵记录两两间是否为子串, 单向图,


                               
登录/注册后可看大图




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

使用道具 举报

wangkd93 发表于 2017-7-25 12:55:33 | 显示全部楼层
感觉这个电面二有点难啊。。。

我目前的思路是首先按String长度从大到小排序然后遍历。用tree的结构来表示substring的关系,比如case4总的话root就是“string", “string”的一个children就是“tring“, 这时遍历到ring的时候就再之前已经建立好的tree去找其对应的位置,这个例子中对应的位置就是”tring“的children。  所有string遍历完成后再找建立好的所有tree的leaf的个数就是最后的结果。

找每个string的位置的时候需要遍历所有之前的string, 所以时间复杂度应该是O(n^2)。大家看下这个思路是不是对的。

补充内容 (2017-7-25 12:57):
时间复杂度好像不对,因为每次找位置的时候都得用到indexOf或者strStr(),这个复杂度我没计算在内。。。
回复 支持 反对

使用道具 举报

dukecat0613 发表于 2017-7-30 00:43:37 | 显示全部楼层
jili 发表于 2017-7-12 07:18
对的要排序,我之前想了一个图的方法,每个String 看做一个Vertex, 建立一个邻接矩阵记录两两间是否为子 ...

尝试着写了一个 但是不能handle duplicate, 如果handle duplicate 改动应该也不大
  1. public static List<String> partitionStr(String[] strs) {. 鍥磋鎴戜滑@1point 3 acres
  2.             Arrays.sort(strs, (String a, String b) -> a.length() - b.length());
  3.             Map<String, Set<String>> parentStr = new HashMap<>();
  4.             for (int i = 0; i < strs.length; i++) {
  5.                     for (int j = i + 1; j < strs.length; j++) {
  6.                             if (strs[j].indexOf(strs[i]) == -1) {. 1point 3acres 璁哄潧
  7.                                     continue;
  8.                             } . visit 1point3acres.com for more.
  9.                             Set<String> s = parentStr.getOrDefault(strs[i], new HashSet<>());. 1point 3acres 璁哄潧
  10.                             s.add(strs[j]);
  11.                             parentStr.put(strs[i], s);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                     }
  13.             }
  14.             .1point3acres缃
  15.             List<String> res = new ArrayList<>();
  16.             Set<String> visited = new HashSet<>();
  17.             for (int i = 0; i < strs.length; i++) {
  18.                     if (parentStr.containsKey(strs[i])) {
  19.                             for (String val: parentStr.get(strs[i])) {
  20.                                     if (parentStr.containsKey(val)) {
  21.                                             parentStr.put(strs[i], nonIntersect(parentStr.get(strs[i]), parentStr.get(val)));
  22.                                     }
  23.                             }. From 1point 3acres bbs
  24.                     }
  25.             }
  26.             for (int i = 0; i < strs.length; i++) {
  27.                     if (!parentStr.containsKey(strs[i])) {
  28.                             continue;
  29.                     }
  30.                     path(parentStr, res, "", visited, strs[i]);
  31.             }
  32.             return res;
  33.     }
  34.    
  35.     public static void path(Map<String, Set<String>> map, List<String> res, String cur,
  36.                     Set<String> visitedKey, String key) {
  37.             if (visitedKey.contains(key)) {
  38.                     return;
  39.             }
  40.             if (map.containsKey(key)) {
  41.                     for (String val: map.get(key)) {. more info on 1point3acres.com
  42.                             path(map, res, cur + key + " ", visitedKey, val);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  43.                     }
  44.                     visitedKey.add(key);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45.             } else {
  46.                     res.add(cur + key);
  47.                     return;
  48.             }
  49.     }
  50.    
  51.     public static Set<String> nonIntersect(Set<String> a1, Set<String> a2) {
  52.             Set<String> res = new HashSet<>();
  53.             for (String val: a1) {
  54.                     if (!a2.contains(val)) {
  55.                             res.add(val);
  56.                     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  57.             }
  58.             return res;
  59.     }
复制代码
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2017-8-1 01:22:30 | 显示全部楼层
感觉第2题像是topological sort,先用字符串两两配对检查是不是有从属关系建立一个有向图,然后进行dfs访问所有path,一边移除所有访问过的图上的edge
回复 支持 反对

使用道具 举报

agraynel 发表于 2017-8-15 02:54:07 | 显示全部楼层
没见过第二题,马上面pg 谢谢lz
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 23:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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