Skip to content

Instantly share code, notes, and snippets.

@kevinwucodes
Last active February 13, 2024 18:32
Show Gist options
  • Save kevinwucodes/f09e58ae908671fdfe2474b6809461f7 to your computer and use it in GitHub Desktop.
Save kevinwucodes/f09e58ae908671fdfe2474b6809461f7 to your computer and use it in GitHub Desktop.
daily coding problem #33: Compute the running median of a sequence of numbers

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
@lAnubisl
Copy link

lAnubisl commented Jul 22, 2019

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

@kevinwucodes
Copy link
Author

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!

@Srushti24
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment