给定入口和出口日志，查找人口最大值。

Question

我在一次面试中遇到了这个问题。我用Python解决了这个问题。想要得到反馈，看看我如何改进我的面试反应。

在购物中心最繁忙的时候，韦斯特菲尔德购物中心的管理层正试图弄清楚，去年购物中心最繁忙的时刻是什么。从商场的门探测器中提取的数据。每个数据点都表示为一个整数数组，其大小为3。索引0、1和2的值分别为时间戳、访问者计数以及访问者是否进入或退出购物中心(出口为0，入口为1)。下面是一个数据点的示例：1440084737，4，0。请注意，时间是以称为Epoch的Unix格式给出的，它是一个非负整数，包含自1970年1月1日星期四世界协调时间00:00:00以来所经过的秒数。给定一个数组、数据和数据点，编写一个函数findBusiestPeriod，返回去年购物中心达到最繁忙时刻的时间。返回值是时间戳，例如1480640292。请注意，如果有多个周期与相同的访客高峰，返回最早的一个。假设数组数据按时间戳按升序排序。

"""
input:  data = [ [1487799425, 14, 1], 
                 [1487799425, 4,  0],
                 [1487799425, 2,  0],
                 [1487800378, 10, 1],
                 [1487801478, 18, 0],
                 [1487801478, 18, 1],
                 [1487901013, 1,  0],
                 [1487901211, 7,  1],
                 [1487901211, 7,  0] ]

output: 1487800378 # since the increase in the number of people
                   # in the mall is the

"""  

def find_busiest_period(data):

  people = 0 
  max_time = 0
  max_people = 0
  for i in range(len(data)):

    if data[i][2] == 1:
      people += data[i][1]
    else:
      people -= data[i][1]

    if (i < len(data)-1 and data[i][0] == data[i+1][0]):
      continue

    if people > max_people:
      max_people = people
      max_time = data[i][0]
  return max_time 




data = [ [1487799425, 14, 1], 
                 [1487799425, 4,  0],
                 [1487799425, 2,  0],
                 [1487800378, 10, 1],
                 [1487801478, 18, 0],
                 [1487801478, 18, 1],
                 [1487901013, 1,  0],
                 [1487901211, 7,  1],
                 [1487901211, 7,  0] ]



test = find_busiest_period(data)
print(test)

Answer 1

算法

我不明白在这里比较下一个数据的时间戳的目的：

如果(i < len(data)-1和data我 == datai+1)：继续

这两个事件是在同一秒钟内发生的，但假设它们是有序的是合理的，因此我们应该考虑在这一秒内的总数，除非问题语句不这么说。

没有这个约束，我们就不需要索引i，并且可以只考虑输入数据的成员；我们可以给元素取有意义的名称：

  for time,quantity,direction in data:

现在，我们知道当人们退出时，我们不会找到一个新的最大值(假设我们没有给出负数)，所以我们可以将测试移到+=分支中：

    if direction == 1:
      # Some people entered
      people += quantity
      # Have we reached a new maximum?
      if people > max_people:
        max_time, max_people = time, people
    elif direction == 0:
      # Some people left
      people -= quantity
    else:
      raise ValueError(direction)

总评

• PEP8建议每个缩进级别有四个空格。
• 这个文档-评论既不完整，也不正确：“”输出: 1487800378 #因为商场中人数的增加#是“”。
• doc-注释在错误的位置(应该在函数体内)。
• 我们应该用main警卫。
• 考虑使用doctest提供更多的测试用例。

改进的代码

