तकनीकी इंटरव्यू का बिगड़ना (2022)

• Palima Aethera Techaro के अव्यवस्थित infrastructure को बचाने वाली candidate जैसी लगती हैं, लेकिन live coding में जानबूझकर एक अजीब sorting solution देकर इंटरव्यू का माहौल पलट देती हैं
• interviewer Jeff नाम के उच्चारण और चेहरा असली है या नहीं, यह पक्का करने के बाद Palima के MovieFlix infrastructure अनुभव और FreeBSD चुनने के मामले में गहरी दिलचस्पी दिखाता है
• numbers की array sort करने के task में Palima Haskell में हर value के लिए एक thread बनाती हैं, value के अनुपात में sleep करने के बाद output करने वाला sleepsort implement करती हैं
• Palima इस solution को “constant-time sorting” बताकर अड़ी रहती हैं, और delay को 100000 से 10000 microseconds के multiplier तक घटाकर 10 गुना optimization किया है, यह समझाकर Jeff को हंसा देती हैं
• इंटरव्यू के बाद Palima reject होने की उम्मीद करती हैं, लेकिन Techaro काफी बड़ी रकम के साथ hiring का इरादा भेजता है, और Palima सोचती हैं कि काम अपने-आप sort हो जाएगा, इसलिए सो जाने का फैसला करती हैं

---

सपने से शुरू हुआ इंटरव्यू का दिन

• Palima सपने में अपनी कलाई का awakening talisman गायब देखकर समझ जाती हैं कि वे सपना देख रही हैं
• सुबह wristwatch की vibration से जागने के बाद उन्हें याद आता है कि उस दिन एक महत्वपूर्ण schedule है
• commute 30 सेकंड में खत्म हो जाता है, और Palima ऐसी chair पर बैठती हैं जिसे उनकी tail और dorsal fin के लिए modify किया गया है
• workstation बताता है कि Firefox पुराना हो गया है, और script नया version build करके run करती है

Techaro इंटरव्यू की शुरुआत

• video conference E100 series service पर होता है, और Palima camera lighting चालू करती हैं
• पहला interviewer Jeff, Palima का नाम गलत उच्चारित करता है और तुरंत सुधारता है
  • Palima बताती हैं कि Pa-lee-mah और Aethera को Ay-theer-ah उच्चारित किया जाता है
  • Jeff कहता है कि वह note करेगा ताकि दूसरे लोग भी सही तरह से बुला सकें
• जब Jeff पूछता है कि क्या वे virtual avatar इस्तेमाल कर रही हैं, Palima जवाब देती हैं, “यही मेरा असली चेहरा है”
• Palima hiring description देखकर ही समझ जाती हैं कि Techaro का infrastructure अव्यवस्थित है और उसे किसी hero की जरूरत है

career परिचय और infrastructure अनुभव

• Palima बताती हैं कि उन्होंने digital automata बनाकर उन्हें दुनिया में छोड़ने और लक्ष्य पूरा करवाने का काफी काम किया है
• MovieFlix में उन्होंने popular movies और TV programs के concurrent streaming infrastructure बनाने में योगदान दिया
• ऐसे कई projects भी हैं जिन्हें वे disclose नहीं कर सकतीं, और जोड़ती हैं कि Jeff अभी उनमें से कम-से-कम तीन का लाभ ले रहा है
• छोटी company में शामिल होने की वजह यह है कि वे लोगों को ज्यादा व्यक्तिगत रूप से जानना चाहती हैं; उनका मानना है कि मशीन के अंदर anonymous part की तरह काम करने का आकर्षण ज्यादा देर नहीं टिकता
• पसंदीदा infrastructure project के तौर पर वे MovieFlix backend के लिए OS kernel benchmarks का जिक्र करती हैं
  • Palima चाहती थीं कि Linux जीते, लेकिन epoll(7) के बाद FreeBSD ज्यादा तेज चला, इसलिए उन्होंने FreeBSD चुना
  • वे यह भी जोड़ती हैं कि शायद अभी भी उनके पास FreeBSD commit rights हों

live coding: sleepsort

