Mark As Completed Discussion

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?

Description

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

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

JAVASCRIPT
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?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's our guided, illustrated walk-through.

How do I use this guide?