一亩三分地论坛

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

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

Microsoft On Campus Interview

[复制链接] |试试Instant~ |关注本帖
八月 发表于 2016-10-13 03:24:53 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Microsoft - 校园招聘会 - 校园招聘会 |Other其他

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

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

x
9月份在career fair投的简历,上周日才收到on campus 面试通知,30分钟,刚面完
面我的是一位在bing组的三姐姐,上来先聊了五分钟简历,然后她说了五分钟关于自己在做的一些东西。讲完后突然就给我一道题。
题目是一个2darray,里面都是数字,求maxsum subarray。
我说了思路以后,她让我写1d的code。我就写写写(用笔在纸上写 = =),边写边说。三姐姐也不说话,都是我在说,写完给她,她说ok good。。。。
最后问了些问题,然后30分钟就过去了。。。

求第二轮 = =

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Camel_Yan 发表于 2016-10-13 12:38:18 | 显示全部楼层
找到了,应该是这道 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
回复 支持 1 反对 0

使用道具 举报

zhuhai_ZFC 发表于 2016-10-13 10:08:05 | 显示全部楼层
二维的有专门的模式的。包括找largest sum no larger than k, maximum submatrix that sums to k的二维版本,都是一个模式。这些题O(n^4)非常简单,但是如果要做到O(n^3),就要在外两层循环里对列进行循环,一个是起始列,一个是终止列。然后第三层循环是对这两列之间的行进行循环。
回复 支持 1 反对 0

使用道具 举报

123呆板彻底 发表于 2016-10-13 03:31:37 | 显示全部楼层
巨硬的intern面试这么难啊。。。。
我同学面他家fulltime的on-campus一道比一道简单。。全是medium-easy级别的
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 03:33:59 | 显示全部楼层
123呆板彻底 发表于 2016-10-13 03:31
巨硬的intern面试这么难啊。。。。
我同学面他家fulltime的on-campus一道比一道简单。。全是medium-easy级 ...

= =我觉得还好,就是三姐姐不说话,心里很慌
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 03:35:49 | 显示全部楼层
123呆板彻底 发表于 2016-10-13 03:31.鐣欏璁哄潧-涓浜-涓夊垎鍦
巨硬的intern面试这么难啊。。。。
我同学面他家fulltime的on-campus一道比一道简单。。全是medium-easy级 ...

他家fulltime on-campus在我们这边是一起面的,上一个同学也是这个三姐姐,但他是FT,不过题目好像是一样的(看三姐姐的草稿纸)
回复 支持 反对

使用道具 举报

graininear 发表于 2016-10-13 03:36:09 | 显示全部楼层
楼主你好,请问题目能再具体描述一下么?  2d里面 跨行也要算subarray么? 能不能说下你的思路,谢谢了
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 03:39:02 | 显示全部楼层
graininear 发表于 2016-10-13 03:36
楼主你好,请问题目能再具体描述一下么?  2d里面 跨行也要算subarray么? 能不能说下你的思路,谢谢了

跨行不能算,就比如一个m*n的矩阵,任意的i*j大小的array都算subarray,不过他没让我写2d的算法,让我写了1d的,1d就每次存curr sum,max 和min
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-13 03:45:20 | 显示全部楼层
八月 发表于 2016-10-13 03:39
跨行不能算,就比如一个m*n的矩阵,任意的i*j大小的array都算subarray,不过他没让我写2d的算法,让我写 ...

跨行会算, 这题是facebook的原题,有一点难度。
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 03:47:39 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-13 03:45
跨行会算, 这题是facebook的原题,有一点难度。

= =真的吗。。。她好像也没说什么,如果是这样那我应该就想错了。。。
回复 支持 反对

使用道具 举报

graininear 发表于 2016-10-13 03:49:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-13 03:45
跨行会算, 这题是facebook的原题,有一点难度。

你好,请问leetcode上有么? 好像没找到啊。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-13 03:49:51 | 显示全部楼层
八月 发表于 2016-10-13 03:47
= =真的吗。。。她好像也没说什么,如果是这样那我应该就想错了。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2d肯定是找submatrix, submatrix,肯定跨行了。
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-13 04:01:46 来自手机 | 显示全部楼层
我就是你前面的那个。。你确定是subarray?他给我的题目是 任意形状!!!!
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-13 04:04:19 来自手机 | 显示全部楼层
最后我说这题没法做啊 任意形状做个蛋啊。。他说我就是让你找我这题哪错了
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-13 04:11:04 来自手机 | 显示全部楼层
submatrix可以用prefix sum 然后遍历 对每轮求一次一维最大值
回复 支持 反对

使用道具 举报

Camel_Yan 发表于 2016-10-13 12:10:12 | 显示全部楼层
fackbook哪道原题请问,lz能详细描述一下吗,1d用dp,2d 的lz怎么说的
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 12:43:04 | 显示全部楼层
Camel_Yan 发表于 2016-10-13 12:38
找到了,应该是这道 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d ...

对,好像就是这个!谢谢你。
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-13 20:51:51 | 显示全部楼层
clxy2008 发表于 2016-10-13 04:01
我就是你前面的那个。。你确定是subarray?他给我的题目是 任意形状!!!!

这。。。。我问她是不是subarray 她说是 = =
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-14 07:16:03 | 显示全部楼层
八月 发表于 2016-10-13 20:51
这。。。。我问她是不是subarray 她说是 = =

估计就是他一拍脑门想出来的题目,他给我的test case就是在矩阵里随意选取了一个形状,然后他不让我做,先让我做一维的,然后问怎么做这个,我不会,就只能先说 如果是求matrix,那么就是做prefix 然后再用一次一维的算法,但是如果是随意形状,我不会做,而且应该没法做吧,因为可以向各个方向跑,就算用bfs也不知道什么时候停止,因为可能碰到了负数,但是负数后紧接着是一个足够大的正数。
. 1point 3acres 璁哄潧
她说对对对,我就是让你找我这道题哪里有错误。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

反正我到现在还是很懵逼,只能求人品,求onsite了
回复 支持 反对

使用道具 举报

 楼主| 八月 发表于 2016-10-27 06:11:55 | 显示全部楼层
clxy2008 发表于 2016-10-14 07:16
估计就是他一拍脑门想出来的题目,他给我的test case就是在矩阵里随意选取了一个形状,然后他不让我做, ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这么坑爹啊 - - 同求onsite。。。我暂时还没消息 你呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 17:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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