Microsoft on campus

刚刚面完，新鲜的microsoft on campus interview上来问了下简历，问了之前的project/实习的东西，问得没有特别细，但也go down one level

coding只有一道题：
给你一个array of integer of length n and it contains 1 ... n-1.
我的解题非常简单，就是一个loop，然后用个set储存已见的，如果见到已见过的数字，就return那个数字
runtime O(n), space O(n)
然后考官就问如何optimize space.
脑子当时就抽了，不知道怎么optimize，但是考官还是很nice来给了我接近5-6分钟的hint。
他一开始说"Can you covert integer into some other data type?"
我都没答起来。
然后他还很nice的给我形象地描述了“假如我有一堆数字n个，你有很多n - 1 个bucket，我给你个数字，你如何通过不拿我的数字来记录下来你见过什么数字？”
他都说到这份上，我还是蒙了一会儿。最后我说出了什么什么bitmap之类的，但最后也通过他的提示下知道一个bool array就可以解决。
就是说Ο(n) of integer space 变成 O(n) of boolean。
最后解出来了，就问了几个问题就结束了。

这么简单的题脑子抽了要考官给那么多hint，大概率是凉了。
. Waral dи,我就不设限制了，求加个米。

如果有什么写得不清楚的，欢迎评论。我会解答的

嗷嗷，题目是要找那唯一一个的duplicate。

array of length n，但只有数字只有 1...n-1，所以里面有一个duplicate。要找到那个

蠡口而霸气？

leetcode 268

悲剧了 moveon 了