Microsoft Interview第一轮

上来随意交谈了一小会儿,开了点小玩笑,chat了一些关于他们recruter行程的话题,缓和了一下气氛。

进入正题,问了做的research的方向,我说是DLT,然后大概给他讲解了一下具体是什么, 跟平行计算很像,举了一个例子:矩阵乘法如何划分使并行效率最高。他表示理解。然后他又问我有没有过end to end的experience, front end back end那种, 我跟他简单介绍了一个简历上的social database设计的project,简单介绍了我们front end和back end的功能。然后他又问我最chanllenging的coding experience,我说是我第一个NP project, 跟他大概介绍了一下,他问大概多少行代码。

他说通不通过主要取决于当场写算法。然后就开始出第一道题

1. Anagram问题,如何判断两个String是不是Anagram,他先让我讲思路。我说一般两种做法,一是转换为char array, sorting, 看sort了之后的char array是不是一样的。另外一种做法是用hashMap, 把第一个String的元素依次输入hashMap, 再把另一个String的元素依次输入另一个HashMap, 然后比对这两个HashMap是不是一样。他问我各自的时间复杂度是多少,我说分别是O(NlongN)和O(N), 并解释了原因。他然后让我用HashMap那种方法,问我to save trouble,能不能用其他的数据结构而不用HashMap. 我说用int array, 假设字符是ASCII码,建立一个256 size的array, 对每一个字符,到int array的相应的位置去+1,对第二个String再来一次扫描,到相应位置-1, 最后看是不是全零array. 这样是O(2N),他问能不能O(N),我说可以把+1-1的操作放到一次scan里面完成。他点点头。

2. 然后他把白板擦了出第二道题。一个M*N grid, 一个人从左上去右下,问有多少种路径。我跟他说这是一道DP的题,建立一个M*N矩阵,对每一个entry,表示从start到当前位置有多少条路径. matrix[M-1][N-1]为所求。matrix[0][0] = 1. 递推式是 matrix[x][y] = matrix[x-1][y] +matri[x][y-1]. 然后还要考虑一下corner case, 比如matrix[0][x]. 他让我拿4*4矩阵推导一下,我推导了,得到matrix[3][3] = 20. 他说OK

3. 前两道题都感觉还可以,这道题就感觉比较难了。酒瓶问题。第一行1个,第二行2个,3行3个....,每个酒瓶承1加仑的酒,超过就均匀溢出给左右两个child酒瓶。问如果我有C加仑的酒,第N个酒瓶有多少酒。我推导了一下,也没有拿出太好的方案,他便给了一个提示,找parent的index和child index的关系。 我说假设N在第x+1 row, 如何找x, 就是比对N在哪个x(x+1)/2 和(x+1)(x+2)/2之间,找到了x, 那N的parent的index是N-x-1以及N-x。这是step one. 讲到这里没时间了,也讲的比较混乱。 step2没做,现在想想, 如果假设N-x-1为P1, N-x为P2,应该是

f(N) = f(P1)>1? (f(P1) -1) / 2 : 0 + f(P2)>1? (f(P2) - 1) / 2 : 0, 不考虑cornor case的情况。base case是f(1) = C; 最后return f(N)>1? 1 : f(N)

时间: 09-25

Microsoft Interview第一轮的相关文章

2014年百度之星程序设计大赛 - 初赛(第一轮) hdu Grids (卡特兰数 大数除法取余 扩展gcd)

题目链接 分析:打表以后就能发现时卡特兰数, 但是有除法取余. f[i] = f[i-1]*(4*i - 2)/(i+1); 看了一下网上的题解,照着题解写了下面的代码,不过还是不明白,为什么用扩展gcd, 不是用逆元吗.. 网上还有别人的解释,没看懂,贴一下: (a / b) % m = ( a % (m*b)) / b 笔者注:鉴于ACM题目特别喜欢M=1000000007,为质数: 当gcd(b,m) = 1, 有性质: (a/b)%m = (a*b^-1)%m, 其中b^-1是b模m的逆

第一轮迭代团队贡献分分配

经过我们团队的讨论,第一轮迭代团队贡献的分配方案如下: 团队成员 最终得分 高孟烨 64 邓亚梅 39 陈少杰 62 金鑫 57 雷元勇 36 王迪 37 郑培蕾 55 第一轮迭代的成绩让我们都不是很满意,所以成败就看M2阶段了,小伙伴们加油啦~ 暂定转会的成员是邓亚梅,明天上课的时候最后确定.

