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