daily coding problem #33: Compute the running median of a sequence of numbers

readme.md

Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.

Recall that the median of an even-numbered list is the average of the two middle numbers.

For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:

2
1.5
2
3.5
2
2
2

Thought process:

1. need a function to calculate median for any array
2. need a function to iterate through that function to get output of streaming array

calculateMedian logic:

• edge cases
  • when array is empty, return 0
  • when array has just a single element, return that element
• we need to sort the array before we can compute the median
• create example arrays to determine what elements to capture (this helps to see what patterns emerge). I realized that there will be a different logic between even-length arrays and odd-length arrays so we need to separate that logic.

separate logic for even and odd length arrays

Even-length arrays

• [1,2,3,4] => length = 4, we need index (1,2).
  • To get these indexes, we take length / 2 which is 2. The second index is 2 - 1, which is 1.
• [1,2,3,4,5,6] => length = 6, we need index (2,3).
  • To get these indexes, we take length / 2 which is 3. The second index is 3 - 1, which is 2.
• [1,2,3,4,5,6,7,8] => length = 8, we need index (3,4).
  • To get these indexes, we take length / 2 which is 4. The second index is 4 - 1, which is 3.

Once we get the indexes (first, second) for evens, the median is (ary[first] + ary[second]) / 2.

Odd-length arrays

• [1,2,3] => length = 3, we need index (1).
  • To get this index, we take length / 2, which is 1.5. We Math.floor(1.5) to get index 1.
• [1,2,3,4,5] => length = 5, we need index (2).
  • To get this index, we take length / 2 which is 2.5. We Math.floor(2.5) to get index 2.
• [1,2,3,4,5,6,7] => length = 7, we need index (3).
  • To get this index, we take length / 2, which is 3.5. We Math.floor(3.5) to get index 3.

Once we get the indexes (middle) for odds, the median is just ary[middle].

Iterator Logic

Iterate through array. During each iteration, we output a new array from the beginning to the current iterator index. Then send that new array through calculateMedian.

Code

const ary = [2, 1, 5, 7, 2, 0, 5]


function calculateMedian(ary) {
  const sorted = ary.sort((a, b) => a - b)

  if (sorted.length == 0) return 0

  if (sorted.length == 1) return sorted[0]

  if (sorted.length % 2 == 0) {
    const firstIndex = sorted.length / 2
    const secondIndex = firstIndex - 1
    return ((sorted[firstIndex] + sorted[secondIndex]) / 2)
  } else {
    const middleIndex = Math.floor(sorted.length / 2)
    return (sorted[middleIndex])
  }
}

function iterateArray(ary) {
  ary.forEach((el, index, ar) => {
    const currentStreamedArray = ar.slice(0, index + 1)
    console.log(calculateMedian(currentStreamedArray))  //2, 1.5, 2, 3.5, 2, 2, 2
  })
}


iterateArray(ary) //2, 1.5, 2, 3.5, 2, 2, 2

it is not efficient. The running time of your algorithm is O(n**2 logn) It is possible to implement O(n logn)

Ah, thanks @lAnubisl, I'm still trying to master algorithms and data structures. I've got a long ways to go before I consider myself somewhat decent!

Hi, can you describe the time complexity of your solution?