कोडिंग इंटरव्यू: डेटा स्ट्रीम से मीडियन निकालना

समस्या और लागू संदर्भ

MedianFinder को दो operations के साथ डिज़ाइन करें:

• addNum(num) स्ट्रीम में एक integer जोड़ता है।
• findMedian() अब तक देखे गए प्रत्येक मान का मीडियन लौटाता है। विषम संख्या होने पर यह मध्य मान लौटाता है; सम संख्या होने पर यह दो मध्य मानों का औसत लौटाता है।

केवल insertions मानें, कोई deletion नहीं, और findMedian() को कम से कम एक insertion के बाद ही कॉल किया जाता है। Inputs में ऋणात्मक संख्याएँ, duplicates, और signed 32-bit integers शामिल हो सकते हैं, अधिकतम 50,000 operations के साथ। लक्ष्य insertion पर O(log n), query पर O(1), और O(n) space है।

उदाहरण के लिए, 5, 2, 10, 4 insert करने के बाद, running medians 5, 3.5, 5, 4.5 हैं। प्रत्येक query पर sort करना सही है लेकिन प्रति query O(n log n) का खर्च आता है। एक array को पूरी तरह sorted रखने से query O(1) हो जाती है, लेकिन बीच में insert करने पर अभी भी O(n) elements shift होते हैं।

2026 में सार्वजनिक interview-preparation सामग्री इसे एक प्रतिनिधि two-heaps coding समस्या के रूप में प्रस्तुत करती रहती है। यह सामान्य software, backend, data, और infrastructure coding rounds पर लागू होती है। उपयोगी संकेत "max-heap plus min-heap" वाक्यांश याद करना नहीं है। यह query से संरचना को derive करना, दोनों invariants बताना, और यह साबित करना है कि एक निश्चित transfer sequence partition को क्यों सुरक्षित रखती है।

Interviewer क्या मूल्यांकन कर रहा है

पहला संकेत operation mix से एक संरचना चुनना है। एक median केवल sorted क्रम के मध्य पर निर्भर करता है, इसलिए पूरा क्रम बनाए रखना अनावश्यक है। O(1) में उत्तर देने के लिए, एक या दो मध्य candidates हमेशा सीधे पठनीय स्थितियों पर उपलब्ध होने चाहिए। Heap tops ठीक वही boundary access प्रदान करते हैं।

दूसरा संकेत partition और balance दोनों बनाए रखना है:

1. एक max-heap lower छोटे आधे भाग को store करता है, एक min-heap upper बड़े आधे भाग को store करता है, और lower का प्रत्येक

मान upper के प्रत्येक मान से अधिकतम होता है।

1. lower का आकार upper के समान है या उससे ठीक एक अधिक है।

अकेली कोई भी शर्त पर्याप्त नहीं है। समान आकार मानों को गलत आधे भाग में रखे जाने से नहीं रोकता। सही partition क्रम एक heap को बहुत बड़ा होने से नहीं रोकता, जिससे उसका top मध्य का प्रतिनिधित्व करना बंद कर देता।

तीसरा संकेत सटीक complexity विश्लेषण है। एक insertion heap operations की एक स्थिर संख्या करती है, प्रत्येक O(log n)। एक query एक या दो tops पढ़ती है, इसलिए यह O(1) है। संरचना अभी भी प्रत्येक input को store करती है और इसलिए O(n) space उपयोग करती है। यहाँ "Streaming" का अर्थ online updates है, न कि constant memory।

अंत में, interviewer sample से परे validation की तलाश करता है। एक मजबूत उत्तर पहले element, सम और विषम counts, duplicates, सभी-ऋणात्मक मान, बढ़ते और घटते sequences, और integer extremes को test करता है। यह random operation sequences की तुलना एक धीमे, स्पष्ट रूप से सही sorted-list model से भी करता है।

उत्तर देने से पहले स्पष्टीकरण प्रश्न

• क्या केवल inserts हैं, या पुराने मान delete भी होने चाहिए? केवल inserts के लिए दो साधारण heaps पर्याप्त हैं। एक sliding window को lazy deletion या एक ordered multiset की आवश्यकता है।
• क्या query एक खाली stream पर चल सकती है? यह prompt नहीं कहता। एक production API को एक खाली top पढ़ने के बजाय optional value लौटानी चाहिए या explicit error उठानी चाहिए।
• क्या inputs integers हैं या floating-point values? यह version integers उपयोग करता है। यदि floating-point NaN की अनुमति है, तो मान एक सामान्य total order नहीं बनाते, इसलिए rejection या ordering semantics को परिभाषित किया जाना चाहिए।
• सम संख्या के लिए median कैसे परिभाषित है? यह prompt दो मध्य मानों के arithmetic mean का उपयोग करता है, इसलिए return type को fractions represent कर सकना चाहिए।
• क्या result सटीक होनी चाहिए? हाँ। एक fixed memory budget के अंतर्गत unbounded stream को इसके बजाय approximate quantile contract की आवश्यकता होती है।
• क्या averaging overflow हो सकता है? Python integers overflow नहीं होते। Fixed-width languages को addition और division से पहले दोनों operands को promote करना चाहिए।
• query-to-insert ratio क्या है? दो heaps बारंबार queries के लिए उपयुक्त हैं। यदि median केवल एक बार सारा input आने के बाद माँगा जाता है, तो collect करना और sort करना आमतौर पर सरल है।
• क्या concurrent access आवश्यक है? implementation single-threaded है। एक concurrent version को transfers और queries के लिए दोनों heaps की एक state observe करनी होगी।

