10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1175|回复: 16
收起左侧

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

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

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

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

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

x
OA: Zombie cluster, 不多说啦.1point3acres缃

Phone1:
题是小哥口述的,让自己take notes. more info on 1point3acres.com
http://www.1point3acres.com/bbs/thread-217589-1-1.html
-google 1point3acres

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



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).鏈枃鍘熷垱鑷1point3acres璁哄潧
"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也没有发挥出来,也许是口袋宝石意识到题库泄露,有意的加新题或是改条件,最近面的小伙伴要注意啦, 最后求个大米. visit 1point3acres.com for more.


评分

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 | 显示全部楼层
这个电话面试没有懂,能再讲解一下么
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2017-7-12 04:32):
电面2
回复 支持 反对

使用道具 举报

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

补充内容 (2017-7-12 04:32):
. from: 1point3acres.com/bbs
case 1:   bc 是 abc 子串,  算一个partition.鏈枃鍘熷垱鑷1point3acres璁哄潧
case 2:   str 是 string子串 组成 (string, str). from: 1point3acres.com/bbs
             ing 是 string 子串 组成 (string, ing)
             str ing 之间没有子串关系, 返回2
             返回2

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

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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
要先排序把,每次往前扫,str和string是一组,ing和string是一组

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


                               
登录/注册后可看大图



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

使用道具 举报

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)。大家看下这个思路是不是对的。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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) {
  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) {
  7.                                     continue;
  8.                             }
  9.                             Set<String> s = parentStr.getOrDefault(strs[i], new HashSet<>());
  10.                             s.add(strs[j]);
  11.                             parentStr.put(strs[i], s);
  12.                     }
  13.             }
  14.            
  15.             List<String> res = new ArrayList<>();
  16.             Set<String> visited = new HashSet<>();
  17.             for (int i = 0; i < strs.length; i++) {. From 1point 3acres bbs
  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.                             }
  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]);
    . 1point3acres.com/bbs
  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)) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  42.                             path(map, res, cur + key + " ", visitedKey, val);
  43.                     }
  44.                     visitedKey.add(key);
  45.             } else {. 1point3acres.com/bbs
  46.                     res.add(cur + key);. 1point3acres.com/bbs
  47.                     return;
  48.             }
  49.     }
  50.     . 1point3acres.com/bbs
  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-10-17 14:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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