FastPrep
Problem

Recover Corrupted Master Page

Learn this problem
Microsoft logoMicrosoftFULLTIMEONSITE INTERVIEW
See Microsoft hiring insights

Problem statement

A storage system keeps files as linked lists of pages. Each page has:

  • a page offset or id,
  • an empty bit indicating whether the page is unused, and
  • the offset of the next page in the same file, or an EOF sentinel.

Page 0 is the master page. It normally stores the starting offsets, or heads, of all file chains. Page 0 has been corrupted, and you need to reconstruct it.

You are given pages, where each row is [id, emptyBit, next]. emptyBit is 1 for an empty page and 0 for a used page. next is the next page offset, or -1 for EOF.

Return the sorted list of starting offsets for all file chains. A starting offset is a used page id that is not pointed to by the next field of any other used page.

Function

recoverMasterPage(pages: int[][]) → int[]

Examples

Example 1

pages = [[1,0,3],[2,0,5],[3,0,10],[4,1,-1],[5,0,-1],[10,0,-1]]return = [1,2]

The used chains are 1 -> 3 -> 10 and 2 -> 5. Page 4 is empty, so it is ignored. The recovered master page offsets are [1,2].

Example 2

pages = [[7,0,-1],[3,0,4],[4,0,-1],[9,1,-1]]return = [3,7]

Page 4 is pointed to by page 3, so it is not a head. Pages 3 and 7 are used and not pointed to by any used page.

Constraints

  • 1 <= pages.length
  • pages[i].length == 3
  • pages[i][1] is either 0 or 1.
  • pages[i][2] == -1 or pages[i][2] is a page offset.

More Microsoft problems

drafts saved locally
public int[] recoverMasterPage(int[][] pages) {
  // write your code here
}
pages[[1,0,3],[2,0,5],[3,0,10],[4,1,-1],[5,0,-1],[10,0,-1]]
expected[1,2]
checking account