Microsoft nổi tiếng là có các câu hỏi phỏng vấn nhân viên mới mang tính kỹ thuật theo dạng đố “mẹo” (đa số là về thuật toán hoặc lập trình C/C++). Có nhiều bộ sưu tập các câu hỏi dạng này đã từng được hỏi ở các cuộc phỏng vấn ở Microsoft. Gần đây Google cũng phỏng vấn theo kiểu tương tự. Mỗi câu trả lời chỉ được cho khoảng 5-10 phút suy nghĩ. Đôi khi người ta quan tâm đến quá trình suy nghĩ của bạn hơn là bản thân câu trả lời.
Trong chuỗi bài này tôi sẽ nêu chọn lọc một số câu hỏi tôi thích nhất. Các câu hỏi được chọn không nhất thiết là khó nhất, tiêu chuẩn là gọn gàng và đẹp.
- Cho một danh sách liên kết đơn (simple linked list) hữu hạn. Có hai trường hợp: một là cuối danh sách trỏ về NULL, hai là trỏ về một phần tử đã gặp – tạo nên một vòng tròn trong danh sách.
Ví dụ trường hợp 1: A –> B –> C –> D –> NULL.
Ví dụ trường hợp 2: A –> B –> C –> D –> E –> F –> C.
Cho trước một con trỏ vào một danh sách liên kết đơn L nào đó, hữu hạn nhưng có thể có độ dài tùy ý. Làm thế nào để kiểm tra nhanh nhất nếu danh sách L thuộc trường hợp 1 hay trường hợp 2, với điều kiện là ta chỉ được dùng vài chục bytes bộ nhớ. - Cho một chuỗi ký tự s bao gồm nhiều từ. Viết một đoạn chương trình C đảo thứ tự các từ.
Ví dụ: với input là “this is a nice blog” thì output là “blog nice a is this“. - Cho hai dãy số đã xếp thứ tự tăng dần A và B, mỗi dãy có n phần tử. Xét tập hợp sau:
S = { A[i] + B[j] | 1 < = i, j <= n }.Chú ý rằng S có thể có đến n2 phần tử. Viết một chương trình in ra n số lớn nhất trong S. Chương trình phải chạy trong thời gian O(n).
9 Comments
Hôm nay em được biết đến các câu hỏi phỏng vấn này, suy nghĩ mãi xin nêu ra cách giải tạm chấp nhận được cho bài 1:
Lưu lại vị trí bắt đầu Linked List, sau đó duyệt list, khi duyệt tới node nào thì đảo chiều liên kết của nó lại: A->B thì B->A
nếu node của chúng ta là null –> Linked List loại 1
nếu node của chúng ta trở về vị trí bắt đầu: Linked List loại 2, lúc này ta lại duyệt Linked List 1 lần nữa theo cách duyệt như vậy sẽ cho trở lại Linked List ban đầu
Mong anh Hưng và các bạn chỉ bảo cách nhanh nhất để thực hiện yêu cầu trên
Chào Hùng,
Cách giải rất hay! Về asymptotic thì không có cách nào nhanh hơn (đều cần O(n) bước). Nhưng, có cách không cần phải “sửa” bất kỳ link nào trong link list cả.
Hi thầy Hưng (do em không biết dùng từ nào phù hợp hơn ^^),
Bài 1.Ta có thể thấy, nếu rơi vào trường hợp 1 và list đủ dài thì dù ta nhanh tới mấy thì thời gian cũng không thể chấp nhận được (và do đó không biết thuộc TH1 hay TH2), do đó em định cận là thời gian hợp lý phụ thuộc vào tốc độ tính toán, nếu quá thời gian mà không tìm ra NULL thì dừng và quyết định thuộc trường hợp 2, nếu tìm ra NULL thì hiển nhiên là trường hợp 1.
Bài 2.Bài này em chia làm hai giai đoạn: giai đoạn 1 em đơn thuần đảo toàn bộ xâu, trong ví dụ thì xâu trở thành: « golb ecin a si siht ». Giai đoạn 2 em đọc từng từ vào một biến tạm rồi đảo từng từ đọc được sau đó ghép vào một xâu chung, ví dụ đọc xong từ « golb » em sẽ đảo thành « blog » rồi ghép vào đầu xâu. Làm tiếp tục em sẽ có kết quả.
Bài 3.Bài này ngoài hai mảng A và B lưu mảng được sắp của đầu bài, em dùng thêm một mảng, mảng C chẳng hạn với ý nghĩa: C[i] lưu chỉ số j sao cho A[i] + B[j] là kết quả nếu ta chọn A[i].
Khởi tạo: C[i] = 1 với mọi i (A[1] lớn nhất, sau đó là A[2], …)
Giả sử ta đang xét A[i], ta so sánh tổng A[i] + B[C[i]] với A[i + 1] + B[C[i + 1]] và A[i – 1] + B[C[i – 1]]. Ta có 3 trường hợp xảy ra:
TH1.Tổng A[i] + B[C[i]] lớn nhất, ta in tổng và tăng C[i + 1].
TH2.Tổng A[i + 1] + B[C[i + 1]] lớn nhất, ta in tổng và tăng C[i + 1], đồng thời chuyển xuống xét vị trí i + 1.
TH3.Tổng A[i – 1] + B[C[i – 1]] lớn nhất, ta in tổng và tăng C[i - 1], đồng thời chuyển con trỏ lên vị trí i – 1.
Ta cần lưu ý giá trị cận như i – 1 vượt mảng, còn giá trị mảng C thì không cần.
Độ phức tạp: O( 2n ).
bạn donnghi thử dùm mình cái test này nhá
A: 10 9 8 7 -100
B: 100 10 10 10 10
Cảm ơn bạn đã tìm ra lỗi của giải thuật, trong TH3 ta chưa in kết quả và bổ sung một vòng lặp kiểm tra điều kiện leo lên trong khi vẫn phát hiện ra giá trị lớn nhất là i – 1.
Độ phức tạp O( 2n ).
Mình có cuốn Cracking The Coding Interview 4ed, bản đẹp. Bạn nào thích thì gửi email vào clairsang@gmail.com mình sẽ reply đính kèm.
Hi thầy Hưng.
Hôm nay em đọc bài này, thấy câu 1 chưa ai giải nên em comment luôn. Cách giải ko phải do em nghĩ ra, nên ko biết có… vô duyên quá ko
Trong cuốn Elements of Programming có 1 chương về Transformations với Orbits. Trong đó có thuật toán (tổng quát hơn tí xíu) để xét coi chu kỳ của 1 hàm kết thúc hay lẩn quẩn. Thuật toán sẽ dừng nếu chu kỳ hữu hạn.
Nôm na là như vầy: Cho 2 biến lần lần theo giá trị trong danh sách. Biến A mỗi lần đi 2 bước, biến B mỗi lần đi 1 bước. Nếu danh sách ko có vòng thì biến A luôn đi nhanh hơn và cuối cùng sẽ đụng NULL trước. Nếu danh sách có vòng, sẽ đến lúc cả 2 biến A và B cùng vào vòng. Vì A đi nhanh hơn 1 bước nên sau mỗi bước lặp, khoảng cách giữa 2 biến sẽ giảm 1, tức là chắc chắn có lúc A=B.
@Phuc Nguyen: hi, cách giải bạn nói gọn thật, complexity
(A=B, ý bạn chắc so sánh addresses của hai biến?). Nhưng sao không thấy cần dùng đến “vài chục bytes” bộ nhớ như anh Hưng nói nhỉ.
Trước đó em mới nghĩ được cách với complexity
, n là độ dài thật sự của list. Ngoài ra nếu 
thì cần đến những 
Bytes bộ nhớ 
(giải sử address 4 bytes)
lưu addresses của các elements có index 
trong quá trình duyệt list. Nếu gặp NULL thì là list loại 1. Với mỗi element khác NULL của list, check xem address của element này có trong list 
chưa. Nếu có rồi thì là list loại 2.
Cách của em như này: list
Lời giải Phuc Nguyen ghi là chính xác rồi!
@Pjthon, tôi viết “vài chục bytes” thật ra ý là tổng bộ nhớ ta cần không phụ thuộc vào n.