Python diff 两个列表的时间复杂度是多少？

Question

我在一次技术面试中被问到这个问题，我想知道我的回答是否完全错误。

面试官让我区分两个列表。这是例子

[1, 2, 3, 4], [1, 2, 3] => [4]
[1, 2, 2, 2], [1, 2] => [2, 2]
[1, 2, 2, 2], [1, 2, 3, 3] => [2, 2]


def diff_two_list(list1, list2):
  hash_map1 = {}
  for i in list1:
    hash_map1[i] = hash_map1.get(i, 0) + 1

  hash_map2 = {}
  for j in list2:
    hash_map2[j] = hash_map2.get(j, 0) + 1

  result = []
  for i in hash_map1.keys():
    if i not in hash_map2:
      for _ in range(hash_map1[i]):
        result.append(i)
    else:
      remained_value = hash_map1[i] - hash_map2[i]
      if remained_value > 0:
        for _ in range(remained_value):
          result.append(i)

  return result

我意识到这不是最好的代码。我想知道我的解决方案是否完全错误？这个解决方案的时间复杂度是多少。我想在 codereview.stackexchange.com 上问这个问题，但他们说代码必须正确才能要求审查，所以我在这个房间里问。

我回答的时间复杂度是2o(n)

Answer 1

当您面试一份工作时，面试官会寻找有关候选人的许多方面。一些例子:

• 候选人是否就问题提出了正确的问题？
• 候选人是否具备我看重的技能？
• 候选人能否思考问题并得出合理的答案？
• 候选人是否编写了可在我的团队中维护的干净代码？

面试官要求您区分两个列表，并提供了一组解决方案。我查看了数据并将其解释为左数组与右数组的位置比较，其中:

• 结果列表将包含左侧不同的值
• 当右侧位置为空时，结果列表将包含左侧的值

如果您盯着测试用例看的时间足够长，您可能会想出其他解释。

我希望最优秀的候选人能够提出有关数据集的问题或解释问题解释背后的假设和边缘案例。

• 这些示例列表出现排序，是巧合吗
• 这似乎是位置上的差异。我的理解对吗？
• 右侧总是相同大小还是更小？
• 如果右侧更大，我应该包含一个元素吗？
• 数据集的最大大小是多少？

对于像这样的简单问题，我希望最好的候选人能够编写您可以快速理解的代码，而无需花费大量精力去思考代码的作用。

我希望最佳候选人能够根据他们的假设以节省时间或空间的方式解决问题。

在这种情况下，我希望候选人会创建一个 O(n) 解决方案。

作为面试官，我会认为您的回答难以理解且效率低下。随着循环的嵌套，您的解决方案可能不是 O(n)。

我可能不会花太多时间来弄清楚您的解决方案的时间复杂度或者它是否可行。我会提出问题以确保问题相当清楚，然后继续下一个技能或合适的问题。

我会按如下方式解决问题:

test_cases = [
    [[1, 2, 3, 4], [1, 2, 3], [4]],
    [[1, 2, 2, 2], [1, 2], [2, 2]],
    [[1, 2, 2, 2], [1, 2, 3, 3], [2, 2]]
]


def left_diff_array(left, right):
    smallest_length = min(len(left), len(right))
    differences = []

    for x in range(1, smallest_length):
        if left[x] != right[x]:
            differences.append(left[x])

    if len(left) > len(right):
        differences += left[len(right):]

    return differences


for test in test_cases:
    first, second, answer = test

    assert(left_diff_array(first, second) == answer)
    print first, second, "=>", answer