Các cuộc phỏng vấn về lập trình ngày càng khó hơn và việc chuẩn bị để có kết quả tốt không phải là một việc dễ dàng. Không có giới hạn cho các loại câu hỏi mà nhà tuyển dụng có thể được đưa ra trong một cuộc phỏng vấn. Tùy vào kiến thức, kinh nghiệm và kỹ năng của mỗi người mà các câu hỏi có thể khó với người này nhưng lại có thể dễ dàng với người khác và ngược lại.
Bài viết này tổng hợp 3 câu hỏi khó nhất thường được hỏi trong các cuộc phỏng vấn về lập trình tại các công ty công nghệ hàng đầu FAANG (Facebook, Apple, Amazon, Netflix và Google). Cho dù có hay không có cơ hội để tham gia vào các cuộc phỏng vấn của các công ty đó, các câu hỏi này cũng giúp cho bạn học hỏi thêm được nhiều điều. Bạn có cũng có thể xem lại 11 câu hỏi phỏng vấn về lập trình Python của các công ty FAANG trong bài viết trước
1-Cách thiết kế bộ thu gom rác – design garbage collector
Các vấn đề liên quan đến garbage collector (bộ thu gom rác) thường là rất khó. Mục đích của hệ thống thu gom rác là tự động khôi phục bộ nhớ không sử dụng, giúp cho bộ nhớ heap luôn có dung lượng cho các objects mới được tạo. Garbage collection (thu gom rác) là một quá trình quản lý bộ nhớ tự động và là một khái niệm quan trọng trong một số ngôn ngữ lập trình hiện đại. Bất kể bạn làm việc bằng ngôn ngữ lập trình nào nào, điều quan trọng là phải biết làm thế nào ngôn ngữ đó giải quyết vấn đề này một cách hiệu quả.
Trong các cuộc phỏng vấn về thiết kế hệ thống, người phỏng vấn thường đặt ra các câu hỏi về chủ đề này và không chỉ có ở các công ty FAANG. Dưới đây là một số vấn đề đáng chú ý bạn cần nắm vững để có thể trả lời tốt câu hỏi này.
Yêu cầu của hệ thống garbage collector
1/ Yêu cầu chức năng
Có hai chức năng cơ bản mà hệ thống thu gom rác của sẽ cần thực hiện:
- Tìm kiếm các đối tượng không còn được tham chiếu (referenced).
- Giải phóng các đối tượng không được tham chiếu này khỏi bộ nhớ.
2/ Yêu cầu phi chức năng (non-functional)
Ngoài các chức năng trên, việc triển khai tốt bộ thu gom rác cần có các thuộc tính sau để nâng cao trải nghiệm người dùng:
- Hiệu suất nhanh: thời gian chạy của bộ thu gom rác càng ngắn càng tốt.
- Độ tin cậy: việc triển khai GC phải luôn hoạt động chính xác.
- Sử dụng không gian tối thiểu: bộ thu gom rác cần sử dụng không gian bộ nhớ một cách hiệu quả.
Giải pháp để cải thiện hiệu suất: chia theo thế hệ
Các garbage collector thực hiện theo một chiến thuật chung là chia đối tượng theo thế hệ (generation). Ý tưởng garbarge collection thế hệ dựa trên giả thuyết thế hệ (generational hypothesis) của David Ungar , nói rằng nếu một vật thể tồn tại trong một khoảng thời gian nhất định, thì nó được kỳ vọng sẽ tồn tại lâu hơn. Các đối tượng mới có xu hướng biến thành rác nhanh hơn các đối tượng cũ.
Sử dụng giả thuyết này, chúng ta tạo ra một garbage collector có thể hoạt động theo từng bit, theo dõi các đối tượng trẻ thường xuyên hơn, vì chúng có xu hướng chết nhanh và giải phóng nhiều dung lượng hơn cho máy tính. Đối với các đối tượng cũ, chúng có thể được giám sát ít thường xuyên hơn. Cách tiếp cận này giúp tăng tốc hiệu suất và giảm thời gian tạm dừng cho ứng dụng.
Trong bộ thu gom rác thế hệ (generational garbage collectors), chẳng hạn như bộ thu gom rác được sử dụng trong Java, các đối tượng được chia thành các nhóm theo độ tuổi của chúng thành nhiều vùng được gọi là thế hệ, như thể hiện trong sơ đồ trên. Có Thế hệ trẻ, Thế hệ già và Thế hệ vĩnh viễn (Young Generation, Old Generation and Permanent Generation).
Thiết kế hệ thống garbage collector
Có một số cách khác nhau để thiết kế hệ thống garbage collector. Mặc dù việc triển khai thực tế phức tạp hơn và liên quan đến các tối ưu hóa khác nhau, chúng ta cần tìm hiểu về các khái niệm phổ biến nhất, bao gồm mark-and-sweep (đánh dấu và quét ) và reference counting (đếm tham chiếu) để có thể trả lời tốt trong phỏng vấn:
Thuật toán đánh mark-and-sweep
Một trong những hình thức thu gom rác đơn giản nhất là thuật toán mark-and-sweep. Nó được phát minh bởi John McCarthy khi phát triển ngôn ngữ lập trình LISP. LISP là ngôn ngữ lập trình đầu tiên được phát triển vào năm 1960, sử dụng bộ thu gom rác.
Thuật toán này là một bộ thu gom rác theo dõi (tracing garbage collector) vì nó theo dõi tất cả các đối tượng mà chương trình có thể truy cập trực tiếp hoặc gián tiếp. Như tên của nó, thuật toán bao gồm hai giai đoạn: đánh dấu và quét. Mọi đối tượng đều có một bit đánh dấu. Nó được lưu trữ trong header của object. Ngay sau khi đối tượng được tạo, bit đánh dấu của nó là 0 (false).
Ưu và nhược điểm của thuật toán mark and sweep:
Ưu điểm:
- Nó xử lý trường hợp với các tham chiếu theo chu kỳ, ngay cả trong trường hợp có chu kỳ, thuật toán này không bao giờ kết thúc trong một vòng lặp vô hạn.
- Không có thêm chi phí phát sinh trong quá trình thực hiện thuật toán.
Nhược điểm:
- Nhược điểm chính của phương pháp đánh dấu và quét là thực tế là việc thực thi chương trình bình thường bị tạm dừng trong khi thuật toán thu gom rác chạy.
- Điểm bất lợi khác là, sau khi Thuật toán Đánh dấu và Quét được chạy nhiều lần trên một chương trình, các đối tượng có thể truy cập cuối cùng bị phân tách bởi nhiều vùng nhớ nhỏ không sử dụng.
Tìm hiểu thêm về thuật toán mark-and-sweep tại đây
2- Bài toán tìm lượng đồng xu nhỏ nhất (Coin change problem)
Bài toán tìm lượng đồng xu nhỏ nhất, coin change prolem, thường thấy trong các cuộc phỏng vấn của Facebook và Amazon. Bạn được cung cấp tiền xu có mệnh giá khác nhau và tổng số tiền. Từ đó, bạn cần viết một hàm để tính số lượng xu ít nhất mà bạn cần để tạo nên số tiền đó. Nếu bạn không thể đạt được số tiền nhất định với bất kỳ sự kết hợp nào của các đồng xu, bạn sẽ trả về -1.
Dưới đây là ba cách bạn có thể giải quyết vấn đề này:
- Brute force
- Quy hoạch động theo cách tiếp cận từ trên xuống (Top-down) với Memoization.
- Quy hoạch động theo cách tiếp cận từ dưới lên (Bottom-up) với Tabularization.
Tìm hiểu thêm về:
- Các giải bài toán coin change problem trong bài viết của Andrew Romanenco
- Tìm hiểu về Memoization và Tabularzation trong quy hoạch động
3- Bài toán bữa tối của các triết gia (dining philosophers problem)
Bài toán nhà triết học ăn uống thường được sử dụng trong thiết kế thuật toán đồng thời để chứng minh các vấn đề với sự đồng bộ hóa và các kỹ thuật để giải quyết chúng. Bài toán nói rằng có năm triết gia đang ngồi quanh một chiếc bàn tròn. Các triết gia phải thay đổi suy nghĩ và ăn uống.
Mỗi triết gia có một bát thức ăn trước mặt họ và họ yêu cầu mỗi người cầm một đôi đũa để ăn. Tuy nhiên, chỉ có năm chiếc đũa có sẵn. Bạn cần thiết kế một giải pháp mà mỗi triết gia đều có thể ăn thức ăn của họ mà không gây ra bế tắc.
Với vấn đề này được dùng để minh họa các loại vấn đề mà bạn có thể gặp phải khi thực thi chương trình theo chuỗi và / hoặc xử lý khóa cẩu thả. Ý tưởng là giúp bạn suy nghĩ về những hạn chế và sắp xếp thứ tự phù hợp để hoàn thành nhiệm vụ này một cách hiệu quả nhất.
Để chuẩn bị cho câu hỏi này, bạn cần tìm hiểu sâu về đồng bộ hóa (synchronization), điều khiển đồng thời (concurrency control) và semaphores
Dưới đây là hai cách có thể để giải quyết vấn đề này:
Bài viết có tham khảo từ các nguồn:
Bạn có biết?
tham gia cộng đồng ITguru trên Linkedin, Facebook và các kênh mạng xã hội khác có thể giúp bạn nhanh chóng tìm được những chủ đề phát triển nghề nghiệp và cập nhật thông tin về việc làm IT mới nhất
Linkedin Page:
Facebook Group:
cơ hội việc làm IT : ITguru.vn
