Question d’entretien chez Jash Data Sciences
Question 1: Bridge Crossing Problem (Python) Problem Description: You are given a bridge represented as a list of integers where 1 is an intact section and 0 is a hole. A person must cross from start to end. Walking between two 1s is 1 step. Jumping over 0s counts as the distance between the two 1s. Find the longest jump (maximum distance) required to cross. If the bridge starts or ends with 0s, assume the person jumps from/to solid ground outside. Sample Input: bridge = [1, 0, 0, 1, 0, 1, 0, 0, 0, 1] Sample Output: 4
Réponse à la question d'entretien
Utilisateur anonyme
def longest_jump(bridge): # We treat 'solid ground' outside the bridge as a '1' at index -1 # and index len(bridge) # Find the indices of all 1s (intact sections) intact_indices = [i for i, val in enumerate(bridge) if val == 1] # Add virtual start and end points (outside the bridge) # Start ground is at index -1, End ground is at index len(bridge) all_points = [-1] + intact_indices + [len(bridge)] max_step = 0 # Compare distance between every consecutive intact point for i in range(len(all_points) - 1): distance = all_points[i+1] - all_points[i] if distance > max_step: max_step = distance return max_step # Example usage: bridge = [1, 0, 0, 1, 0, 1, 0, 0, 0, 1] print(longest_jump(bridge)) # Output: 4