科技面试问题-我的方法正确吗？

Question

最近我接受了一家软件公司的采访。我没能挺过第一轮。

也许我在形成想法或解决问题方面太慢了，而且对我面试的公司来说也不够好。我想对我的面试有第二种看法，我找不到比堆叠式社区更好的人了。

所以这次采访是个基本的采访

1. Introduction
2. Why你申请了这个职位吗？
3. One Techincal问题(详见下文)
4. 你使用过的最糟糕的软件是什么？为什么？改进
5. 您使用过的最佳软件是什么？为什么要改进？

原始技术问题(如面试官所问)

给定一定范围的数字M.M+N-1 i构造一个大小为N的数组，并将该数组中的一个元素替换为一个数字。您将如何找到被替换的元素？

我让他再重复一遍问题，因为我认为输入不足以解决问题。他重复了这句话

问:然后我问他，你从数列中得到的数组是按顺序排列的吗？

面试官:没有必要

在替换元素之前，我们知道数组吗？

面试官:不

然后，我开始写一些伪代码(同时做大量的思考)。我立即意识到，如果原始数组有重复的话，它就不能工作。所以我一直在思考如何解决this.Then问题，最后我问了一些重要的问题

问:如何从范围中选择元素来形成数组？

面试官:我的号码是M，M+1，M+2.M+N1.一个数字只选一次。我形成一个N大小的数组(这实际上意味着没有重复，范围内的所有元素都会被选择)。

你用的号码是多少？它在同一范围内吗？

面试官:是的。

然后一切都清楚了

，这就是他的意思：

Q有一系列从M开始的数字，如M，M+1，M+2，M+3...M+N。我形成一个大小为N的数组，这样每个元素只被选择一次，而原始数组没有任何重复。我将数组中的一个元素替换为相同范围内的一个数字。找出我从靶场里选了什么来替换？

这相当于在数组中查找重复项。在这里，在替换后，只有一对重复，我们可以很容易地找到在O(N^2)时间或O(nlogn)时间。我给了他两种算法。

最后，我忍不住问他：“我在这个问题上表现如何？”他说，“你花了很多时间回答这个问题。”

显然，他对我处理这个问题的方式并不满意。

，你认为我在回答这个问题时应该做些什么？

Answer 1

这是一个经典的采访“谜语”。实际上，在O(n)中使用所描述的技巧解决这个问题是相当容易的。

我们在数据结构1中教授的一件事是，当您的领域受到限制时，可能可以将其用于比O(nlogn)更好的函数--显然，在没有任何额外知识的情况下对域进行排序不能少于这一点。因此，当你知道你的领域-一个小小的红色灯泡应该打开在你的头脑某处:-)

我认为你应该立即指出关于复制件的问题。这将清楚地表明，这个问题没有很好的表述。否则，他只是认为你很慢(尽管这实际上是他的错.)。

我也认为问题4,5是很好的问题。它们展示了申请人的经历，以及申请人的想法。所以你可能因为你在面试中说过的话而没能通过面试。

Answer 2

如果我得到正确的问题，你可以在O(n)时间内解决这个问题。

1. 使用大小为N
2. 的“散列”找到两个相同的元素，其中一个设置为0。
3. 对元素进行和，并从计算的和中减去元素(元素之和为(2m+N1)*(N)/2

)。

编辑：

对1. point的解释(使用大小为N的“散列”找到两个相同的元素)

如果您不知道M是否找到它(找到最小的元素为O(n)，只需一个大小为N的loop)

• Alocate数组h，并将元素设置为0(可以输入BOOL )

• 转到低谷表，并在h

• 附近的适当位置检查1，如果是1，则进行分叉，否则设置为1.

。

最后一部分的代码：

for(i=0;i<N;i++)
{
    if(h[a[i]-M] == 1) return i;
    h[a[i]-M] == 1;
}

Answer 3

由于不对允许使用的内存量指定限制，所以有一个O(N)解决方案:将大小为N的数组初始化为全为零。查看列表中的每个元素b，标记Ab = 1，然后走A，如果Ac == 0返回c。