微软一面挂经

虾图血汗工厂跳槽，面了下国内微软的社招，因为没有冷冻期，刷了点题看了看面经直接就上了，问了问项目和基础知识，答的一般，重写和重载我记反了，好像问了20分钟。问的题很常规，151. Reverse Words in a String，不过我给出reverse whole string 再reverse each word，说需要one pass，我就想啊想，然后想了10几分钟，面试官给hint，我想到scan word back to front直接根据index，append到res=[] 上去，但是说用了additional space，不是O(1)，当时就晕了，实在想不到怎么用O(1)解出来,python string 是immutable的，不让用list想不出其他解法了..面试完了，看leetcode也没看出有什么别的办法可以O(1) 解出来，而且其实那样scan 再copy word我感觉也是two pass吧，相当于scan back-front 再copy [i..j] word上去，本质上和reverse 2次有啥区别。。。有点无语，看了讨论区的解法，也没看到O(1) space的解法，感觉有点故意刁难的意思，在那个所谓one pass上墨迹了很久，我当时脑袋有点蒙圈事后想了想java 的string也是 不能改的，除非是C/C++ 那种给定的string * 形式才有in-place solution的意义吧。。。还有一道是设计矩阵运算的OOD，支持加法和乘法，没写完就到时间了










补充内容 (2021-06-08 14:42 +8:00):
hr给我了feedback，有点无语，比如feedback里直接写我没有给出完整的edge case，但实际上我没有第一时间写出来全部的，但是剩下的2个在没有提示的情况下还是自己添上去了...

python的话应该不可能O（1）的，因为他的字符串类型不可变，你应该像面试官说明这一点

苏州还是北京职位？

我觉得面试官晕菜了吧，非要One pass的话就是leetcode解答里面第三种解法，用Deque，但是不可能常数的空间复杂度的。