welcome to
evildojo


HackerRank

Cracking the Coding Interview

Heaps: Find The Running Medium

Located here: https://www.hackerrank.com/challenges/ctci-find-the-running-medium

Notes:

This example is done in Python.


Not formatting the problem text. Read the link. I am too lazy.


Essentially, we need to write a "find the median" function.

Our input parameter will be a list of sorted integers.

First, if the length of the list mod 2 is 0, then our median will be the average of the two center numbers

Otherwise, the median will simply be the center number.

In a list of length 5, the center index will be 2. 5 / 2 = 2.

In a list of length 11, the center index will be 5. 11 / 2 = 5.

In a list of length 4, the two center indices are 1 and 2, because 4 / 2 = 2 and 2 - 1 = 1.

In a list of length 20, the two center indices are 20 / 2 = 10 and 9.


Some pseudocode

define get_median_index(list_len):
    if list_len mod 2 == 0:
        return (list_len / 2) - 1
    else:
        return (list_len / 2)

define get_median(list):
    sort(list)
    i = get_median_index(len(list))
    if len(list) mod 2 == 0:
        return (list[i] + list[i+1]) / 2
    else:
        return list[i]