Most-Read Page Across Every Valid Storyline
Duolingo● HardNEW GRADINTERNOAPHONE SCREENProblem statement
You are reading a branching story book whose pages are numbered from 1 through 50. Every storyline begins on page 1.
On an ordinary page, reading continues to the next numbered page. A row [page, first, second] in choices makes page a choice page whose two options jump to first and second. A page in endings finishes the current storyline immediately.
Within one storyline, each option of a choice page can be used at most once. Revisiting a choice page after both options have already been used makes that branch invalid. Advancing past page 50 also makes a branch invalid.
Consider every valid storyline that reaches an ending. Count every visit to every page across all of those storylines. Return [page, count] for the page with the greatest total count. If several pages tie, return the smallest page number. If no valid storyline reaches an ending, return [-1].
Function
mostReadStoryPage(endings: int[], choices: int[][]) → long[]Examples
Example 1
endings = [5,10]choices = [[3,7,9],[9,10,8]]return = [9,6]There are four valid ending-reaching storylines. Pages 1, 2, 3, 8, and 10 are each read four times, while page 9 is read six times. Therefore the result is [9, 6].
Example 2
endings = [5]choices = [[1,1,1]]return = [-1]Both options on page 1 return to page 1. After each option has been used once, the branch is invalid and never reaches page 5. No valid storyline exists.
Constraints
1 <= endings.lengthand every ending is a unique page from1through50.0 <= choices.length <= 12.- Every choice row has exactly three page numbers from
1through50. - Choice-page numbers are unique.
- Counts fit in a signed 64-bit integer.