Problem · Array
Recover Document Hierarchy from Indentation
Learn this problem● Easy
ReductoFULLTIMEPHONE SCREEN
ReductoFULLTIMEPHONE SCREENProblem statement
A document parser returns text objects in reading order. texts[i] is the object's text, and distances[i] is [left, top, right, bottom], its distances from the four page borders.
The left distance encodes indentation. A positive baseUnit is one indentation level, and every quotient distances[i][0] / baseUnit is within 0.01 of one unique nonnegative integer.
Return one string per object, preserving reading order, in the form level|text. The level is that unique integer. The other three border distances do not affect it.
Function
recoverIndentation(texts: String[], distances: double[][], baseUnit: double) → String[]Examples
Example 1
texts = ["Title","Section","Paragraph","Note"]distances = [[0,0,8,1],[2.01,1,5.99,1],[4,2,4,1],[6.02,3,1.98,1]]baseUnit = 2return = ["0|Title","1|Section","2|Paragraph","3|Note"]Each left distance is within one hundredth of a multiple of 2, so the levels are 0 through 3.
Example 2
texts = ["Heading","Indented","Back"]distances = [[0,7,9,2],[2.49,0,1,3],[1.26,8,4,0]]baseUnit = 1.25return = ["0|Heading","2|Indented","1|Back"]The levels follow left distance only and preserve input order; they do not need to be monotone.
Constraints
1 <= texts.length == distances.length <= 100000.- Each text has length from
1through100. - Every distance row is
[left, top, right, bottom]. - All distances are finite values from
0through1000000with at most two decimal places. 0.01 <= baseUnit <= 1000000and it has at most two decimal places.- Every
left / baseUnitquotient is within0.01of one unique nonnegative integer no greater than1000000.