Dynamic First and Last Position in Sorted Data
Bloomberg LP● HardNEW GRADPHONE SCREENProblem statement
You maintain a sorted multiset of integers. It initially contains every value in the nondecreasing array initial.
Process operations from left to right:
["insert", "x"]inserts one occurrence of integerx. The multiset remains sorted conceptually.["range", "x"]asks for the zero-based first and last positions occupied byxin the current sorted multiset. Return[-1, -1]whenxis absent.
Return one two-integer result for each range operation, in operation order. Insertions may append a new maximum, insert a new minimum, fall between existing values, or add a duplicate.
Function
dynamicSearchRange(initial: int[], operations: String[][]) → int[][]Examples
Example 1
initial = [1,2,2,4]operations = [["range","2"],["insert","5"],["range","5"],["insert","2"],["range","2"]]return = [[1,2],[4,4],[1,3]]The initial copies of 2 occupy indices 1 through 2. Appending 5 places it at index 4. Inserting another 2 expands that value's range to indices 1 through 3.
Example 2
initial = []operations = [["range","7"],["insert","7"],["insert","3"],["range","7"],["range","3"]]return = [[-1,-1],[1,1],[0,0]]The first query sees an empty multiset. After inserting 7 and then the smaller value 3, their sorted positions are 1 and 0.
Example 3
initial = [-2,-2,0]operations = [["insert","-3"],["insert","-2"],["range","-2"],["range","1"]]return = [[1,3],[-1,-1]]After both insertions, the sorted multiset is [-3,-2,-2,-2,0]. Value -2 occupies indices 1 through 3, while 1 is absent.
Constraints
0 <= initial.length <= 50000.1 <= operations.length <= 50000.-10^9 <= initial[i], x <= 10^9.initialis sorted in nondecreasing order.- Every operation is exactly
["insert", "x"]or["range", "x"], wherexis a signed decimal integer. - At least one operation is
range.