Good afternoon! Here's our prompt for today.

Many modern programming languages have the notion of a stream. A stream is a resource that's broken down and sent (usually over a network) in small chunks.

Imagine a video that's playing-- it would be inefficient to need to download an entire 1 gigabyte movie before being able to watch it. Instead, browsers will gradually download it in pieces.

Given a stream of numbers with an infinite length, can you find the nth smallest element at each point of the streaming?

In the below example, we are looking for the second smallest element.

1// stream is the resource, the "..." represents future integers
2const stream = [3, 4, 5, 6, 7, ...]
3nthSmallestNumber(2); // 2nd smallest number
4// [null, 4, 4, 4, ...] (4 is always second smallest)

Let's use a for-loop to simulate a stream. Your method will be called as follows:

1for (let i = 0; i < 10; i++) {
2  const newInt = Math.floor(Math.random() * 10) + 1;
3  nthSmallestNumber(n);
4  // return nth smallest number
5}

Constraints

• Length of the stream <= 100000
• The values in the stream will be between -1000000000 and 1000000000
• Expected time complexity : O(nlogn)
• Expected space complexity : O(n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

# Import the heap functions from python library

from heapq import heappush, heappop, heapify

import math, random

​

​

def makeStream(length):

    for i in range(length):

        yield math.floor(random.random() * 10) + 1

​

​

def nthSmallestNumber(n):

    return n

​

​

​

​

import unittest

​

class Test(unittest.TestCase):

​

if __name__ == "__main__":

    unittest.main(verbosity=2)

    print("Nice job, 0/0 tests passed!")

​

Here's our guided, illustrated walk-through.

How do I use this guide?