Given entrance and exit logs, find the population maximum

Question

I was given this problem during an interview. And I solved it using Python. Would like to get feedback to see how I can improve my interview response.

Busiest Time in The Mall

The Westfield Mall management is trying to figure out what the busiest moment at the mall was last year. You’re given data extracted from the mall’s door detectors. Each data point is represented as an integer array whose size is 3. The values at indices 0, 1 and 2 are the timestamp, the count of visitors, and whether the visitors entered or exited the mall (0 for exit and 1 for entrance), respectively. Here’s an example of a data point: [ 1440084737, 4, 0 ].

Note that time is given in a Unix format called Epoch, which is a nonnegative integer holding the number of seconds that have elapsed since 00:00:00 UTC, Thursday, 1 January 1970.

Given an array, data, of data points, write a function findBusiestPeriod that returns the time at which the mall reached its busiest moment last year. The return value is the timestamp, e.g. 1480640292. Note that if there is more than one period with the same visitor peak, return the earliest one.

Assume that the array data is sorted in an ascending order by the timestamp.

"""
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

Algorithm

I don't understand the purpose of comparing the timestamp of the next datum here:

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

The two events happened during the same second, but it's reasonable to assume that they are ordered, and therefore we should consider the total within that single second, unless the problem statement says otherwise.

Without that constraint, we have no need for the index i, and can consider just the members of the input data; we can give the elements meaningful names:

  for time,quantity,direction in data:

Now, we know we won't find a new maximum when people are exiting (assuming we're not given negative numbers of people), so we can move the test into the += branch:

    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)

General review

• PEP8 recommends four spaces per indent level.

• This doc-comment is both incomplete and incorrect:

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

• The doc-comment is in the wrong place (it should be just within the function body).

• We should use a main guard.

• Consider using doctest to provide more test cases.

---

Improved code

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

Toby has covered many excellent points in his review. I won't repeat them here. What I will do is cover composition of the algorithm. You are trying to do everything in one function. It is often better to break the algorithm down into steps, and chain the individual pieces together.

You start off with a stream (list) of raw data, containing the time, quantity of people, and direction they are moving. You can create a "generator expression" which can turn the quantity of people and direction they are moving into a incremental change in the total number of people.

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

The above generator expression will take each row of data from the list, calling the individual pieces time, quantity and the enter flag respectively. It then converts quantity and enter flag into a positive quantity, for people entering, or a negative quantity, for people leaving. It produces a stream of tuples containing the time and the change in the number of people. Ie, print(list(deltas)) would produce:

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

We can feed this stream into another generator which accumulates the change in number of people. This time, I'll use a generator function, since population is a state quantity that needs to persist from sample to sample:

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

This would turn the list of times and deltas into a list of times and populations. Ie) print(list(population_over_time(deltas))) would produce:

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

From this stream of tuples, the max() function can easily return the first tuple corresponding to the maximum population. We'll need to use operator.itemgetter(1) to extract the population value from the tuple to use as the key:

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

This will assign (1487901211, 24) to peak. Since we just want the time of the maximum population, we can return peak[0].

Putting the pieces together, and reorganizing a bit, we can get:

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]

In addition to the busiest period, you also have a function to produce the population over time, if you wanted to graph that information. Instead of writing many functions to process the data from start to finish, you have tiny pieces of code which can be assembled as needed to produce the desired product, and could be combined in different fashions as needed to produce other data.

An important aspect of the above approach which bears mentioning: no lists are being created. The population_deltas and population_over_time are generators, which produce one value at a time. The max() function asks population_over_time() for a value, which in turns asks population_deltas() for a value, which retrieves an item from data. Then, max() asks for the next value, and keeps the largest. Then it asks for another value and keeps the largest, and so on. Memory requirement: \$O(1)\$.