Find minimal time for four people crossing
Company: Exoduspoint
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Assume there are four people who need to cross a narrow bridge at night using a single flashlight.
- Each person \(i\) requires a different, known amount of time \(t_i\) to cross the bridge when walking alone.
- At most two people can be on the bridge at the same time.
- Whenever one or two people cross, they **must** carry the flashlight with them.
- If two people cross together, the time for that crossing is the **maximum** of their two individual times (they must move at the speed of the slower person).
- The flashlight cannot be thrown or sent by any means other than being carried by a person walking back across the bridge.
You are given the four crossing times \(t_1, t_2, t_3, t_4\) (positive integers). You may assume, without loss of generality, that they are sorted so that
\[ t_1 \le t_2 \le t_3 \le t_4. \]
**Tasks:**
1. Determine a strategy (sequence of crossings and returns) that minimizes the **total** time required for all four people to end up on the other side of the bridge with the flashlight.
2. Express the minimal total time in terms of \(t_1, t_2, t_3, t_4\) and clearly describe the order in which people cross and who returns with the flashlight.
Do **not** write code; just provide the final minimal total time and explain your reasoning and crossing sequence step by step.
Quick Answer: This question evaluates algorithmic problem-solving and combinatorial optimization skills, focusing on reasoning about constrained pairing, state-space search, and minimizing total time under movement constraints.
Given four sorted crossing times, return the optimal total time and a deterministic strategy.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,5,10],)
Expected Output: {'total': 15, 'strategy': [[1, 2, 'cross'], [1, 'return'], [5, 10, 'cross'], [2, 'return'], [1, 2, 'cross']]}
Explanation: Classic 17-minute solution.
Input: ([1,2,7,8],)
Expected Output: {'total': 13, 'strategy': [[1, 2, 'cross'], [1, 'return'], [7, 8, 'cross'], [2, 'return'], [1, 2, 'cross']]}
Explanation: Alternative comparison.
Input: ([2,3,4,5],)
Expected Output: {'total': 13, 'strategy': [[2, 3, 'cross'], [2, 'return'], [4, 5, 'cross'], [3, 'return'], [2, 3, 'cross']]}
Explanation: Sorted input.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.