- Microsoft इंटरव्यू puzzle के रूप में पेश किया गया number guessing game binary search और expected value के बारे में पूछता है, लेकिन संख्या को random चुनने की शर्त में “प्रतिभागी के लिए नुकसानदेह” वाला निष्कर्ष गलत है
- नियम यह है कि 1~100 के बीच की संख्या को hints के आधार पर range घटाते हुए पहचानना है, और सही जवाब तक पहुंचने में लगने वाली guesses की संख्या बढ़ने पर $5 से शुरू होने वाला reward घटता जाता है, बाद में प्रतिभागी को पैसे देने पड़ते हैं
- यह बात सही है कि Ballmer जानबूझकर मुश्किल संख्या चुन सकता है, और binary search strategy में भी 37 खास संख्याएँ 7वीं guess पर ही मिलती हैं, जिससे प्रतिभागी को $1 चुकाना पड़ता है
- अगर संख्या random हो, तो Perl code और probability calculation दोनों में गेम का expected value $0.20 निकलता है, यानी प्रतिभागी के लिए positive expected value है
- अगर $0 reward वाला चरण न होता और 6वीं guess से ही प्रतिभागी को पैसे देने पड़ते, तो expected value -$0.49 होता और Ballmer का निष्कर्ष सही निकलता
Number guessing puzzle के नियम
- Steve Ballmer ने एक छोटे वीडियो में वह puzzle बताया जो उन्होंने Microsoft इंटरव्यू उम्मीदवारों से पूछा था
- एक व्यक्ति 1 से 100 के बीच की संख्या सोचता है, और उम्मीदवार हर guess पर “ऊपर” या “नीचे” जैसा hint पाकर range को संकुचित करता है
- reward सही guess की संख्या पर निर्भर करता है
- 1वीं guess: $5
- 2वीं: $4
- 3वीं: $3
- 4वीं: $2
- 5वीं: $1
- 6वीं: $0
- 7वीं: प्रतिभागी $1 देता है
- 8वीं: प्रतिभागी $2 देता है
- 9वीं: प्रतिभागी $3 देता है
- मुख्य सवाल है: “क्या यह गेम स्वीकार करना चाहिए?”
- Ballmer का निष्कर्ष “No” था, और उसके दो कारण थे
- वह खुद सबसे मुश्किल संख्या चुन सकता है
- वह संख्या random चुने तब भी expected value negative है, इसलिए प्रतिभागी को Ballmer को पैसे देने पड़ेंगे
जहां Ballmer सही था: वह विरोधी ढंग से संख्या चुन सकता है
- Ballmer का मुश्किल संख्या चुन सकने वाला पहला कारण सही है
- संख्या के random चुने जाने की शर्त में binary search strategy optimal है
- binary search इस्तेमाल करने पर भी, अगर Ballmer कुछ खास संख्याएँ चुने, तो प्रतिभागी को $1 देना पड़ेगा
- वे संख्याएँ हैं 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98, 100
- बाकी संख्याओं पर या तो $0 मिलता है या positive reward मिलता है
- $0 देने वाली संख्याएँ हैं 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95, 99
- बाकी संख्याओं पर प्रतिभागी Ballmer के पैसे में से कुछ जीतता है
संख्या 59 का उदाहरण
- Ballmer ने वीडियो में 59 चुना
- binary search strategy के अनुसार 50, 75, 62, 56, 59 के क्रम में 5 guesses में इसे पाया जा सकता है
- इस स्थिति में इंटरव्यूअर Emily Chang को $1 मिलता है
- Emily Chang की वास्तविक guesses 50, 75, 60, 55, 57, 58, 59 थीं, जो binary search के 5-step समाधान के काफी करीब थीं
Random selection होने पर expected value positive है
- अगर मान लें कि Ballmer संख्या random चुनता है, तो expected value negative है वाला निष्कर्ष गलत है
- Perl code 1~100 की हर संख्या के लिए binary search से पता लगाता है कि उसे कितनी guesses में खोजा जाता है, फिर rewards को जोड़कर average निकालता है
- गणना के अनुसार गेम का expected value $0.20 है
- यही नतीजा probability के नज़रिए से भी पुष्टि किया जा सकता है
- 1वीं guess में 50 चुना जाता है, success probability 1/100 है और reward $5 है
- 2वीं guess में 25 या 75 चुना जाता है, success probability 2/100 है और reward $4 है
- 3वीं guess में 12, 37, 62, 88 चुने जाते हैं, success probability 4/100 है and reward $3 है
- 4वीं guess में 6, 18, 31, 43, 56, 68, 81, 94 चुने जाते हैं, success probability 8/100 है और reward $2 है
- इसके बाद भी यही पैटर्न जारी रहता है
- expected value का सूत्र
5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100है, और परिणाम 0.2 है - आख़िरी
-1 * 37/100पद binary search के अंत तक पहुंचने के बाद बची हुई संभावित संख्याओं को दर्शाता है
गलती कहां हुई हो सकती है
- एक संभावना यह है कि Ballmer का इरादा $0 reward चरण रखने का नहीं था
- अगर नियम “$5, $4, $3, $2, $1, उसके बाद प्रतिभागी $1, $2, $3 देगा” होते, तो expected value -$0.49 होता
- इस variant में Ballmer का “expected value negative है” वाला निष्कर्ष सही बैठता है
1 टिप्पणियां
Hacker News की राय
लेख यह संकेत देता है कि इंटरव्यू देने वाला मानता है कि संख्या randomly चुनी जाती है, लेकिन असल में Ballmer इसे adversarial तरीके से भी चुन सकते हैं
हालांकि अगर इंटरव्यू देने वाला Ballmer के adversarial चयन को मानकर चले, तो वह अपना पहला guess अलग रखकर probability बदल सकता है। मूल लेखक भी मानते हैं कि शुरुआत 50 से होती है, लेकिन binary search की प्रकृति देखते हुए अगर 50 से हटकर शुरुआती मान को हर बार random offset से चुना जाए, तो heuristic को निशाना बनाने वाले सरल adversarial attack को रोका जा सकता है और फिर भी binary search के ज्यादातर फायदे मिल सकते हैं
ऐसे सरल adversarial चयन के जवाब में optimal random offset selection algorithm का analysis देखना चाहूंगा
मैं Ballmer को कहते हुए कल्पना कर सकता हूं: “नहीं, पहला guess 50 से शुरू होना चाहिए। सबको यही पता है”
यानी पहले guess के दोनों तरफ अधिकतम 64 numbers ही होने चाहिए। जैसा कहा गया, अगर इस offset को randomly चुना जाए, तो binary search की खामी का फायदा उठाने वाले ज्यादातर adversarial examples बेअसर हो जाएंगे, और शायद adversarial selection का फायदा ही खत्म हो जाए। हालांकि उस स्थिति में offset के हिसाब से distribution की जरूरत पड़ सकती है
मैं भी ऐसा analysis देखना चाहूंगा
मुख्य बात यह है कि अगर Ballmer randomly चुनें और इंटरव्यू देने वाला उसके अनुसार optimally खेले, तब भी game की expected value negative रहती है, और सिर्फ इतना ही यह भरोसा करने के लिए काफी है कि यह game इंटरव्यू देने वाले के लिए नुकसानदेह है
लेख इस ज्यादा कठिन सवाल का जवाब नहीं देता कि “तो actual expected value कितनी है।” लेकिन अगर इंटरव्यू देने वाला पहला guess 40~60 के बीच randomly चुने और फिर वहां से binary search करे, तो लगता नहीं कि Ballmer को शुरुआत में number randomly चुनने की तुलना में कोई खास बढ़त मिल पाएगी
simulation ने जो एक Nash equilibrium खोजा, उसमें Ballmer वाला पक्ष range के दोनों सिरों के पास mix करके चुनता है। हमेशा 1 या 100 नहीं, लेकिन उनके आसपास। नतीजा यह आया कि Ballmer player प्रति round करीब 0.85~1.00 dollar की expected value से जीतता है
नतीजतन guess करने वाली side की strategy भी binary search को range के extreme से शुरू करके, किसी एक side को hit करने की उम्मीद वाली बन जाती है। यह football penalty kick में kicker और goalkeeper के एक-दूसरे की direction चुनने जैसा है। goalkeeper वही side चुनना चाहता है, kicker opposite side चाहता है। लेकिन यहां 100 choices हैं, इसलिए goal बहुत चौड़ा लगता है
अब मुझे लगता है कि अगर बाकी choices को binary search pattern से न बांधा जाए, तो equilibrium पूरी तरह बदल जाएगा और player के results बेहतर होंगे। हालांकि हर range के लिए strategy choice आ जाएगी, इसलिए calculation कहीं ज्यादा भारी हो जाएगी। और यह करते-करते मैंने 2 घंटे काम से बचने में लगा दिए, जो अच्छा नहीं है। फिर भी यह जानने की curiosity है कि binary search constraint हटाने पर क्या होता है
हाल ही में एक जटिल domain, payments, में senior role के लिए interview दिया था, और इस क्षेत्र में 10 साल से ज़्यादा काम किया है
अमेरिका ही नहीं, UK और EU के ज़्यादातर jurisdictions में payments की बारीक जानकारी होने के कारण interview बेदाग़ चला। Senior role होने की वजह से subject expertise से ज़्यादा influence, सहज communication और conflict management अहम थे, और वह हिस्सा भी अच्छा रहा। उन्होंने जानबूझकर एक ऐसे बदमिज़ाज senior manager को लगाया जो लगातार बीच में टोकता रहा, और बाद का feedback यह था कि conflict handling की masterclass थी
Final round एक business stakeholder के साथ था जो खुद को de facto domain expert मानता था, और वह payments से जुड़े trivia questions लगातार पूछता रहा। ऐसा लगा जैसे योजना यह थी कि जितना हो सके उतना trivia खंगाला जाए और reject करने के लिए कोई एक आधार ढूंढ लिया जाए
आख़िरी सवाल था कि क्या real-time payments का वास्तविक अनुभव है, और कई देशों में ऐसा अनुभव था। अमेरिका का FedNow बहुत हाल में आया था, इसलिए उसके specs पढ़े थे और build vs buy तय करने के लिए कुछ vendors को evaluate किया था। उसने इसी आधार पर real-time payments experience नहीं है कहते हुए negative recommendation दे दी
सच कहूं तो मैं ऐसे माहौल में काम नहीं करना चाहता। वह एक बड़ा अमेरिकी bank था, और सबसे बड़ी समस्या product innovation या customer focus नहीं, बल्कि operational outages थी। Payments expertise से अलग, यह वह क्षेत्र है जिसे मैंने कई बड़े enterprises में संभालकर सुधारा है, और यह बात भी साफ़ तौर पर बताई थी। फिर भी अगर किस्मत अच्छी हो, तो ऐसी जगह के अप्रिय होने का पता कष्ट झेलकर लगाने की ज़रूरत नहीं पड़ती
यह न सिर्फ़ संकेत है कि company में toxic culture है, बल्कि यह भी कि वे उस culture को स्वीकार करते हैं। ऐसी जगहें conflict पसंद करने वाले लोगों को आकर्षित करती हैं, और ऐसे लोग पर्याप्त हो जाएं तो वही culture बना देते हैं
यह बात अक्सर नहीं कही जाती, लेकिन conflict leadership failure है। कई बार कोई बहुत senior leader बस उंगली चटकाकर “आप दोनों इसे अंजाम तक पहुंचाइए” कह दे, तो conflict सुलझ जाता है। लेकिन leadership या तो ground से इतनी दूर होती है कि teams को align नहीं कर पाती, या competition के नाम पर teams के भीतर conflict को स्वभावतः बढ़ावा देती है। दोनों ही स्थितियों में ऐसी जगह काम करने के लिए नर्क जैसी हो सकती है
तरीका यह था कि आखिरकार उस बिंदु तक पहुंचा जाए जहां candidate को मौके पर जवाब न पता हो। मकसद hostile या rude होना नहीं था; मैं देखना चाहता था कि क्या वह “मुझे नहीं पता” कह सकता है। न जानना technical work का रोज़मर्रा का हिस्सा है, लेकिन अगर कोई यह बात सहजता से नहीं कह पाता, तो बड़ी समस्या हो सकती है
कुल मिलाकर सबसे सक्षम candidates “मुझे नहीं पता” जवाब देने में सबसे सहज थे। Defensive होना मुझे हमेशा red flag लगता था
Toxic management को कम पैसे पाने वाले internal employees की तुलना में बहुत ज़्यादा fees लेने वाले external consultants और advisors ज़्यादा पसंद आते हैं
पूरी तरह तैयार और योग्य होने के बावजूद, जब process skills और experience का असली assessment न लगकर trivia quiz जैसा लगे, तो बहुत frustration होती है। जैसा दूसरों ने कहा, ऐसा व्यवहार toxic culture का साफ़ संकेत है
और भी अजीब बात यह है कि मूल रूप से इसका उल्टा होना चाहिए। अगर team बढ़ानी हो या किसी को replace करना हो, तो कोशिश यह होनी चाहिए कि मौजूदा लोगों में से किसी से भी बेहतर व्यक्ति मिले
Reject करने की वजह खोजने के लिए छोटी-छोटी बातों में मीन-मेख निकालना या irrelevant details में घुसना बहुत बड़ा red flag है। इसका मतलब है कि innovation या वास्तविक problem solving में रुचि नहीं है। वही अंतहीन operational outages जैसे मुद्दे भी, जिन्हें हम पहले ही दूसरी companies में solve कर चुके होते हैं
ऐसी स्थिति में सबसे अच्छा है कि समय बर्बाद करने के लिए माफ़ी कहें और चले जाएं। लेकिन अगर उस इलाके में वही job हो, तो nonsense झेलने का मन होना भी समझ आता है। फिर भी कभी-कभी वह bullet dodge करना disguised blessing बन जाता है। भले ही उस समय आप मेरी तरह बेरोज़गार हों और पैसे ख़त्म हो रहे हों
पूर्वजों के बारे में तब तक पूछताछ करने जैसा, जब तक जवाब “किसान” न हो जाए
“क्या यह game स्वीकार करना चाहिए?”
बेशक हां। मुझे games पसंद हैं, और game का उद्देश्य मज़ा है। शुरुआती लगभग 20 dollars तक, इसे 10 मिनट तक मज़ेदार game खेलने की लागत माना जा सकता है
ख़त्म होने के बाद आप कह सकते हैं कि “मैंने कभी Steve Ballmer के साथ binary search करते हुए 20 dollars गंवाए थे,” और यह dinner table पर सुनाने लायक line है, इसलिए मेरे लिए इसकी value 20 dollars से ज़्यादा है
शायद Ballmer के दौर में Microsoft के influence खोने की वजह भी कुछ ऐसी ही रही होगी। वे technical चीज़ों को ही देखते रहे और human side बहुत कम देख पाए
अगर interview में ऐसा जवाब दिया होता, तो मैं कभी hire नहीं करता। असल में मैंने एक बार ऐसे candidate का interview लिया था। जब पूछा “आप इसे कैसे करेंगे?”, तो उसने जवाब दिया, “वह नहीं करना चाहिए, मुझे लगता है कुछ और करना चाहिए।” उसे hire नहीं किया गया
कई सालों में धीरे-धीरे समझ आया कि binary search खासकर बहुत बड़े और जटिल सिस्टमों में, जहाँ debug करना मुश्किल होता है, एक कमाल का problem-solving tool है
हाल ही में एक सहकर्मी को Figma rendering tool में समस्या आ रही थी, जिसका source code नहीं था। किसी खास design को export करते समय बहुत ज्यादा समय लग रहा था, और सहकर्मी कई दिनों तक random तरीके से अलग-अलग चीज़ें बदलता रहा, लेकिन कोई फायदा नहीं हुआ। एक कोशिश में कई घंटे लगते थे, और कभी-कभी browser crash भी हो जाता था
मेरा सुझाया समाधान था कि आधे elements हटाकर देखें कि export time पर क्या असर पड़ता है। फिर जिस group में समस्या अब भी रहती, उस पर यही दोहराया। कुछ ही घंटों में वह element मिल गया जो लगभग infinite loop पैदा कर रहा था
end device, जैसे workstation, से हर बार एक step दूर जाने पर network hierarchy में दो step ऊपर जाते थे। इससे scope आसानी से बड़ा किया जा सकता था, फिर भी “यहाँ तक सब ठीक है, और यहाँ टूट रहा है” को बहुत जल्दी narrow down कर सकते थे
administrator ने responsible subscriber को जल्दी पकड़ने के लिए binary search इस्तेमाल किया, और message में कहीं extra whitespace character डालकर content को selectively बदला
code का कुछ हिस्सा हटाकर देखते थे कि क्या अब भी break हो रहा है, फिर और हटाते जाते थे
क्या उस गलती का कोई नाम है जिसमें इंसान जीवन की सफलता का श्रेय अपनी intelligence को देता है, और इसलिए मान लेता है कि वह सब से ज्यादा smart है और हर चीज़ में सही है?
यह कुछ हद तक impostor syndrome के उलट जैसा है
“मैं superior हूँ और सब कुछ जानता हूँ” वाला दूसरा हिस्सा बस पुराना खराब स्वभाव कहा जा सकता है
https://en.wikipedia.org/w/index.php?title=Luciferianism&old...
अगर आप smart हैं, तो खुद को दुनिया का guardian बनना चाहिए—यह उसी तरह का प्रलोभन है। अपनी learning और ultimate truth पर आधारित दुनिया बनाना, और यह मानना कि आप ऐसे truths को आम लोगों से ज्यादा आसानी और तेजी से खोज लेते हैं। इस तरह morality को license मिल जाता है, और ends means को justify करने लगते हैं। जैसे यह विश्वास कि अभी जो बुरा किया जा रहा है, वह बाद में दोगुनी अच्छाई से चुका दिया जाएगा
fundamental attribution error और Dunning-Kruger effect भी हैं। behavior के स्तर पर illusory superiority moral licensing से जुड़ती है, और ज्यादा success वाले लोगों में बड़े risks लेने का disinhibition effect भी शामिल होता है। उन risks में दूसरों पर negative impact डालना भी शामिल है
लगता है ये सारे effects कुछ हद तक मिल जाते हैं। जरूरी नहीं कि intelligence ही मुद्दा हो; कम से कम व्यक्ति द्वारा महसूस की गई power समस्या लगती है। उदाहरण के लिए, जो व्यक्ति मानता है कि वह जन्म से X में बेहतर है, वह ज्यादा power महसूस करता है, और superiority दिखाने या दूसरों पर dominance करने में उसकी रोक-टोक कम हो जाती है
हमने ऐसे लोगों को देखा है जो पुराने glory से चिपके रहते हैं, यह नहीं समझते कि अब उनका peak नहीं रहा, और ऐसी power इस्तेमाल करने की कोशिश करते हैं जो अब उनके पास नहीं है। मेरे लिए वही असली impostor syndrome का opposite है। अपने बारे में और social dynamics के बारे में awareness समय के बदलावों के साथ move नहीं करती
narcissistic personality disorder
antisociality
पहले मेरा एक सहकर्मी था जिसके पास पसंदीदा interview question था। वह graph data structure से जुड़ा question था, और candidates जवाब देते तो वे लगातार reject होते रहते थे
अजीब तरह से, समय के साथ उस question का जवाब देने वाले सभी candidates reject हो गए। इसलिए हम सब इकट्ठा हुए और देखा कि वह कौन-सा question पूछता है, और उसे साथ में solve करते हुए हमें एहसास हुआ कि उसका अपना solution गलत था
पता चला कि वह अपने पूरे career में इसी एक question से लोगों को reject कर रहा था
यह हम सबके लिए humility सिखाने वाला अनुभव था, और lesson मिला कि question पूछने से पहले हर चीज़ दोबारा verify करनी चाहिए। interview देने वाले ज्यादातर candidates hiring के लायक होते हैं। कभी-कभी गलत आप भी हो सकते हैं
गलती की तो तुरंत reject? क्या इतने perfect applicants थे कि लगभग सभी को filter कर सकें?
अगर मैं interviewee होता, तो मेरा पहला question होता: “क्या आप fair play करेंगे, और मैं इसे कैसे verify कर सकता हूँ?”
“दूसरा, जब meaningful money stake पर हो, तो inputs verify किए जाते हैं। इसका मतलब यह नहीं कि मुझे आप पर personally भरोसा नहीं है, बल्कि मैं situation पर भरोसा नहीं करूँगा। इसे कैसे verify किया जा सकता है, या आप चाहते हैं कि हम इसे verified मानकर आगे बढ़ें?”
अच्छे सवाल हैं, लेकिन कैसे पूछते हैं यह भी important है। software engineering pure engineering भर नहीं है; communication बहुत important है
ज्यादातर interview questions की तरह, मैं उम्मीद करूँगा कि यह इस बात को देखने वाला question है कि आप अपनी thinking कैसे develop करते हैं और solution process कैसे दिखाते हैं
अगर interviewer ने यह question पूछा और आपने गलती पकड़ ली, तो उल्टा hiring में मदद मिलने की संभावना है
यहाँ एक और दिलचस्प बात भी है। जब Ballmer को साफ हो गया कि Chang इस question को explicitly binary search और expected value के रूप में approach नहीं कर रही हैं, तो वह इसी exact question की discussion से हटने और diplomatically direction बदलने की काफी कोशिश करता दिखा
यह surprising नहीं है। वह professional journalist हैं। हैरानी की बात यह है कि Ballmer को कई technical interviewers की तरह यह question इतना पसंद था कि Chang के question से इसका ज्यादा संबंध न होने के बावजूद वह इसे निकालने से खुद को रोक नहीं सका
Nash equilibrium हल सच में जानने की जिज्ञासा है
जैसा किसी comment में कहा गया था, guess करने वाले की strategy शायद binary search के आसपास कोई random number लौटाने जैसी होगी। लेकिन यह जानना चाहता हूँ कि चुनने वाला uniform initial distribution इस्तेमाल करता है या non-uniform distribution। HN पर कोई न कोई यह ज़रूर जानता होगा या समझा सकता होगा
5-number game और 100-number game के बीच ज़ाहिर है बड़ा अंतर है। जैसे-जैसे options की संख्या बढ़ती है, optimal mixed strategy stable हो सकती है, या मेरी जानकारी में वह और भी अजीब होती जा सकती है। अगर कोई 6, 7 वगैरह numbers वाले games को ठीक से explore करे, तो कृपया मुझे ज़रूर बताए
बाकी strategies में candidate के पास “trick number” guess करने की strategy है, और Ballmer के पास “trick number न चुनने” की strategy है
candidate Ballmer को trick इस्तेमाल करने के लिए मजबूर नहीं कर सकता