Câu hỏi phỏng vấn kỹ sư phần mềm tôi thích: tính trung vị

 (krisshamloo.com)
1 điểm bởi GN⁺ 4 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Các bài toán cài đặt nhỏ trong phỏng vấn kỹ thuật có thể hiệu quả hơn những câu đố, và tính trung vị giúp bộc lộ cả năng lực lập trình cơ bản lẫn cảm quan thiết kế
  • Vì đây là bài toán cần sắp xếp, nó tự nhiên dẫn sang thảo luận API như hàm có nên tự sắp xếp hay người gọi phải sắp xếp trước, và có được thay đổi mảng gốc hay không
  • Nhánh xử lý cho độ dài lẻ và chẵn, tính chỉ mục, cùng các lỗi off-by-one rất phù hợp để quan sát quá trình gỡ lỗi của ứng viên
  • Trong một bài toán ngắn, có thể kiểm tra thêm sự khác biệt giữa trung vị và trung bình, mức độ dễ viết kiểm thử, cũng như hiểu biết về thư viện chuẩn statistics của Python
  • Cách cài đặt ví dụ sẽ ném ValueError với danh sách rỗng, sao chép rồi sắp xếp bằng sorted(), sau đó với độ dài chẵn trả về trung bình của hai giá trị ở giữa, còn độ dài lẻ trả về giá trị ở giữa

Vì sao bài toán trung vị phù hợp cho phỏng vấn

  • Một câu hỏi phỏng vấn kỹ thuật tốt không nên là bài toán đánh đố, mà phải có khả năng mở ra những chủ đề sâu hơn từ một cài đặt trực quan
  • Câu hỏi “hãy viết một hàm nhận vào mảng số và trả về trung vị” rất phù hợp để dùng như một tín hiệu kiểu Fizz Buzz nhằm xác nhận ứng viên có thực sự biết lập trình hay không
  • Việc rút gọn các giá trị trong mảng thành một kết quả là một năng lực cơ bản, và bản thân bài toán cũng đủ nhỏ để dễ quan sát cả phần trao đổi lẫn gỡ lỗi

Những điểm thể hiện khả năng phán đoán trong quá trình cài đặt

  • Để tính trung vị, trước hết cần sắp xếp
    • Cần quyết định liệu hàm sẽ tự sắp xếp hay người gọi phải truyền vào một mảng đã được sắp xếp
    • Khi mảng được truyền theo tham chiếu, việc có được phép thay đổi dữ liệu gốc hay không cũng là một phần của hợp đồng API
    • Những lựa chọn này cũng dẫn sang thảo luận về hiệu năng
  • Việc tính chỉ mục có bẫy off-by-one
    • Quan trọng không chỉ là có mắc lỗi hay không, mà còn là cách ứng viên gỡ lỗi một vấn đề nhỏ như vậy
  • Cách trả về thay đổi theo độ dài của mảng
    • Với độ dài chẵn, trả về trung bình của hai giá trị ở giữa
    • Với độ dài lẻ, trả về giá trị ở giữa

Cuộc trò chuyện có thể mở rộng từ một bài toán ngắn

  • Có thể dẫn sang thảo luận thống kê, chẳng hạn vì sao trong đa số trường hợp trung vị có thể là lựa chọn tốt hơn trung bình
  • Đầu vào và giá trị kỳ vọng đều đơn giản nên rất dễ kiểm thử, phù hợp để ứng viên thể hiện cảm quan về kiểm thử
  • Trong Python, đây cũng là cơ hội để bộc lộ hiểu biết về thư viện chuẩn statistics

Các lựa chọn trong ví dụ cài đặt Python

  • Với danh sách rỗng, phát sinh ValueError("median called with empty list")
  • Dùng sorted(numbers) nên khác với numbers.sort() ở chỗ không sắp xếp trực tiếp danh sách đầu vào
  • Độ dài được lấy bằng len(numbers), và chỉ mục giữa được tính bằng mid = length // 2
  • Với độ dài chẵn, trả về (numbers[mid - 1] + numbers[mid]) / 2.0, còn với độ dài lẻ, trả về numbers[mid]

Bài viết liên quan

