Mấy hôm gần đây. tình cờ mình đọc được cuốn sách: Cracking the Coding Interview: 150 Programming Questions and Solutions. Đây là một cuốn sách khá hay; sách viết về những câu hỏi thường gặp trong các cuộc phỏng vấn, qui trình phỏng vấn của Yahoo, Google, Amazon, Facebook. Trong cuốn sách có rất nhiều câu hỏi về lập trình hay, mình chỉ chia sẽ một số câu mình cảm thấy đơn giản và thú vị. Bạn nào muốn tìm hiểu thêm hãy tự tìm ebook nhé.

Linked List (Chuỗi liên kết)

1. Hiện thực thuật giải tìm phần tử thứ n tính từ cuối lên của 1 linked list. (Đây là linked list chứ không phải double linked list nhé).

Chuỗi: a->b->c->d->e->f. n = 3, cho ra phần tử d.

2. Hiện thực thuật giải xóa một phần từ khỏi linked list, bạn chỉ được access vào phần tử đó?

Chuỗi: a->b->c->d->e->f. Đưa vào phần tử c, chuỗi còn lại a->b->d->e->f.

Dịch bit

3. Hãy cho biết đoạn code sau làm gì: ((n & (n-1)) == 0).

Đố mẹo

4. Sử dụng + – * / ( ), hãy làm biểu thức sau đúng: 3 1 3 6 = 8

5. Một bàn cờ vua 8 x 8, bị cắt mất 1 ô góc trên bên trái, 1 ô góc dưới bên phải. Mỗi quân domino có thể che được 2 ô trên bàn cờ. Có thể dùng 31 quân domino để che hết 62 ô còn lại của bàn cờ không? Vì sao/Vì sao không?

Testing

6. Hãy tìm lỗi trong đoạn code sau

unsigned int i;
for (i = 100; i <= 0; --i) printf(“%d\n”, i);

Hại não (Code)

7. Viết 1 hàm swap 2 số, không dùng biến tạm.

8. Tìm số lớn hơn trong 2 số đưa vào. Không được dùng if/else hoặc các phép so sánh = < >.

Các bạn có giải được câu nào không? Nếu không được cũng đừng buồn, hãy xem đáp án ở dưới nhé

1. Thuật toán khá đơn giản, chắc bạn nào cũng nghĩ ra. Ta sử dụng 2 con trỏ p1 và p2, con trỏ p2 sẽ nằm sau con trỏ p1 (n-1) phần tử. Cho 2 con trỏ này chạy cùng lúc, khi con trỏ p2 chạy tới cuối list, con trỏ p1 sẽ trỏ tới phần tử thứ n từ cuối lên

LinkedListNode nthToLast(LinkedListNode head, int n) {
   if (head == null || n < 1) {
    return null;
   }

   LinkedListNode p1 = head;
   LinkedListNode p2 = head;
   for (int j = 0; j < n - 1; ++j) { // p2 chạy hơn p1 n-1 phần tử
     if (p2 == null) return null; // Không tìm ra vì mảng ít hơn n phần tử
     p2 = p2.next;
   }

   //Cho 2 con trỏ cùng chạy tới cuối list
   while (p2.next != null) {
     p1 = p1.next;
     p2 = p2.next;
   }
   return p1;
}

2. Một câu hỏi khá đơn giản nữa. Chỉ việc lấy data của node ngay sau note hiện tại, sau đỏ trỏ tới note tiếp sau là xong:

1. Lấy data của note sau a->b->c->d->e sẽ thành a->b->d->d->e
2. Trỏ tới node tiếp sau: a->b->d->e

Điểm lắt léo của câu đố này là: Nếu như node cần xóa là node cuối cùng của list, ta không thể xóa được, chỉ có thể set data của nó là null. Bạn cần phải chỉ ra được điều này thì mới xem như trả lời đúng.

public static boolean deleteNode(LinkedListNode n) {
    if (n == null || n.next == null) {
     return false; // Failure
    }
    LinkedListNode next = n.next;
    n.data = next.data;
    n.next = next.next;
    return true;
}

3. Một bài toán đố khá thú vị, bạn nào từng làm việc với bit chỉ cần nhìn là đoán ra ngay. Toán tử & tức là áp dụng toán tử AND từng bit của 2 số. (n & (n-1)) == 0 nghĩ là bit biểu diễn 2 số này không có số 1 nào chung. Có thể xem 2 trường hợp sau:

