 # Code Challenge #14: July 12, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Amazon:

### Basic Difficulty

Write a function, `getMedian`, that will return the median value of a list of numbers.

• Function Name: `getMedian`
• Input: An unsorted `List` of `integers`
• Output: The `integer` which is the median value of the input list.
• Examples: `getMedian([6,10,2,5,9,3,10,12,18,-3]) => 7.5` (average of the middle two values)
`getMedian([5,10,-3,7,9]) => 7`

### Intermediate difficulty

Write a function, `getX`, that given an integer `x` and a list returns the `Xth` number if the list was in sorted order.

• Function Name: `getX`
• Input: An `integer`, x, and an unsorted `list of integers`
• Output: The `integer` corresponding to the `Xth` number in the sorted list
• Example: `getX(2, [5,10,-3,7,9]) => 5`
`getX(4, [5,10,-3,7,9]) => 9`
• Note that this assumes the first number is position `1` not `0`.

### Hard Difficulty

Write `getX` so that the list is not simply sorted and then the `Xth` element picked out. It is possible to solve this problem in linear time, `O(n)`.

#### `Reply` to this thread with a link to your code on repl.itand paste your properly formatted code to participate! Don’t just submit your code, remember to `explain` your solution, too! If you want to be considered as the winner, your function `must` have the `correct name` and provide `output in the format specified` above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as `itertools` will not be considered for the winner.

The fine print:

Just to clarify something, to sort the lists, are we allowed to use built-in functions to to sort the lists or should we also do that part with our own code like last week’s challenge?

Do it without using imports to do all the heavy lifting (such as `itertools`)!

4 Likes

Yay first code! Lol.

Basic Difficulty.

## https://repl.it/JYnO/0

