Generate All Contiguous Protein Chains
Benchling● MediumFULLTIMEPHONE SCREENProblem statement
Each named gene sequence has a half-open interval [start,end). A protein chain may begin at any sequence and append another sequence whenever the next start equals the current end.
Return every non-empty contiguous chain as joined_names:start:end, sorted lexicographically. Each interval strictly advances, so the sequence graph is acyclic.
Interview follow-up
A candidate was also asked how to incorporate newly added sequences into the existing result without naively rerunning full enumeration. Discuss updating endpoint indexes and generating only chains containing at least one new sequence, including chains that contain several new sequences. Account for duplicate discoveries and the unavoidable cost of emitting new results. The judged function performs initial enumeration.
Function
generateAllProteins(names: String[], ranges: int[][]) → String[]Examples
Example 1
names = ["acG","Bf5","e5c","6a5d","7f6c","0Pf","0f5c"]ranges = [[0,5],[0,22],[5,16],[5,17],[2,13],[13,23],[0,13]]return = ["0Pf:13:23","0f5c:0:13","0f5c_0Pf:0:23","6a5d:5:17","7f6c:2:13","7f6c_0Pf:2:23","Bf5:0:22","acG:0:5","acG_6a5d:0:17","acG_e5c:0:16","e5c:5:16"]Every input sequence is a protein, plus each chain whose endpoints touch.
Constraints
- Names are unique.
1 <= names.length <= 15.names.length == ranges.length.0 <= start < end <= 10^9.- The number of output chains is at most
10000. - For this exercise, assume every sequence name contains only ASCII characters; an empty name is permitted. Lexicographic order compares these ASCII characters.