Solve string merge and grid path tasks
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### Question
Given two equal-length strings s1 and s2, create a new string by iterating i = 0 … n-1, comparing s1[i] with s2[n-1-i]: append s1[i]; if the two characters are identical append that character again, otherwise append s2[n-1-i]. Examples: s1 = "abc", s2 = "def" → "afcd"; s1 = "abp", s2 = "jda" → "aaaapj"; s1 = "abp", s2 = "abp" → "appa". Return the resulting string. Design an algorithm for a robot moving on a 2-D grid containing: walls (impassable), healing cells (+health), and monster cells (–health). Starting with a given health value, find the shortest path from start to goal such that the robot’s health never drops to 0 or negative. Output that shortest distance (or the path itself). Solve an array/string problem that requires a sliding-window technique to meet a given constraint (details unspecified in the notes).
Overview: This multi-part question evaluates string manipulation and sequence merging, stateful shortest-path planning under resource constraints (health-aware grid pathfinding), and sliding-window optimization for arrays/strings within the Coding & Algorithms domain.
Given two equal-length strings s1 and s2 of length n, build a new string by iterating i from 0 to n-1. Let j = n - 1 - i. Append s1[i] to the result. If s1[i] == s2[j], append that character again; otherwise, append s2[j]. Return the resulting string.
Constraints
- 0 <= n <= 200000, where n = len(s1) = len(s2)
- s1 and s2 must have equal length
- Characters may be any printable ASCII
- Aim for O(n) time and O(n) extra space
Examples
Input:
Expected Output: afbecd
Input:
Expected Output: aabdpj
Hints
- Use j = n - 1 - i to index s2 from the end while scanning s1 from the start.
- Build the result with a list of characters and join at the end for efficiency.
- Handle the empty-string case (n = 0) by returning an empty string.