Remove Invalid Parentheses | Dataford Interview Questions

Your question is Remove Invalid Parentheses. Start with the requirements and the one table on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Remove the minimum number of invalid parentheses from a string and return all valid results.

Asked in the Coding stage. Algorithmic coding task focused on search space and string manipulation.

Task

Write a PostgreSQL query that reads candidate Instagram Reels captions from a table and returns every caption that is valid after removing the minimum number of parentheses.

Requirements

Treat only ( and ) as parentheses, all other characters are literal text.
Return every distinct valid result that can be formed with the minimum removals.
If multiple captions have the same minimum removals, return all of them.
Order results by removed_count ascending, then valid_caption ascending.

Schema

reels_caption_candidates

Column	Type	Description
candidate_idPK	INT	Unique identifier for the caption candidate
caption_text	TEXT	Instagram Reels caption text to validate