Solve three algorithm tasks
Overview
This multi-part question evaluates algorithmic problem-solving across string processing (text justification), handling ambiguous state in sequence validation (parentheses with wildcards), and grid graph traversal with path reconstruction, testing competencies in formatting and spacing logic, state-tracking for correctness under uncertainty, and shortest-path search and reconstruction. It is commonly asked in Coding & Algorithms interviews to assess correctness under edge cases, ability to reason about trade-offs and invariants, and the analysis of time and space complexity, requiring both conceptual understanding and practical implementation skills.
Solve the following algorithm tasks and explain your approach, time complexity, and space complexity for each:
- Fully justify text: Given an array of words and an integer maxWidth, break the words into lines so that each line has exactly maxWidth characters and is fully justified. Distribute spaces as evenly as possible; when spaces do not divide evenly, put more spaces in the leftmost gaps. The last line should be left-justified with single spaces between words and padded on the right. Assume every word's length is <= maxWidth. Return the list of formatted lines.
- Validate parentheses with wildcards: Given a string s consisting of '(', ')' and ' ', where ' ' may represent '(' or ')' or the empty string, determine whether there exists a replacement that yields a balanced parentheses sequence. Return a boolean result and, if true, optionally output one valid replacement instantiation.
- Find a shortest path in a grid with obstacles: Given a 2D grid of 0s and 1s (0 = open cell, 1 = obstacle), a start coordinate (rs, cs), and a target coordinate (rt, ct), return any shortest path as a list of coordinates from start to target (inclusive). Movement is allowed only up, down, left, and right with unit cost. If no path exists, return an empty list. Discuss your path reconstruction method and how you handle cases where start/target are out of bounds or blocked.