Can You Solve This Mind-Boggling Coding Challenge From LinkedIn? My Solution and Analysis

Yesterday I was working through the problems in the most recent LeetCode Contest (#327) and came across this beast of a problem, “Time to Cross a Bridge.”

Someone from the Leetcode comments section pointed out that this was a question from LinkedIn’s online technical screen in late 2022.

My first reaction? I probably would’ve taken ten minutes just to understand what the question is asking and how the test cases work. It’s a lot to take in and tagged as a “Hard” question!

My thought process

Upon first read, this felt a bit like a “simulation”; I have some workers, they can each take some actions given some rules, and I want to find the time for them to complete a desired task.

I need to keep track of the total time — specifically, the “time at which the last worker reaches the left bank of the river after all n boxes have been put in the new warehouse.”

One of the complex parts of this problem is the “bridge” mechanism. Only one worker can cross the bridge at a time, and the least “efficient” worker crosses the bridge first.

While one worker is crossing the bridge, workers on either side of the bridge can be picking up / setting down packages at the same time, so I’ll also need some way of tracking when each of those tasks will be complete.

We’ll need to keep track of a few things:

• The workers ready to cross the bridge.
• The workers who are currently picking up or setting a package; specifically, we want to track the time that package job is completed so the worker can be queued up to cross the bridge again.
• The time of the last bridge crossing; that’s what we return for our answer. Importantly, note that this is a monotonically increasing value. The bridge can only be used by one worker at a time!

This makes our code fairly straightforward:

1. We send the next worker across the bridge and advance our time by however long that takes.
2. We check “package” events; if completed, we add that event’s worker back to the “bridge” queue.
3. We repeat until there are no packages left.

What data structures should I use?

The data structure that immediately came to mind is a heap. A heap can tell me who the next worker to cross the bridge is; I just need to figure out what values to insert into the heap to respect the ordering rules.

❗Note that Python’s heaps are min-heaps; the first element of the heap is going to be the smallest value.❗

The “efficiency” score for a worker is the sum of the time to cross from the left to right and the time to cross from right to left. A higher score means the worker is less efficient. If there’s a tie, then the worker with the greater index is considered less efficient.

Let’s start with the easier question of how to initialize my heap. If all workers start on the left of the bridge, then for each worker, I can insert a list like:

[-efficiency score, -index]

We want the larger efficiency score and larger indices to come first, so we’ll need to negate the values.

However, what if there’s also a worker on the right side of the bridge? We know that workers on the right will always cross before workers on the left, so I can also add a value indicating which side of the bridge the worker is on:

[side of bridge, efficiency score, index]

If we want the workers on the right to cross first, we can assign “right side” to 0 and “left side” to 1.

Now, we can stitch everything together!

The code (with lots of comments)

from heapq import heappush, heappop
def solve(n, k, time):
    # n = num boxes
    # k = num workers
    # time = list of worker information

    # Which side is the worker on? Workers on the right always cross before those on the left.
    RIGHT = 0
    LEFT = 1
    waiting_bridge = [] # Workers waiting for the bridge. [[side, efficiency, worker_idx]]
    working = [] # Events of workers picking up / setting a package. [[completion_time, side, worker_idx]]
    curr_time = 0

    # initialize workers waiting for bridge
    for idx, (left_to_right, _, right_to_left, _) in enumerate(time):
        heappush(waiting_bridge, [
            LEFT,
            -(left_to_right + right_to_left), # min-heap; need to negate total
            -idx, #min-heap, negate index
            ]
        )

    pending = n # We need this to handle the last package.
    while n:
        # If there are no workers waiting for the bridge,
        # advance time to the next "package" event.
        if not waiting_bridge and curr_time < working[0][0]:
            curr_time = working[0][0]
        
        # While there are package events, and they happened before the current time, process them
        while working and curr_time >= working[0][0]:
            _, side, efficiency, idx= heappop(working)
            # add the worker back to the bridge heap
            heappush(waiting_bridge, [
                side,
                efficiency,
                -idx
            ])

        # Let the next worker on the bridge.
        side, efficiency, next_worker_idx = heappop(waiting_bridge)
        next_worker_idx *= -1
        if side == RIGHT: # If they came from the right side, we finished a package delivery.
            curr_time += time[next_worker_idx][2]
            n -= 1
        else:
            if not pending: # If there aren't any packages left, don't send any more workers over.
                continue
            pending -= 1
            curr_time += time[next_worker_idx][0]

        # Add the next worker to the bridge line.
        heappush(working, [
            # The time the package event finishes depends on which side the worker is on.
            curr_time + time[next_worker_idx][1] if side == LEFT else curr_time + time[next_worker_idx][3],
            1 - side, # Flip the side. Left becomes right, right becomes left.
            efficiency,
            next_worker_idx
        ])
    return curr_time

(I’m sure this isn’t the *best* solution, but I hope it’s understandable and let me know if you have any suggestions on how you’d improve this!)

Is this a “good” interview question?

I think this question deserves its “Hard” rating if you’re under time pressure. It’s a lot to read in a short amount of time.

I’d also say this question is fairly difficult because you’re tracking a lot of state, leveraging a heap’s functionality in a fairly advanced way (using multiple values in each element to order them), and you need to make the key insight that you should just track the time of the last bridge crossing and use that to process “package events.”

However, I think this can be an effective interview question in some ways because you’re making the candidate read and implement a lot of business logic (with some edge cases) within a short amount of time. If this is what the candidate’s day-to-day work will look like, this question could be a high-signal screen.

I think verbose problem statements aren’t necessarily bad things; they’re filtering for different abilities. I found this type of question similar to one I encountered in my on-site interview loop with Stripe, which I wrote about here. For jobs that are more reading-heavy, e.g. at Stripe where you might need to read a lot of technical documentation from partners, this type of interview question offers an experience a bit more similar to your day-to-day work.

Extensions I’d ask in a real interview

• What’s the time and space complexity for this solution? Can you do better? Can you do this without any additional memory but additional time?
• How would you design this in an object-oriented way? e.g., design a class for workers, the bridge, and the overall simulation.
• How would you reason about this problem if there were two bridges? Three? N?

If you’re looking for more practice, https://leetcode.com/problems/task-scheduler/ seems pretty similar. There’s also a good list of heap questions in this discussion post.

I’m curious what my readers think of this problem statement. Let me know what you think in the comments below!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!