PLS帮助带面试问题!! [英] PLS HELP w/ Interview Question!!
问题描述
我一直在寻找一份工作，现在已经两次碰到这个
的面试问题了...并且愚蠢地将它吹了两次...
（虽然我已经变得更好了）...时间终于把这件事搞清楚了......
基本上面试的问题是：给出一个未分类的列表如：
3,1,3,7,1,2,4,4,3
找到FIRST UNIQUE号码，在这种情况下7 ...当然列表可以
数百万...
我第一次得到这个问题，我的解决方案是类似于：
1）声明第二个数组A2，其中包含n个元素
2）循环遍历原始数组A1并将元素插入其已排序的
在A2中的位置，如果我发现匹配消除，则将该元素的所有副本标记为
为重复
3）循环通过原始数组A1再次找到第一个数字是
未在A2中列为副本
我认为在那次访谈时，我指出这不是一个非常好的b $ b好算法，因为它会像O（2 *（n ^ 2）），但它会得到
完成了工作（我确实得到了那份工作，但愚蠢地把它变成了
下来）......
我然后在那次采访中提出了另一种解决方案，我认为这更好：
更好：
1）建立一个A1的副本，它具有每个元素的原始位置
2）排序A1
3）循环排序A1删除任何重复项目
4）现在A1只包含唯一的项目......所以循环再看它
为步骤1中标记的最小位置
这是我在面试＃2中开始的那种算法（我确实想要，但是没有得到）......因为面试官要我给他那个算法的运行时间，我说的是：
步骤＃1：n
步骤＃2：n log n
步骤＃3：n
步骤＃4：n
导致3n + n log n ...
这比原算法好很多，但仍然不太好
因为3n术语...
昨天我从排名第二的位置得到了我的拒绝，所以我有点想起来如何让它更快......
我想出了这样的东西：
1）循环通过A1构建一个自定义的AVL树...一个AVL树插入
是O（log n），所以构建这棵树应该花费O（n log n）..定制的
部分是......插入的每个节点都会带来它在
$ b $中的原始位置b array（0..n）...如果我遇到一个重复的节点，我会将树中已经存在的节点的位置标记为-1。并转储节点我正在尝试
插入
所以基本上我花了O（n log n）来组合步骤1,2 &安培;我的上一个
解决方案中的3个...基本上将2n + n log n降低到O（n log n）...
2）但是现在我需要访问树中的每个节点，找出哪一个具有最低位置，即O（n）明显忽略我标记为
为-1的任何节点。
所以最后优化了我昨晚想出的解决方案仍然需要O（n + n log n）。
有没有办法进一步优化？还是一个更好的算法所有
在一起？我想也许是为了跟踪第一个独特的节点，因为我要创建树吗？但是我无法确定一个可行的想法...
我有点隐瞒树上有一个名为m_nPos的成员初始化
到0 ......并且正在构建树，如果我在
m_nPos中找到一个重复元素，则递增它。所以基本上我插入元素0，然后稍后，我
找到它的副本，所以第一个唯一的项目不可能是零，
它有至少在第1位。但是当我做了几个测试用例时，我很容易在这个想法中挖洞。
有什么想法吗？
I''ve been looking for a job for a while now, and have run into this
interview question twice now... and have stupidly kind of blown it twice...
(although I''ve gotten better)... time to finally figure this thing out...
basically the interview question is: given an unsorted listed such as:
3,1,3,7,1,2,4,4,3
find the FIRST UNIQUE number, in this case 7... and of course the list can
be millions long...
the first time I got this question, my solution was something like:
1) declare a second array A2 with n elements
2) loop through original array A1 and insert the element in its sorted
position in A2, if I find a match eliminate, mark all copies of that element
as "duplicate"
3) loop through original array A1 again and find the first number that is
not listed as a duplicate in A2
I think at the time of that interview, I pointed out that this wasnt a very
good algorithm as it would be something like O(2*(n^2)), but it will get the
job done (I did get offered that job actually, but stupidly turned it
down)...
I then offered up another solution at that interview which I thought was
better:
1) build a copy of A1 that has the original position of each element
2) sort A1
3) loop through sorted A1 deleting any duplicate items
4) now A1 will only contain unique items... so loop through it again looking
for the smallest position that was marked in step 1
this was kind of the algorithm I started out with in interview #2 (which I
really wanted, but didnt get)...as the interviewer asked me to give him the
run time of that algorithm which I said was:
step #1: n
step #2: n log n
step #3: n
step #4: n
resulting in 3n + n log n...
this was a lot better then the original algorithm, but still not too great
because of the 3n term...
I got my rejection from the 2nd place yesterday, so I kind of was up all
night trying to figure out how to get it faster...
I came up with something like this:
1) loop through A1 building a customized AVL tree... an AVL tree insertion
is O(log n), so building this tree should take O(n log n).. the customized
part is... each node inserted will bring along its original position in the
array (0..n)... if I run across a duplicate node, I will mark the position
of the node thats already in the tree as "-1" and dump the node I''m trying
to insert
so basically I''ve spent O(n log n) to combine steps 1, 2 & 3 of my last
solution... basically taking 2n + n log n down to O(n log n)...
2) but now I need to visit every node in the tree to find out which one has
the lowest position which is O(n) obviously ignoring any nodes I marked
as -1.
so this final "optimized" solution I came up with last night would still
require O(n + n log n).
Is there any way to optimize this further? or a better algorithm all
together? I''m thinking perhaps to keep track of the first unique node as I''m
creating the tree? but I couldn''t nail down an idea that would work...
I''m sort of invisioning the tree having a member called m_nPos initialized
to 0... and as I''m building the tree, if I find a duplicate element at
m_nPos, to increment it. So basically I insert element 0, then later on, I
find a duplicate for it, so the first unique item can''t possibly be at zero,
it has to be at least at position 1. But then as I did a few test cases, I
poke holes in this idea very easily.
Any ideas?
推荐答案
基本上面试的问题是：给出一个未分类的列出如下：
3,1,3,7,1,2,4,4,3
basically the interview question is: given an unsorted listed such as:
3,1,3,7,1,2,4,4,3
还有其他限制吗？
Where there any other constraints?
< ha ********** @ gmail.comwrote in消息
news：11 ********************** @ m73g2000cwd.googlegr oups.com ...
<ha**********@gmail.comwrote in message
news:11**********************@m73g2000cwd.googlegr oups.com...
>
>
>基本上面试的问题是：给出一个未分类的列表如：
3,1,3,7,1,2,4,4,3
>basically the interview question is: given an unsorted listed such as:
3,1,3,7,1,2,4,4,3
哪里有其他限制？
Where there any other constraints?
不，只要给出一个n个未编号的列表（n可能是数百万），找到
第一个唯一号码。显然你不能使用内置的
" FindFirstUnique（）"数字功能，练习是写了
功能。我认为使用数据库可能会有一些技巧，但
认为数据库的开销会导致
算法中的任何性能提升。
显然关键是要在最短的时间内找到第一个唯一的数字
...我在原帖中描述的算法是O（n + n log
n）...我想知道它是否可以更快完成。
Nope, just given an unsorted list of n numbers (n could be millions), find
the first unique number. Obviously you can''t use a built in
"FindFirstUnique()" number function, the exercise was to write that
function. I thought there may be some tricks with using a database, but
thought the overhead of the database would kill any performance gains in the
algorithm.
Obviously the point is to find the first unique number in the shortest time
possible... the algorithm I described in the original post was O (n + n log
n)... I''m wondering if it can be done faster.
不知道解决这个问题。 AVL树对我来说还不清楚，但是b / b $ b b暴力解决方案很简单，虽然很耗时
No idea for solving that. The AVL tree is unclear for me, but a
brute-force solution is simple, though time-consuming
这篇关于PLS帮助带面试问题!!的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
