一面：
英文自我介绍，
第一题是个模拟，给一种字符串加密方法，加密过程是把一个串不断左右左右移动： abcde => dbace，你需要写一个还原函数，简单模拟，注意长度 奇数偶数分开讨论。。O(n)解决。。但是可以常数小一点。。
第二题。给一个森林（数组形式），每个树有个高度，现在我要选一个高度，高于这个高度的树木会被砍下，我只砍一次，在给定个目标树木和target, 要求看下的树木之和在>= target 基础上尽可能小，求最接近的答案
简单的二分。。。 O(n) check… 但是据说。。计数排序可以O(n)排序树木。。。 一旦有序。。记录后缀和然后再二分中套个二分就可以让时间复杂度变成 O(n + log(n) * log(n) )。。
二面：
直接做题，把中文数字转化为阿拉伯数字， 比如 一百零一 =》 101， 二零一九 =》 2019 ，
分两种情况。。
第一种情况就是纯数字。 check下字串。不带 百、十、万，只包含一、二、三。。。这样的，直接暴力处理。
第二种情况就是代表一个有大小的数字： 三种解法
O( n * log(n) ) ： 直接暴力递归， 每次找当前串中最大的部分 然后划分左右部分，左边计算完乘以中间最大值再加上右边部分， 当当前串长度为1特判。零也要特判，（比如一百零一里的零其实没啥特殊意义）
O( n ) : 单调栈从左到右扫一遍， 出栈时特殊处理一下，把栈顶元素累加到当前值上，最后再把当前值入栈，结果就是栈内元素累加和。
O( n ) 空间复杂度小一点的 ： 从右到左去扫，记录最大值，累加。。。
2、取整问题
例如3.14取整到3.1，3.15取整到3.2，3.25取整到3.2，3.取整3.3。先说规则以及为什么要这么取整。然后码代码，给float和取整位数n。
（这个是四舍六入五成双问题）
（1）被修约的数字小于5时，该数字舍去；
（2）被修约的数字大于5时，则进位；
（3）被修约的数字等于5时，要看5前面的数字，若是奇数则进位，若是偶数则将5舍掉，即修约后末尾数字都成为偶数；若5的后面还有不为“0”的任何数，则此时无论5的前面是奇数还是偶数，均应进位。
微软的面试官确实比较nice的，外企一般就是考coding
一面：
自我介绍，简单问了项目
算法题是乐扣的767题，事后才知道。。一开始不太会做，后来和面试官交流交流，有了思路，然后最后还讨论了为啥要排序，在我的碎碎念下我知道了为啥要这么做，因为当时我只是直觉要排序，，最后面试官说挺好的。
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
二面：
二面一开始问我有没有英文面试，我说没有。他说让我英文自我介绍一下，，我没准备，于是鼓起勇气磕磕巴巴的说完了。。面试官期间会说恩这类语气词，表示他听懂了哈哈
算法题是，微软小冰，根据语音输入的是一些语言的金额，怎么转化为书面的数字金额。类似于一千二百万亿五百万六千七百零二十，转化为数字。
一开始不会做，然后想了想，用字符串分隔和dfs递归勉强work了。。不过有一些细节没有处理，不过面试官可以了，又问有没有什么优化的方法，别的思路，我想了一下，，表示没有别的（我是个渣渣）
又问了一下关于通信懂多少，问sql学过吗之类的。
过了大概不到一个周吧，收到了意向书，是我收到的第一个正式的邮件offer，感谢！虽然我投的是机器学习，但是后面把我调到 Software Engineer~
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/174277.html原文链接：https://javaforall.net
