สัมภาษณ์งานสายเทคฯ ล่มไม่เป็นท่า (2022)

 (xeiaso.net)
1 คะแนน โดย GN⁺ 2023-07-09 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Palima Aethera ดูเหมือนจะเป็นผู้สมัครที่อาจกอบกู้โครงสร้างพื้นฐานอันยุ่งเหยิงของ Techaro ได้ แต่กลับพลิกบรรยากาศการสัมภาษณ์ด้วยการจงใจยื่นคำตอบการเรียงลำดับสุดประหลาดในช่วง live coding
  • Jeff ผู้สัมภาษณ์ให้ความสนใจอย่างมากกับประสบการณ์ด้านโครงสร้างพื้นฐานของ Palima ที่ MovieFlix และกรณีการ เลือก FreeBSD หลังจากตรวจสอบทั้งการออกเสียงชื่อและว่าหน้าตาเป็นของจริงหรือไม่
  • ในโจทย์เรียงลำดับอาร์เรย์ตัวเลข Palima เขียน sleepsort ด้วย Haskell โดยสร้างเธรดให้แต่ละค่า หลับตามเวลาที่แปรผันตามค่า แล้วค่อยพิมพ์ผลลัพธ์
  • Palima ยืนกรานเรียกวิธีนี้ว่าเป็น “การเรียงลำดับเวลาแบบคงที่” และอธิบายว่าลดเวลาหน่วงจากตัวคูณ 100000 เหลือ 10000 ไมโครวินาที ทำให้ เพิ่มประสิทธิภาพได้ 10 เท่า จน Jeff หัวเราะออกมา
  • หลังสัมภาษณ์ Palima คาดว่าตัวเองน่าจะไม่ผ่าน แต่ Techaro กลับส่งความตั้งใจจะจ้างพร้อมตัวเลขเงินก้อนใหญ่ และ Palima ก็ตัดสินใจนอนต่อโดยคิดว่างานคงจะจัดเรียงตัวมันเองได้

วันสัมภาษณ์ที่เริ่มต้นจากความฝัน

  • Palima เห็นในความฝันว่า เครื่องรางปลุกสติ บนข้อมือหายไป จึงรู้ตัวว่ากำลังฝันอยู่
  • เมื่อตื่นขึ้นมาตอนเช้าจากแรงสั่นของนาฬิกาข้อมือ ก็พลันนึกได้ว่าวันนั้นมีนัดหมายสำคัญ
  • การไปทำงานใช้เวลาเพียง 30 วินาที และ Palima ก็นั่งลงบนเก้าอี้ที่ดัดแปลงให้รองรับหางและครีบหลัง
  • เวิร์กสเตชันแจ้งว่า Firefox เก่าแล้ว และสคริปต์ก็ทำการบิลด์เวอร์ชันใหม่ขึ้นมารัน

จุดเริ่มต้นของการสัมภาษณ์กับ Techaro

  • การประชุมวิดีโอจัดขึ้นผ่านบริการตระกูล E100 และ Palima ก็เปิดไฟส่องกล้อง
  • Jeff ผู้สัมภาษณ์คนแรกออกเสียงชื่อของ Palima ผิด ก่อนจะรีบแก้ทันที
    • Palima บอกว่าออกเสียง Pa-lee-mah และ Aethera เป็น Ay-theer-ah
    • Jeff บอกว่าจะจดไว้เพื่อให้คนอื่นเรียกได้ถูกต้องด้วย
  • เมื่อ Jeff ถามว่าใช้ อวตารเสมือน อยู่หรือไม่ Palima ตอบว่า “นี่คือหน้าจริง”
  • แค่ดูคำอธิบายตำแหน่งรับสมัคร Palima ก็พอจะจับได้แล้วว่าโครงสร้างพื้นฐานของ Techaro กำลังยุ่งเหยิงและอยู่ในสภาพที่ต้องการฮีโร่

