คำถามสัมภาษณ์วิศวกรรมซอฟต์แวร์ที่ผมชอบ: การคำนวณค่ามัธยฐาน

 (krisshamloo.com)
1 คะแนน โดย GN⁺ 4 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โจทย์เขียนโค้ดขนาดเล็กในการสัมภาษณ์ทางเทคนิคอาจได้ผลดีกว่าปริศนา และ การคำนวณค่ามัธยฐาน ช่วยเผยให้เห็นทั้งทักษะการเขียนโค้ดพื้นฐานและเซนส์ด้านการออกแบบ
  • เพราะเป็นโจทย์ที่ต้องมีการเรียงลำดับ จึงนำไปสู่การพูดคุยเรื่อง API ได้อย่างเป็นธรรมชาติ เช่น ฟังก์ชันควรเรียงลำดับเองหรือให้ผู้เรียกเป็นคนเรียง และสามารถ แก้ไข อาร์เรย์ต้นฉบับได้หรือไม่
  • การแยกเงื่อนไขความยาวคี่กับคู่ การคำนวณดัชนี และข้อผิดพลาดแบบ off-by-one เหมาะสำหรับสังเกตกระบวนการดีบักของผู้สมัคร
  • ภายในโจทย์สั้น ๆ นี้ ยังตรวจสอบได้ถึงความแตกต่างระหว่างมัธยฐานกับค่าเฉลี่ย ความง่ายในการเขียนเทสต์ และความรู้เกี่ยวกับไลบรารีมาตรฐาน statistics ของ Python
  • ตัวอย่างการทำงานจะโยน ValueError เมื่อเป็นลิสต์ว่าง ใช้ sorted() เพื่อเรียงลำดับแบบคัดลอก สำหรับความยาวคู่จะคืนค่าเฉลี่ยของสองค่าตรงกลาง และสำหรับความยาวคี่จะคืนค่าตรงกลาง

เหตุผลที่โจทย์มัธยฐานเหมาะกับการสัมภาษณ์

  • คำถามสัมภาษณ์ทางเทคนิคที่ดีไม่ควรเป็นโจทย์ที่บิดให้เหมือนปริศนา แต่ควรเปิดประเด็นที่ลึกขึ้นได้จาก การเขียนโค้ดที่เข้าใจง่าย
  • คำถาม “จงเขียนฟังก์ชันที่รับอาร์เรย์ของตัวเลขแล้วคืนค่ามัธยฐาน” เหมาะใช้เป็นสัญญาณแบบ Fizz Buzz เพื่อดูว่าผู้สมัครเขียนโปรแกรมได้จริงหรือไม่
  • งานที่ลดค่าต่าง ๆ ในอาร์เรย์ให้เหลือผลลัพธ์เดียวเป็นทักษะพื้นฐาน และตัวโจทย์ก็เล็กพอที่จะดูการสนทนาและการดีบักไปพร้อมกันได้ง่าย

จุดตัดสินใจที่เผยให้เห็นระหว่างการทำโจทย์

  • การคำนวณมัธยฐานต้องมีการ เรียงลำดับ ก่อน
    • ต้องตัดสินใจว่าฟังก์ชันจะเรียงลำดับเอง หรือผู้เรียกต้องส่งอาร์เรย์ที่เรียงแล้วเข้ามา
    • เมื่อส่งอาร์เรย์ด้วยการอ้างอิง การแก้ไขข้อมูลต้นฉบับได้หรือไม่ก็เป็นส่วนหนึ่งของสัญญา API
    • ตัวเลือกเหล่านี้ยังเชื่อมโยงกับการพูดคุยเรื่องประสิทธิภาพด้วย
  • การคำนวณดัชนีมีหลุมพรางแบบ off-by-one
    • แทนที่จะดูแค่ว่าพลาดหรือไม่ สามารถสังเกตได้ว่าผู้สมัครดีบักโจทย์เล็ก ๆ อย่างไร
  • วิธีคืนค่าจะแตกต่างกันตามความยาวของอาร์เรย์
    • ความยาวคู่จะคืนค่าเฉลี่ยของสองค่าตรงกลาง
    • ความยาวคี่จะคืนค่าตรงกลาง

