Python interview with a FAANG engineer: Max people alive

[programmingpassion]

Sound is very bad indeed, you need to improve sound quality.

[CyboreoTwinkie]

Awesome content and both the interviewee and interviewer did a great job. I think another approach with no death date is just to assume it's infinity, so the original code wouldn't change much. Also, I don't think it matters if the death is ordered before birth year if they're in the same year since it will be processed anyways soon or later.

Here is my take:
def get_year_max_alive(self, persons: List[Dict[str, Union[str, int]]]) -> Union[int, None]:
"""
Complexity: O(N*logN) time and O(N) space
"""
if len(persons) == 0:
return None

# Convert birth and death to events and sort by year. Birth is +1 and death is -1
events = []
for person in persons:
heapq.heappush(events, (person['birth'], 1))
heapq.heappush(events, (person.get('death', float('inf')), -1))

# Tracking
current_alive = 0
max_alive = 0
max_year = None

# Pop heap and track those values
while events:
year, count = heapq.heappop(events)

# Optimization: if we hit float('inf'), then no need to go further.
if year == float('inf'):
break

current_alive += count
if max_alive < current_alive:
max_alive = current_alive
max_year = year

return max_year