一亩三分地论坛

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

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

微软 Onsite Event - 已跪

[复制链接] |试试Instant~ |关注本帖
lfzh123 发表于 2016-7-20 05:34:19 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Microsoft - 内推 - Onsite |Fail在职跳槽

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

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

x
1.     给一些intervals,每个interval除了start和end,还有一个ID,返回所有有交集的intervalsID pair。我的想法是先按start sort一下,然后依次查看有没有交集,但是还是用nested loop,O(N^2),有没有更好的solution呢?
2.     class Lstream{
void put(long);
long get();   每次返回一个long,然后自动指向下一个。
Boolean EOS();
}
Merge(Lstream[] input, Lstream output),是merge k sorted list的变种,我是用priorityqueue方式实现的,tricky的地方是这个priorityqueue只是存long,但是要想办法知道它是属于哪个Lstream,这样才能接着从这个Lstream里取一个long放入output,还问了priorityqueue是怎么实现的。
3.     LC wall and gate. 写了DFS,问了复杂度。问有没有bettersolution,之前只写了DFS,就写过BFS。最后没有时间写BFS了。
4.     没有搞清楚要考什么,给了很多提示也不知道怎么做,最后面试官给我说了一种designpattern,叫做decorator,然后建议我看看designpattern的书,这轮被碾压了。
Recruiter周一下午就给我打电话说no hirefeedbacksolutionsare not optimal。其实人很好,让我过6个月再试试。
感觉现在MS Azure虽然狂招人,但要求也挺高的。

评分

5

查看全部评分

 楼主| lfzh123 发表于 2016-7-20 08:26:30 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-20 07:15
LZ这几道比我面的难一个档次. from: 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-7-20 07:21):
. 1point 3acres 璁哄潧
你也快写一下你的面经哈。
关于2D的BFS和DFS的时间复杂度,我从面试官那里学到了。可以把这个2D matrix看成graph,一共有M*N个点和4*M*N个edge,所以单纯遍历graph的话, 就是M*N.但是这个M*N是嵌套到M*N的loop里,所以DFS的话是(M^2 * N ^2). BFS的话,先用M*N找到所有0,然后再用M*N遍历matrix,所以就是M*N-google 1point3acres
回复 支持 1 反对 0

使用道具 举报

jimmyzzxhlh 发表于 2016-7-20 05:43:38 | 显示全部楼层
Patpat楼主,同样刚面过Azure,还没得到消息. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题能不能举例说明一下什么是“所有有交集的interval ID pair”?是比如说有下面的interval
ID 1: [1,4]
ID 2: [3,7]
ID 3: [9,12]
ID 4: [5,10]
那么返回(1,2),(2,4),(3,4)吗?如果是的话感觉可以sort一遍然后对于每个interval [start[i],end[i]]用Binary Search找最后一个interval [start[k], end[k]]使得start[k]<end[i]
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-20 05:54:27 | 显示全部楼层
第一题,我感觉这种球所有可能性的应该是用DFS做,思路类似于LEETCODE 77 Combinations,然后具体到这个题目,k=2,n是代表Interval set的集合,停止条件除了满足k=2,还要满足纳入的两个Interval相交。这个可能不是最优解。
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-7-20 06:07:03 | 显示全部楼层
请问下楼主是怎么参加这个event的。网上感觉找不到申请链接啊。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2016-7-20 06:11:42 | 显示全部楼层
第一题可以用Interval search tree 找出所有相交pair. https://www.youtube.com/watch?v= ... Rs-DqAx&index=4
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-20 06:14:03 | 显示全部楼层
zq13667243992 发表于 2016-7-20 06:11
第一题可以用Interval search tree 找出所有相交pair. https://www.youtube.com/watch?v=E-9b8k7JK6I&list= ...

赞!!!!!!
回复 支持 反对

使用道具 举报

