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.
Overview: 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.
Read the full Exoduspoint Software Engineer interview experience this question came from
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.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.