แนะนำประสบการณ์และงานด้านโครงสร้างพื้นฐาน

  • Palima แนะนำตัวว่าเคยทำงานเกี่ยวกับการสร้างอุปกรณ์อัตโนมัติดิจิทัลแล้วปล่อยออกไปสู่โลกเพื่อให้ไปทำภารกิจตามเป้าหมายอยู่มาก
  • ที่ MovieFlix ได้มีส่วนช่วยสร้างโครงสร้างพื้นฐานสำหรับ การสตรีมพร้อมกัน ของภาพยนตร์และรายการทีวียอดนิยม
  • ยังมีอีกหลายโปรเจกต์ที่เปิดเผยไม่ได้ และ Palima เสริมว่า Jeff ก็กำลังได้รับประโยชน์จากอย่างน้อยสามโปรเจกต์ในนั้นอยู่ตอนนี้
  • เหตุผลที่อยากเข้าบริษัทเล็กกว่าคืออยากรู้จักผู้คนอย่างเป็นส่วนตัวมากขึ้น และมองว่าเสน่ห์ของการทำงานแบบเป็นชิ้นส่วนไร้ชื่อในเครื่องจักรนั้นอยู่ได้ไม่นาน
  • โปรเจกต์โครงสร้างพื้นฐานที่ชอบที่สุดคือการทำ benchmark เคอร์เนลระบบปฏิบัติการสำหรับแบ็กเอนด์ของ MovieFlix
    • Palima หวังว่า Linux จะชนะ แต่หลัง epoll(7) กลับพบว่า FreeBSD ทำงานได้เร็วกว่า จึงเลือก FreeBSD
    • พร้อมเสริมว่าน่าจะยังมีสิทธิ์ commit บน FreeBSD อยู่

live coding: sleepsort

  • Jeff อธิบายว่าพื้นหลังของ Palima ดูเข้ากับคนที่ Techaro กำลังมองหา แต่เพื่อให้ทุกคนถูกประเมินบนมาตรฐานเดียวกัน จึงยังต้องทำ โจทย์เขียนโค้ด
  • โจทย์คือให้เรียงอาร์เรย์ตัวเลขบนเว็บไซต์ และอธิบายวิธีเรียงลำดับด้วย
  • จะใช้ภาษาอะไรก็ได้ และ Palima ก็เลือกเขียน Haskell
  • วิธีที่ใช้คือสร้าง green thread แยกให้ตัวเลขแต่ละตัว แล้วหลัง threadDelay (100000 * time) จึงเขียนค่าลงช่องทางสื่อสารเพื่อพิมพ์ออกมา
  • Palima บอกว่าการเรียงลำดับนี้ไม่ใช้การเปรียบเทียบ และ “บางครั้งแค่พักสักนิดก็พอ”
  • เมื่อ Jeff ถามว่าเวลาในการทำงานไม่ได้เปลี่ยนไปตามค่าที่รับเข้ามาหรือ Palima ก็ตอบว่าความซับซ้อนเชิงเวลาไม่สนผลข้างเคียงอย่างเรื่องเวลา

การปรับแต่งและผลลัพธ์ที่คาดไม่ถึง

  • เมื่อ Jeff ถามถึงวิธีปรับแต่งประสิทธิภาพ Palima ก็แค่เปลี่ยนตัวคูณของเวลาหน่วง
    • ลดจาก 100000 * time เหลือ 10000 * time
    • Palima อธิบายว่าตอนนี้มัน เร็วขึ้น 10 เท่า
  • สุดท้าย Jeff ก็หัวเราะลั่น และเมื่อ Palima ถูกถามว่าทำไมถึงใช้ขั้นตอนวิธีเรียงลำดับประหลาดแบบนี้ ก็สวนกลับว่า “แล้วทำไมถึงถามคำถามประหลาดแบบนั้นล่ะ”
  • Palima มองว่า Techaro ยังซับซ้อนไม่พอจะรองรับตัวเอง และจริง ๆ น่าจะใช้เซิร์ฟเวอร์เฉพาะเครื่องเดียวของ Typhoon Digital แทน Kubernetes ก็เพียงพอแล้ว
  • หลังจบการสัมภาษณ์ Palima คาดว่าอีกไม่นานคงมีอีเมลปฏิเสธส่งมา
  • แต่ Techaro กลับส่งอีเมลบอกว่าอยากจ้างด้วยจำนวนเงินก้อนใหญ่พอสมควร ทำให้ Palima สงสัยว่าพวกเขารู้ไหมว่ากำลังจะรับมือกับอะไร
  • Palima ตัดสินใจว่างานคงจะจัดเรียงตัวมันเองได้ภายในช่วงเย็น จึงกลับไปนอนอีกครั้ง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-07-09