1 bình luận

 
GN⁺ 4 giờ trước
Các ý kiến trên Lobste.rs

  • Tôi không hiểu rõ bài này lắm. Có vẻ tác giả không biết rằng trung vị có thể được tính trong O(n). Tham khảo: https://rcoh.me/posts/linear-time-median-finding/
    Vì vậy câu “các số phải được sắp xếp ngay từ đầu” là sai. Vì lý do này, tôi cũng không nghĩ đây là một câu hỏi phỏng vấn hay. Lời giải tối ưu là một thuật toán phức tạp, nên nếu không phải đã thuộc sẵn thì khó có thể kỳ vọng ứng viên nghĩ ra ngay tại chỗ, và việc họ có thuộc hay không cũng không giúp ích nhiều cho việc đánh giá ứng viên.
    Cùng lắm có thể yêu cầu ứng viên đưa ra lời giải ngây thơ: sắp xếp mảng bằng hàm thư viện rồi trả về giá trị ở giữa

    • Tôi nhớ mình từng bị loại ở vòng phỏng vấn qua điện thoại vì đưa ra lời giải n*log(n) cho bài này, nên suýt nữa đã nổi cáu
      Sau này tôi học quickselect trong lớp thuật toán, và đã nghĩ “chắc họ không kỳ vọng mình nghĩ ra cái này ngay tại chỗ đâu nhỉ”. Mà cũng có thể tôi không phù hợp với vị trí đó
    • Tôi là tác giả bài viết. Nếu ứng viên nhắc đến quickselect thì tôi nghĩ khá ấn tượng. Dù vậy tôi không nghĩ đây là một câu hỏi tệ. Chỉ với thuật toán trực quan thôi cũng đã có nhiều chuyện để bàn
      Về ý kiến rằng có thể kỳ vọng “lời giải ngây thơ: sắp xếp mảng bằng hàm thư viện rồi trả về giá trị ở giữa”, tôi không kỳ vọng ứng viên viết mã tốt hơn python standard library

  • Như phần thưởng thêm, có thể biết ngay ai đó đã học thuật toán hay ít nhất đã chuẩn bị phỏng vấn hay chưa. Vì họ sẽ đề xuất dùng quickselect: https://en.wikipedia.org/wiki/Quickselect

    • Tôi ngạc nhiên vì nó không được nhắc đến. Nếu nhận câu hỏi này và dùng C++, chắc tôi sẽ dùng nth_element
      Và nếu phải tự viết quickselect từ đầu thì tôi cũng làm được. Về cơ bản nó gần với phân hoạch + tìm kiếm nhị phân
    • Thực tế tôi không nghĩ vậy. Câu hỏi này trông giống một bài kiểm tra cơ bản kiểu “có thật sự lập trình được không?”, tức là “người sàng lọc có làm đúng việc của mình không?”. Dù có thể đọc vanh vách quickselect trong đầu, tôi cũng không nghĩ mình sẽ làm hoàn hảo, và để không lãng phí thời gian của người phỏng vấn, tôi sẽ chọn lời giải ngây thơ
    • Trường hợp độ dài mảng là số chẵn khá thú vị. Có thể chạy quickselect thông thường hai lần cho hai chỉ số ở giữa, hoặc điều chỉnh quickselect cho phù hợp với bài toán. Hai cách đó về thực chất có thể trở thành cùng một việc
    • Tôi đã bối rối vì có yêu cầu rằng danh sách phải được sắp xếp. Theo trực giác thì cũng không nhất thiết phải như vậy
    • Câu trả lời tôi nhận được từ LLM là như thế này, và còn có thêm cả biến thể bất biến có thể chọn nếu cần

  • Kiểu int của Python không bị tràn số, nhưng nếu dùng C, C++ hoặc Go thì chẳng phải ở nhánh mảng có độ dài chẵn cũng phải lo tràn phép cộng sao?

    • Phép cộng đó diễn ra trên float chứ không phải int. Dù vậy vẫn có khả năng tràn thành inf. Nếu hai phần tử của mảng đều là sys.float_info.max thì đáp án cũng phải là sys.float_info.max, nhưng kết quả phép cộng sẽ thành inf, và chia nó cho 2 thì vẫn là inf
      Có thể cố sửa bằng cách phân phối phép chia cho 2 vào phép cộng, nhưng như vậy sẽ cho đáp án sai với số phi chuẩn hóa. Có vẻ đa số giả định rằng trong chương trình sẽ không xuất hiện các số đủ lớn để gây ra vấn đề này. numpy ở đây cũng trả về inf kèm cảnh báo: 
      >>> 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)

  • Thực ra ngay cả cách chọn chính giá trị trung vị cũng có nhiều kiểu. Có các lựa chọn như dùng nội suy tuyến tính, lấy cận trên, hay lấy cận dưới
    Và nếu chuyển sang phân vị thì có thể nói chuyện hàng giờ. Chọn một giá trị và chọn nhiều giá trị cùng lúc nên có cách tiếp cận khác nhau

  • Tôi không dùng dạng câu hỏi phỏng vấn như bài gốc. Tôi yêu cầu độ mượt, nghĩa là độ khó của việc giải bài phải thay đổi một cách trơn tru theo năng lực và kinh nghiệm của ứng viên. Đặc biệt, nếu việc biết đến sự tồn tại của hàm thư viện, quickselect, hay các thuật toán như sắp xếp cơ số làm kết quả thay đổi đột ngột, thì đó không phải là một bài tốt để đo lường
    Như vậy là đang kiểm tra xem ứng viên có biết một bảo vật ma thuật cụ thể hay không, chứ không phải đo kinh nghiệm và năng lực của họ. Có thể bù đắp bằng các câu hỏi tiếp theo, nhưng tốt hơn là ngay từ đầu nên đưa ra một bài toán mượt hơn

    • Nếu có thể chia sẻ, tôi rất tò mò về ví dụ cụ thể của một bài toán mượt như vậy