Các câu hỏi lập trình (C++)

[Ms. Moderator]

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

3. Viết một đoạn chương trình C++ để xác định xem máy chạy chương trình là big-endian hay little-endian.

Source: Blog KHMT

[weevil]

1. Câu hỏi không đề cập tới việc mình có được quyền sửa dữ liệu INPUT trong lúc chạy chương trình hay không nhưng tui nghĩ là OK nếu như INPUT lúc hoàn thành vẫn giống ban đầu.
Bài này mình traverse linearly 2 lần.
Lần 1: Traverse qua node nào thì sửa chiều link của node ấy theo hướng ngược lại. A -> B thì thành A <- B. Như đảm bảo mình không bao giờ bị loop vô thời hạn. Nêu node cuối cùng trước khi gặp NULL giống node ban đầu thi đây là trường hợp 2, còn nếu không là trường hợp 1. (Chú ý: trong trường hợp 2

Lần 2: làm y hệt Lần 1 bắt đầu từ node cuối cùng của Lần 1 để sửa link lại cho đúng.

Worst case chắc là 4*n...

2. Cái này tui nghĩ kỹ thuật cài đặt là chính. Mình cần lưu 2 cặp con trỏ lần mò từ từ của 2 dãy. Worstcase cỡ 2n.

3. Không biết cài này xài được hong:

#include <stdio.h>
int main() {
  return fprintf(stderr, "This machine is %s endian.\n",
                         *((char*)(new int(1)))?"little":"big");
}

[dexter8310]

Originally Posted by weevil

1. Câu hỏi không đề cập tới việc mình có được quyền sửa dữ liệu INPUT trong lúc chạy chương trình hay không nhưng tui nghĩ là OK nếu như INPUT lúc hoàn thành vẫn giống ban đầu.
Bài này mình traverse linearly 2 lần.
Lần 1: Traverse qua node nào thì sửa chiều link của node ấy theo hướng ngược lại. A -> B thì thành A <- B. Như đảm bảo mình không bao giờ bị loop vô thời hạn. Nêu node cuối cùng trước khi gặp NULL giống node ban đầu thi đây là trường hợp 2, còn nếu không là trường hợp 1. (Chú ý: trong trường hợp 2

Lần 2: làm y hệt Lần 1 bắt đầu từ node cuối cùng của Lần 1 để sửa link lại cho đúng.

Worst case chắc là 4*n...
[/code]

Trong trường hợp bị loop thì traverse lần 1 sẽ cho node ban đầu và node cuối đều là A . Khi mình traverse lần 2 sẽ cho 1 vòng tròn, ko tái tạo được điểm loop (e.g. C) .
Có lẽ phải detect điểm loop .

[weevil]

Cái này là tại do cái post đầu tự nhiên bị xóa mất ngay chỗ "(Chú ý: trong trường hợp 2..."

Bây giờ điền lại nhé:
(Chú ý: trong trường hợp 2, sau cái lần 1 thì cái từ A tới C vẫn có chiều giống ban đầu do bị đổi 2 lần:
Traverse như sau:
A –> B –> C –> D –> E –> F –> C -> B -> A -> NULL
Thành ra sau lần 1 cái link list là:
A -> B -> C <- D <- E <- F <- C

Như vậy lần 2 bắt đầu từ A vẫn được như thường:
A -> B -> C -> F -> E -> D -> B -> A -> NULL
Và chiều sẽ trở lại y chang ban đầu.

Cho nên tui mới nói là 4*n nếu như trong trường hợp cái loop chỉ xảy ra ở node cuối cùng...

[Khoa Tran]

Câu 1 không đòi hỏi giữ nguyên input nên đáp án của bác Yên là good enough.

3 câu này không biết có hay hỏi trong quant interviews hay không nhưng khi xin việc làm software engineer cho các cty phần mềm như Microsoft thì rất hay hỏi.