30-सेकंड उत्तर Framework

"मैं छोटे आधे भाग को lower नामक max-heap में और बड़े आधे भाग को upper नामक min-heap में रखूँगा। lower का प्रत्येक मान upper के प्रत्येक मान से अधिकतम होना चाहिए, और lower का आकार समान या एक अधिक होना चाहिए। Insertion पर, मैं पहले lower में push करता हूँ, partition क्रम बहाल करने के लिए इसके maximum को upper में move करता हूँ, और यदि upper बड़ा हो जाए तो upper का minimum वापस move करता हूँ। विषम count के लिए, median lower का top है; सम count के लिए, यह दोनों tops का औसत है। Insertion O(log n) heap operations की एक स्थिर संख्या उपयोग करती है, query O(1) है, और space O(n) है।"

चरण-दर-चरण विस्तृत विवेचन

चरण एक: baseline approaches की तुलना करें और bottleneck की पहचान करें।

Binary search O(log n) में एक array insertion index ढूँढता है, लेकिन यह O(n) shifting cost को नहीं हटाता। एक regular balanced tree क्रम बनाए रखता है, लेकिन subtree sizes के बिना यह kth element को सीधे नहीं चुन सकता। दो heaps median के लिए केवल दो आवश्यक boundaries बनाए रखते हैं, जो उन्हें इस contract के लिए सबसे छोटी complete संरचना बनाता है।

चरण दो: median को एक या दो heap tops के रूप में फिर से लिखें।

मान लीजिए lower में छोटा आधा भाग max-heap में है, जो उस आधे भाग का सबसे बड़ा मान expose करता है। मान लीजिए upper में बड़ा आधा भाग min-heap में है, जो उस आधे भाग का सबसे छोटा मान expose करता है। lower को एक अतिरिक्त element की अनुमति दें:

Odd total:  lower has one extra, median = max(lower)
Even total: heaps have equal sizes, median = (max(lower) + min(upper)) / 2

व्यापक रूप से उपलब्ध Python heapq interface min-heaps पर आधारित है। implementation को सामान्य Python versions में portable रखने के लिए, lower में negated values store करें। एक logical maximum x सबसे छोटे stored negative value -x बन जाता है, इसलिए -lower[0] lower half का maximum है।

चरण तीन: एक निश्चित push, transfer, और rebalance sequence का उपयोग करें।

नए मान के लिए प्रत्येक संभावित destination पर branching करने के बजाय, हमेशा:

1. Negated num को lower में push करें।
2. lower का logical maximum pop करें और इसे upper में push करें।
3. यदि upper अब बड़ा है, तो इसका minimum वापस lower में move करें।

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.lower = []  # Negated max-heap containing the smaller half
        self.upper = []  # Min-heap containing the larger half

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def find_median(self) -> float:
        if not self.lower:
            raise ValueError("median is undefined for an empty stream")

        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

यह sequence एक apparently extra transfer करती है, लेकिन यह कई error-prone cases को हटा देती है। एक अन्य valid implementation num की तुलना -lower[0] से करता है, एक heap चुनता है, और फिर rebalance करता है। दोनों की asymptotic cost समान है। एक interview में, उस version को प्राथमिकता दें जिसके invariants आप विश्वसनीय रूप से prove और review कर सकते हैं।

चरण चार: order invariant को साबित करें।

Insertion से पहले मान लें कि lower का प्रत्येक मान upper के प्रत्येक मान से अधिकतम है। नए मान को अस्थायी रूप से lower में push करने के बाद, केवल वही नया मान गलत आधे भाग में हो सकता है। बड़े हुए lower का maximum pop करें:

• lower में बचा प्रत्येक मान popped value से अधिकतम है।
• हर पुराना lower मान पहले से ही हर पुराने upper मान से अधिकतम था।
• इसलिए, popped maximum को upper में जोड़ने के बाद, हर नया lower मान अभी भी हर नए

upper मान से अधिकतम है।

