Câu hỏi phỏng vấn (3)

Kỳ này tôi xin giới thiệu các câu hỏi về mặt thuật toán và lập trình (C/C++), một số câu hỏi liên quan đến các vấn đề chung của tin học.

1. 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“.

2. 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 n^2 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).

3. Lệnh printf(“%d”); sẽ in ra cái gì, tại sao?

4. Trong các định nghĩa sau đây, cái gì là const?

const char* variable;
const* char variable;
char* const variable;

5. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like. Try both O(n) and O(n^2). [I ended up giving about 4 or 5 different solutions for this, each supposedly better than the others].

6. Give a fast way to multiply a number by 7.

7. How do we test most simply if an unsigned integer is a power of two? (Thử dùng một #DEFINE).

8. 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.

9. 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.)

9*. An cần gửi một nhẫn kim cương cho Bình. An và Bình mỗi đứa có vài cái khóa và chìa tương ứng (mỗi khóa một chìa). An có một cái hộp thừa lớn để bỏ nhẫn vào. Hộp có móc tròn khá lớn để tròng khóa vào. Làm thế nào để An gửi nhẫn cho Bình một cách bảo đảm?

10. An và Bình thay phiên nhau chọn các số nguyên từ 1 đến 9. Số đã chọn không được chọn lại. Ai chọn được 3 số có tổng bằng 15 trước là thắng. Ai sẽ thắng?

One response to “Câu hỏi phỏng vấn (3)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s