技术面试问题 - 我的方法是否正确？

Question

最近我接受了一家软件公司的采访.我没有通过第一轮本身.

也许我在形成想法或解决问题方面太慢,对我采访的公司来说也不够好.我想对我的访谈有第二个意见,我找不到比stackoverflow社区更好的人.

所以这次采访是基本的

原始技术问题(由面试官提出)

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

我让他再次重复这个问题,因为我认为输入不足以解决问题.他重复了同样的声明

问:然后我问他是按照排序顺序从数字范围得到的数组？
采访者:没必要

问:在替换元素之前,我们是否知道数组？
采访者:没有

然后我开始写一些伪代码(同时做大声思考).我立即意识到,如果原始数组有重复,它就无法工作.所以我一会儿想着要解决这个问题.然后我终于问了一些重要的问题

问:如何从Range中选择元素来形成数组？
采访者:我有一个数字范围M,M + 1,M + 2 ...... M + N-1.一个数字只被选中一次.我形成一个大小为N的数组.(这实际上意味着没有重复项,并且范围内的所有元素都被选中)

问你用它替换它的数量怎么样？它是否在同一范围内？
采访者:是的.

然后一切都变得清晰

这就是他的意思:
QI有一系列从M开始的数字,如M,M + 1,M + 2,M + 3 ...... M + N. 我形成一个大小为N的数组,这样每个元素只被选中一次,原始数组没有任何重复.我用相同范围内的数字替换数组中的一个元素.找出我从该系列中挑选出来的产品？

这相当于在数组中查找重复项.在替换后,将只有一对副本我们可以很容易地在O(N ^ 2)时间或O(nlogn)时间内找到它.我给了他两个算法.

最后,我无法抗拒地问他"我是怎么在这个问题上表现的？他说好了你花了很多时间回答.

显然他对我对这个问题的处理方式不满意.
在回答这个问题时,您认为我应该做些什么？

Answer 1

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

编辑:

1. point的解释(使用大小为N的"hash"找到两个相同的元素)

最后一部分的代码:

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

Answer 2

这是一个经典的采访"谜语".事实上,使用所描述的技巧ralu在O(n)中很容易解决.

我们在数据结构1中教授的一件事是,当您的域有限时,可能会将其用于比O(nlogn)更好的函数[显然,在没有任何额外知识的情况下对域进行排序不能在更少的情况下完成比起那个来说].所以,当你知道自己的领域时 - 应该在你的脑海中打开一个小红灯泡:-)

我认为你应该立即指出有关重复的问题.它会清楚表明问题没有很好地形成.否则,他只是觉得你很慢(虽然这实际上是他的错...).

我也认为问题4,5是个好问题.它们显示了申请人的经历以及申请人的想法.所以你可能因为你在那里说的话而未能通过面试.

我可能会失败.我根本无法在头脑中保留一千个最好和最差的前五个名单.问我最不喜欢的食谱是什么,以及我要做些什么来改善它.我不知道,但我不确定这会告诉你我做饭有多好.再说一遍,当被问到一个主观问题,或说"我不知道最坏的情况,但这是非常糟糕的"时,没有反对说谎的规则;-) (2认同)