微软STCA一面+三面
2.28 一面：
一道简单数据结构
3.4 三面：
全程中文；给我的感觉有点像压力面，整个过程中面试官不怎么会表示赞同，而是一直提出问题。
20min项目。问得很深。最后问到了知识边界没答上来。
做题：去除数组中重复的元素。
clarify:
1. 数组是裸的，并非vector。但是会传入数组的正确长度。
2. 元素32位int。
3. 数组未排序。
4. 原地去重。返回去重后数组的长度。
设计函数签名：int removeDuplicates(int[] a, int n)
版本1：
写了一个哈希set，数组塞进去。最后将hashset里的元素拷贝回去。
面试官：塞到set再拷贝回去太慢了，优化一下时间。
版本2：
哈希set维护遍历过的元素。双指针原地删除。
面试官：我不想要额外空间。
然后卡住了。一直在思考一个时间复杂度O(n)，空间复杂度O(1)的解法。
求hint之后和面试官提出的可能方案：
1. 原地哈希。但会改变数组元素，否决。
2. 用bitset压缩额外空间的常数。但空间仍不是O(1)，否决。
然后就到时间了。面试官说你可以offline再想想。
思考：似乎空间O(1)只能靠牺牲时间复杂度来做。网上似乎也没什么好的方法，我目前只能想到每次check的时候暴力遍历所有已经看到的数。这样空间O(1)时间O(n^2)。但当时根本没往暴力去想。
总结：
今天面完之后很难受。说实话还是很想去微软的。在床上躺了几个小时。
学校的事很多还没干，国内的厂还没投。我的春招才刚刚开始。
就当作一次历练吧。不管发生了什么，life still goes on。
#实习经验分享##微软##面经#
游卡开奖27人在聊