33 câu hỏi phỏng vấn của Google

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 sẽ nêu chọn lọc một số câu hỏi . 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.
1. 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ớ.
2. 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“.
3. 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
4. Chỉ với các phép tính cộng, trừ, nhân, chia, các hàm lượng giác, phép lũy thừa, và phép
lấy căn, cùng với ba số 2, làm thế nào để viết một biểu thức định trị ra 2005? (Gợi ý:
2005 không có gì đặc biệt, số nguyên dương nào cũng được.) [Câu này tôi biết qua chị
Hà Dương, lúc giải ra rất thích! Đơn giản và độc đáo]
5. Bụt, diêm vương, và Tèo đứng trước mặt bạn. Bụt và diêm vương cái gì cũng biết. Tèo
thì cái biết cái không. Bụt luôn nói thật, diêm vương luôn nói dối. Với 3 câu hỏi
có/không, mỗi câu chỉ hỏi một trong ba đối tượng, xác định ai là ai.

đến (tốc độ đều). Sáng sáng Tèo ra bến xe buýt và đón xe nào đến trước thì đi về hướng
ấy. Sau một thời gian dài thì Tèo đi thăm Tấm gấp ba lần đi thăm Cám.
Hỏi: sao lại thế được?
15. Có hai xe tải đứng đối diện nhau, cách nhau 100km. Xe 1 có tốc độ 50km/h, xe 2 có
tốc độ 30km/h, một con ruồi đậu trên mũi xe 1 bay qua bay lại giữa hai mũi xe với tốc độ
5000km/h. Cả hai xe và con ruồi đều xuất phát cùng một lúc.
Hỏi: đến khi con ruồi bị đè bẹp gí giữa hai xe (đụng nhau) thì con ruồi bay được bao xa?
16. Cho một linked list (danh sách liên kết) và pointer đến đầu linked list. Ta không biết
trước tổng số phần tử trong list là bao nhiêu. Viết một function trả về pointer đến một
phần tử ngẫu nhiên trong list (uniform distribution), mà chỉ được duyệt qua linked list 1
lần. (Nghĩa là không được đếm tổng số phần tử n, chọn ngẫu nhiên từ 1 đến n, rồi duyệt
lần 2 để trả về con trỏ ngẫu nhiên.)
17. Cho một array *A* các ký tự trong một bộ ký tự nào đó, và một tập *S* của vài ký
tự. Viết một function chạy trong thời gian tuyến tính,trả về sub-array nhỏ nhất của *A*
chứa tất cả các ký tự trong *S*.
18. Cho một ma trận m hàng n cột. Các con số trên các hàng đều tăng dần từ trái sang
phải, và trên các cột đều tăng dần từ trên xuống dưới. Viết một thủ tục tìm một số xem nó
có trong ma trận không? Thời gian chạy là bao nhiêu? *Lưu ý*: đây là phiên bản 2-D của
binary search.)
19. Ba người thuê một phòng khách sạn. Họ đưa cho anh bảo vệ 30 đô. Anh bảo vệ đưa
cho người quản lý, nhưng người quản lý trả lại 5 đô vì giá phòng chỉ có 25. Cầm 5 đô,
không biết làm sao chia cho 3 người, anh bảo vệ cầm lấy 2 đô xem như tiền boa, còn lại
đưa mỗi người 1 đô.
Mồi người bỏ ra 10 đô, lấy lại 1 đô, vị chi là mỗi người 9 đô – tổng cộng 27 đô. Anh bảo
vệ lấy 2 đô nữa là 29 đô. Vậy còn 1 đô đi đâu?
20. Có n người, trong đó một số luôn nói thật, một số lúc thật lúc dối không biết đâu mà
lường. Ta phải phỏng vấn đám người này và chỉ ra tất cả những người luôn nói thật.
Những người này biết thông tin thật/dối của tất cả những người còn lại. Các câu hỏi chỉ
có thể ở dạng: “hỏi anh A xem anh B thuộc loại nào”.
(i) Nếu biết trước hơn nửa số người thuộc dạng luôn nói thật, tìm chiến thuật phỏng vấn

28. Viết một đoạn chương trình C để biết stack của một máy grow down hay grow up?
29. Cho chuỗi S_1 = \{ a, b, c, d, \dots, x, y, z, aa, ab, ac, \dots \}. Biết rằng chuỗi này có
ánh xạ một-một đến chuỗi S_2 = \{1, 2, 3, 4, \dots \}. Viết một chương trình để chuyển
một phần tử của S_1 thành một phần tử tương ứng của S_2. Viết chương trình chuyển
theo chiều ngược lại.
30. Cho một hình vuông đơn vị, mô tả các điểm trong hình vuông này mà nằm gần tâm
hơn cạnh ngoài.
31. Có bao nhiêu số 0 ở đằng cuối của biểu diễn thập phân của n!?
32. Khi ta soi gương, giơ tay trái lên thì hình nhân trong gương giơ tay phải của hắn. Tuy
nhiên, khi ta cúi đầu thì hình nhân trong gương cũng cúi đầu. Tại sao gương “lật”
trái/phải, nhưng không “lật” trên/dưới?
33. Có 9 túi đựng tiền, mỗi túi chứa ít nhất 100 đồng tiền, trong đó có một túi chứa toàn
tiền giả. Các đồng tiền thật đều nặng 100 grams. Các đồng tiền giả đều nặng 90 grams.
Cho một cái cân đĩa (1 đĩa và đồng hồ chỉ cân nặng), cân 1 lần để xác định túi nào chứa
tiền giả?

Source: internet