STCA 苏州微软实习生面经（1、2面）（已过）
一面：
英文自我介绍，
第一题是个模拟，给一种字符串加密方法，加密过程是把一个串不断左右左右移动： 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 ) 空间复杂度小一点的 ： 从右到左去扫，记录最大值，累加。。。
面试都过了。。但是offer还要等。。不清楚得到了面试通过邮件算不算口头offer了。。
（如果涉及私密信息，私聊楼主，立刻删除）
/////
4.16更新。。收到offer了。。。刚发完面经就收到了。。祝大家好运。。
#微软实习##微软##实习##软件研发工程师##面经#
查看5道真题和解析
