Round 1
Questions: There is a 2 lane road, each lane is represented by a String, l1 represents the first lane and l2 represents the second lane. A given lane is made up of N segments. A given segment can be either smooth or can have potholes. If we consider these 2 strings, l1 = "..XX.X" and l2 = "X.X.X..". Here "." represents smooth road and "X" represents the pothole. A car can be driven through pothole segments but it is just uncomfortable. Now the task is to patch the maximum number of potholes while keeping the road open for travel.
Example 1:
- l1 = "..XX.X"
- l2 = "X.X.X..",
- output: 4
Road visualization:
| . | . | X | X | . | X | | X | . | X | . | X | . |
Path a car can take while patching potholes (* represents the segment selected):
| * | * | - | - | - | - | | - | * | * | * | * | * |
Potholes that can be patched:
| . | . | (X) | (X) | . | (X) | | (X) | . | X | . | X | . |
If you are finding difficulty with the above example, I can prepare and share visually appealing diagrams representing the examples.
Candidate's Approach
I used a recursive-backtracking approach to solve the problem. The total number of potholes minus the minimum number of potholes in an optimal path gives the answer.
Interviewer's Feedback
No feedback provided.