Median of Parsed Integer Strings
Rippling● EasyNEW GRADPHONE SCREENProblem statement
You are given a nonempty array values of canonical base-10 signed integer strings. Parse every string and return the median of the resulting multiset as a double.
Duplicates are retained. If the number of values is odd, the median is the middle value after sorting. If it is even, the median is the arithmetic mean of the two middle values.
Dictionary follow-up
After solving the direct list version, explain or implement how the same result can be computed from a frequency dictionary whose keys are parsed integers and whose values are their multiplicities. Median positions must be located by visiting dictionary keys in increasing numeric order.
Function
parsedMedian(values: String[]) → doubleExamples
Example 1
values = ["10","2","7"]return = 7.0Parsing and sorting gives [2, 7, 10]. The single middle value is 7.
Example 2
values = ["-5","20","3","8"]return = 5.5The sorted values are [-5, 3, 8, 20]. The two middle values are 3 and 8, so the median is (3 + 8) / 2 = 5.5.
Example 3
values = ["4","4","4","9","12","12"]return = 6.5Duplicates remain in the multiset. The middle positions contain 4 and 9, whose arithmetic mean is 6.5.
Constraints
1 <= values.length <= 2 * 10^5.- Every
values[i]is the canonical base-10 representation of an integer in[-10^4, 10^4]. - Zero is written as
"0"; nonzero values have no leading zeros, and positive values have no leading plus sign.