kevinwucodes/readme.md

## readme.md

      
    Raw
  

              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:


need a function to calculate median for any array
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