मेरा पसंदीदा Software Engineering इंटरव्यू सवाल: Median की गणना

 (krisshamloo.com)
1 पॉइंट द्वारा GN⁺ 4 시간 전 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • टेक्निकल इंटरव्यू में छोटे implementation सवाल पहेलियों की तुलना में अधिक प्रभावी हो सकते हैं, और median की गणना बुनियादी coding क्षमता और design sense दोनों को साथ में दिखाती है
  • यह sorting की मांग करने वाली समस्या है, इसलिए इससे स्वाभाविक रूप से ऐसे API सवाल निकलते हैं जैसे function खुद sort करे या caller sort करे, और क्या मूल array को बदला जा सकता है
  • odd और even length को अलग करने वाली branch, index calculation, और off-by-one गलतियां उम्मीदवार की debugging प्रक्रिया को देखने के लिए उपयुक्त हैं
  • median और average के अंतर, test लिखने की आसानी, और Python की statistics standard library की जानकारी तक, इस छोटे सवाल के भीतर बहुत कुछ जांचा जा सकता है
  • उदाहरण implementation खाली list पर ValueError फेंकता है, sorted() से copy sort करता है, फिर even length पर बीच के दो मानों का average और odd length पर बीच का मान लौटाता है

Median समस्या इंटरव्यू के लिए उपयुक्त क्यों है

  • अच्छा टेक्निकल इंटरव्यू सवाल कोई उलझी हुई puzzle नहीं होना चाहिए, बल्कि सहज implementation के भीतर से गहरे विषय निकाल पाने वाला होना चाहिए
  • “संख्याओं की array लेकर median लौटाने वाला function लिखिए” जैसा सवाल यह जांचने के लिए अच्छा Fizz Buzz-प्रकार का संकेत है कि उम्मीदवार वास्तव में programming कर सकता है या नहीं
  • array के मानों को घटाकर एक परिणाम तक लाना बुनियादी क्षमता का हिस्सा है, और समस्या इतनी छोटी भी है कि बातचीत और debugging दोनों को साथ में देखना आसान होता है

Implementation के दौरान सामने आने वाले निर्णय बिंदु

  • median की गणना के लिए पहले sorting चाहिए
    • यह तय करना होता है कि function खुद sort करे या caller sorted array दे
    • जब array reference से pass हो, तब क्या मूल को बदलना स्वीकार्य है, यह भी API contract का हिस्सा बनता है
    • ऐसे विकल्प performance discussion से भी जुड़ते हैं
  • index calculation में off-by-one का जाल होता है
    • गलती हुई या नहीं, उससे ज्यादा महत्वपूर्ण यह देखना है कि उम्मीदवार छोटी समस्या को debug कैसे करता है
  • array की length के अनुसार return value बदलती है
    • even length में बीच के दो मानों का average लौटाया जाता है
    • odd length में बीच का मान लौटाया जाता है

छोटे सवाल से आगे बढ़ती बातचीत

  • median, average की तुलना में अधिकतर स्थितियों में क्यों बेहतर विकल्प हो सकता है, इस तरह की statistics discussion तक बात जा सकती है
  • input और expected value सरल होने से इसे test करना आसान है, इसलिए उम्मीदवार अपने testing sense को अच्छे से दिखा सकता है
  • Python में statistics standard library की जानकारी दिखाने का मौका भी मिलता है

उदाहरण Python implementation की पसंद

  • खाली list पर ValueError("median called with empty list") उठाया जाता है
  • sorted(numbers) का उपयोग किया जाता है, इसलिए numbers.sort() के विपरीत input list सीधे sort नहीं होती
  • length को len(numbers) से लिया जाता है, और middle index को mid = length // 2 से निकाला जाता है
  • even length में (numbers[mid - 1] + numbers[mid]) / 2.0 लौटाया जाता है, और odd length में numbers[mid] लौटाया जाता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 4 시간 전
