苏州微软8月六轮面筋

苏州微软的面
一共面了六轮，第一轮视频面试，过了后第二天通知onsite，然后四轮onsite连面，三轮组员一轮leader，总体感觉比较好，反馈速度也是很快，第二天就通知过了。最后就是boss面，boss地方飘忽不定，所以是远程视频。六轮都是technical，主要算法，ood design为主，但是败在最后一轮，考的不是算法，也不是coding，考得是细心程度和想问题想得深不深。这次精力消耗还挺大的，反正今天还没缓过来，比较难受，准备先休息休息，有问题后面会慢慢回答的。

视频screen：longest palindrome，要求用dp。还有一个是merge k sorted linkedlist
onsite:
第一轮：longest substring with at most K distinct letter, the longest consecutive sequence of numbers that sum to K。第一个讲思路，第二个思路+手写。最后test case全过后多余时间面试官塞了我几道题，reverse a linked list, intersection of two linkedlist，秒了，结束。
第二轮：BQ, ood design，有一个二维界面，有很多图形，圆啊矩形什么的，要求任意两个图形能返回对应位置和判断相互是否重叠。一套给设计出来。并且implement圆和矩形是否重叠的function。这个我不强，但是面试官很耐心，我也不清楚就问，最后是搞出来了，面试官也觉得可以。还剩点时间，做了个求树上任意节点的最大的路径和，也差不多秒了。
第三轮：把之前做过的project流程图画出来解释了一下，然后做题，find median of two sorted array，这个题我想了一会，从brute force到利用merge sort思想，再到用heap，最后用的一个利用partition来找中位数的一个方法，然后最后在提醒下完成了最后一个方法的implementation，测试完testcase，结束。
第四轮leader面：实现a % b 不能用乘除，naive way是用减法。然后面试官想提高time，我就每次找了update b += b，相当于是指数数率的一个增长找，但是后面在找具体的数时候卡死了，卡了我很久，最后面试官看不下去了，叫我算了，让我设计一套算法，来解决地图上的文字能够不重叠，瞎逼逼了一些，他觉得还行，然后结束。

我以为这已经全部面完了，没想到这个组惯例是六面，叫我回去等消息。
第二天hr就给我说了结果，不得不说微软效率真快，然后确定了最终boss面。

最后一轮：把一串string转化成int。具体是三百二十八万三千二百八十转化成数字，你不能依靠client输入valid的string，如果是三百二十千八百二十八这个就不行，有可能是负数。数量是1兆到-1兆。我最开始以为不算很难，但是用stack思想做了后漏洞百出，怎么判定是invalid？十一这个testcase你怎么办？十是算作单位还是算作一个数？一到九和其他单位是不是要分开考虑？五万零三百二十这个test case怎么办？还有一点我比较无语，他说int overflow怎么办？我用的是python，我记得是不用管的，不会有overflow的问题，但是强行让我管...我只能瞎说了。反正后面头都要炸了，说得也比较乱，强行扯了一波，其实面完就知道我要跪了。

果不其然，跪了，微软还是算法题为主，碰到最后一轮的那种题也只能认了。还是菜，没理由，只是有些不甘心。大家自行看看吧，希望有大家能教下我a%b那个优化和最后一轮面试的题该怎么去规范的approach。加油吧！

觉得有用的给点米呗：）

取余那道是原题吧，利口二舅，最后那个就是实现atoi,  网上实现挺多的，用stack来做的比较少。至于说整数溢出，你用个long long 存中间值，判断是否大于INT_MAX或者小于INT_MIN，如果溢出了处理方法也可以自己设，比如大于INT_MAX就返回INT_MAX这种，最后返回时把long long转换回int就行了

hunterinstant 发表于 2019-10-25 09:38
a%b 的优化参考leetcode 除法 实现

http://blog.sina.com.cn/s/blog_7b7cad23010163vy.html   如果是正数  好像可以用这篇Blog 里面说的实现 ？
如果是leetcode 的 除法实现 还真的有点难呐

yanjinbin 发表于 2019-12-2 15:58
没懂 能讲讲思路吗？

#a%b
while a>=b:
  t=b
  while a>=t<<1:
     t=t<<1
  a-=t

return a

求问一下 第二轮的sum to k 那道题 number里面有负数吗

补充内容 (2019-8-3 14:40):
说错了 第一轮

想问下楼主微软可以面多个部门吗？比如苏州的挂了还能投北京的吗

sentry 发表于 2019/08/04 22:58:29
取余那道是原题吧，利口二舅，最后那个就是实现atoi,  网上实现挺多的，用stack来做的比较少。至于说整数溢出，你用个long long 存中间值，判断是否大于INT_MAX或者小于INT_MIN...

不是atoi吧，人家输入的是中文汉字啊，而且要真用longlong面试官肯定不满意吧

sentry 发表于 2019/08/04 22:58:29
取余那道是原题吧，利口二舅，最后那个就是实现atoi,  网上实现挺多的，用stack来做的比较少。至于说整数溢出，你用个long long 存中间值，判断是否大于INT_MAX或者小于INT_MIN...

不一样吧，atoi就是简单的提取数字，那道里面没有单位啊。一百三十五万三千二百转化成数字，首先要把一百三十五万的一百三十五给先转化成数字，遇到单位了还要乘上单位，如果你有比stack更好的办法可以分享分享

coldyan 发表于 2019/08/05 09:43:34
想问下楼主微软可以面多个部门吗？比如苏州的挂了还能投北京的吗

一共两个组的机会，不分地点

请问为什么你这么早就面试了？ 不是还没有开始吗？
难道你不是校园招聘，而是社招？

lisun97 发表于 2019/08/05 15:28:24
请问为什么你这么早就面试了？ 不是还没有开始吗？
难道你不是校园招聘，而是社招？

我没走流程，是组内内推的

都是好同志 发表于 2019/08/05 13:21:14


一共两个组的机会，不分地点

楼主是校招还是社招？