उस transfer के बाद, upper में एक अतिरिक्त element हो सकता है। इसका minimum वापस lower में move करने से क्रम सुरक्षित रहता है: moved value upper में बचे हर चीज़ से अधिकतम है और पुरानी lower boundary से कम नहीं है। Heaps के बाद समान आकार होते हैं या lower में एक अतिरिक्त होता है।

दोनों invariants दो खाली heaps के लिए valid हैं। प्रत्येक insertion उन्हें सुरक्षित रखती है, इसलिए induction द्वारा tops किसी भी operation sequence के बाद मध्य positions का प्रतिनिधित्व करते हैं।

चरण पाँच: partition को पार करने वाली एक sequence trace करें।

Insert 5:  lower = [5]       upper = []        median = 5
Insert 2:  lower = [2]       upper = [5]       median = 3.5
Insert 10: lower = [5, 2]    upper = [10]      median = 5
Insert 4:  lower = [4, 2]    upper = [5, 10]   median = 4.5

एक heap की backing array पूरी तरह sorted नहीं है। [4, 2] का अर्थ केवल यह है कि 4 max-heap top है। Debug checks को heap order, दो tops, और cross-heap invariant verify करना चाहिए, न कि backing arrays की sorted lists के रूप में तुलना करनी चाहिए।

चरण छह: complexity calculate करें और पहचानें कि कब एक simpler approach बेहतर है।

add_num अधिकतम पाँच pushes या pops करता है। प्रत्येक heap operation O(log n) है, इसलिए एक स्थिर संख्या O(log n) रहती है। find_median lengths और heap tops को O(1) में पढ़ता है। प्रत्येक मान ठीक एक heap में रहता है, जिससे O(n) space बनती है।

यदि कोई product एक batch collect करता है और अंत में एक median माँगता है, तो array store करना और sort करना छोटा है और बेहतर contiguous-memory behavior हो सकता है। एक online structure बनाए रखना अनावश्यक है। यदि हर मान 0 से 100 की fixed range में है, तो 101 counts की एक array O(1) insertion देती है और 101 fixed buckets का एक scan, उस fixed domain के लिए भी constant।

चरण सात: deterministic cases और randomized differential testing से loop बंद करें।

कम से कम test करें:

एक randomized test के लिए, प्रत्येक generated integer को MedianFinder और एक reference array दोनों में जोड़ें। Reference को sort करें और प्रत्येक insertion के बाद इसका मध्य calculate करें। दोनों results की तुलना करें और assert करें कि len(lower) len(upper) के बराबर है या एक अधिक है। Slow model target performance के लिए अनुपयुक्त है लेकिन correctness oracle के रूप में उत्कृष्ट है।

उच्च-गुणवत्ता नमूना उत्तर

"मैं पहले confirm करूँगा कि यह एक insert-only exact median है और queries खाली stream पर नहीं होती। यदि पुराने window elements delete होने चाहिए, तो ordinary heaps arbitrary values को efficiently remove नहीं कर सकते, इसलिए design बदलती है।

Constant-time queries के लिए, मैं चाहता हूँ कि sorted क्रम का मध्य structure boundaries पर लगातार exposed रहे। मैं छोटे आधे भाग के लिए एक max-heap lower और बड़े आधे भाग के लिए एक min-heap upper उपयोग करूँगा। दो invariants मायने रखते हैं: lower का प्रत्येक मान upper के प्रत्येक मान से अधिकतम है, और lower का आकार समान या एक अधिक है।

Insertion पर मैं एक fixed three-step sequence उपयोग करता हूँ। नया मान lower में push करें, partition बहाल करने के लिए lower का maximum upper में move करें, और यदि upper बड़ा हो जाए तो upper का minimum वापस move करें। दोनों invariants तब फिर से valid हो जाते हैं। विषम count के साथ, lower में extra value होती है और इसका top median है। सम count के साथ, मैं दोनों tops का औसत लेता हूँ।

Insertion heap operations की एक स्थिर संख्या करती है, इसलिए यह O(log n) है। Query tops को O(1) में पढ़ती है, और प्रत्येक मान retain करने में O(n) space लगती है। मैं एक element, सम counts, duplicates, negative values, monotonic input, और integer extremes test करूँगा, फिर sort-on-every-step model के विरुद्ध randomized differential tests चलाऊँगा। यदि values 0 से 100 तक सीमित हैं, तो मैं 101 counters उपयोग करूँगा; यदि केवल एक final query है, तो मैं simply sort करूँगा।"

सामान्य गलतियाँ

