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
Great Article IoT Projects for Students
DeleteDeep Learning Projects for Final Year
JavaScript Training in Chennai
JavaScript Training in Chennai
The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training
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
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.
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
US Open Tennis
ReplyDeleteUS Open
US Open Tennis 2018
US Open 2018
2018 US Open
PGA Championship Golf 2018
2018 US Open Tennis
US Open 2018 Schedule
US Open 2018 Tennis Schedule
US Open Tennis 2018 Schedule
U.S. Open
U.S. Open 2018
2018 U.S. Open
US Open Tennis Live
US Open Tennis Live Stream
US Open Tennis Live Streaming
US Open Live
US Open Live Stream
US Open Live Streaming
US Open 2018 Live
US Open 2018 Live Stream
US Open 2018 Live Streaming
US Open Tennis 2018 Live
US Open Tennis 2018 Live Stream
US Open Tennis 2018 Live Streaming
US Open 2018 TV Channel
US Open 2018 Dates
US Open Tennis Championships
US Open Tennis Championships 2018
https://ususopen.com/
US Open Tennis
ReplyDeleteUS Open
US Open Tennis 2018
US Open 2018
2018 US Open
2018 US Open Tennis
US Open 2018 Schedule
US Open 2018 Tennis Schedule
US Open Tennis 2018 Schedule
U.S. Open
U.S. Open 2018
2018 U.S. Open
US Open Tennis Live
US Open Tennis Live Stream
US Open Tennis Live Streaming
US Open Live
US Open Live Stream
US Open Live Streaming
US Open 2018 Live
US Open 2018 Live Stream
US Open 2018 Live Streaming
US Open Tennis 2018 Live
US Open Tennis 2018 Live Stream
US Open Tennis 2018 Live Streaming
US Open 2018 TV Channel
US Open 2018 Dates
US Open Tennis Championships
US Open Tennis Championships 2018
Clemson Football
ReplyDeleteClemson Football 2018
Clemson Football Schedule
Clemson Football 2018 Schedule
Clemson Football Live
Clemson Football Live Streaming
Clemson Football Live Stream
Clemson Tigers Football
https://clemsonfootball.de/
UFC 229: Khabib vs. McGregor is a upcoming mixed martial arts event made by the Ultimate Fighting Championship which will be held on October 6, 2018 at T-Mobile Arena in Paradise, Nevada, a portion of the Las Vegas Metropolitan region.
ReplyDeleteThe incident is expected to be headlined using a UFC Lightweight Championship bout between current winner Khabib Nurmagomedov and former featherweight and lightweight winner Conor McGregor.McGregor caught the lightweight title at UFC 205, when he had been the reigning featherweight champion.The Irishman never defended the name, because he took off some time in 2017 because of the arrival of his first son and afterwards venturing himself at a boxing game against Floyd Mayweather Jr. (where he lost).
https://ufc229fightlive.com/
ReplyDeleteFast forward to the conclusion of Jedrzejczyk's scrum alongside a reporter circled back into asking her for a prediction. When Jedrzejczyk revealed she was 50/50, the reporter subsequently altered to asking her about McGregor's behavior.
UFC 229 Live Stream Online
The 2018 Country Music Association has announced that the 52nd annual CMA Awards Live Stream. Country Music Association it's called CMA. annual music awards program on network broadcast here.
ReplyDeleteCheck live cricket score, schedule, results, scorecard, and ball by ball commentary, upcoming matches list on Cricket Country. Latest Cricket News Today Headlines, live cricket match score online news on Cricket Country along with player stats, player profiles, team profiles and live cricket commentary on CricketCountry.comFind latest cricket news, IPL, World Cup 2019 Live Cricket Score, Match Coverage, Schedule, Photos, Cricket Match Highlights, and live updates. Stay updated on Cricket News on CricketCountry.Australia’s ICC Cricket World Cup 2019 preparations are officially underway with 15 men now summoned to walk Justin Langer’s carefully plotted path towards a sixth title.The squad will convene for the first time on Friday for the start of a week-long training camp in Brisbane, where plans will be put into practice and shaped.
ReplyDelete
ReplyDeleteفني تظيف مكيفات بالرياض
شركة تنظيف افران بالرياض
شركة تركيب غرف نوم بالرياض
فني تركيب مكيفات بالرياض
شركة تركيب اثاث ايكيا بالرياض
online software learning
ReplyDeleteThe article you've shared here is fantastic because it provides some excellent information that will be incredibly beneficial to me. Thank you for sharing that. Keep up the good work. Tennis Live Streaming 2022
ReplyDeleteFor the love of travelling, we're here to explore the spectacular beauty of nature. Join us in our hunt for the most beautiful places. Let's explore together https://travelingtotally.com/!
ReplyDelete