• Jeff समझाता है कि Palima का background Techaro जिस तरह के व्यक्ति को खोज रहा है, उससे मेल खाता लगता है, लेकिन सभी को समान standard पर देखने के लिए coding challenge करना होगा
• task website पर numbers की array sort करना और sorting method भी explain करना है
• language free थी, और Palima Haskell code लिखती हैं
• implementation में हर number के लिए अलग green thread बनाया जाता है, और threadDelay (100000 * time) के बाद channel में value लिखकर output किया जाता है
• Palima कहती हैं कि यह sorting comparison इस्तेमाल नहीं करती, और “कभी-कभी बस थोड़ा आराम ही काफी होता है”
• जब Jeff पूछता है कि input value के हिसाब से time बदलता नहीं है क्या, Palima जवाब देती हैं कि time complexity, time जैसे side effects की परवाह नहीं करती

optimization और अप्रत्याशित नतीजा

• Jeff optimization का तरीका पूछता है, तो Palima सिर्फ delay multiplier बदलती हैं
  • 100000 * time को 10000 * time तक घटाती हैं
  • Palima समझाती हैं कि अब यह 10 गुना तेज हो गया है
• आखिर में Jeff जोर से हंस पड़ता है, और जब Palima से पूछा जाता है कि उन्होंने इतना अजीब sorting algorithm क्यों इस्तेमाल किया, तो वे उल्टा पूछती हैं, “आपने ऐसा अजीब सवाल क्यों पूछा”
• Palima निष्कर्ष निकालती हैं कि Techaro उन्हें संभालने लायक पर्याप्त complex नहीं है, और Kubernetes के बजाय Typhoon Digital का एक single dedicated server भी काफी रहा होता
• इंटरव्यू खत्म होने के बाद वे उम्मीद करती हैं कि rejection email जल्द आएगा
• लेकिन Techaro काफी बड़ी रकम के साथ उन्हें hire करना चाहता है, ऐसा email भेजता है, और Palima सोचती हैं कि क्या उन्हें पता है कि वे किस चीज को संभालने की कोशिश कर रहे हैं
• Palima तय करती हैं कि शाम तक काम अपने-आप sort हो जाएगा, इसलिए वे फिर से सो जाएंगी

[GN⁺]

Hacker News की राय

• यह constant time भी नहीं है, और polynomial time भी नहीं, बल्कि pseudo-polynomial time है। negative values पर यह शायद fail करेगा, और input को represent करने वाले bits की संख्या के हिसाब से linear होने के लिए 10000 * log(time + min(time) + 1) जैसी कोई चीज़ चाहिए होगी
  computational complexity theory में यह कहना कि कोई numeric algorithm pseudo-polynomial time में चलता है, इसका मतलब यह है कि उसका running time input के numeric value, यानी input में आने वाले सबसे बड़े integer, के सापेक्ष polynomial है; इसका यह मतलब नहीं कि वह input length (उस संख्या को represent करने के लिए जरूरी bits की संख्या) के सापेक्ष polynomial है
  https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

  • तुम्हें पता है न कि यही मज़ाक का हिस्सा है? अगर detail में जाकर मज़ाक खराब करना ही है, तो असल में real time तक इंतज़ार करने की भी ज़रूरत नहीं
    computational complexity गणना मॉडल के अंदर steps की संख्या से मतलब रखती है, यह नहीं कि घड़ी पर कितना समय बीता। sleep sort operating system scheduler की properties का उपयोग करता है, और virtual time environment में समय सीधे अगले scheduled event तक बढ़ जाता है। अगर ऐसी चीज़ को computation model मानें, तो यह वास्तव में polynomial complexity में चल जाता है
    और अगर दूसरों को सिखाना है, तो कम-से-कम pseudo-polynomial की spelling तो सही रखनी चाहिए
  • क्या ऐसा नहीं है कि किसी भी pseudo-polynomial problem को सिर्फ encoding बदलकर polynomial time बनाया जा सकता है? अगर कोई box किसी value को pseudo-polynomial time में compute कर सकता है, तो एक ऐसा box बनाया जा सकता है जो single input ले, जिसमें हर value की length के बराबर 1 हों और 0 से separator दिया गया हो
    उसे वापस integer में बदलना linear है, फिर original box को call करके result लौटाया जाए, तो अब यह मेरी input length के सापेक्ष polynomial time हो गया। मैंने integer कहा, लेकिन असल बात encoding scheme की है, इसलिए decimals के लिए एक 0, और inputs के separator के लिए 00 जैसी scheme भी संभव है
    वैसे भी, मज़ाक का core point यही नहीं है क्या कि सोने का समय count नहीं होता? उस दौरान computer दूसरे काम कर सकता है। “बेवकूफ़ी है, पर पसंद आई” वाली भावना में यह काफ़ी persuasive है