• केवल heap sizes को balance करें → values partition को पार कर सकती हैं और tops दो मध्य values नहीं होते → order और size दोनों invariants बनाए रखें।
• छोटे आधे भाग को min-heap में रखें → इसका top global minimum है, lower half का maximum नहीं → छोटे आधे भाग के लिए max-heap उपयोग करें।
• सम count के लिए एक top लौटाएँ → median definition गलत है → sizes समान होने पर दोनों tops का औसत लें।
• Conversion से पहले fixed-width integers जोड़ें → दो बड़े values पहले overflow हो सकते हैं → जोड़ने और भाग देने से पहले दोनों operands को promote करें।
• Sorted-array insertion को O(log n) कहें → index ढूँढना तेज़ है लेकिन shifting O(n) रहती है → search cost को mutation cost से अलग करें।
• Python के heap array को fully sorted मानें → debugging assertions invalid हो जाती हैं → केवल root और parent-child heap property पर निर्भर रहें।
• खाली heap से index zero पढ़ें → एक unclear boundary पर failure होती है → empty queries forbid करें या explicitly optional value लौटाएँ।
• दावा करें कि online algorithm constant space उपयोग करता है → दोनों heaps सभी inputs retain करते हैं → exact median के लिए O(n) space बताएँ।
• Sliding window के लिए same code पुनः उपयोग करें → expired values एक top पर रह सकती हैं और result को corrupt कर सकती हैं → lazy deletion और valid sizes जोड़ें, या ordered multiset उपयोग करें।
• केवल sample test करें → negation, duplicate, और rebalance bugs trigger नहीं हो सकते → edge cases को randomized differential testing के साथ combine करें।

अनुवर्ती प्रश्न और उत्तर

अनुवर्ती प्रश्न 1: यदि प्रत्येक integer 0 और 100 के बीच हो तो क्या बदलता है?

101 counts और कुल element count की एक array रखें। Insertion O(1) में एक bucket increment करती है। Query के लिए, एक या दो मध्य ranks तक पहुँचने तक buckets scan करें। Scan और space इस fixed domain के लिए constant हैं। यदि range input के साथ बढ़ती है, तो scan range size O(R) के लिए R है और इसे अब constant नहीं कहा जाना चाहिए।

अनुवर्ती प्रश्न 2: यदि 99% values 0 और 100 के बीच हों लेकिन बाकी arbitrary हों तो?

In-range values के लिए 101 counters और 0 से नीचे और 100 से ऊपर के values के लिए order-statistic structures रखें। उनकी counts यह निर्धारित करती हैं कि target rank lower outliers, fixed range, या upper outliers में है; फिर relevant structure के भीतर select करें। Ordinary heaps arbitrary rank selection को support नहीं करते, इसलिए 99% statement अकेले constant-time queries को justify नहीं करता। एक adversarial prefix अभी भी median rank को outliers के बीच रख सकता है।

अनुवर्ती प्रश्न 3: Latest k values का median कैसे compute करेंगे?

Window movement के लिए outgoing value को delete करना आवश्यक है। Binary heaps किसी arbitrary entry को efficiently locate नहीं कर सकते। एक सामान्य solution एक delayed-deletion count map जोड़ता है और दोनों heaps के लिए valid sizes track करता है। एक outgoing value को logically deleted mark करें, और physically तभी pop करें जब वह एक top पर पहुँचे; median पढ़ने से पहले दोनों tops को prune करें। Updates amortized O(log k) हैं, जबकि top lookup O(1) रहता है। जब language इसे provide करती है तो duplicate support वाला balanced multiset सरल है।

अनुवर्ती प्रश्न 4: क्या एक fixed-memory algorithm unbounded stream का exact median लौटा सकता है?

सामान्यतः, arbitrary integer streams के लिए नहीं। एक discarded historical value बाद में middle rank निर्धारित कर सकती है। Contract को approximate quantile में बदलना होगा, explicit rank-error guarantee, confidence requirement, और merge behavior के साथ quantile sketch उपयोग करते हुए। यह exact two-heaps structure से एक अलग उत्तर है।

अनुवर्ती प्रश्न 5: Concurrent insertions और queries को कैसे support करेंगे?

दोनों heaps एक logical state बनाते हैं। सबसे सरल correct extension पूरे add_num और find_median operations को same mutex से protect करती है, एक query को उस क्षण observe करने से रोकती है जब एक value lower छोड़ने के बाद upper में enter करने से पहले होती है। एक read-heavy service immutable median snapshots publish कर सकती है, लेकिन snapshot interval एक freshness trade-off introduce करता है जो API contract में होना चाहिए।

अनुवर्ती प्रश्न 6: कई shards के medians को global median में combine किया जा सकता है?

नहीं। एक shard median अपने shard का size और distribution खो देता है; shard medians का weighted average भी global median नहीं है। एक exact result के लिए एक structure चाहिए जो global rank का उत्तर दे सके, जैसे bounded domain पर counts aggregate करना और distributed selection perform करना। एक approximate result mergeable quantile summaries उपयोग कर सकता है। Global structure से पहले precision और latency requirements चुनी जानी चाहिए।