Hackbright Code Challenges

Most Active Period: Solution

Most Active Period: Solution

Problem

Most Active Period

Whiteboard

Harder

Challenge

Medium

Concepts

Logic, Loops

Download

most-active-solution.zip


You can do this by keeping track of how many people are active for any given year, and then find the start and end of that window:

active.py
def most_active(bio_data):
    """Find window of time when most authors were active."""

    # START SOLUTION

    # Make a minefield of years 1900-1999
    century = [0] * 100

    # Add 1 in every year when someone was active

    for person, start, end in bio_data:
        for year in range(start, end + 1):
            century[year - 1900] += 1

    # Find the period of time when the max number of people were active

    best = 0
    in_best = True
    best_start = 0
    best_end = 100

    for year, num_active in enumerate(century):

        if num_active > best:  # New best; start tracking it
            best = num_active
            in_best = True
            best_start = year

        elif num_active < best and in_best:  # End of best-period window
            best_end = year - 1
            in_best = False

    return best_start + 1900, best_end + 1900

This performs in O(1) time — but it does require sweeping over the lifetime of an author to mark all the years they were active. Can you find a way that reduces the amount of work? It will still be linear time, but will perform better.

Faster Solution

You can remove the loop that marks every year an author is active and instead, as you sweep over the century, keep a +/- running count of how many people are active.

active.py
def most_active_faster(bio_data):
    """Find window of time when most authors were active."""

    # Make two minefields of years 1900-1999

    starts = [0] * 100
    ends = [0] * 100

    for person, start, end in bio_data:
        starts[start - 1900] += 1
        ends[end - 1900] += 1

    best = 0
    in_best = False
    best_start = 0
    best_end = 0

    # How many people are currently active/inactive
    num_active = 0

    for year in range(100):

        num_active -= ends[year]
        num_active += starts[year]

        if num_active > best:  # New best; start tracking it
            best = num_active
            in_best = True
            best_start = year

        elif in_best and num_active < best:  # New best; start tracking it
            best_end = year
            in_best = False

    return best_start + 1900, best_end + 1900