Find median in string

Question

Given a string of integers separated by spaces, write a function to find the median of the numbers. The function should handle both odd and even lengths of the list, returning the median as a float. Ensure your solution is efficient, with a time complexity of O(n log n) or better.

Codemia · Accepted Answer

To find the median of a string of integers, we need to first convert the string into a list of integers and then determine the median of that list. The median is defined as the middle element in a sorted list of numbers. If the length of the list is odd, the median is the middle element. If it is even, the median is the average of the two middle elements. This leads us to identify a sorting-based approach as the primary strategy here, as sorting the list will allow us to access the middle elements directly. Given the constraints, we aim for an efficient solution with a time complexity of O(n log n) due to the sorting step.

1. **Input Parsing**: Split the input string by spaces to get the individual numbers. For example, given the string '3 1 4 2', we will convert it into the list [3, 1, 4, 2].
2. **Convert to Integers**: Convert the list of string numbers into a list of integers: [3, 1, 4, 2] becomes [3, 1, 4, 2].
3. **Sort the List**: Sort the list to arrange the numbers in ascending order: [1, 2, 3, 4].
4. **Calculate Median**: Determine the median based on the length of the list. If the length is odd, return the middle element. If even, compute the average of the two middle elements. For our example, the length is 4 (even), so the median is (2 + 3) / 2 = 2.5.

Here is the Python implementation of the above approach:

```python
def find_median(s: str) -> float:
    # Step 1: Parse the string into a list of integers
    numbers = list(map(int, s.split()))
    # Step 2: Sort the list
    numbers.sort()
    n = len(numbers)
    # Step 3: Calculate the median
    if n % 2 == 1:
        return float(numbers[n // 2])  # Odd length
    else:
        mid1, mid2 = numbers[n // 2 - 1], numbers[n // 2]
        return (mid1 + mid2) / 2.0  # Even length
```

This implementation first converts the input string into a list of integers, sorts that list, and then computes the median based on the list's length.

The time complexity of this solution is O(n log n) due to the sorting step. The space complexity is O(n) as we store the list of integers created from the input string. In a worst-case scenario, if the input string contains a large number of integers, our approach remains efficient given the constraints of the problem.

1. **Empty String**: If the input string is empty, we should return None or raise an exception, as there are no numbers to compute a median.
2. **Single Number**: For input like '5', the median should be 5.0.
3. **Negative Numbers**: The solution should correctly handle negative numbers in the input, like in '-1 0 1', resulting in a median of 0.0.
4. **Large Numbers**: Ensure that the implementation can handle very large integers without overflow. Python's integer type naturally manages large integers, but it's good to consider performance implications.

Find median in string

Jane Street

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Jane Street Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string