一亩三分地论坛

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

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

M家skype OTS

[复制链接] |试试Instant~ |关注本帖
Flumao 发表于 2016-6-28 01:49:57 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Microsoft - 内推 - 在线笔试 |Fail在职跳槽

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

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

x
发一个M家SKYPE的OTS
三个题,60分钟,感觉不容易,已跪
1.palindrome digital clock: 找到所有的palindrome时间,例如:1:01, 12:21, 3:13这些都是。自己设计方法,参数和返回值
2.merge email: 有很多个类似于这种的数据结构:
Name : email addresses
c1 : aaa@gmail.com,  bbb@gmail.com.鐣欏璁哄潧-涓浜-涓夊垎鍦
c2: bbb@gmail.com
c3: aaa@gmail.com
c4: ddd@gmail.com
c5: ccc@gmail.com ddd@gmail.com
如果email地址overlapping则合并他们的name
结果为: (c1, c2, c3), (c4, c5)-google 1point3acres

3.如果你是email组的,例如gmail, 让你在client里面加入一个"important" folder应该怎么做?

评分

2

查看全部评分

本帖被以下淘专辑推荐:

jmnjmnjmn 发表于 2016-6-28 02:23:28 | 显示全部楼层
60min要写这么三道确实难了点
第二题是不是用union find
第三题怎么整啊
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-6-28 09:21:14 | 显示全部楼层
卧槽 这OA难度 1个小时。。 疯了吧。。
回复 支持 反对

使用道具 举报

 楼主| Flumao 发表于 2016-6-28 09:56:15 | 显示全部楼层
jmnjmnjmn 发表于 2016-6-28 02:23
60min要写这么三道确实难了点
第二题是不是用union find
第三题怎么整啊

我感觉自己跪在了第三题,我到现在都没想清楚他们究竟想要什么样的答案。
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-6-28 11:45:19 | 显示全部楼层
Flumao 发表于 2016-6-28 09:56
我感觉自己跪在了第三题,我到现在都没想清楚他们究竟想要什么样的答案。
. visit 1point3acres.com for more.
HR 有给feedback么
回复 支持 反对

使用道具 举报

 楼主| Flumao 发表于 2016-6-28 12:26:05 | 显示全部楼层
jmnjmnjmn 发表于 2016-6-28 11:45-google 1point3acres
HR 有给feedback么

还没有结果呢,不过我估计是fail了
回复 支持 反对

使用道具 举报

say543 发表于 2016-6-29 14:26:02 | 显示全部楼层
Flumao 发表于 2016-6-28 09:56. From 1point 3acres bbs
我感觉自己跪在了第三题,我到现在都没想清楚他们究竟想要什么样的答案。

第三题真的不知道什么answer...
回复 支持 反对

使用道具 举报

lxyjscz 发表于 2016-7-7 04:46:40 | 显示全部楼层
请问楼主是内推的还是自己投的啊?
回复 支持 反对

使用道具 举报

liuliu146 发表于 2016-7-7 10:12:29 | 显示全部楼层
楼主第二题什么思路?我能想到的是:先把Name按照包含的email的个数由大到小排个序,从大的开始一个一个挑,每取出一个就跟现有的group里含有email数最多的那个Name进行比较,如果包含就把他放在那个group里,否则就新建一个group
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-7 12:26:36 | 显示全部楼层
liuliu146 发表于 2016-7-7 10:12
楼主第二题什么思路?我能想到的是:先把Name按照包含的email的个数由大到小排个序,从大的开始一个一个挑 ...

我这样想的 用倒排+并查集(结点就是name) 先像倒排索引那样,建一个从email到name的map, 只需要keep第一个出现的<email, name> pair 就够了, 当读进下一个的record的时候,只要是email出现过, 就把当前的name结点的parent指针指向之前email对应name的节点。 这样用O(N)时间就可以建立好并查集。之后只要再用O(N)扫一遍并查集分组输出共同parent的name就OK了
回复 支持 反对

使用道具 举报

 楼主| Flumao 发表于 2016-7-7 13:00:26 | 显示全部楼层
liuliu146 发表于 2016-7-7 10:12
楼主第二题什么思路?我能想到的是:先把Name按照包含的email的个数由大到小排个序,从大的开始一个一个挑 ...
-google 1point3acres
合并interval比较类似,两层循环。
回复 支持 反对

使用道具 举报

liuliu146 发表于 2016-7-7 13:00:41 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-7 12:26. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我这样想的 用倒排+并查集(结点就是name) 先像倒排索引那样,建一个从email到name的map, 只需要keep第一 ...

这道题需要进一步clarification。我之前的理解是只有完全包含的关系才能放到一个group里,比如
c1: a@xx.com, b@xx.com
c2: a@xx.com
c3: b@xx.com
c1完全包含c2和c3。
不知道这种情况应不应该merge:
c1: a@xx.com, b@xx.com
c2: a@xx.com, c@xx.com
按你的假设上述是可以merge的,如果这样确实可以用union find
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-7 13:48:21 | 显示全部楼层
liuliu146 发表于 2016-7-7 13:00. From 1point 3acres bbs
这道题需要进一步clarification。我之前的理解是只有完全包含的关系才能放到一个group里,比如
c1: ,
...

我觉得也是可以merge的 一般来说电话本里的记录 存人的名字时候有不同的缩写简写 但是email相当于是一个primary key是唯一的 只要出现了一样的email 按理应该就被归类成同一个人
如果onsite还可以跟面试官交流一下 OTS的话 只要注释写清楚应该都OK吧
回复 支持 反对

使用道具 举报

leyhzm 发表于 2016-7-9 21:05:30 | 显示全部楼层
请问OTS不是网测吗?为什么会用到Skype吖?有面试官看着你做题吗?
OTS有规定要用什么语言嘛~谢谢~
回复 支持 反对

使用道具 举报

specialton 发表于 2016-8-4 06:11:30 | 显示全部楼层
leyhzm 发表于 2016-7-9 21:05
请问OTS不是网测吗?为什么会用到Skype吖?有面试官看着你做题吗?. visit 1point3acres.com for more.
OTS有规定要用什么语言嘛~谢谢~
.1point3acres缃
是Skype组的OTS
回复 支持 反对

使用道具 举报

tiancaihxx 发表于 2016-8-11 12:34:23 | 显示全部楼层
第三题是系统设计题吗?client的意思是电脑上的app?
回复 支持 反对

使用道具 举报

feichangh 发表于 2016-8-25 04:44:37 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-7 13:48
我觉得也是可以merge的 一般来说电话本里的记录 存人的名字时候有不同的缩写简写 但是email相当于是一个p ...

上上周做了他们组的OTS第一题也是这个题,我的想法和你差不多也是倒排索引加并查集,交之前我还特地在IDE跑了几个结果都是对的.结果今天受到挂信,说algorithm over complicated也是醉了
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-8-27 07:28:32 | 显示全部楼层
feichangh 发表于 2016-8-25 04:44
上上周做了他们组的OTS第一题也是这个题,我的想法和你差不多也是倒排索引加并查集,交之前我还特地在IDE ...

真是醉了 面试官水平不行啊 看不懂并查集吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 23:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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