• sleep sort की शुरुआत /prog/ [0] से हुई थी। उस समय sleep sort thread में शामिल HN lurkers में से काफ़ी लोग यहाँ होंगे, xena भी शायद उन्हीं में से एक हो :)
  [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

  • अगर मैं अभी numbers के हिसाब से तोप में gunpowder भरूँ, बड़े numbers के लिए ज़्यादा gunpowder डालकर उन्हें और दूर उड़ाऊँ, और फिर चलते हुए रास्ते में पड़े numbers उठा लाऊँ, तो क्या यह physical sort होगा?
  • /prog/ की याद सच में बहुत समय बाद आई। मेरी सबसे पसंदीदा post वह थी जिसमें किसी apprentice programmer ने “छोटा, बराबर, या बड़ा” check करने के लिए <=> operator invent किया था। कमाल का था

• जैसा original author ने कहा, यह लेख aphyr की Interview series, जैसे “Rewriting the Technical Interview”, की storytelling style से बहुत मिलता-जुलता है। सब कुछ मज़े से पढ़ने लायक है
  [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

  • writing style काफ़ी अलग है, लेकिन technical interviews का मज़ाक उड़ाने के मामले में “Fizzbuzz in Tensorflow” (2016) भी है
    https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
    झलक:

    interviewer: Um, you understand the problem is fizzbuzz, right?
    me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer

• computer sorting में input को पढ़ना पड़ता है, इसलिए कम-से-कम linear time तो चाहिए ही। अगर input के बारे में uniform distribution जैसी कोई अतिरिक्त जानकारी न हो, तब तो और भी
  linear time sorting के कई तरीके हैं, जैसे sleep sort, postman sort, counting sort आदि। बस, यह restricted number sets या sortable keys पर लागू होता है
  लेकिन computer की जगह abacus इस्तेमाल करें, तो लगभग सचमुच का constant time sort मिलता है: https://en.wikipedia.org/wiki/Bead_sort

  • sorting network नाम की चीज़ भी होती है। हालाँकि इससे मूल बात ज़्यादा नहीं बदलती :D

• मज़ेदार बात है, लेकिन किसी भी मायने में यह constant time नहीं है
  N threads बनाकर उन्हें sorted wake-up list में जोड़ने में operating system या language runtime के अनुसार O(N log N) से O(N^2) तक समय लगता है
  कहीं न कहीं पीछे sorted list, heap, या N^2 algorithm होता है। इसी तरह sleep sort खुद भी कम-से-कम linear time है, क्योंकि N sorted items output करने के लिए N threads को जगाना पड़ता है
  इससे भी बुरा यह है कि वास्तविक clock time भी values के size के साथ बढ़ता है। पहले minimum और maximum ढूँढ़कर range को compress किया जा सकता है, लेकिन वह भी linear time है

  • मज़ाक खराब करने का जोखिम उठाऊँ तो, जब मैंने “constant time” कहा था, तब मैं time complexity analysis की भाषा और रूप का संकेत दे रहा था, लेकिन मेरा मतलब वास्तव में वह नहीं था
    यहाँ “time” शब्द के दो टकराते नज़रियों पर आधारित श्लेष है। complexity analysis के नज़रिए से sorting algorithm को constant time बनाना असंभव है, यह बात सही है
    मज़ाक का असली आशय clock time था। interview में वही ज़्यादा प्रासंगिक है, और व्यवहार में जब कोई “integer sorting function लिखिए” जैसी चीज़ देता है, तो 100 से छोटे numbers ही इस्तेमाल हों ऐसा कम ही होता है, इसलिए यह program अनुभव में लगभग तुरंत चल जाता है
    यह computer science कैसे काम करती है, इस समझ को उलटकर चिढ़ाने वाला एक सूक्ष्म meta-linguistic मज़ाक है। अफ़सोस कि मज़ाक चल नहीं पाया
  • सीमित आयु वाले ब्रह्मांड में सब कुछ constant time है
    https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
  • सैद्धांतिक रूप से sleep में जाने वाला argument अंततः integer में सिमटना चाहिए, इसलिए radix sort जैसी किसी चीज़ से इसे linear time में किया जा सकता है
    ऐसे problem spaces होते हैं जहाँ सबसे बड़े value के size पर निर्भरता होने पर भी फायदा मिलता है
    बेशक, व्यवहार में ऐसा कोई system नहीं है। system call timeout आम तौर पर वह जगह नहीं है जहाँ यह तरीका फायदेमंद हो। और स्वाभाविक रूप से, maximum value के अनुपात में linear तरीके से बेहतर है कि सीधे radix sort लगाया जाए, जो सिर्फ log(max_value) के अनुपात में बढ़ता है
  • N threads बनाकर उन्हें sorted wake-up list में जोड़ने की लागत O(N log N) से O(N^2) होना scheduling system की कोई मूलभूत सीमा नहीं है
    खासकर अगर हम ऐसे special hardware को भी मानें जो threads की संख्या के संदर्भ में constant-time scheduling संभव बना दे। उदाहरण के लिए, भले ही व्यवहार में इसकी आर्थिक उपयोगिता बिल्कुल न हो, लेकिन एक scheduler बनाया जा सकता है जो laser से information packets को दूरी के हिसाब से रखे गए विशाल mirrors के समूह पर उछालकर computer से जुड़े detector तक वापस भेजे
    यह light की speed का इस्तेमाल करके निर्धारित समय जितनी delay पैदा करने का तरीका है। इसलिए sleep sort किसी thread scheduling पद्धति की छिपी algorithmic complexity पर स्वभावतः निर्भर नहीं है, और भले ही यह practical न हो, सिद्धांततः इसे O(1) तक optimize किया जा सकता है
  • यह “Hello World” लौटाने के लिए Kubernetes cluster खड़ा करने वाली शैली जैसा है

• अगर यह पसंद आया हो, तो Protos नाम की एक तरह की sequel भी है: https://xeiaso.net/blog/protos
  इस “worldbuilding” की और कहानियाँ लिखी जा रही हैं, लेकिन satire की ऊर्जा चढ़ने में थोड़ा समय लगता है। अगला भाग शायद spatial computing पर हो

  • “standup meeting अभी शुरू होने वाली है, ठीक उसी समय calendar alert बज उठता है” वाला हिस्सा हमारे ब्रह्मांड जैसा लगता है
    फिर भी उस ब्रह्मांड में नाम रखने का काम शायद बेहतर होता है

• threadDelay (100000 * time) को threadDelay (10000 * time) में बदलकर “अब यह दस गुना तेज़ हो गया है” कहना इस लेख से जुड़ा है: https://thedailywtf.com/articles/The-Speedup-Loop

• लेख नहीं पढ़ा, लेकिन ऐसी चीज़ें मुझे नापसंद हैं। मैंने पहले Meta का remote interview दिया था, और सामने वाला पूरे समय mic में खाते रहा
  इतना distracting था कि मैं for loop लिखना भी भूल गया

  • remote hiring कहीं बेहतर है। पहले recruiter या HR से थोड़ी बात करने के बाद suit पहनकर दूर drive करके या flight लेकर जाना पड़ता था, और आम तौर पर पूरा दिन निकल जाता था
    अगर नौकरी में होते, तो leave लेनी पड़ती थी, और “क्या मैं अपनी सीमित leave यहाँ बर्बाद कर रहा हूँ?”, “parking मिलेगी?”, “समय पर पहुँच पाऊँगा?” जैसे तनाव रहते थे। फिर 30 मिनट का “initial interview” होता, उसके बाद कई हफ्तों तक इंतज़ार करना पड़ता कि proper interview का बुलावा आएगा या सीधा ghost कर दिया जाएगा
    पूरी process में एक महीना लग सकता था, और कम-से-कम दो दिन की छुट्टी तथा काफ़ी travel की ज़रूरत पड़ सकती थी
    अब recruiter या HR phone करके पूछ लेते हैं कि video call कर सकते हैं या नहीं, उसी दिन 15~20 मिनट बात होती है, फिर resume decision maker को भेज दिया जाता है, और एक या अधिक video interviews या technical sessions तय हो जाते हैं। कुछ कंपनियाँ कहती हैं कि घर पर आराम से personality/technical tests दे दीजिए
    अगर आप remote worker हैं, तो यह सब lunch break में भी हो सकता है। आमने-सामने की communication bandwidth ज़रूर बहुत बड़ी होती है, लेकिन एक ही दिन सुबह Tel Aviv की company, दोपहर में Warsaw की company, और शाम को California की company के interview देना सिर्फ remote में ही संभव है

• 1000 threads बनाना कम-से-कम linear time तो है, नहीं? शायद log तक घटाया जा सके, लेकिन यह code अपने-आप ऐसा करेगा, ऐसा नहीं लगता

  • “time” को क्या माना जाए, इस पर निर्भर करता है। अगर algorithmic complexity वाला time है, तो कम-से-कम linear सही है। अगर clock time, यानी interview code में ज़्यादा अहम time, माना जाए, तो constant time है
  • sleep sort को दूसरे sorting algorithms से ज़्यादा constant-time कहना मुश्किल है
    sleep sort के constant time होने के लिए input पर upper bound होना चाहिए, यानी सबसे बड़े number की सीमा तय होनी चाहिए, और input पढ़ना-प्रोसेस करना, thread creation जैसी मनमानी चीज़ों को गिनती में नहीं लेना चाहिए
    लेकिन अगर यह मान लें, तो बाकी सभी sorts भी constant time हो जाते हैं। शायद इन दोनों में से सिर्फ एक बात मान लेना ही काफ़ी होगा
  • असल में यह linear भी नहीं है। सोना तो heap insertion है, और उसमें O(log n) लगता है
  • interview के दौरान वह सचमुच सो रहा था। नहीं तो input के हर value पर sequential loop चलाने वाले program की पहली ही line होते हुए भी उसकी asymptotic complexity को “constant time” नहीं कहा जा सकता

• अगर thread runtime अपनी खुद की time की अवधारणा बनाए रखता है, तो algorithm को वास्तविक समय के हिसाब से सोने की ज़रूरत ही नहीं होती
  सभी threads बन जाने के बाद runtime यह देख सकता है कि सभी threads idle हैं और अगला schedule होने वाला thread समय N वाला thread है, तो वह वर्तमान समय को N पर update करके उस thread को चला सकता है। इसे दोहराने पर बिना किसी sleep के sorted array मिल जाता है
  आखिरकार sorting का काम तो threads के सोना शुरू करते ही पूरा हो चुका था, और वे बाद में जगाने वाले किसी coordinator, जैसे timer wheel, में खुद को register कर चुके थे। वास्तव में sleep करने की ज़रूरत नहीं है
  Haskell के बारे में नहीं जानता, लेकिन Rust का tokio runtime start_paused के साथ यह संभव बनाता है: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

  • मेरी समझ में यह मूल रूप से वही तरीका है जिससे discrete event simulation अंदर काम करती है। उपयुक्त data structure, जैसे heap, में future events की सीमाएँ रखी जाती हैं, और heap में future event जोड़ने तथा heap से अगला event निकालने की प्रक्रिया बारी-बारी से चलती है
    abstraction की कई layers और छोड़ी गई implementation details को अलग रख दें, तो ऐसे scheduler से values को sort करना बस heap sort ही है :)
  • अगर आप वास्तव में यह गणना करने लगते हैं कि अगला क्या चलाना है, तो आप selection sort को फिर से invent कर रहे हैं, और यह अब linear time नहीं रहता। इसलिए व्यावहारिक रूप से यह कोई समझदारी भरा sorting algorithm नहीं है :)