11001100   và    00110011
100000000 (n) và 011111111 (n-1)

Dễ thấy ở trường hợp 2, 2 số n và n-1 không có số 1 chung nào. Vậy n sẽ là 1 số mà các bit của nó là: 10, 100, 1000, 10000. Các bạn gần đoán ra rồi đấy, nếu đổi từ nhị phân sang thập phân, n sẽ lẽ: 2, 4, 8, 16 … Kết luận: Dòng code có tác dụng xác định giá trị n là một số lũy thừa của 2.

4. Bài này bạn có thể giải bằng cách mò và đoán, tuy nhiên người phỏng vấn muốn thử cách suy luận logic của bạn. Đầu tiên, hãy thử phân tích xem số 8 có thể được tạo thành từ các số nào:

1. 8 = 1 * 8 = 1 + 7 = 2 * 4 = 4 + 4 = 4 * 2 …
2. Tách tiếp ra, ta sẽ thấy: 4 = 3 + 1 (2 số đầu), 2 = 6 / 3 (2 số cuối).
3. Ta đảo vị trí 3 và 6 để ra đáp án cuối cùng: (3 + 1) / 3 * 6 = 8.
4. Còn 1 đáp án trên trời rơi xuống nữa là: 3 – 1^3 + 6 = 8 nhé.

5. Một bài toán suy luận khá hay. Hãy thử đặt 1 quân lên bàn cờ, quân domino chiếm 2 ô liền nhau, 1 đen 1 trắng. Ta có thể suy luận: Mỗi quân demino chiếm 1 ô đen và 1 ô trắng, 31 quân sẽ chiếm 31 ô đen, 31 ô trắng. Do bàn cờ đã bị mất 1 ô góc trên bên trái, 1 ô góc dưới bên phải, 2 ô này cùng màu với nhau (Bạn nhìn hình sẽ thấy). Do đó bàn cờ chỉ còn 32 ô đen, 30 ô trắng, không thể dùng 31 quân domino để xếp đầy bàn cờ.

6. Câu này không khó, chỉ tương đương với 1 bài trắc nghiệm trong trường. Code sẽ không chạy vì i = 100, không thỏa điều kiện i <= 0. Câu này chỉ thử khả năng suy luận và đọc code của bạn thôi.

7. Một bài đố mẹo đơn giản thường được các thầy dùng để số sinh viên

public static void swap(int a, int b) {
    //b = 9, a = 5
    a = b - a; // 9 - 5 = 4
    b = b - a; // 9 - 4 = 5
    a = a + b; // 4 + 5 = 9
    //b = 5, a = 9
}

//Một cách khác optimize và nhanh hơn, sử dụng toán tử XOR
public static void swap_opt(int a, int b) {
   a = a^b;
   b = a^b;
   a = a^b;
}

8. Bài toán này khá khó, ta có thể giả bằng cách “suy luận ngược” như sau:

1. Nếu a < b: return b, ngược lại return a
2. Nếu a – b < 0: return b, ngược lại return a
3. Ta nhẩm:
   b = a – (a – b) = a – 1*(a-b) = a – k*(a-b) với k = 1
   a = a – 0 = a – 0*(a-b) = a – k*(a-b) với k = 0
4. Kết hợp 2 và 3 ta có:
5. Return a – k*(a-b). Nếu a – b < 0: k = 1, ngược lại k = 0
6. Gọi c = a-b. Ta không thể so sánh c với 0, tuy nhiên ta biết rằng c < 0 nếu c là số âm. Số âm có đặc tính gì nhỉ: bit ngoài cùng bên trái của nó sẽ bằng 1. Bit ngoài cùng bên trái của số dương sẽ bằng 0. Ồ, đúng là số k chúng ta đang tìm còn gì.

Lời giải khá ngắn gọn, nhưng logic để có được lời giải này cũng không phải dạng vừa đâu.

int getMax(int a, int b) {
   int c = a - b;
   int k = (c << 31) & 0x1;
   int max = a - k * c;
   return max;
}

Tới đây mình chắc các bạn cũng khá nhức não rồi, mình cũng vậy. Lâu lâu hãy đọc những câu hỏi như thế này để tăng tư duy lập trình nhé. Hẹn gặp lại các bạn ở bài viết sau.