This is a question that involves lots of discussion because it may be quite vague and may require taking some assumptions. Obviously we can't do any kind of in-memory sorting because we don't have enough memory. We may possibly fit one set at a time, which would be under 1 GB of memory.

The first obvious solution is an external merge sort and then a look up of the n/2 element (or the average of n/2 and n/2 + 1 on even n's). This solution would be

*n log n*, but you may look for an*O (n)*solution, which someone may find impossible, since you need a sorted set to determine the median that involves element comparison which leads to the*n log n*complexity. But, who says we need sort by comparison.. ?
Another solution comes from our observation that we need to find the n/2 element in a sorted array, which can be generalized to the order statistics algorithm of finding the kth smallest number in an unsorted array. This algorithm is also called quick select or the selection algorithm. I talked about an implementation of this algorithm in this article. The problem is that this is an in-memory algorithm and we would not have enough memory to maintain all the sets. So we will need a distributed version of this algorithm which will basically need a routine to swap numbers across servers. We have to assume that this is an optimized and efficient routine, because there's just too many factors that can affect the efficiency of this routine (network latency, connection problems). This is a

*O(n)*solution and the distributed version of kth smallest may look like this:
Another solution comes from the second observation that we shouldn't use a comparison sort. We could use a histogram of the counts of the numbers across the servers, like in the counting sort. But here we would have to assume a few more things. First we have to know something about the range of the numbers. If we have ranges of order of billions we could store an array of a few billions cells or at least one billion since the problem statement allows us to process a billion numbers in memory, which is the second assumption. Again this is a

*O(n)*solution because we compute the histogram by going once through all the numbers and then find the kth number (the median) by going through the elements of the histogram. In code it may look similar to this:
We could think of more solutions if we could assume even more facts. Let's say we know that the numbers across all servers are uniformly distributed. Having this large amount of numbers we could say the median is also the average of all numbers. So if we also know the range of distribution, say 0.. 1 billion, then computing the median is a

*O(1)*operation and all we need to do is to compute*0 + (1 billion - 0) / 2*which is 500 million. If we don't know the range we can compute the median of medians in*O(n)*by using order statistics on each server.
If the distribution is not uniform but we know some information about it we could still calculate the median with some probability. Of course we can find other different solutions if we take various assumptions, but the above solutions can probably satisfy any interviewer or whoever asked this question.

cách trị thâm nách

ReplyDeletetrị thâm nách tại nhà

trị hôi nách giá rẻ

chữa hôi nách ở hà nội

trị hôi nách vĩnh viễn

kem trị thâm nách tốt nhất

điều trị thâm nách

trị thâm nách vĩnh viễn

thuốc trị thâm nách

trị thâm nách tự nhiên

trị thâm nách tốt nhất

kem trị thâm nách tốt nhất

Kênh game

I have been checking out a few of your stories and i can state pretty good stuff. I will definitely bookmark your blog

ReplyDeleteFREE learning management system

State of Origin 2017

ReplyDeleteState of Origin 2017 live

2017 State of Origin

2017 Holden State of Origin

The US Open Live

ReplyDeleteUS Open 2017

US Open 2017 Live

2017 US Open

US Open Golf

US Open 2017

US Open 2017 Live

2017 US Open

US Open Golf

US Open

NBA Finals

It's the Millennium boxing match or an abomination that spins in a cross code, but what we can say with certainty, in the end, is that it's happening. Once retired all-time great McGregor vs Mayweather Live boxer will take UFC star in Las Vegas.

ReplyDeleteThere has been what it feels like years of speculation about the McGregor vs Mayweather Fight, with so many name calling on both sides. But the two fighters have announced that it is in fact, in.

Yes, that's right, a boxer with a 49-0 record against a man who has never taken part in a professional boxing matchup.

Anyway, here you have everything you need to know about the McGregor vs Mayweather fight.

In the UFC 214: Cormier vs Jones 2 Fight Card, Date, Betting Odds, Preview and Live Stream Info

ReplyDeleteUFC 214 Live

UFC 214 Live Stream

UFC 214 Fight

UFC 214

UFC 214 Live

Watch UFC 214

UFC 214 Fight Card

Heya i'm i am for the primary the first time here. I came across found this board and I in finding find to find It truly really useful helpful & it helped me out a lot much . I am hoping I hope I'm hoping to give to offer to provide to present something one thing back again and help aid others like you such as you helped aided me.

ReplyDeleteCanelo vs GGG A standout amongst the most expected boxing battles of 2017 has been fixed, marked and affirmed with Canelo Alvarez going up against middleweight boss Gennady Golovkin on sixteenth September 2017 in Las Vegas for the most part presumably at the MGM Grand Garden.

ReplyDeleteCanelo vs GGG

GGG vs Canelo

Canelo vs GGG Live

GGG vs Canelo Live

Canelo vs GGG Live Stream

GGG vs Canelo Live Stream

Golovkin vs Alvarez Live

Canelo vs Gennady Live

Canelo vs Golovkin

Alvarez vs Golovkin

Golovkin vs Alvarez

Canelo vs Gennady

Gennady vs Canelo

Canelo Alvarez vs Gennady Golovkin Live

Gennady Golovkin vs Canelo Alvarez Live

Canelo vs Golovkin Live Stream

Golovkin vs Canelo Live Stream

Canelo Alvarez vs Gennady Golovkin

Gennady Golovkin vs Canelo Alvarez

Canelo vs Golovkin Live

Golovkin vs Canelo Live

Alvarez vs Golovkin Live Stream

Golovkin vs Alvarez Live Stream

Canelo vs Golovkin Fight

Golovkin vs Canelo Fight

Canelo vs GGG Fight

GGG vs Canelo Fight

Alvarez vs Golovkin Fight

Canelo vs Gennady Fight

Gennady vs Canelo Fight

Canelo vs Golovkin Fight Card

Golovkin vs Canelo Fight Card

Canelo vs GGG Fight Card

GGG vs Canelo Fight Card

Alvarez vs Golovkin Fight Card

Golovkin vs Alvarez Fight Card