Interview Prep for Facebook

from Queue import PriorityQueue

input = [[0,1,1000,2020],[2,1002,2030],[10,1001,2040]]

# Used in the K array merge
queue = PriorityQueue(0)

# Holds the last value taken from each array
lastValues = [0]*len(input)

# Helper function to get the range of an array of values
def getRange(array):
    min = sys.maxint;
    max = -sys.maxint;
    for node in array:
        if(node[0] < min):
            min = node[0]
        if(node[0] > max):
            max = node[0]
    return [min, max]

# Initialize the priority queue with the 'heads' of each array
for x in xrange(0, len(input)):
    # value, pos, id
    node = (input[x][0],0, x)
    lastValues[x] = node
    queue.put(node)

# Initialize best range
bestRange = getRange(lastValues)

while not queue.empty():
    node = queue.get()
    # update the last taken element
    lastValues[node[2]] = node
    newRange = getRange(lastValues)
    # If range is smaller update best range
    if(newRange[1] - newRange[0] < bestRange[1] - bestRange[0]):
        bestRange = newRange
    # array from which the node was taken
    array = input[node[2]]
    # If not at end of array, add next element
    if(len(array) > node[1] + 1):
        queue.put((array[node[1]+1],node[1] + 1,node[2]))

print(bestRange)

Browser Version Not Supported

Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+ Firefox 4+ Safari 5+
IE 10+

Let me try anyway!

Python Fiddle

Python Cloud IDE