def find_busiest_period(data):
    """
    Find the timestamp when the greatest number of people
    are in the building.

    >>> find_busiest_period([]) is None
    True

    >>> find_busiest_period([ [0, 0, 2] ])
    Traceback (most recent call last):
        ...
    ValueError: 2

    >>> find_busiest_period([ [0, -5, 0] ])
    Traceback (most recent call last):
        ...
    ValueError: -5

    >>> find_busiest_period([ [0, 5, 1], [2, 5, 1], [3, 5, 0] ])
    2

    >>> find_busiest_period([ [1487799425, 14, 1], \
                              [1487799425, 4,  0], \
                              [1487799425, 2,  0], \
                              [1487800378, 10, 1], \
                              [1487801478, 18, 0], \
                              [1487801478, 18, 1], \
                              [1487901013, 1,  0], \
                              [1487901211, 7,  1], \
                              [1487901211, 7,  0] ])
    1487901211
    """  
    people = 0 
    max_time = None
    max_people = 0

    for time,quantity,direction in data:
        if quantity < 0:
            raise ValueError(quantity)
        if direction == 1:
            # Some people entered
            people += quantity
            # Have we reached a new maximum?
            if people > max_people:
                max_time, max_people = time, people
        elif direction == 0:
            # Some people left
            people -= quantity
        else:
            raise ValueError(direction)

    return max_time 


if __name__ == "__main__":
    import doctest
    doctest.testmod()

Answer 2

托比在他的评论中提到了许多优秀的观点。我不会在这里重复。我要做的是掩盖算法的组成。你正试图在一个函数中完成所有的事情。通常更好的做法是将算法分解成几个步骤，并将各个部分链接在一起。

首先是原始数据流(列表)，其中包含时间、人员数量和移动方向。您可以创建一个“生成器表达式”，该表达式可以将人员数量和他们移动的方向转化为总人数的递增变化。

deltas = ((time, quantity if enter else -quantity) for time, quantity, enter in data)

上面的生成器表达式将从列表中获取每一行数据，分别调用各个片段time、quantity和enter标志。然后，它将quantity和enter标志转换为正的数量，对于进入的人来说，或者对离开的人来说是负数。它产生一组元组，包含时间和人数的变化。Ie，print(list(deltas))将产生：

[(1487799425, 14), (1487799425, -4), (1487799425, -2), (1487800378, 10), (1487801478, -18), (1487801478, 18), (1487901013, -1), (1487901211, 7), (1487901211, -7)]

我们可以把这个流输入到另一个发生器中，它积累了人数上的变化。这一次，我将使用生成器函数，因为population是一个状态量，需要从一个样本持续到另一个样本：

def population_over_time(deltas):
    population = 0
    for time, delta in deltas:
        population += delta
        yield time, population

这将把时间和三角洲的列表转化为时间和人口的列表。Ie) print(list(population_over_time(deltas)))将产生：

[(1487799425, 14), (1487799425, 10), (1487799425, 8), (1487800378, 18), (1487801478, 0), (1487801478, 18), (1487901013, 17), (1487901211, 24), (1487901211, 17)]

从这个元组流中，max()函数可以很容易地返回对应于最大总体的第一个元组。我们需要使用operator.itemgetter(1)从元组中提取总体值，并将其用作键：

peak = max(population_over_time(deltas), key=operator.itemgetter(1))

这将将(1487901211, 24)分配给peak。因为我们只想要最大人口的时间，所以我们可以return peak[0]。

把这些片段拼凑起来，再重新组织一下，我们就可以得到：

from operator import itemgetter

def population_deltas(data):
    return ((time, quantity if enter else -quantity) for time, quantity, enter in data)

def population_over_time(data):
    population = 0
    for time, delta in population_deltas(data):
        population += delta
        yield time, population

def find_busiest_period(data):
   return max(population_over_time(data), key=itemgetter(1))[0]

除了最繁忙的时段之外，如果您想要绘制该信息，您还可以使用一个函数来生成随时间变化的人口。与编写许多函数来从头到尾处理数据不同，您有一些很小的代码，这些代码可以根据需要组装以生成所需的产品，并且可以根据需要以不同的方式组合以生成其他数据。

上述办法的一个重要方面值得一提:没有编制清单。population_deltas和population_over_time是生成器，每次产生一个值。max()函数向population_over_time()请求一个值，该值依次向population_deltas()请求一个值，该值从data检索一个项。然后，max()请求下一个值，并保留最大值。然后，它要求另一个值，并保持最大，以此类推。内存需求：O(1)。