forteller 发表于 2016-7-20 06:16:30 | 显示全部楼层
第一题用scan line加queue 具体可以参考lintcode 的 number of airplane
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-20 06:39:57 | 显示全部楼层
jimmyzzxhlh 发表于 2016-7-20 05:43.1point3acres缃
Patpat楼主,同样刚面过Azure,还没得到消息
第一题能不能举例说明一下什么是“所有有交集的interval ID p ...

是的,你的理解是对的。但是我不太明白怎么做binary search。我看楼下有一个关于interval search tree的link,感觉应该可以。
但是当时面试官说,O(n^2)的naive解法,就是她想要的。。
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-20 06:40:30 | 显示全部楼层
csushin1992 发表于 2016-7-20 05:54
第一题,我感觉这种球所有可能性的应该是用DFS做,思路类似于LEETCODE 77 Combinations,然后具体到这个题 ...

我就是暴力nested loop解得
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-20 06:41:03 | 显示全部楼层
glaciersilent 发表于 2016-7-20 06:07
请问下楼主是怎么参加这个event的。网上感觉找不到申请链接啊。

内推啊,OA过了之后,HR给你发link注册
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-20 06:41:36 | 显示全部楼层
zq13667243992 发表于 2016-7-20 06:11
. 鍥磋鎴戜滑@1point 3 acres第一题可以用Interval search tree 找出所有相交pair. https://www.youtube.com/watch?v=E-9b8k7JK6I&list= ...

嗯,这个赞,第一次知道这个advanced data structure
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-20 06:42:33 | 显示全部楼层
forteller 发表于 2016-7-20 06:16
第一题用scan line加queue 具体可以参考lintcode 的 number of airplane

类似,但是要记录所有的pair啊,我但是尝试sort之后,用two pointer解,但是不work。
回复 支持 反对

使用道具 举报

jimmyzzxhlh 发表于 2016-7-20 06:55:55 | 显示全部楼层
lfzh123 发表于 2016-7-20 06:39
是的,你的理解是对的。但是我不太明白怎么做binary search。我看楼下有一个关于interval search tree的l ...

噢不好意思我以为是要返回有几个pair,看起来是要返回所有的pair.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如排好序了以后:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 1point3acres.com/bbs
[1,5]
[2,3]
[2,4].鐣欏璁哄潧-涓浜-涓夊垎鍦
[3,6]
[4,8]
[5,9]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[6,7]

从第一个interval [1,5]开始,end是5,那么就是在所有的interval里找最后一个start<5的,也就是[4,8],[4,8]的index是4,[1,5]的index是0,意味着有4-0组是和[1,5]相交的
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-20 07:15:58 | 显示全部楼层
LZ这几道比我面的难一个档次
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-7-20 07:21):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对了 wall and gates那个 我怎么感觉DFS跟BFS复杂度一样的  k个门的话都是K*M*N
回复 支持 反对

使用道具 举报

sunyangtian 发表于 2016-7-20 07:41:22 | 显示全部楼层
jimmyzzxhlh 发表于 2016-7-20 05:43
Patpat楼主,同样刚面过Azure,还没得到消息
第一题能不能举例说明一下什么是“所有有交集的interval ID p ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
跪求二楼分享你的面经啊。。。。
回复 支持 反对

使用道具 举报

sunyangtian 发表于 2016-7-20 08:15:47 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-20 07:15
LZ这几道比我面的难一个档次

补充内容 (2016-7-20 07:21):

请问下你也是面azure compute的么?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-20 12:14:22 | 显示全部楼层
lfzh123 发表于 2016-7-20 08:26
你也快写一下你的面经哈。.鐣欏璁哄潧-涓浜-涓夊垎鍦
关于2D的BFS和DFS的时间复杂度,我从面试官那里学到了。可以把这个2D matrix ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
学习了 这样BFS确实是最优的
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-7-20 13:09:40 | 显示全部楼层
楼主知道有拿到offer的嘛?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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