Buổi phỏng vấn kỹ thuật thất bại (2022)
(xeiaso.net)- Palima Aethera có vẻ như là ứng viên có thể cứu hạ tầng hỗn loạn của Techaro, nhưng lại cố tình đưa ra một lời giải sắp xếp kỳ quặc trong phần live coding, làm đảo lộn bầu không khí buổi phỏng vấn
- Người phỏng vấn Jeff, sau khi xác nhận cách phát âm tên và việc đó có phải khuôn mặt thật hay không, tỏ ra rất quan tâm đến kinh nghiệm hạ tầng của Palima tại MovieFlix và trường hợp chọn FreeBSD
- Trong bài toán sắp xếp mảng số, Palima triển khai sleepsort bằng Haskell: tạo một luồng cho mỗi giá trị, ngủ trong khoảng thời gian tỷ lệ với giá trị đó rồi in ra
- Palima khăng khăng gọi lời giải này là “sắp xếp thời gian hằng số”, và giải thích rằng đã giảm độ trễ theo bội số micro giây từ
100000xuống10000để tối ưu nhanh hơn 10 lần, khiến Jeff bật cười - Sau buổi phỏng vấn, Palima đoán mình sẽ bị loại, nhưng Techaro lại gửi ý định tuyển dụng với một khoản tiền khá lớn, còn Palima thì quyết định ngủ vì tin rằng mọi việc sẽ tự sắp xếp ổn thỏa
Ngày phỏng vấn bắt đầu từ trong mơ
- Trong mơ, Palima nhận ra mình đang mơ khi thấy bùa tỉnh thức trên cổ tay đã biến mất
- Sau khi tỉnh dậy vào buổi sáng vì đồng hồ đeo tay rung lên, Palima nhớ ra rằng hôm đó có một lịch hẹn quan trọng
- Việc đi làm kết thúc chỉ trong 30 giây, và Palima ngồi vào chiếc ghế đã được cải tạo để chứa đuôi và vây lưng
- Máy trạm báo rằng Firefox đã cũ, rồi một script biên dịch và chạy phiên bản mới
Bắt đầu buổi phỏng vấn với Techaro
- Cuộc họp video diễn ra qua dịch vụ dòng E100, và Palima bật đèn chiếu cho camera
- Người phỏng vấn đầu tiên, Jeff, phát âm sai tên của Palima rồi lập tức sửa lại
- Palima cho biết
Pa-lee-mah, cònAetherađược phát âm làAy-theer-ah - Jeff nói sẽ ghi chú lại để những người khác cũng có thể gọi đúng
- Palima cho biết
- Khi Jeff hỏi có dùng avatar ảo hay không, Palima trả lời: “Đây là khuôn mặt thật.”
- Chỉ nhìn vào mô tả tuyển dụng thôi, Palima đã nhận ra hạ tầng của Techaro đang hỗn loạn và ở trong tình trạng cần một anh hùng
Giới thiệu sự nghiệp và kinh nghiệm hạ tầng
- Palima giới thiệu rằng mình đã làm rất nhiều công việc tạo ra các thiết bị tự động số rồi đưa chúng ra thế giới để hoàn thành mục tiêu
- Tại MovieFlix, Palima đã góp phần xây dựng hạ tầng streaming đồng thời cho các bộ phim và chương trình TV nổi tiếng
- Cũng có nhiều dự án không thể công khai, và Palima nói thêm rằng hiện Jeff đang hưởng lợi từ ít nhất ba trong số đó
- Lý do muốn gia nhập một công ty nhỏ là vì muốn hiểu con người ở mức cá nhân hơn; sức hấp dẫn của việc làm như một linh kiện vô danh trong cỗ máy sẽ không kéo dài lâu
- Dự án hạ tầng yêu thích là benchmark kernel hệ điều hành cho backend của MovieFlix
- Palima từng hy vọng Linux sẽ thắng, nhưng sau
epoll(7)thì FreeBSD chạy nhanh hơn, nên đã chọn FreeBSD - Palima nói thêm rằng có lẽ mình vẫn còn quyền commit trên FreeBSD
- Palima từng hy vọng Linux sẽ thắng, nhưng sau
Live coding: sleepsort
- Jeff giải thích rằng nền tảng của Palima có vẻ phù hợp với kiểu người Techaro đang tìm, nhưng để tất cả được đánh giá theo cùng một tiêu chuẩn thì vẫn phải làm bài coding challenge
- Bài tập là sắp xếp một mảng số trên trang web và giải thích cả cách sắp xếp
- Được tự do chọn ngôn ngữ, và Palima đã viết mã Haskell
- Cách triển khai là tạo một green thread riêng cho mỗi số, rồi sau
threadDelay (100000 * time)thì ghi giá trị vào kênh để in ra - Palima nói rằng kiểu sắp xếp này không dùng phép so sánh, và “đôi khi chỉ cần nghỉ một chút là được”
- Khi Jeff hỏi liệu thời gian có thay đổi theo giá trị đầu vào hay không, Palima trả lời rằng độ phức tạp thời gian không bận tâm đến các tác dụng phụ như thời gian
Tối ưu hóa và kết quả ngoài dự đoán
- Khi Jeff hỏi cách tối ưu, Palima chỉ thay đổi bội số độ trễ
- Giảm
100000 * timexuống10000 * time - Palima giải thích rằng giờ nó đã nhanh hơn 10 lần
- Giảm
- Cuối cùng Jeff cười lớn, còn khi bị hỏi vì sao lại dùng một thuật toán sắp xếp kỳ quặc như vậy, Palima đáp lại: “Sao anh lại hỏi một câu kỳ quặc như thế?”
- Palima cho rằng Techaro không đủ phức tạp để chứa mình, và rằng thay vì Kubernetes thì chỉ một máy chủ chuyên dụng đơn lẻ của Typhoon Digital cũng đã đủ
- Sau khi kết thúc buổi phỏng vấn, Palima dự đoán rằng email từ chối sẽ sớm xuất hiện
- Nhưng Techaro lại gửi email nói rằng muốn tuyển với một khoản tiền đáng kể, khiến Palima tự hỏi liệu họ có biết mình đang định gánh lấy điều gì không
- Palima quyết định đi ngủ lại, vì tin rằng đến tối thì công việc sẽ tự sắp xếp ổn thỏa
1 bình luận
Ý kiến trên Hacker News
Đây không phải thời gian hằng số, cũng không phải thời gian đa thức, mà là thời gian giả đa thức. Có vẻ nó sẽ thất bại với số âm, và để tuyến tính theo số bit dùng để biểu diễn đầu vào thì cần kiểu như
10000 * log(time + min(time) + 1)Trong lý thuyết độ phức tạp tính toán, việc một thuật toán số học chạy trong thời gian giả đa thức nghĩa là thời gian chạy là đa thức theo giá trị số của đầu vào, tức số nguyên lớn nhất xuất hiện trong đầu vào, chứ không phải đa thức theo độ dài đầu vào (số bit cần để biểu diễn con số đó)
https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
Độ phức tạp tính toán nói về số bước trong mô hình tính toán, chứ không nói về việc đồng hồ thực đã trôi qua bao lâu. sleep sort dựa vào tính chất của bộ lập lịch hệ điều hành, và trong môi trường thời gian ảo thì thời gian sẽ nhảy ngay tới sự kiện được lên lịch tiếp theo. Nếu giả định đó là mô hình tính toán thì trên thực tế nó chạy với độ phức tạp đa thức
Và nếu định dạy người khác thì ít nhất cũng nên viết đúng chính tả của pseudo-polynomial
1lặp theo độ dài của từng giá trị và dùng0để phân táchViệc đổi nó lại thành các số nguyên là tuyến tính, sau đó gọi hộp cũ rồi trả lại kết quả thì giờ đây nó đã thành thời gian đa thức theo độ dài đầu vào của tôi. Dù tôi nói là số nguyên, mấu chốt nằm ở cách mã hóa, nên với số thập phân cũng có thể dùng một
0cho dấu chấm và00để ngăn cách đầu vàoDù sao thì trọng tâm của trò đùa chẳng phải là thời gian ngủ không được tính sao? Trong lúc đó máy tính vẫn có thể làm việc khác. Kiểu “ngu nhưng tôi thích” nên nghe cũng khá thuyết phục
sleep sort bắt nguồn từ /prog/ [0]. Chắc cũng có kha khá người chỉ đọc HN từng tham gia luồng sleep sort ngày đó, có khi xena cũng là một trong số đó :)
[0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...
<=>để dùng khi muốn kiểm tra “nhỏ hơn, bằng hoặc lớn hơn”. Thiên tài thậtNhư tác giả bài gốc đã nói, bài này rất giống loạt Interview của aphyr, như “Rewriting the Technical Interview”, về mặt phong cách kể chuyện. Tất cả đều đọc rất vui
[0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
Trích đoạn:
Máy tính muốn sắp xếp thì phải đọc đầu vào, nên ít nhất cũng cần thời gian tuyến tính. Nếu không biết thêm thông tin nào khác về đầu vào như phân phối đều thì lại càng đúng
Có nhiều kiểu sắp xếp thời gian tuyến tính như sleep sort, postman sort, counting sort, v.v. Nhưng chỉ áp dụng cho tập số hoặc khóa có thể sắp xếp bị giới hạn
Tuy nhiên, nếu dùng bàn tính thay vì máy tính thì có một kiểu sắp xếp thời gian hằng số gần như là thật: https://en.wikipedia.org/wiki/Bead_sort
Một câu chuyện dễ thương, nhưng theo bất kỳ nghĩa nào thì đây cũng không phải là thời gian hằng số
Việc tạo
Nluồng và thêm tất cả vào danh sách đánh thức đã được sắp xếp sẽ mất từ O(N log N) đến O(N^2) tùy vào hệ điều hành hoặc runtime ngôn ngữỞ đâu đó phía sau sẽ có một danh sách sắp xếp, heap, hoặc thuật toán N^2. Tương tự, bản thân sleep sort cũng phải đánh thức N luồng để in ra N phần tử đã được sắp xếp, nên tối thiểu là thời gian tuyến tính
Tệ hơn nữa, thời gian thực tế theo đồng hồ cũng tăng theo độ lớn của các giá trị. Có thể tìm giá trị nhỏ nhất và lớn nhất trước để nén phạm vi, nhưng việc đó cũng là thời gian tuyến tính
Đây là một trò chơi chữ hai nghĩa dựa trên hai cách hiểu xung đột nhau của từ “thời gian”. Đúng là theo góc nhìn phân tích độ phức tạp thì không thể có một thuật toán sắp xếp chạy trong thời gian hằng số
Ý thực sự của trò đùa là thời gian theo đồng hồ. Trong phỏng vấn thì kiểu thời gian đó phù hợp hơn, và thực tế khi ai đó đưa ra kiểu bài “hãy viết hàm sắp xếp số nguyên”, hiếm khi họ chỉ dùng các số nhỏ hơn 100, nên chương trình này cho cảm giác gần như chạy ngay lập tức
Đó là một trò đùa siêu ngôn ngữ khá tinh tế, trêu chọc bằng cách đảo ngược hiểu biết về cách khoa học máy tính vận hành. Tiếc là trò đùa không trúng đích
https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
sleepcuối cùng cũng phải quy về số nguyên, nên có thể dùng thứ như radix sort để xử lý trong thời gian tuyến tínhCó những không gian bài toán mà việc phụ thuộc vào độ lớn của giá trị lớn nhất vẫn là có lợi
Tất nhiên, không có hệ thống thực tế nào như vậy. Timeout của system call thường không phải nơi cách đó có lợi. Và dĩ nhiên thay vì dùng cách tỷ lệ tuyến tính theo giá trị lớn nhất, tốt hơn là áp dụng trực tiếp radix sort vốn chỉ phụ thuộc vào
log(max_value)Nluồng và thêm chúng vào danh sách đánh thức đã sắp xếp ở mức O(N log N) đến O(N^2) không phải là giới hạn căn bản của hệ thống lập lịchĐặc biệt là nếu tính đến cả phần cứng chuyên dụng có thể cho phép lập lịch thời gian hằng số theo số lượng luồng thì lại càng không phải. Ví dụ, dù hoàn toàn không khả thi về kinh tế, bạn có thể tạo một scheduler dùng laser bắn các gói thông tin qua một tập gương khổng lồ đặt ở các khoảng cách khác nhau rồi phản hồi về cảm biến nối với máy tính
Cách đó dùng tốc độ ánh sáng để tạo độ trễ đúng bằng thời gian chỉ định. Vì vậy sleep sort không về bản chất phụ thuộc vào độ phức tạp thuật toán ẩn của một cách lập lịch luồng nào đó, và dù không thực dụng thì về lý thuyết vẫn có thể tối ưu xuống O(1)
Nếu thích cái này thì còn có Protos, kiểu như một tác phẩm kế tiếp: https://xeiaso.net/blog/protos
Tôi vẫn đang viết thêm các câu chuyện trong “vũ trụ” này, nhưng phải mất một lúc năng lượng châm biếm mới tích đủ. Phần tiếp theo có thể sẽ là điện toán không gian
Dù vậy có vẻ vũ trụ đó đặt tên giỏi hơn
Đoạn đổi
threadDelay (100000 * time)thànhthreadDelay (10000 * time)rồi nói “giờ nhanh hơn gấp mười lần” có liên quan đến bài này: https://thedailywtf.com/articles/The-Speedup-LoopTôi chưa đọc bài, nhưng ghét mấy chuyện như thế này. Trước đây tôi từng phỏng vấn từ xa với Meta, và người bên kia cứ ăn vào micro suốt buổi
Phân tâm đến mức tôi còn quên cả cách viết vòng lặp for
Nếu đang có việc thì còn phải xin nghỉ phép, rồi chịu đủ thứ căng thẳng kiểu “mình có đang phí ngày nghỉ ít ỏi vào chuyện này không?”, “có chỗ đậu xe không?”, “mình có tới đúng giờ không?” Sau đó lại chỉ có một buổi “phỏng vấn ban đầu” 30 phút, rồi chờ vài tuần để được mời vào vòng phỏng vấn tử tế hoặc bị bặt vô âm tín
Toàn bộ quá trình có thể kéo dài một tháng, và cần ít nhất hai ngày nghỉ cùng kha khá thời gian di chuyển
Giờ thì recruiter hoặc HR gọi điện hỏi có thể gọi video không, rồi ngay trong ngày nói chuyện 15–20 phút, sau đó chuyển CV cho người ra quyết định và sắp xếp một hay nhiều buổi phỏng vấn video hoặc phiên kỹ thuật. Một số công ty còn cho làm bài kiểm tra tính cách/kỹ thuật thoải mái tại nhà
Nếu làm việc từ xa thì có thể xử lý hết trong giờ nghỉ trưa. Băng thông giao tiếp trực tiếp đúng là lớn hơn nhiều, nhưng chỉ có từ xa mới cho phép buổi sáng phỏng vấn với công ty ở Tel Aviv, buổi trưa với công ty ở Warsaw, và buổi tối với công ty ở California
Tạo 1000 luồng ít nhất cũng là thời gian tuyến tính chứ? Có thể giảm xuống tới log, nhưng tôi không nghĩ đoạn code đó tự động làm được vậy
Để sleep sort là thời gian hằng số thì đầu vào phải có cận trên, tức giới hạn cho số lớn nhất, và phải bỏ qua việc đọc và xử lý đầu vào, tạo luồng, cùng các tác vụ tùy ý khác
Nhưng nếu cho phép như vậy thì mọi thuật toán sắp xếp khác cũng đều thành thời gian hằng số. Có vẻ chỉ cần cho phép một trong hai điều đó là đủ
Nếu runtime của thread duy trì một khái niệm thời gian riêng, thì thuật toán thậm chí không cần ngủ theo thời gian thực
Sau khi mọi thread được tạo xong, runtime có thể nhận ra rằng tất cả thread đều đang nhàn rỗi và thread tiếp theo sẽ được lên lịch là thread ở thời điểm N, nên chỉ cần cập nhật thời gian hiện tại thành N rồi chạy thread đó. Lặp lại việc này thì sẽ thu được một mảng đã sắp xếp mà không cần
sleepnàoRốt cuộc, việc sắp xếp đã hoàn tất ngay khi các thread bắt đầu đi ngủ, và sau đó chúng đã tự đăng ký với một bộ điều phối sẽ đánh thức chúng sau này, ví dụ như timer wheel. Không thực sự cần phải thực hiện thao tác ngủ
Không rõ Haskell thế nào, nhưng runtime tokio của Rust cho phép điều này với
start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...Bỏ qua nhiều tầng trừu tượng và các chi tiết triển khai đã lược bớt, thì việc sắp xếp giá trị bằng kiểu scheduler này đơn giản chỉ là heap sort :)