访谈中的问题，从字典中检索字母顺序[已关闭

StackOverflow https://stackoverflow.com/questions/3123554

题

我的女友在一次采访中得到了这个问题，我非常喜欢它，我以为我会分享的...编写一种接收词典（单词数组）的算法。阵列在词典上是分类的，但是ABC顺序可以是任何东西。例如，可以是z，y，x，..，c，b，a。或者它可能会完全混乱：d，g，w，y，...甚至不需要包含所有ABC字母，最后根本不必是字母。它可能是形成字符串的任何符号。例如，它可以由5，α，！， @，θ...组成。您明白了。要发现字母是什么（简单的部分）取决于您的算法。

该算法应返回符号的正确词典顺序。

注意/要考虑的事情：1。对于给定的词典，您能始终发现所有字母的完整顺序吗？考虑一个只有1个字的字典，具有超过1个符号... 2.您不能假设字典没有错误。该算法应确定字典是否包含矛盾和输出是否存在错误。 3.提示：考虑一个良好的数据结构，以表示您在符号之间发现的关系。这应该使问题更容易。

我可能明天发布我的解决方案。我绝不声称这是最有效的。我想首先看到别人的想法。希望你喜欢这个问题

PS我认为发布解决方案的最佳格式是使用伪代码，但我将其留给您考虑

有帮助吗？

解决方案

这是 拓扑排序 在 定向无环图. 。您需要首先构建图形：顶点是字母，如果一个字母在词典上比另一个词汇少。然后，拓扑顺序为您提供答案。

一个矛盾是指向图不是无环的。唯一性取决于是否存在哈密顿路径，这是在多项式时间内可检验的。

构建图

您可以通过比较字典中的每两个连续的“单词”来做到这一点。假设您有这两个单词接一个地出现：

x156@
x1$#2z

然后，您找到最长的常见前缀， x1 在这种情况下，并在此前缀之后检查立即关注字符。在这种情况下，我们有 5 和 $. 。由于字典中以此顺序出现单词，我们可以确定 5 必须在词典上小于 $.

同样，给定以下单词（字典中一个接一个地出现）

jhdsgf
19846
19846adlk

我们可以说 'j' < '1' 从第一对（最长的常见前缀是空字符串）。第二对没有告诉我们任何有用的东西（因为一个是另一个的前缀，因此没有字符可以比较）。

现在假设稍后我们看到以下内容：

oi1019823
oij(*#@&$

然后我们发现了一个矛盾，因为这对说 '1' < 'j'.

拓扑排序

有两种传统方法可以进行拓扑分类。算法更简单是 深度优先搜索 方法，那里有优势 x 到 y 如果 y < x.

算法的伪代码在Wikipedia中给出：

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no incoming edges

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)

在上述算法结束后，列表 L 将按拓扑顺序包含顶点。

检查独特性

以下是维基百科的报价：

如果拓扑排序具有分类顺序中所有连续顶点的属性，则通过边缘连接，则这些边缘在DAG中形成一个定向的汉密尔顿路径。如果存在哈密顿路径，则拓扑排序秩序是独一无二的。没有其他秩序尊重路径的边缘。相反，如果拓扑排序不形成哈密顿路径，则DAG将具有两个或更多有效的拓扑订购，因为在这种情况下，可以通过交换两个未通过边缘连接的连续连接的两个连续的顶点来形成第二个有效订购对彼此。因此，是否可以在多项式时间内测试是否存在独特的顺序，以及是否存在哈密顿路径。

因此，要检查订单是否唯一，您只需检查所有两个连续的顶点是否在 L （从上述算法）通过直接边缘连接。如果是，那么订单是唯一的。

复杂性分析

一旦构建图，拓扑排序是 O(|V|+|E|). 。独特检查是 O(|V| edgeTest), ， 在哪里 edgeTest 测试是否通过边缘连接两个顶点的复杂性。带着 邻接矩阵, ， 这是 O(1).

构建图仅需要单词的单个线性扫描。如果有 W 话，那是 O(W cmp), ， 在哪里 cmp 是比较两个词的复杂性。您始终比较两个后续单词，因此您可以在必要时进行各种优化，但否则，幼稚的比较是 O(L) 在哪里 L 是单词的长度。

一旦确定您对字母表等有足够的信息，您也可以将词典读取词典，但即使是天真的建筑步骤也会采取 O(WL), ，这是字典的大小。

其他提示

您想找到符号的总顺序。

1）您显然不能总是确定总订单。

2）您可以使用定向的无环图表示符号之间的部分顺序。每个字母在图中仅表示一次。您可以通过在每对连续单词中查看相同位置的所有字母来填充它。您在图形中创建的任何循环指向字典中的错误。您将一组关系（如A-> d，a-> b，b-> d）成a-> b-> d。如果您最终获得的是一个带有一个源的图形（没有前身的字母）和一个接收器（没有继任者的字母），则您的总订单，例如字母。

我使用Wikipedia中的其他建议算法解决了这一点。这是Wikipedia的psuedocode：

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

我认为它提供了一种更“常识”的方法来找到一条路径（即，如果我要查看图形并必须找到路径，我将如何解决）。尽管如此，它对多弹药剂建议的深度优先方法没有任何优势（如果您添加了评论中建议的周期检测代码），感谢您的评论。答案

您的字典用一系列的单词使用，我建议使用此数据结构，因为它足够好，转换需要时间。

您想找到正确的字符顺序

C1，C2，C3，C4，...，CN

您的字典中有m数量。拥有一组规则，例如（CI，CJ），这将是很棒的，这意味着Ci <= CJ，其中I，J是正常数，并且I <m，j <m。我们应该有一组错误

因为V是一个巨大的数字，并且大于M * m，因此我认为的一种好方法是以下内容：

foreach i = 1, m do
    foreach j = i + 1, m do
        findFirstDifferenceInTheWords
        /*charI is the first difference in Wi from Wj and charJ is the first difference in 
          Wj*/
        if (Wi <> Wj)
            if (Wi contains Wj or Wj contains Wi) == false
            charSet.add(charI, charJ)
        else if k exists and the following is true ((i < k < j) and (Wi <> Wk))
            error.addIfDoesntExist("paradox", Wi)
        else
            error.addIfDoesntExist("redundant", Wi)
        end_if
    end_foreach
end_foreach

我们发现了l规则数量

foreach i = 1，l do foreach j = i + 1，l如果charset。

此后，您可以通过考虑Chari = Charj既是（Chari，Charj）和（Charj，Chari）来构建单词顺序那个chari <charj。

结论：使用“ <=”关系比使用“ <”关系更好，因为“ <=”是数字理论中的完整和良好的有序关系，<“只是好排序。注意：如果Chari <charj或chari = charj，则输出必须正确显示。例如，您可以使用以下符号：字符（C1C2C3，C4，C5C6，...）其中C1 = C2 = C3 = C3 <C4 <C5 = C5 = C6 ...

我希望这有帮助。

当然，如果WJ包含Wi，那么我们将无法从那里提取规则

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top