[Challenge] Select a number, any number

challenge

#1

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
Find out more about basic challenges.

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.
Find out more about intermediate challenges.

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).

Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and 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:

Click the links to find out more about:


Essential Information on Code Challenges
#2

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?


#3

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


#4

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]))

#5

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 :slight_smile:

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]))

#6

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.


#7

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]);

#8

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.


#9

Ok, now it makes much more of a challange!!! :slight_smile:


#10

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


#11

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


#12

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)

#13

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


#14

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 ...


#15

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


#16

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


#17

Hard Difficulty: Python 3.6.1
Link: https://repl.it/J075/2

def getX(x,lst):
  mn = lst[0] #minimum value
  mx = lst[0] #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.


#18

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

#19

@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)


#21

Link to python code: here

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[0])
  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([15]) => %s' % getMedian([15]))
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('----------------------------')