บทสนทนาที่ต่อยอดได้จากโจทย์สั้น ๆ

  • มัธยฐานสามารถนำไปสู่ การพูดคุยเชิงสถิติ เช่น ทำไมในหลายกรณีจึงอาจเป็นตัวเลือกที่ดีกว่าค่าเฉลี่ย
  • อินพุตและค่าที่คาดหวังเรียบง่าย ทำให้ทดสอบได้ง่าย และช่วยให้ผู้สมัครแสดงเซนส์ด้านการทดสอบได้ดี
  • ใน Python ยังเป็นโอกาสให้แสดงความรู้เกี่ยวกับไลบรารีมาตรฐาน statistics ด้วย

ทางเลือกในตัวอย่างการทำงานด้วย Python

  • ลิสต์ว่างจะทำให้เกิด ValueError("median called with empty list")
  • ใช้ sorted(numbers) จึงไม่เรียงลำดับลิสต์อินพุตโดยตรง ต่างจาก numbers.sort()
  • หาความยาวด้วย len(numbers) และคำนวณดัชนีตรงกลางด้วย mid = length // 2
  • ความยาวคู่จะคืนค่า (numbers[mid - 1] + numbers[mid]) / 2.0 ส่วนความยาวคี่จะคืนค่า numbers[mid]

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

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

 
GN⁺ 4 시간 전
ความคิดเห็นบน Lobste.rs

  • ผมไม่ค่อยเข้าใจบทความนี้ ดูเหมือนผู้เขียนจะไม่รู้ว่า ค่ามัธยฐานสามารถคำนวณได้ใน O(n) ดูเพิ่มเติม: https://rcoh.me/posts/linear-time-median-finding/
    ดังนั้นคำพูดที่ว่า “ตัวเลขต้องถูกเรียงมาตั้งแต่แรก” จึงผิด ด้วยเหตุนี้ผมจึงไม่คิดว่านี่เป็นโจทย์สัมภาษณ์ที่ดี คำตอบที่เหมาะที่สุดเป็นอัลกอริทึมที่ซับซ้อน ถ้าไม่ได้ท่องจำมาก่อนก็ยากที่จะคาดหวังให้คิดออกสด ๆ และการรู้ว่าผู้สมัครท่องจำมาหรือไม่ก็ไม่ได้ช่วยประเมินผู้สมัครมากนัก
    อย่างมากก็อาจให้ผู้สมัครเสนอ วิธีแบบง่าย ๆ ที่เรียงอาร์เรย์ด้วยฟังก์ชันไลบรารีแล้วคืนค่าตรงกลางได้

    • ผมเกือบโมโห เพราะจำได้ว่าเคยเสนอวิธี n*log(n) กับโจทย์นี้แล้วถูกคัดออกในการสัมภาษณ์ทางโทรศัพท์
      ภายหลังได้เรียน quickselect ในวิชาอัลกอริทึม แล้วคิดว่า “คงไม่ได้คาดหวังให้คิดอันนี้ออกสด ๆ หรอกใช่ไหม” แต่ก็อาจเป็นได้ว่าผมไม่เหมาะกับตำแหน่งนั้นเอง
    • ผมเป็นผู้เขียนบทความ ถ้าผู้สมัครพูดถึง quickselect ผมคงประทับใจพอสมควร ถึงอย่างนั้นผมก็ยังไม่คิดว่านี่เป็นคำถามที่แย่ แค่อัลกอริทึมเชิงสัญชาตญาณก็มีเรื่องให้คุยกันได้เยอะแล้ว
      ส่วนที่บอกว่าคาดหวังได้ให้ผู้สมัครทำ “วิธีแบบง่าย ๆ ที่เรียงอาร์เรย์ด้วยฟังก์ชันไลบรารีแล้วคืนค่าตรงกลาง” นั้น ผมไม่ได้คาดหวังให้ผู้สมัครเขียนโค้ดได้ดีกว่า python standard library หรอก

  • แถมยังรู้ได้ทันทีด้วยว่าใครเคยเรียนอัลกอริทึม หรืออย่างน้อยก็เตรียมตัวสัมภาษณ์มา เพราะเขาน่าจะเสนอให้ใช้ quickselect: https://en.wikipedia.org/wiki/Quickselect

    • แปลกใจที่ไม่มีใครพูดถึงเรื่องนั้น ถ้าได้คำถามนี้แล้วใช้ C++ ผมน่าจะใช้ nth_element
      และถ้าต้องเขียน quickselect เองตั้งแต่ต้นก็ทำได้ โดยพื้นฐานแล้วมันใกล้เคียงกับ การแบ่งพาร์ทิชัน + binary search
    • ในทางปฏิบัติผมว่าไม่ใช่อย่างนั้น คำถามนี้ดูเหมือนเป็นโจทย์พื้นฐานเพื่อดูว่า “เขียนโปรแกรมจริง ๆ ได้ไหม?” หรือก็คือ “คนคัดกรองทำงานของตัวเองดีหรือเปล่า?” ถึงจะอธิบาย quickselect จากความจำได้เป็นฉาก ๆ ผมก็ไม่น่าจะทำได้สมบูรณ์แบบ และเพื่อไม่ให้เสียเวลาผู้สัมภาษณ์ ผมจะเลือก วิธีแบบง่าย ๆ แทน
    • กรณีที่ความยาวอาร์เรย์เป็นเลขคู่น่าสนใจ จะรัน quickselect แบบทั่วไปสองครั้งสำหรับดัชนีกลางสองตำแหน่ง หรือปรับ quickselect ให้เข้ากับงานนี้ก็ได้ ซึ่งทั้งสองวิธีอาจกลายเป็นการทำสิ่งเดียวกันในทางปฏิบัติ
    • ผมสับสนเพราะมีข้อกำหนดว่าลิสต์ต้องถูกเรียงแล้ว ทั้งที่ตามสัญชาตญาณก็ไม่จำเป็นต้องเป็นอย่างนั้น
    • คำตอบที่ได้จาก LLM คืออันนี้ และยังแถม เวอร์ชันแบบ immutable ให้เลือกใช้หากจำเป็นด้วย

  • ใน Python ประเภท int ไม่มี overflow แต่ถ้าใช้ C หรือ C++ หรือ Go ในกรณีอาร์เรย์ยาวเป็นเลขคู่ ไม่ต้องกังวลเรื่อง integer overflow จากการบวก ด้วยหรือ?

    • การบวกนั้นเกิดขึ้นกับ float ไม่ใช่ int ถึงอย่างนั้นก็ยังมีโอกาส overflow จนกลายเป็น inf ได้ ถ้าองค์ประกอบสองตัวในอาร์เรย์เป็น sys.float_info.max ทั้งคู่ คำตอบควรเป็น sys.float_info.max แต่ผลลัพธ์การบวกจะเป็น inf และหารด้วย 2 แล้วก็ยังเป็น inf อยู่
      อาจพยายามแก้โดยกระจายการหารด้วย 2 เข้าไปในการบวก แต่ถ้าทำอย่างนั้นจะได้คำตอบผิดกับ subnormal numbers ดูเหมือนคนส่วนใหญ่จะสมมติว่าในโปรแกรมไม่มีตัวเลขใหญ่พอที่จะทำให้ปัญหานี้เกิดขึ้น numpy เองก็ให้ 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)

  • จริง ๆ แล้ววิธีเลือกค่ามัธยฐานเองก็มีหลายแบบ เช่น จะใช้ linear interpolation หรือใช้ค่าขอบบน หรือค่าขอบล่าง
    และถ้าขยับไปเรื่อง quantile ก็คุยกันได้เป็นชั่วโมง การเลือกค่าเดียวกับการเลือกหลายค่าพร้อมกันควรมีแนวทางต่างกัน

  • ผมไม่ใช้โจทย์สัมภาษณ์แบบบทความต้นฉบับ ผมต้องการ ความลื่นไหล หมายถึงความยากในการแก้โจทย์ควรเปลี่ยนไปอย่างราบรื่นตามความสามารถและประสบการณ์ของผู้สมัคร โดยเฉพาะถ้าการรู้ว่ามีฟังก์ชันไลบรารีหรืออัลกอริทึมอย่าง quickselect หรือ radix sort อยู่ ทำให้ผลลัพธ์เปลี่ยนอย่างฉับพลัน แบบนั้นไม่ใช่โจทย์ที่ดีสำหรับการวัดผล
    มันกลายเป็นการทดสอบว่ารู้จัก ของวิเศษ บางอย่างหรือไม่ แทนที่จะวัดประสบการณ์และความสามารถของผู้สมัคร แม้จะชดเชยด้วยคำถามต่อเนื่องได้ แต่การเริ่มด้วยโจทย์ที่ลื่นไหลกว่าย่อมดีกว่า

    • ถ้าแชร์ได้ ผมอยากรู้มากว่าตัวอย่างที่เป็นรูปธรรมของ โจทย์ที่ลื่นไหล แบบนั้นคืออะไร