一亩三分地论坛

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

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

微软Hiring Event面经,已挂

[复制链接] |试试Instant~ |关注本帖
liuliu146 发表于 2016-7-7 08:07:04 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Microsoft - 猎头 - Onsite |Fail在职跳槽

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

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

x
上周参加的Hiring Event,今天得知挂了,由于有NDA就不说明是哪个组了,但把题透露出来希望对大家有帮助:

1) 偶数个球排成一排,每个球上都有分数,两个人进行游戏,每个人轮流拿走一排球里的第一个或最后一个,求第一个人拿球的人所能获得的最大分数. from: 1point3acres.com/bbs
我记得这道题是lc书里的一道题,但从来没在oj里出现过,所以没怎么练,没想到考出来了,可以用暴力的递归法,需要注意当前拿球的是玩家1还是2,或者是用DP,但两种方法的难点都在于在玩家2的策略怎么反映出来,当时我在那里纠结了很久。事后静下心来也想出来解法了,但当时那种紧张的环境实在没转过弯来,估计也是因为这一轮fail掉的

2) 口头上问了问如何反转链表。然后一道题是:有个系统api可以返回1GB的内存,定义一个method可以返回任意大小的内存。我当时被那个api返回的值限制住了,以为是int*, 但我估计可以用链表来代替的
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
3) 把一个链表倒叙输出。我能想到的是要么递归,要么把链表反转正序输出,大家还有别的办法吗?然后人家让我设计扫雷游戏。具体到地图是如何初始化的,雷是如何随机分配的,每个格子会有不同的状态,是怎么表示的。.鐣欏璁哄潧-涓浜-涓夊垎鍦

4)时针和分针的夹角。设计一个二维码读取器。如何fault tolerant?如何防止把一些黑客把code编到二维码里,进而对系统进行破解?目前的二维码就黑白两种色,如果以后加入别的颜色,该如何处理?-google 1point3acres

欢迎大家讨论!

评分

1

查看全部评分

lfzh123 发表于 2016-7-7 08:36:34 | 显示全部楼层
谢谢楼主分享,我知道是哪个event了,我之前做OTS没有过。。不过下周去参加另外一个event了。. 1point 3acres 璁哄潧
楼主知道feedback吗?
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-7 09:10:25 | 显示全部楼层
lfzh123 发表于 2016-7-7 08:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢楼主分享,我知道是哪个event了,我之前做OTS没有过。。不过下周去参加另外一个event了。
楼主知道fee ...

就说我大概75分,almost there,比较可惜,算法需要加强,虽然暴力法可以接受,但需要更好的方法(估计就是第一道算法题),还有就是有些地方解释的不是很清楚(估计是那些design的东西,尤其是二维码那个题,对那个东西的编码什么的毫无概念,只是大概说了说idea),他会再找个hiring event让我试试。
回复 支持 反对

使用道具 举报

xujingcheng 发表于 2016-7-7 11:35:11 | 显示全部楼层
所以Microsoft hiring event 挂了会有冷冻期么?
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-7 12:00:49 | 显示全部楼层
xujingcheng 发表于 2016-7-7 11:35. Waral 鍗氬鏈夋洿澶氭枃绔,
所以Microsoft hiring event 挂了会有冷冻期么?

貌似可以面不同的组。另外以前看版里有人说,onsite挂了如果觉得你有希望还是会再帮你找机会
回复 支持 反对

使用道具 举报

lfzh123 发表于 2016-7-7 12:32:16 | 显示全部楼层
liuliu146 发表于 2016-7-7 09:10. visit 1point3acres.com for more.
就说我大概75分,almost there,比较可惜,算法需要加强,虽然暴力法可以接受,但需要更好的方法(估计就 ...

楼主加油!和你讨论一下这几道题吧。
1. 如果是求player1最大值,那么player2每次都选小的那个,是这样的吧?
2. 关于API返回内存的题,需要考虑多种情况吧,比如1.4G, 内存不足啊,然后把每次调用的内存连在一起,然后返回初始地址,是吗?有点像LC 157. Read N Characters Given Read4。
3. 我觉得就是递归输出吧,也不会改变结构。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
4. 二维码读取器这个东西,牵扯到encoding/decoding,如果不知道原理的话,怎么回答啊。 。感觉太坑了。刚搜了一片文章关于二维码的 http://coolshell.cn/articles/10590.html。好复杂啊
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-7 13:24:45 | 显示全部楼层
lfzh123 发表于 2016-7-7 12:32
楼主加油!和你讨论一下这几道题吧。. 1point 3acres 璁哄潧
1. 如果是求player1最大值,那么player2每次都选小的那个,是这样 ...

谢谢!.鐣欏璁哄潧-涓浜-涓夊垎鍦
1) 这道题可以有各种问法,比如说让你找到一个最简单的方式使得你分比另一个人高,这时候只要你算一遍奇数的分,偶数的分,哪个分高你就每次都选奇数或偶数,让对手选另一半,还有可能像你说的,可以操纵玩家2,每次都选小的,使得玩家1分数最高。但我的理解是这里假设玩家1玩家2都很精明,每次都尽量使自己得分最高,这时候问玩家1能拿多少分。
2) 对,需要考虑各种edge case,但重点在于找出一个合理的分配内存的方法。有一点我当时没有clarify,就是说是不是要求返回的内存是连续的。我当时把API定义成了返回int*,这样就需要返回地址是连续的。所以在面试官提醒我用链表之前我怎么都不会想到用链表。我当时一开始想着用每一个bit来代表那个int是不是被占用,到后来又用hashtable来记录所占用的内存的开始结束点,再后来又用tree和hashmap结合。但这些方法都需要额外空间,而内存本身我一直在用int 数组来维持。于是面试官说用链表,我想估计可以把int 数组分成好几大段,每一个大段用链表的节点来表示?并且每一段的尺寸可以不一样,用来满足不同的需求。. Waral 鍗氬鏈夋洿澶氭枃绔,
3) 这哥们态度不太好,问我递归输出和把链表存到数组里然后再倒序输出有啥区别,我也想不到啥太大区别
4) 没啥办法讨论细节啊。。。。。
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-7 14:36:08 | 显示全部楼层
lfzh123 发表于 2016-7-7 08:36
谢谢楼主分享,我知道是哪个event了,我之前做OTS没有过。。不过下周去参加另外一个event了。-google 1point3acres
楼主知道fee ...

