求职面试算法? [英] Job Interview Algorithm?

问题描述

更新:可以请原谅我对n的最后评论.代词"米的答案?

请注意:我之前曾问过这个问题，但这完全是一团糟，因此我将以原始格式编写更多细节.

Please Note: I have asked this before but it was a complete mess so I am writing it with more details and in the original form.

问题:

我正在管理N位参与者(从1到N的每个索引)之间的投票系统，在这里我要支持以下功能:

I am managing a vote system between N participants (Each one indexed from 1 to N) where I want to support the following functions:

1. Init(N)-初始化数据结构.-O(1)
2. 投票(j，i)-将j投票给i的人(准确为1)添加到结果表中-不允许某人对自己进行投票.-O(1)
3. 投票人数(i)-返回投票给i的人数.-O(1)
4. 来源(j)-返回人物j给予他人的票数.-O(1)
5. 最喜欢的(k)-根据获得的票数打印出排名靠前的参与者(降序排列).-O(k)
6. Avoided()-打印未获得任何投票的所有参与者.-O(r)，其中r是打印的参与者的数量

在此问题中，空间复杂度应为 O(N).

仅允许使用数组和(双重)链表.

我做了什么?我只需声明一个大小为N的数组，每个单元格都包含值，就很容易地解决了1-4. got 和 sent .当 i 投票给 j 时，我增加了 j 的价值，并发送了 i 的价值.

What I did? I solved 1-4 so easily simply by declaring an array whose size is N and each cell contains to values; got and sent. when i votes to j I increase got value for j and sent value for i by one.

我仍然不知道如何以所需的复杂度求解5和6.

Still I have no idea on how to solve 5 and 6 in the required complexity.

注意:我在寻找算法/想法，而不是实际的代码.

Note: I'm looking for the algorithm/idea rather than an actual code.

推荐答案

请注意，对于每个操作，被投票支持的候选人的得分都会增加一个.

Note that the for each operation, the candidate that got voted for increased their score by exactly one.

这开启了一种新策略-与其将候选人映射到其分数，不将其映射到具有该分数的候选人列表.

This opens a new strategy - rather than mapping a candidate to its score, map a score to the list of candidates with this score.

这可以很简单地实现为候选列表:(在类似语法的模板中: list< list< Candidate>> ).

This can be implemented quite simply as a list of lists candidates: (in template like syntax: list<list<Candidate>>).

此外，保留一个将每个候选编号映射到实际 Candidate 元素的指针的数组.

In addition, keep an array mapping each candidate number, to the pointer of the actual Candidate element.

最初为

投票时:

1. 您可以从参考文献中找到候选人:O(1)
2. 您将其从当前列表中删除，并将其添加到下一个列表:O(1)
3. 要在 O(r)中支持 Avoided():如果"0"中的元素数为列表小于一半，请将其更改为常规列表.
4. 如果表示分数的上一个元素现在没有候选者，则将其删除，然后将先前的分数直接链接到下一个(例如，如果没有分数为3的候选者，则连接 2 -4)
code>)由于没有太多的空列表节点，因此可以确保 O(n)空间.

1. You find the candidate from the reference: O(1)
2. You remove it from its current list, and add it to the next list: O(1)
3. To support Avoided() in O(r): If the number of elements in the "0" list is smaller than half, change it to be a regular list instead.
4. If the previous element representing a score now has no candidates, drop it, and link the previous score to the next one directly, (i.e. if no candidate with score 3, connect 2<->4) This ensures O(n) space due to not too much empty list nodes.

• 获取topK现在很容易，并且可以通过从头到尾迭代得分列表(在输出 k 个候选者之后停止)，在 O(k)中完成
如果避免了一半以上的候选者，则
• Avoided现在为 O(n)= O(r)，否则为 O(r)，否则要进行优化(3)插入.
• Getting topK is now easy and done in O(k) by iterating the scores list from end to start (stopping after outputting k candidates)
• Avoided is now O(n) = O(r) if more than half the candidates were avoided, or O(r) otherwise thanks to optimization (3) in insertion.

这篇关于求职面试算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！