How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Walmart Labs.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Walmart Labs during technical interviews.

Compute maximum simultaneous bus routes | Walmart Labs Coding Question

Quick Overview

This question evaluates algorithmic proficiency with interval overlap counting and concurrent event aggregation, emphasizing correctness reasoning and time/space complexity analysis. It falls under the Coding & Algorithms domain and is commonly asked to assess practical algorithm implementation and complexity-analysis skills rather than purely conceptual understanding.

Compute maximum simultaneous bus routes

Company: Walmart Labs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given N bus routes, each defined by a start time (inclusive) and an end time (exclusive). Compute the maximum number of routes running simultaneously. Clarify your algorithm, justify correctness, and analyze time and space complexity.

Quick Answer: This question evaluates algorithmic proficiency with interval overlap counting and concurrent event aggregation, emphasizing correctness reasoning and time/space complexity analysis. It falls under the Coding & Algorithms domain and is commonly asked to assess practical algorithm implementation and complexity-analysis skills rather than purely conceptual understanding.

You are given a list of bus routes, where each route is represented by a pair (start, end). A route is active from its start time inclusive to its end time exclusive, meaning it covers the interval [start, end). Compute the maximum number of routes running at the same time. Because the input can be large, your solution should be more efficient than checking every pair of routes. If the list is empty, return 0. Important: since end times are exclusive, a route ending at time t does not overlap with a route starting at time t.

Constraints

0 <= len(routes) <= 200000
0 <= start < end <= 1000000000
All start and end values are integers

Examples

Input: []

Expected Output: 0

Explanation: There are no routes, so the maximum number running at the same time is 0.

Input: [(10, 20)]

Expected Output: 1

Explanation: A single route is active by itself, so the maximum overlap is 1.

Input: [(1, 3), (3, 5), (5, 8)]

Expected Output: 1

Explanation: Each route starts exactly when the previous one ends. Because end times are exclusive, they do not overlap.

Input: [(1, 5), (2, 6), (4, 8), (5, 7)]

Expected Output: 3

Explanation: From time 4 to 5, the first three routes overlap. At time 5, the first route ends before the fourth begins, so the maximum remains 3.

Input: [(0, 10), (0, 10), (0, 10), (5, 6)]

Expected Output: 4

Explanation: All three long routes are active when the short route runs from 5 to 6, giving a maximum overlap of 4.

Solution

def solution(routes):
    if not routes:
        return 0

    starts = sorted(start for start, end in routes)
    ends = sorted(end for start, end in routes)

    n = len(routes)
    i = 0
    j = 0
    active = 0
    best = 0

    while i < n and j < n:
        if starts[i] < ends[j]:
            active += 1
            if active > best:
                best = active
            i += 1
        else:
            active -= 1
            j += 1

    return best

Time complexity: O(n log n). Space complexity: O(n).

Hints

Instead of comparing every pair of routes, sort all start times and end times separately and scan through them with two pointers.
Since end times are exclusive, if a start time equals an end time, process the ending route first.

Quick Overview