是7月15 Azure的么
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-7 16:07:48 | 显示全部楼层
liuliu146 发表于 2016-7-7 13:24
谢谢!. From 1point 3acres bbs
1) 这道题可以有各种问法,比如说让你找到一个最简单的方式使得你分比另一个人高,这时候只要你 ...

请问一下楼主
api返回1GB内存,然后要求实现返回任意大小内存的意思是从这个1GB里分配么? 如果全分配完了或者这个1GB里剩余的不够要求的大小了,就再申请一个1GB的开始分配。 不知道题目是不是这个意思?
回复 支持 反对

使用道具 举报

lfzh123 发表于 2016-7-7 23:24:22 | 显示全部楼层

是的                  
回复 支持 反对

使用道具 举报

whisperty 发表于 2016-7-8 04:00:09 | 显示全部楼层
递归输出和存数组输出的区别是用到的space大小不一样吧。 递归输出是链表长度*结点大小,数组输出是链表长度*值大小 (还不一定,跟具体实现有关),而且貌似后者还有额外时间开销。
回复 支持 反对

使用道具 举报

whisperty 发表于 2016-7-8 04:05:51 | 显示全部楼层
第一题得用动态规划吧。。
f(0, n) = Max(s(0) + total(1, n) - f(1, n), s(n) + total(0, n-1) - f(0, n-1))

f(0, n) means the max score of the 1st player for 0 to n balls.
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-8 08:24:12 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-7 16:07
请问一下楼主
api返回1GB内存,然后要求实现返回任意大小内存的意思是从这个1GB里分配么? 如果全分配完 ...
. visit 1point3acres.com for more.
对,但不用那么复杂,如果这个1GB不够用了就返回NULL好了,关键点还是如何管理这1GB
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-8 08:26:18 | 显示全部楼层
whisperty 发表于 2016-7-8 04:00
递归输出和存数组输出的区别是用到的space大小不一样吧。 递归输出是链表长度*结点大小,数组输出是链表长 ...

差不多吧,我觉得递归的时候可能会把指针存起来。
回复 支持 反对

使用道具 举报

 楼主| liuliu146 发表于 2016-7-8 08:32:05 | 显示全部楼层
whisperty 发表于 2016-7-8 04:05
第一题得用动态规划吧。。
f(0, n) = Max(s(0) + total(1, n) - f(1, n), s(n) + total(0, n-1) - f(0, n- ...

感觉你写的这个也有道理,只不过还需要计算total[j]. From 1point 3acres bbs

感觉大概是这样的:
maxScores[j] = Max(scores + Min(maxScores[i+2][j], maxScores[i+1][j-1]),
                               scores[j] + Min(maxScores[j-2], maxScores[i+1][j-1]))

回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-8 14:06:27 | 显示全部楼层
liuliu146 发表于 2016-7-8 08:24. visit 1point3acres.com for more.
对,但不用那么复杂,如果这个1GB不够用了就返回NULL好了,关键点还是如何管理这1GB

谢谢回复, 这个内存分配的问题网上搜了下发现有个叫buddy算法用链表实现的 每次分配或者释放都能O(lgN) 感觉像是面官在问的
回复 支持 反对

使用道具 举报

Simon-Chan 发表于 2016-7-11 06:24:04
first question looks like http://www.jiuzhang.com/solutions/coins-in-a-line-iii/
支持 反对

cicean 发表于 2016-10-2 06:59:27 | 显示全部楼层
楼主看不明白二维码这个。不是可以把http link 存在一张图里么。但是这东西是怎么实现的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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