``````def median(lst):
med = []
for i in range(len(lst)):
for j in range(len(lst) - 1):
if lst[j] > lst[j+1]:
lst[j+1], lst[j] = lst[j], lst[j+1]
if len(lst) % 2 == 0:
num1 = lst[(len(lst)//2)-1]
num2 = lst[(len(lst)//2)]
med.append((num1 + num2)/2)
elif len(lst) % 2 == 1:
med.append(lst[((len(lst)+1)//2)-1])
return med
print(median([6,10,2,5,9,3,10,12,18,-3]))
print()
print(median([5,10,-3,7,9]))

``````

Side note: Still trying to come up with a neater way of sorting a list of integers. For now, used the same sort method as for the previous challenge [ TopScoreSorter ]

Intermediate Difficulty:

https://repl.it/JYya

``````def getX(x,lst):
for i in range(len(lst)):
for j in range(len(lst) - 1):
if lst[j] > lst[j+1]:
lst[j+1], lst[j] = lst[j], lst[j+1]
return lst[(x-1)]
print(getX(2, [5,10,-3,7,9]))
``````

Here’s my take on the basic challenge using Python 3: https://repl.it/JYfZ/4
I didn’t use sorted() to sort the initial list to avoid using more built-ins, though I still don’t feel happy with the way I sorted the list, it should have been cleaner
Anyway, now I’m gonna work on the intermediate difficulty ``````def getMedian(num_list):
#the following chunk of code is used to sort the num_list in \
#ascending order, the result is sorted_num_list; this is equivalent \
#to sorted(num_list)
sorted_num_list = []
while num_list:
min_num = float('+inf')
for num in num_list:
if num < min_num:
min_num = num
sorted_num_list.append(min_num)
num_list.remove(min_num)

#test if the number of items in sorted_num_list is even or odd
if len(sorted_num_list)%2 == 0:
#if it's even the median will be the average of the two middle \
#numbers in sorted_num_list
median_value = (sorted_num_list[len(sorted_num_list)//2] + sorted_num_list[(len(sorted_num_list)//2) - 1]) / 2
else:
#if it's odd then the madian will just be the middle number \
#of sorted_num_list
median_value = sorted_num_list[len(sorted_num_list)//2]

return median_value

print('getMedian([6,10,2,5,9,3,10,12,18,-3]) =>', getMedian([6,10,2,5,9,3,10,12,18,-3]))
print('getMedian([5,10,-3,7,9]) =>', getMedian([5,10,-3,7,9]))
``````

edit: Completed the intermediate difficulty: https://repl.it/JYf8/5
Started by doing the exact same sorting method from the basic difficulty, then looped through the sorted list to find the index corresponding to the given index (taking into account this index starts at 1 not 0) using a count variable

``````def getX(x, num_list):
#the following chunk of code is used to sort the num_list in ascending \
#order, the result is sorted_num_list; this is equivalent to sorted(num_list)
sorted_num_list = []
while num_list:
min_num = float('+inf')
for num in num_list:
if num < min_num:
min_num = num
sorted_num_list.append(min_num)
num_list.remove(min_num)

#to find the xth number in the list i use a count variable, starting \
#at 1, since the x variable will also start at 1 rather than 0
count = 1

#now simply loop through sorted_num_list to find the number \
#corresponding to the index x
for num in sorted_num_list:
if count == x:
return num
count += 1
#created an else just in case the index given is out of range
else:
return 'The index you chose doesn\'t exist in the given list.'

print('getX(2, [5,10,-3,7,9]) =>', getX(2, [5,10,-3,7,9]))
print('getX(4, [5,10,-3,7,9]) =>', getX(4, [5,10,-3,7,9]))
#a final input to test my else clause
print('getX(4, [5,10,-3,7,9]) =>', getX(6, [5,10,-3,7,9]))
``````

JavaScript Hard & Linear

https://repl.it/JZC1/2

``````function getX(x, arr) {
"use strict";
const aboveMax = arr.length - x,
belowMax = x - 1;

let above = 0,
below = 0,
upper, lower, target;

// testing cause it caught me with another test dataSet :P
if (x > arr.length) {
console.error("'x' is larger than arr.length");
return;
}

// Single loop for O(n) speed
for (let i = 0, l = arr.length; i < l; i++) {
if (i === 0) {
// first iteration, store number as target and continue
target = arr[i];
continue;
}

if (arr[i] > target) {
// array value is above current target
if (above < aboveMax) {
above++;
if (typeof upper === "undefined" || arr[i] < upper) {
upper = arr[i];
}

} else {
lower = target;
// added this typeof test for an 'x' of arr.length
if (typeof upper === "undefined" || arr[i] < upper) {
target = arr[i];
} else {
target = upper;
upper = arr[i];
}
}

} else {
// array value is below current target
if (below < belowMax) {
below++;
if (typeof lower === "undefined" || arr[i] > lower) {
lower = arr[i];
}
} else {
upper = target;
// added this typeof test for an 'x' of 1
if (typeof lower === "undefined" || arr[i] > lower) {
target = arr[i];
} else {
target = lower;
lower = arr[i];
}
}
}
console.log(upper, target, lower);  // TEST
}

return target;
}

const dataSet = [5, 10, -3, 7, 9];
const dataSet2 = [10, 5, 11, 12, 13, 0, 1, 2, 3];

console.log(getX(1, dataSet2));
``````

I was really stumped as to how to pluck out a given sorted index without sorting or resorting to double loops. I had done exercises where the largest and smallest values were retrieved in O(n) time so I wrote one of those and tried tweaking bits for a while then scrapped the whole thing.

I needed to cast a wide net and store a few values each iteration to help me compare. Initially I wanted to build up 2 intermediate arrays to store extra values in a pseudo-sorted manner but that became ugly and unmanageable.

My big breakthrough came when I realized I didn’t need ‘x’ so much as the number of values I expected above and below it. So I defined some Max constants and created some counters for above and below values.

With these I could work with a three number net and filter values into it while shifting it up or down based on the status of my above and below counters.

This works on the data sets that I tried though its hard to test it against ridiculously large number sets because I need to know what I expect from the nth value in an array of 10000 values.

This solution is unpredictable when the data set is permitted to have repeating values so I’ll have to come back to that.

EDIT: Drat, this does not work on large data sets. Back to the drawing board.

One of the first times I am participating in the challanges, so I hope I am following the rules…
For the Hard difficulty I am not sure if I have understood the task, should it return the Xth value without sorting the array first?

Easy

``````function getMedian(list){
return (Math.max(...list) + Math.min(...list)) / 2
}

getMedian([6,10,2,5,9,3,10,12,18,-3]);
``````

Inter

``````function getX(x, list){
// chaining list sort and pick elem from array
return list.sort((a, b) => {return a - b})[x - 1]
}

getX(4, [5,10,-3,7,9]);
``````

To clarify, only submissions that implement their own Sorting algorithm will be accepted i.e. you can’t use `sort([])` . Also, as the Hard category states, it is possible to solve this problem without sorting.

4 Likes

Ok, now it makes much more of a challange!!! 1 Like

Python 3 Basic Difficulty

``````#The function getMedian returns the median in a list of integers

def getMedian(ints):

#following code used to sort integers
ordInts = []
#short for ordered integers

while len(ints) > 0:
ordInts.append(max(ints))
ints.remove(max(ints))
#after all integers are sorted

else:
if len(ordInts) % 2 == 0:
#if statement used to determine whether there is a middle number
#or an average of the two middle numbers is needed

return ((ordInts[int(len(ordInts)/2)] + ordInts[int((len(ordInts)/2)-1)])) / 2.0
else:
return ordInts[int(len(ordInts)/2)]

print(getMedian([6,10,2,5,9,3,10,12,18,-3]))
print(getMedian([5,10,-3,7,9]))
``````

https://repl.it/J0AX/14

Intermediate Difficulty Python 3

``````#The funciton getX returns the Xth number of a
#given sequence after the sequence has been sorted

def getX(x, ints):

#following code used to sort integers
ordInts = []
#short for ordered integers

while len(ints) > 0:
ordInts.append(min(ints))
ints.remove(min(ints))
#after all integers are sorted

else:
if x <= len(ordInts):
#prevents x's out of index range

return ordInts[x - 1]

print(getX(2, [5,10,-3,7,9]))
print(getX(4, [5,10,-3,7,9]))
``````

https://repl.it/J0CN/11

I did it in basic difficulty in Python 2.7, using selectionsort: https://repl.it/J0Y1/1

``````def getMedian(listint):
listint = selectionsort(listint)

if len(listint) * 1.0 / 2 != int(round(len(listint) * 1.0 / 2)):
return listint[int(round(len(listint) * 1.0 / 2))-1]
else:
return listint[int(round(len(listint) * 1.0 / 2))-1], listint[int(round(len(listint) * 1.0 / 2))]

def selectionsort(sortlist):
for i in range(0, len(sortlist)-2):
maxIndex = i

for j in range(i+1, len(sortlist)-1):
if sortlist[j] > sortlist[maxIndex]:
maxIndex = j

sortlist[i], sortlist[maxIndex] = sortlist[maxIndex], sortlist[i]

return sortlist

list1 = [6,10,2,5,9,3,10,12,18,-3]
list2 = [5,10,-3,7,9]

print "list 1:", list1
print getMedian(list1)

print "list 2:", list2
print getMedian(list2)``````

Basic Difficulty using Ruby :
https://repl.it/J03o/1

My first time here but I think I got it in JavaScript

``````// Basic
function getMedian(arr) {
var newarr = ''
var sorted = arr.sort((a, b) =>  a - b)
var mid = arr.length / 2
Number.isInteger(mid) ? newarr = (sorted[mid - 1]+sorted[mid])/2 : newarr = sorted[Math.floor(mid)]
return newarr
}
``````

and for Intermediate

``````
// Intermediate
function getX(x,arr){
var newarr = ''
arr = arr.sort((a, b) =>  a - b)
newarr = arr[x -1]
return newarr
}
``````

EDIT
Opps, I used the sort method and shouldn’t have apparently for this challenge …

Sir @Tony Hoare here. This challenge sounded right up my alley so I’m posting my solution for hard level. If the mods ever get back to rating and giving feedback on our submissions and mine wins (it better does, I got knighted for it already), please credit me not @B-Twin. I’m just using his account while he’s busy coding his own stuff, you know these proud kids, always needing to do it their own way.

The good folks at Wikipedia have already done all the explaining for me, go there if you want to know how my code works.

``````def partition(arr, pivot, l, r):
pivval = arr[pivot]
arr[pivot], arr[r] = arr[r], arr[pivot]
idx = l
for i in range(l, r):
if arr[i] < pivval:
arr[idx], arr[i] = arr[i], arr[idx]
idx += 1
arr[r], arr[idx] = arr[idx], arr[r]
return idx

def getX(k, arr):
l, r, k = 0, len(arr)-1, k-1
while True:
if l == r:
return arr[l]
pivot = (l+r)//2
pivot = partition(arr, pivot, l, r)
if k == pivot:
return arr[k]
elif k < pivot:
r = pivot - 1
else:
l = pivot + 1
``````

Code with randomized test at repl.it

2 Likes
``````class Array
def quick
0.upto(self.count - 2) do |x|
if self[x] > self[x + 1]
self[x], self[x+1] = self[x+1], self[x]
quick
end
end
self
end
end

def getMedian(some_list)
some_list.quick
p some_list
median = 0
temp = 0
if some_list.count.even?
temp = some_list.count / 2
median = ( some_list[temp - 1] + some_list[temp] ) / 2.0
else
temp = some_list.count / 2
median = some_list[temp]
end
return median
end

def getX(integer, some_list)
some_list.quick
return some_list[integer - 1]
end
``````

With the test @ https://repl.it/J2Im/0

Hard Difficulty: Python 3.6.1

``````def getX(x,lst):
mn = lst #minimum value
mx = lst #maximum value
val = [] #values list
nxs = len(lst) #indices in lst
rng = 0 #range of val
ttl = 0 #subtotal
ndx = 0 #index in val

#finding the minimum and maximum values
for i in lst:
if i < mn:
mn = i
if i > mx:
mx = i

#setting range
rng = mx - mn + 1

#setting val to contain one index per integer between mn and mx, inclusive (set to zero)
while len(val) < rng:
val.append(0)

#looping through lst to increase the apropriate indices
for j in lst:
val[j - mn] += 1

#looping through val to find the Xth smallest integer
if x < nxs/2:
while ttl < x:
ttl += val[ndx]
ndx += 1
return ndx + mn - 1
else:
while ttl < nxs - x + 1:
ttl += val[rng - ndx - 1]
ndx +=1
return mx - ndx + 1
``````

My first approach was actually to make a sorted intermediary list of the lowest `x` values, but that resulted in a time of `O(n*x)`, which wasn’t quite what I was looking for.

Then, I poked around and tried something that I considered crazy at the time. I made a list representing all the possible values and iterated through the input list to update each with the number of times it occurred. After a little tweaking, this has resulted in a solution that takes at most `T(n,r)≤2n+(3/2)r`, where `n` is the size of the input list and `r` is the range of the integers carried therein. I believe that this counts as linear time `O(n)`.

I am still unsatisfied by the fact that the approach depends on `r`, which is a significant liability.

The code that the link points to contains my testing code that I use to check that it really always works as well as the actual function.

1 Like

My entry for Basic Difficulty in Python 2.7: https://repl.it/J2BB/3

First, I went ahead and stored our test lists.

Next, I defined a sorting function from scratch. It is extremely similar to my sorting function from last week’s challenge.

After this, I went ahead and tackled the main function. I started my sorting the list (using the sorting function I defined earlier), then checking if the list has an even number or odd number of values.

If the list is odd, it returns the middle value of the list. (In this case, middle is defined as the number located at the index which is half the length of the list).

If the list is even, it returns the result of averaging the two middle values. (In this case, the first middle value is the number located at the index which is half the length of the list. The second middle value is the first middle value subtracted by 1).

``````testOne = [6, 10, 2, 5, 9, 3, 10, 12, 18, -3]
testTwo = [5, 10, -3, 7, 9]

def sortList(myList):
orderedList = []
while len(myList) > 0:
for each in myList:
if each == min(myList):
orderedList.append(each)
myList.remove(each)
return orderedList

def getMedian(myList):
newList = sortList(myList)
middle = len(newList) / 2
if len(newList) % 2 != 0:
return newList[middle]
else:
return (newList[middle] + newList[middle - 1]) / 2.0

print getMedian(testOne)
print getMedian(testTwo)
``````

Though, in retrospect, I honestly could have just done this:

``````def getMedian(myList):
newList = sorted(myList)
if len(newList) % 2 != 0:
return newList[(len(newList)/2)]
else:
return (newList[(len(newList)/2)] + newList[(len(newList)/2) - 1]) / 2.0
``````

@b-twin Nice, it’s good, still not the most efficient solution possible though, so might not win.

@naryaclue Very good solution! Your solution is actually called a bucket sort (not sure whether you know that or not). Under a lot of conditions you are right it is O(n), but it all depends on the range of inputs. Say for example you had n inputs but the range of them was n^2. There is another method that can gaurentee O(n)

1 Like

When I saw that you didn’t want a canned sort, I did both solutions without one

``````

def getMedian(medList):
if len(medList) == 0:
return "Emply List, there is no median"
workList = medList
while len(workList) > 2:
workList.remove(min(workList))
workList.remove(max(workList))
if len(workList) %2:
return (workList)
else:
return (max(workList) + min(workList)) / 2

def getX(i, lst):
if i > len(lst) or i<1:
return 'ValueError'
workList = list(lst)
for n in range(i):
m = min(workList)
workList.remove(m)
return m

print('getMedian([6,10,2,5,9,3,10,12,18,-3]) => 7.5')
print('getMedian([6,10,2,5,9,3,10,12,18,-3]) => %s' %  getMedian([6,10,2,5,9,3,10,12,18,-3]) )
print('getMedian([5,10,-3,7,9]) => 7')
print('getMedian([5,10,-3,7,9]) => %s' % getMedian([5,10,-3,7,9]))
print('getMedian() => %s' % getMedian())
print('getMedian([]) => %s' % getMedian([]))
print('----------------------------')

print('getX(2, [5,10,-3,7,9]) => 5')
print('getX(2, [5,10,-3,7,9]) => %s' % getX(2, [5,10,-3,7,9]) )
print('getX(4, [5,10,-3,7,9]) => 9')
print('getX(4, [5,10,-3,7,9]) => %s' % getX(4, [5,10,-3,7,9]) )
print('getX(11, [5,10,-3,7,9]) => %s' % getX(11, [5,10,-3,7,9]) )
print('getX(0, [5,10,-3,7,9]) => %s' % getX(0, [5,10,-3,7,9]) )

print('----------------------------')

``````