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 NVIDIA.

What role is this question designed for?

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

Find minimum time to cross bridge with flashlight

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A group of people must cross a bridge at night with **one flashlight**. The bridge can hold at most **two people** at a time. - If two people cross together, they move at the speed of the **slower** person. - The flashlight must always be carried when crossing. - Everyone starts on the same side and all must end on the other side. Given an array `t[]` of crossing times (positive integers) for each person, compute the **minimum total time** needed for everyone to cross. Clarify assumptions you will use (e.g., can people return, constraints on `n`, etc.) and describe an efficient algorithm.

Quick Answer: This question evaluates algorithmic problem-solving and optimization skills, including modeling constrained state transitions, reasoning about trade-offs under a single shared resource, and minimizing aggregate cost.

A group of people must cross a bridge at night using one flashlight. The bridge can hold at most two people at a time. If two people cross together, they move at the speed of the slower person. The flashlight must always be carried during any crossing, so people may need to return with it until everyone has crossed. Given an array `t` of positive integers where `t[i]` is the time person `i` needs to cross, return the minimum total time required for everyone to reach the other side. Assumptions used in this problem: - `t` may be unsorted. - People are allowed to return with the flashlight. - `n` may be 0. If nobody needs to cross, the answer is 0. - You only need to return the minimum total time, not the crossing sequence. - Your solution should be efficient for large `n`.

Constraints

0 <= n <= 200000
1 <= t[i] <= 10^9
The answer fits in a 64-bit signed integer

Examples

Input: ([],)

Expected Output: 0

Explanation: No one needs to cross, so the total time is 0.

Input: ([3],)

Expected Output: 3

Explanation: Only one person crosses once.

Input: ([4, 7],)

Expected Output: 7

Explanation: Both cross together, taking the slower person's time: 7.

Input: ([1, 2, 5, 10],)

Expected Output: 17

Explanation: Optimal sequence: 1 and 2 cross (2), 1 returns (1), 5 and 10 cross (10), 2 returns (2), 1 and 2 cross (2). Total = 17.

Input: ([2, 2, 2, 2],)

Expected Output: 10

Explanation: Every crossing or return takes 2. Minimum total is 2 + 2 + 2 + 2 + 2 = 10.

Input: ([8, 1, 2, 6, 12],)

Expected Output: 26

Explanation: After sorting to [1, 2, 6, 8, 12], optimally move 8 and 12 first using the two fastest as helpers, then finish the remaining three. Total = 26.

Hints

Sort the crossing times first. Once sorted, the important decision is how to move the two slowest remaining people.
For the two slowest people, compare these two strategies: send the two fastest as helpers, or send only the fastest back and forth.

Quick Overview

This question evaluates algorithmic problem-solving and optimization skills, including modeling constrained state transitions, reasoning about trade-offs under a single shared resource, and minimizing aggregate cost.