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

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.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Loading coding console...