ZJOI2017第一轮游记

ZJOI2017第一轮:2017.3.20---3.23 Day 0 有好多天没做作业了,感觉不错. 温州还是不错的,宾馆也很满意. 感觉明天会听不懂. Day1 第一节课的前半部分还能勉强听懂,后面和下午一脸懵逼. 第一节课是有XJ中学的周子鑫学长上的搜索题,下面是一点总结. part 1:折半搜索 比如说双向广搜之类的,主要是从起点和终点交替搜或者是同时搜,可以降低搜索复杂度. 如果答案容易合并,或者搜索的操作可逆,可以考虑折半搜索. 还有一个技巧,要算方案数时,将折半的两边都存入hash数

2014第六届华为编程大赛初赛第一轮

/*********************************************************************** 1.投票问题 输入若干候选人,以及投票,格式如下,输出(按输入候选人输入顺序)候选人以及得票,以及 无效票数. Input: addCandidate xx1 addCandidate xx2 addCandidate xx3 addCandidate xx4 addCandidate xx5 addCandidate xx6 vote xx2 vot

Microsoft Azure第一步——试用帐户申请

从本文开始,将会对Microsoft Azure云从Iaas, Paas, Saas三种类型的云应用通过文章进行介绍.千里之行,始于帐户:),如果大家需要申请免费试用帐户请参考本文. 对于直接付钱的壕们,您可以选择关闭浏览器. 对我们广大天朝人民来说,有两个Microsoft Azure运营服务可以选择,一个是Microsoft,运营全球的Azure云服务:另外一个是由世纪互联,专为中国区用户运营的Azure云服务. 两者比较: 项目 Microsoft运营 世纪互联 地址 http://azu

第一轮面试题汇总

1.描述下数据库中的事务--ACID各个的特点 原子性(Atomicity):事务中的操作要么全部成功要么全部失败. 一致性(Consistency):事务前后数据的完整性必须保持一致. 隔离性(Isolation):多个并发的事务之间是相互隔离的,互不干扰的. 持久性(Durability):事务提交后,数据是永久改变的. 2.什么是springboot?你们公司是用的哪个版本? SpringBoot是Spring推出用于解决传统框架配置文件冗余,装配组件繁杂的基于Maven的解决方案,旨在快

使用Microsoft设计方案 第一章 企业解决方案中构建设计模式

第一章企业解决方案中构建设计模式 我们知道的系统总是由简单到复杂,而不是直接去设计一个复杂系统.如果直接去设计一个复杂系统,结果最终会导致失败.在设计系统的时候,先设计一个能够正常工作的系统,然后在此基础上逐步扩展.而一个好的企业设计方案就是由一些短小.简单.可靠.有效的并能够解决问题的机制组成.由这些短小精悍的机制进行组合,形成复杂的系统.而这些机制就设计模式.设计模式就是能够记录这些机制的一些描述. 企业级业务解决方案一般是复杂.性能要好.可扩展性好以及容易维护和可伸缩性强,而设计模式可以帮

羊年在即,第一轮资源大放送!

新年新气象,现将平时积攒的开发资源献给大家,希望对于大家平时的工作或学习有所帮助,本人从事开发和架构多年,以后大家有什么问题都可以跟我交流,我也乐于给大家提供力所能及的帮助! 大家拿起手机扫一扫本人微信号吧,以后有更多优质资源送出,希望大家关注: 第一拨资源主要是jquery前端开发资源,附带可运行示例: 178图库jQuery相册代码:点击下载 2款基于jQuery实现的页面预加载动画特效源码:点击下载 360°三维视图jquery插件:点击下载 360音乐歌手切换jQuery选项卡:点击下载

面经:Bloomberg Internship第一轮

上来先问了一个系统设计的问题,一个front end, 一个back end. front end有很多UI,一个UI对10个多customers,back end有许多processor,或者processor有多个进程.线程.问应该怎么设计这个并行分布运算的系统,才能让独立的任务得到优化. 完全那这个系统设计没有办法,需要有相应的经验才能答这种题.不知道为什么new grad也要问系统设计 这其中问了一些父子进程.线程各自的优劣 第一个算法题是给个String,比如AABBBCCCDD,问怎