Lobste.rs की राय

  • यह लेख ठीक से समझ नहीं आता। लगता है लेखक को पता नहीं कि median को O(n) में निकाला जा सकता है। संदर्भ: https://rcoh.me/posts/linear-time-median-finding/
    इसलिए “शुरू से ही संख्याएँ sorted होनी चाहिए” कहना गलत है। इसी वजह से मुझे यह अच्छा interview problem भी नहीं लगता। optimal solution एक जटिल algorithm है, इसलिए अगर किसी ने इसे रटकर न सीखा हो तो उससे मौके पर इसकी उम्मीद करना मुश्किल है, और अगर रटकर सीखा भी हो तो उससे candidate का मूल्यांकन करने में खास मदद नहीं मिलती।
    इसकी बजाय candidate से array को library function से sort करके बीच का मान लौटाने वाला naive solution लिखने को कहा जा सकता है

    • मुझे लगभग गुस्सा आ गया था क्योंकि मैंने इस problem का n*log(n) solution दिया था और phone interview में reject कर दिया गया था
      बाद में algorithms class में quickselect सीखा, और सोचा, “उम्मीद है वे यह नहीं चाह रहे थे कि मैं इसे वहीं तुरंत सोच लूँ।” खैर, शायद वह role मेरे लिए सही नहीं था
    • मैं ही लेखक हूँ। अगर candidate quickselect का ज़िक्र करे तो वह काफ़ी प्रभावशाली लगेगा। फिर भी मुझे नहीं लगता कि यह खराब सवाल है। सिर्फ intuitive algorithms से भी बात करने के लिए बहुत कुछ है
      जहाँ तक “array को library function से sort करके बीच का मान लौटाने वाले naive solution” की उम्मीद की बात है, मैं candidate से python standard library से बेहतर code की उम्मीद नहीं करता

  • bonus के तौर पर, इससे तुरंत पता चल जाता है कि किसी ने algorithms पढ़े हैं या कम से कम interview की तैयारी की है। वे quickselect इस्तेमाल करने का सुझाव देंगे: https://en.wikipedia.org/wiki/Quickselect

    • इसका ज़िक्र न होना मुझे हैरान करता है। अगर मुझे यह सवाल मिलता और मैं C++ इस्तेमाल कर रहा होता, तो शायद nth_element इस्तेमाल करता
      और अगर quickselect को शुरुआत से खुद लिखना पड़े, तो वह भी किया जा सकता है। मूल रूप से यह partition + binary search के काफ़ी करीब है
    • वास्तव में मुझे ऐसा नहीं लगता। यह सवाल ज़्यादा एक बुनियादी “क्या यह व्यक्ति सच में programming कर सकता है?”, यानी “क्या screener ने अपना काम ठीक से किया?” जैसी जाँच लगता है। भले ही मैं quickselect को ज़ुबानी बता सकूँ, मुझे नहीं लगता कि मैं उसे पूरी तरह सही कर पाऊँगा, और interviewer का समय बर्बाद न करने के लिए मैं naive solution चुनूँगा
    • जब array की length even हो, तब मामला दिलचस्प हो जाता है। बीच के दो indices के लिए सामान्य quickselect दो बार चलाया जा सकता है, या काम के हिसाब से quickselect को adjust किया जा सकता है। दोनों असल में लगभग एक ही बात हो सकती हैं
    • यह requirement कि list का sorted होना ज़रूरी है, मुझे भ्रमित कर गई। सहज रूप से भी यह ज़रूरी नहीं लगता
    • LLM ने मुझे यही जवाब दिया था, और बोनस में एक immutable variant भी दिया था जिसे ज़रूरत पड़ने पर चुना जा सकता है

  • Python का int type overflow नहीं करता, लेकिन अगर आप C, C++ या Go इस्तेमाल कर रहे हों, तो even-length array वाले branch में addition overflow की चिंता नहीं करनी चाहिए?

    • वह addition int में नहीं बल्कि float में होता है। फिर भी overflow होकर inf बनने की संभावना है। अगर array के दोनों elements sys.float_info.max हों, तो जवाब भी sys.float_info.max होना चाहिए, लेकिन addition का परिणाम inf होगा और उसे 2 से divide करने पर भी inf ही रहेगा
      इसे ठीक करने के लिए आप addition पर 2 से divide करने को distribute कर सकते हैं, लेकिन तब subnormal numbers में गलत जवाब मिलेगा। ज़्यादातर लोग शायद मान लेते हैं कि program में इतने बड़े numbers आएँगे ही नहीं कि यह समस्या हो। यहाँ numpy भी warning के साथ inf देता है: 
      >>> import sys  
>>> import numpy  
>>> numpy.median([sys.float_info.max, sys.float_info.max])  
.../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
  ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
np.float64(inf)

  • वास्तव में median चुनने के भी कई तरीके हैं। जैसे आप linear interpolation करेंगे, upper bound लेंगे, या lower bound लेंगे
    और quantiles तक पहुँचते-पहुँचते इस पर घंटों बात की जा सकती है। एक मान चुनना और कई मान एक साथ चुनना, दोनों के लिए अलग approach चाहिए

  • मैं मूल पोस्ट जैसे interview problems इस्तेमाल नहीं करता। मैं smoothness चाहता हूँ, यानी problem की कठिनाई candidate की क्षमता और अनुभव के अनुसार सहज रूप से बदलनी चाहिए। खासकर अगर library functions, quickselect, या radix sort जैसे algorithms के बारे में जानकारी अचानक परिणाम को बहुत बदल दे, तो वह measurement के लिए अच्छा सवाल नहीं है
    तब आप candidate के अनुभव और क्षमता को नहीं, बल्कि यह परख रहे होते हैं कि उसे कोई खास magic artifact पता है या नहीं। follow-up questions से इसे कुछ हद तक सुधारा जा सकता है, लेकिन शुरू से ही ज़्यादा smooth problem देना बेहतर है

    • अगर आप साझा कर सकें, तो ऐसे smooth problems के कुछ ठोस उदाहरण जानने में मुझे बहुत दिलचस्पी होगी