344. Reconstruct Corrupted Master Page

Reconstruct Corrupted Master Page

A storage system contains pages numbered from 0 to pages.size() - 1. Page 0 is the master page, while every other page contains metadata describing whether it is empty and which page follows it.

The master page normally stores the first page of every file chain, but its contents have been corrupted. Reconstruct it by finding every non-empty page that is not referenced as the next page of another non-empty page.

Each metadata string uses one of these formats:

"USED,nextPage" for a used page followed by another page.
"USED,EOF" for the last page of a file.
"EMPTY,EOF" for an unused page containing garbage.
"CORRUPTED" for the damaged master page at index 0.

Return the starting page offsets in ascending order.

Method Signature

List<Integer> reconstructMasterPage(List<String> pages)

Parameters

pages contains the metadata for every page. The index of a string is the corresponding page offset.

Return Value

Return a list containing the starting offset of every file chain in ascending order. Return an empty list if there are no used pages.

Constraints

1 <= pages.size() <= 100,000
pages.get(0) is "CORRUPTED".
Every remaining entry is "USED,nextPage", "USED,EOF", or "EMPTY,EOF".
In "USED,nextPage", nextPage is an integer satisfying 1 <= nextPage <= pages.size() - 1.
A used page points only to another used page or to EOF.
Every used page is referenced by at most one other used page.
File chains do not contain cycles.

Examples

Example 1

reconstructMasterPage(pages = ["CORRUPTED", "USED,4", "USED,5", "EMPTY,EOF", "USED,6", "USED,EOF", "USED,EOF"])

Output: [1, 2]

The file chains are 1 -> 4 -> 6 -> EOF and 2 -> 5 -> EOF. Page 3 is empty.

Example 2

reconstructMasterPage(pages = ["CORRUPTED", "USED,EOF", "EMPTY,EOF", "USED,4", "USED,EOF"])

Output: [1, 3]

Page 1 is a single-page file, while pages 3 and 4 form another file chain.

Example 3

reconstructMasterPage(pages = ["CORRUPTED", "EMPTY,EOF", "EMPTY,EOF"])

Output: []

There are no used pages, so the reconstructed master page contains no starting offsets.