ความเห็นบน Hacker News

  • มันไม่ใช่ทั้งเวลาเชิงคงที่ และก็ไม่ใช่เวลาเชิงพหุนาม แต่เป็น เวลาแบบกึ่งพหุนาม น่าจะใช้กับค่าติดลบไม่ได้ และถ้าจะให้เป็นเชิงเส้นเมื่อเทียบกับจำนวนบิตที่ใช้แทนอินพุต ก็ต้องเป็นอะไรประมาณ 10000 * log(time + min(time) + 1)
    ในทฤษฎีความซับซ้อนเชิงคำนวณ การที่อัลกอริทึมเชิงตัวเลขทำงานในเวลาแบบกึ่งพหุนาม หมายความว่าเวลาทำงานเป็นพหุนามของค่าตัวเลขของอินพุต หรือก็คือจำนวนเต็มที่ใหญ่ที่สุดที่ปรากฏในอินพุต ไม่ได้หมายความว่าเป็นพหุนามของความยาวอินพุต (จำนวนบิตที่ต้องใช้แทนค่านั้น)
    https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

    • คุณก็รู้นี่ว่านั่นเป็นส่วนหนึ่งของมุก? ถ้าจะลงรายละเอียดจนมุกกร่อย ก็ไม่จำเป็นต้องรอตามเวลาจริงด้วยซ้ำ
      ความซับซ้อนเชิงคำนวณพูดถึงจำนวนขั้นตอนในแบบจำลองการคำนวณ ไม่ได้พูดถึงเวลาบนนาฬิกาที่ผ่านไปเท่าไร sleep sort อาศัยคุณสมบัติของตัวจัดตารางงานของระบบปฏิบัติการ และใน สภาพแวดล้อมเวลาเสมือน เวลาจะขยับไปยังเหตุการณ์ที่ถูกกำหนดถัดไปทันที ถ้าสมมติสิ่งนั้นเป็นแบบจำลองการคำนวณ มันก็ทำงานได้ในความซับซ้อนแบบพหุนามจริง ๆ
      แล้วถ้าจะสอนคนอื่น อย่างน้อยก็ควรสะกด pseudo-polynomial ให้ถูก
    • ปัญหาแบบ กึ่งพหุนาม ใด ๆ ก็ทำให้เป็นเวลาแบบพหุนามได้ด้วยการเปลี่ยน encoding ไม่ใช่หรือ? ถ้ามีกล่องดำที่คำนวณค่าบางอย่างในเวลาแบบกึ่งพหุนามได้ ก็สร้างกล่องที่รับอินพุตเดี่ยวซึ่งประกอบด้วย 1 จำนวนเท่ากับความยาวของแต่ละค่า แล้วคั่นด้วย 0 ได้
      การแปลงมันกลับเป็นจำนวนเต็มก็เป็นเชิงเส้น จากนั้นเรียกใช้กล่องเดิมแล้วคืนผลลัพธ์ เท่านี้มันก็กลายเป็นเวลาแบบพหุนามเมื่อเทียบกับความยาวอินพุตของฉันแล้ว แม้จะพูดว่าเป็นจำนวนเต็ม แต่แก่นจริง ๆ คือวิธี encoding ดังนั้นกับทศนิยมก็อาจใช้ 0 หนึ่งตัว และใช้ 00 สำหรับคั่นอินพุตได้เหมือนกัน
      ยังไงก็ตาม แก่นของมุกก็คือไม่นับเวลาที่นอนหลับไม่ใช่หรือ? เพราะระหว่างนั้นคอมพิวเตอร์ก็ไปทำอย่างอื่นได้ ฟังดูค่อนข้างมีน้ำหนักในแบบ “โง่ดีแต่ฉันชอบ”

  • sleep sort เริ่มมาจาก /prog/ [0] ตอนนั้นคงมีคนอ่าน HN อยู่ไม่น้อยที่ร่วมอยู่ในเธรด sleep sort ด้วย และ xena อาจเป็นหนึ่งในนั้นด้วยก็ได้ :)
    [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

    • ถ้าฉันใส่ดินปืนลงในปืนใหญ่ตามค่าตัวเลข โดยเลขที่มากกว่าจะใส่ดินปืนมากกว่าเพื่อยิงไปได้ไกลกว่า แล้วฉันเดินไปเก็บตัวเลขที่ตกอยู่ตามเส้นทาง แบบนี้เรียกว่า การจัดเรียงเชิงกายภาพ ไหม?
    • ไม่ได้คิดถึง /prog/ มานานมากแล้ว โพสต์ที่ชอบที่สุดคือเรื่องที่เด็กฝึกโปรแกรมเมอร์คนหนึ่งคิดค้นตัวดำเนินการ <=> สำหรับตรวจว่า “น้อยกว่าหรือเท่ากับหรือมากกว่า” อัจฉริยะมาก

  • อย่างที่ผู้เขียนต้นฉบับบอกไว้ บทความนี้คล้ายกับงานเขียนชุด Interview ของ aphyr มาก เช่น “Rewriting the Technical Interview” ทั้งในแง่สไตล์การเล่าเรื่องและบรรยากาศ อ่านสนุกทั้งหมด
    [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

    • แม้สไตล์การเขียนจะต่างกันมาก แต่ในแง่ที่ล้อเลียนการสัมภาษณ์เทคนิค ก็มี “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

  • การจัดเรียงบนคอมพิวเตอร์ต้องอ่านอินพุต จึงต้องใช้เวลาอย่างน้อยเชิงเส้น ถ้าไม่รู้ข้อมูลอื่นเพิ่มเติมเกี่ยวกับอินพุต เช่น การกระจายแบบสม่ำเสมอ ก็ยิ่งเป็นเช่นนั้น
    การจัดเรียงเชิงเส้นมีหลายแบบ เช่น sleep sort, postman sort, counting sort เป็นต้น แต่ใช้ได้กับชุดตัวเลขหรือคีย์ที่จัดเรียงได้ซึ่งมีขอบเขตจำกัด
    แต่ถ้าใช้ลูกคิดแทนคอมพิวเตอร์ ก็มี การจัดเรียงเวลาเชิงคงที่ ที่เกือบจะจริงอยู่แบบหนึ่ง: https://en.wikipedia.org/wiki/Bead_sort

    • ยังมี sorting network ด้วย แน่นอนว่ามันไม่ได้เปลี่ยนประเด็นหลักไปมากนัก :D

  • เป็นเรื่องน่ารักดี แต่ไม่ว่าในความหมายไหนก็ไม่ใช่ เวลาคงที่
    การสร้างเธรด N ตัวแล้วเพิ่มทั้งหมดเข้าไปในรายการปลุกที่เรียงลำดับไว้ ใช้เวลาตั้งแต่ O(N log N) ถึง O(N^2) ขึ้นอยู่กับระบบปฏิบัติการหรือ language runtime
    ที่ไหนสักแห่งข้างใต้ต้องมี sorted list, heap หรือไม่ก็อัลกอริทึมแบบ N^2 อยู่ และตัว sleep sort เองก็ต้องปลุกเธรด N ตัวเพื่อพิมพ์รายการที่เรียงแล้ว N รายการ ดังนั้นอย่างน้อยก็เป็นเวลาเชิงเส้น
    ที่แย่กว่านั้นคือเวลาในนาฬิกาจริงก็เพิ่มขึ้นตามขนาดของค่าเช่นกัน จะหาค่าน้อยสุดกับมากสุดก่อนแล้วบีบช่วงให้แคบลงก็ได้ แต่สิ่งนั้นก็ยังเป็นเวลาเชิงเส้นอยู่ดี

    • ถ้าจะเสี่ยงฆ่ามุกนิดหน่อย ตอนที่ผมพูดว่า “เวลาคงที่” ผมตั้งใจพาดพิงถึงถ้อยคำและรูปแบบของการวิเคราะห์ time complexity แต่ไม่ได้หมายความตามนั้นจริง ๆ
      ตรงนี้เป็น มุกสองแง่สองง่าม ที่เล่นกับมุมมองของคำว่า “เวลา” สองแบบที่ขัดกัน ซึ่งก็ถูกต้องแหละว่าถ้ามองจากมุมของการวิเคราะห์ความซับซ้อน จะทำให้อัลกอริทึมจัดเรียงเป็นเวลาคงที่นั้นเป็นไปไม่ได้
      แต่เจตนาจริงของมุกคือเวลาในนาฬิกา ในการสัมภาษณ์เวลานั้นเกี่ยวข้องกว่า และในทางปฏิบัติ เวลามีคนพูดอะไรอย่าง “ลองเขียนฟังก์ชัน sort จำนวนเต็มดู” ก็น้อยมากที่จะจำกัดให้ใช้แค่ตัวเลขต่ำกว่า 100 ดังนั้นโปรแกรมนี้จึงให้ความรู้สึกว่าแทบจะรันทันที
      มันเป็นมุกเชิงเมตาภาษาที่ละเอียดอ่อน ซึ่งล้อการกลับหัวความเข้าใจเกี่ยวกับการทำงานของวิทยาการคอมพิวเตอร์ น่าเสียดายที่มุกไม่ติด
    • ในจักรวาลที่มีอายุขัยจำกัด ทุกอย่างก็เป็นเวลาคงที่ทั้งนั้น
      https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
    • ในทางทฤษฎี อาร์กิวเมนต์ที่ส่งเข้า sleep ท้ายที่สุดต้องลงเอยเป็นจำนวนเต็มอยู่แล้ว ดังนั้นอาจใช้วิธีอย่าง radix sort เพื่อจัดการในเวลาเชิงเส้นได้
      ถึงจะมีการพึ่งพาขนาดของค่าที่มากที่สุด ก็ยังมีพื้นที่ปัญหาที่คุ้มจะทำแบบนั้น
      แน่นอนว่าในความเป็นจริงไม่มีระบบแบบนั้น system call timeout มักไม่ใช่จุดที่วิธีนี้ได้เปรียบ และแน่นอนว่าก็ดีกว่าที่จะใช้ radix sort กับข้อมูลโดยตรง แทนที่จะใช้วิธีที่แปรผันเชิงเส้นกับค่าสูงสุด มากกว่าจะพึ่งแค่ log(max_value)
    • ค่าใช้จ่ายในการสร้างเธรด N ตัวแล้วเพิ่มเข้าไปในรายการปลุกที่เรียงไว้ ซึ่งอยู่ที่ O(N log N) ถึง O(N^2) นั้น ไม่ใช่ข้อจำกัดพื้นฐานของระบบจัดตารางเสมอไป
      โดยเฉพาะเมื่อคิดรวมถึงฮาร์ดแวร์เฉพาะทางที่ทำให้การจัดตารางแบบเวลาคงที่ตามจำนวนเธรดเป็นไปได้ยิ่งชัดเจน เช่น ถึงจะไม่คุ้มค่าในโลกจริงเลย แต่คุณสามารถสร้าง scheduler ที่ใช้เลเซอร์ยิงแพ็กเก็ตข้อมูลไปสะท้อนกับชุดกระจกขนาดมหึมาที่จัดวางตามระยะทาง แล้วส่งกลับมายังตัวตรวจจับที่ต่อกับคอมพิวเตอร์ได้
      วิธีนี้ใช้ความเร็วแสงเพื่อหน่วงเวลาให้ได้ตามที่กำหนด ดังนั้น sleep sort จึงไม่ได้ขึ้นกับ hidden algorithmic complexity ของวิธีจัดตารางเธรดใด ๆ โดยเนื้อแท้ และแม้จะไม่ใช่สิ่งที่ใช้ได้จริง แต่ในทางทฤษฎีก็อาจปรับให้เป็น O(1) ได้
    • นี่คล้ายกับสไตล์แบบตั้ง Kubernetes cluster ขึ้นมาเพื่อคืนค่า “Hello World”

  • ถ้าชอบอันนี้ ก็ยังมี Protos ซึ่งเป็นเหมือนภาคต่ออยู่ด้วย: https://xeiaso.net/blog/protos
    ผมกำลังเขียนเรื่องราวใน “จักรวาล” นี้เพิ่ม แต่พลังแห่งการเสียดสีต้องใช้เวลาหน่อยกว่าจะมา ตอนต่อไปอาจเป็นเรื่อง spatial computing

    • ตรงที่บอกว่า “พอดีกับเสียงแจ้งเตือนปฏิทินว่าการประชุม standup กำลังจะเริ่ม” นี่เหมือนจักรวาลของเราเลย
      ถึงอย่างนั้นจักรวาลนั้นก็ตั้งชื่อเก่งกว่าอยู่ดี

  • ตรงที่เปลี่ยน threadDelay (100000 * time) เป็น threadDelay (10000 * time) แล้วบอกว่า “ตอนนี้เร็วขึ้นสิบเท่าแล้ว” เกี่ยวข้องกับบทความนี้: https://thedailywtf.com/articles/The-Speedup-Loop

  • ยังไม่ได้อ่านบทความ แต่เกลียดอะไรแบบนี้ เคยสัมภาษณ์ระยะไกลกับ Meta แล้วอีกฝ่ายเอาแต่เคี้ยวอาหารใส่ไมค์ตลอดเวลา
    เสียสมาธิจนผมลืมไปเลยว่าจะเขียน for loop ยังไง

    • การจ้างงานแบบรีโมตดีกว่ามาก แต่ก่อนคือต้องคุยสั้น ๆ กับ recruiter หรือ HR ก่อน จากนั้นก็ต้องใส่สูทแล้วขับรถไกล ๆ หรือขึ้นเครื่องบินไป และโดยมากทั้งวันก็หายไปเลย
      ถ้ายังทำงานประจำอยู่ก็ต้องลาพักร้อน และมีความเครียดแบบ “ฉันกำลังเสียวันลาที่มีจำกัดไปกับสิ่งนี้หรือเปล่า?”, “จะมีที่จอดรถไหม?”, “จะไปทันเวลาหรือเปล่า?” จากนั้นก็ได้สัมภาษณ์ “รอบแรก” 30 นาที แล้วต้องรอเป็นสัปดาห์ ๆ กว่าจะได้คำเชิญสัมภาษณ์จริงจังหรือไม่ก็โดนเงียบหายไปเลย
      ทั้งกระบวนการอาจกินเวลาหนึ่งเดือน และอาจต้องใช้วันลาอย่างน้อยสองวันพร้อมการเดินทางพอสมควร
      ตอนนี้ recruiter หรือ HR แค่โทรมาถามว่าสะดวกคุยวิดีโอไหม คุยกัน 15–20 นาทีได้ในวันเดียวกัน แล้วก็ส่งเรซูเม่ต่อให้คนตัดสินใจ พร้อมนัดวิดีโอสัมภาษณ์หรือ technical session หนึ่งรอบขึ้นไป บางบริษัทก็ให้ทำแบบทดสอบบุคลิกภาพ/เทคนิคจากบ้านแบบสบาย ๆ
      ถ้าเป็นคนทำงานรีโมต คุณอาจจัดการทั้งหมดในช่วงพักเที่ยงได้เลย แม้แบนด์วิดท์การสื่อสารแบบเจอหน้าจะสูงกว่ามาก แต่มีแค่แบบรีโมตเท่านั้นที่คุณจะสัมภาษณ์กับบริษัทใน Tel Aviv ตอนเช้า, บริษัทใน Warsaw ตอนกลางวัน และบริษัทใน California ตอนเย็นได้ในวันเดียวกัน

  • การสร้าง 1000 เธรด อย่างน้อยก็น่าจะเป็น เวลาเชิงเส้น ไม่ใช่เหรอ? อาจลดให้เหลือมี log ได้ แต่โค้ดนั้นคงไม่ได้ทำแบบนั้นเองอัตโนมัติ

    • มันขึ้นอยู่กับว่าคุณมอง “เวลา” ว่าเป็นอะไร ถ้าเป็นเวลาในความหมายของ algorithmic complexity ก็อย่างน้อยต้องเชิงเส้นแน่ แต่ถ้าเป็นเวลาในนาฬิกา ซึ่งสำคัญกว่าสำหรับโค้ดในสัมภาษณ์ ก็ถือว่าเป็นเวลาคงที่
    • จะบอกว่า sleep sort เป็นเวลาคงที่มากกว่าอัลกอริทึมจัดเรียงอื่น ๆ ก็คงยาก
      ถ้า sleep sort จะเป็นเวลาคงที่ได้ ก็ต้องมีขอบเขตบนของอินพุตก่อน คือมีการจำกัดเลขที่มากที่สุด และต้องไม่นับงานตามอำเภอใจอย่างการอ่านและประมวลผลอินพุตหรือการสร้างเธรด
      แต่ถ้ายอมให้ทำแบบนั้น อัลกอริทึม sort อื่น ๆ ทั้งหมดก็กลายเป็นเวลาคงที่เหมือนกัน แค่ยอมอย่างใดอย่างหนึ่งก็น่าจะพอแล้ว
    • ในความเป็นจริงมันไม่ใช่แม้แต่เชิงเส้นด้วยซ้ำ การนอนคือ heap insertion และใช้เวลา O(log n)
    • เขาน่าจะหลับอยู่จริง ๆ ระหว่างสัมภาษณ์ ไม่อย่างนั้นคงอ้างไม่ได้หรอกว่า asymptotic complexity เป็น “เวลาคงที่” ทั้งที่บรรทัดแรกของโปรแกรมก็มีลูปวิ่งตามค่าทุกตัวในอินพุตแบบลำดับอยู่แล้ว

  • ถ้า thread runtime มีแนวคิดเรื่องเวลาของตัวเอง อัลกอริทึมก็ไม่จำเป็นต้องหลับตามเวลาจริงเลยด้วยซ้ำ
    หลังจากสร้างทุกเธรดเสร็จแล้ว runtime ก็จะสังเกตได้ว่าทุกเธรดอยู่ในสถานะ idle และเธรดถัดไปที่จะถูก schedule คือเธรดที่เวลา N ดังนั้นก็แค่อัปเดตเวลาปัจจุบันเป็น N แล้วรันเธรดนั้น ทำซ้ำแบบนี้ไปก็จะได้อาร์เรย์ที่เรียงแล้วโดยไม่ต้องมี sleep เลย
    สุดท้ายแล้ว งานเรียงลำดับก็เสร็จตั้งแต่ตอนที่เธรดเริ่มหลับ โดยไปลงทะเบียนตัวเองไว้กับตัวประสานที่จะปลุกทีหลัง เช่น timer wheel เป็นต้น จึงไม่จำเป็นต้องทำการหลับจริง ๆ
    ไม่แน่ใจว่า Haskell เป็นไหม แต่ runtime ของ Rust อย่าง tokio ทำแบบนี้ได้ด้วย start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

    • ผมเข้าใจว่านี่ก็คือวิธีที่ การจำลองเหตุการณ์ไม่ต่อเนื่อง ทำงานภายในเป็นพื้นฐานนั่นเอง โดยใช้โครงสร้างข้อมูลที่เหมาะสม เช่นวางขอบเขตของเหตุการณ์ในอนาคตไว้ใน heap แล้วสลับกันระหว่างเพิ่มเหตุการณ์อนาคตลง heap กับดึงเหตุการณ์ถัดไปออกจาก heap
      ถ้าไม่นับชั้นของ abstraction หลายระดับและรายละเอียดการติดตั้งที่ละไว้ การเรียงค่าด้วย scheduler แบบนี้ก็คือ heap sort นั่นเอง :)
    • ถ้าเริ่มคำนวณจริง ๆ ว่าจะรันอะไรเป็นลำดับถัดไป คุณก็กำลังประดิษฐ์ selection sort ขึ้นมาใหม่ และมันก็ไม่เป็นเวลาเชิงเส้นอีกต่อไป ดังนั้นในทางปฏิบัติจึงไม่ใช่อัลกอริทึมเรียงลำดับที่สมเหตุสมผลนัก :)