Uber Intern 二面

Uber 二面
考了一道关于找duplicate的题目，题目不难，但是follow up时对优化的要求挺高。
题目是这样的

您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

两轮Uber技术面下来，感觉Uber给的题都不难，难在不断地推进去优化时间/空间复杂度上。优化到一定的地步，就会需要一些奇技淫巧了。
anyway继续努力，升级打怪～Fulltime再战咯！


补充内容 (2019-4-15 08:08):
题意里，可能有多个duplicate，而且1～n的每个数字出现频率是不固定的，可能一次都不出现，也可能出现多次，比如input = {1, 1, 1, 2, 2}。
所以XOR应该是解决不了的。

补充内容 (2019-4-15 08:16):
既然space要求达到O(1)，完全不能使用extra space，那么就要考虑用原有的input array记录新的信息。

补充内容 (2019-4-15 09:46):
我现在很尴尬地没法回复评论。。。只能写补充，哭
但是，可以看kaipeng21的回复，他说的解法就是了！

谢谢分享～
优化是bit manipulation吗？

谢谢楼主分享
想求一下楼主的TimeLine

楼主这个优化应该怎么做啊，如果用xor的话万一有两个duplicate应该怎么解决啊

所以是类似于桶排序，array[i]记录的是i出现的次数咯

楼主可以讲下思路么？

既然范围都在1-n 之间换到自己的值的index 就能O(1) 了

估计面试官比较expect的是这种解法：https://leetcode.com/problems/fi ... ood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

好了，我终于升级到可以发表回复了_(:3⌒ﾞ)_
leetcode上有原题哦，最后在面试官的提示下，得到的解法是：
space要求达到O(1)，完全不能使用extra space，那么就要考虑用原有的input array记录新的信息。记录的方式是：
假设input = {1, 3, 2, 3}, 遍历到第一个3的时候，去到index=2位置上的数字，把它改成对应的负数，即把2变成-2，然后再往下走，碰到第二个3的时候，再去check index = 2位置上的数字，如果是负数，就说明我已经看到过3了，3就是找到的duplicate。
这样记录的方式，即保留了原有index位上的数值，又用负号来表示是否已经见过对应的数字

这是 利口 而八旗