Về một vài câu hỏi mà mình gặp khi interview C++

1. Hãy implement queue với size bất kỳ

Interviewer muốn tìm một cách nào đó để implement queue thỏa 2 điều kiện: có thể handle bất kỳ size nào và tối ưu.

a. Linked List

Đúng như đề bài trên, mình sẽ phải tìm cách implement một queue sao cho tối ưu nhất có thể, giờ ta xem queue sẽ gồm những gì nhé:

• Một hàm enqueue dùng để thêm một phần tử bất kỳ vào cuối queue.
• Một hàm dequeue dùng để lấy phần tử đầu tiên ra khỏi queue (dựa theo nguyên tắc FIFO).

Một cách mà các bạn thường thấy trong khi học DSA (và cũng là cách mà interviewee mong muốn làm) đó chính là dùng Linked List với head và tail, việc dùng tail sẽ tránh đi việc di chuyển từ đầu Linked List đến cuối Linked List để thực hiện hàm enqueue, vậy là “theo lý thuyết” từ $O(n)$ ta đã giảm còn $O(1)$ độ phức tạp. Còn đối với hàm dequeue ta chỉ cần thay đổi head là được thê nên “theo lý thuyết” nó cũng là $O(1)$, phía dưới là code của Linked List cho queue.

1
struct Node {
2
  Node *next = nullptr;
3
  int data = 0;
4
};
5

6
struct QueueLinkedList {
7
  Node *head = nullptr;
8
  Node *tail = nullptr;
9
  int size = 0;
10

11
  ~QueueLinkedList() {
12
    while (head != nullptr) {
13
      Node *tmp = head;
14
      head = head->next;
15
      delete tmp;
16
    }
17
    tail = nullptr; // head is already nullptr
18
  }
19

20
  int dequeue() {
21
    assert(!is_empty());
22
    Node *temp = head;
23
    int data = temp->data;
24
    head = head->next;
25
    if (head == nullptr) {
26
      tail = nullptr;
27
    }
28
    delete temp;
29
    return data;
30
  }
31

32
  void enqueue(int value) {
33
    Node *new_node = new Node;
34
    new_node->data = value;
35
    if (is_empty()) {
36
      head = new_node;
37
      tail = head;
38
    size = 1;
39
      return;
40
    }
41
    tail->next = new_node;
42
    tail = new_node;
43
  size += 1;
44
  }
45

46
  bool is_empty() { return head == nullptr; }
47

48
  int front() {
49
    assert(!is_empty());
50
    return head->data;
51
  }
52
};

b. Array

Bây giờ ta sẽ qua một cách implement khác là sử dụng Circular Buffer ¹ hay còn gọi là Ring Buffer ² (một cách implement “tối ưu” hơn rất nhiều nhưng về mặt độ phức tạp thì không).

Ok, một circular buffer thật là một array nhưng thay vì chỉ thêm các phần tử vào bên phải array và xóa đi phần tử bên trái cùng (gọi là head hoặc front) của array thì ta vẫn làm tương tự, thế nhưng nếu phần tử bên phải cùng (gọi là rear hoặc tail) không thể thêm được nữa, ta sẽ wrap-around (xoay ngược lại) và thêm vào đầu array (như một hình trong do đó có tên circular).

Giờ qua phần implement thôi nào (các bạn có thể về nhà xem kĩ hơn 👍) (code dưới mình nhờ AI generate ra cho nhanh, xin lỗi vì sự bất tiện này 💀).

1
struct QueueArray {
2
  int *arr = nullptr;
3
  int head = 0;
4
  int tail = 0;
5
  int size = 0;
6
  int capacity = 0;
7

8
  ~QueueArray() { std::free(arr); }
9

10
  int dequeue() {
11
    assert(arr != nullptr && size != 0);
12
    int result = arr[head];
13
    head = (head + 1) % capacity;
14
    size -= 1;
15
    return result;
16
  }
17

18
  void enqueue(int value) {
19
    if (arr == nullptr) {
20
      assert(size == 0 && head == 0 && tail == 0);
21
      capacity = 10;
22
      arr = static_cast<int *>(std::malloc(capacity * sizeof(int)));
23
      arr[tail] = value;
24
      tail = (tail + 1) % capacity;
25
      size = 1;
26
      return;
27
    }
28

29
    if (size == capacity) {
30
      int old_capacity = capacity;
31
      capacity *= 2;
32
      int *new_arr = static_cast<int *>(std::malloc(capacity * sizeof(int)));
33

34
      for (int i = 0; i < size; ++i) {
35
        new_arr[i] = arr[(head + i) % old_capacity];
36
      }
37

38
      std::free(arr);
39
      arr = new_arr;
40
      head = 0;
41
      tail = size;
42
    }
43

44
    arr[tail] = value;
45
    tail = (tail + 1) % capacity;
46
    size += 1;
47
  }
48

49
  int front() {
50
    assert(size > 0);
51
    return arr[head];
52
  }
53
};

Có thể thấy (tính nhẩm một tí) cả 2 operation là enqueue và dequeue của Circular Buffer đều là $O(1)$, lưu ý là trường hợp size và capacity bằng nhau (phải tạo mới) thì lúc này enqueue là $O(n)$ do phải copy $n = \text{size}$ phần tử từ array cũ sang array mới. Thế nhưng $O(n)$ rất ít xảy ra nên có thể giả sử rằng time complexity trung bình của operation enqueue Circular Buffer là $O(1)$. Vậy cả hai Linked List và Circular Buffer đều có time-complexity là như nhau.

Giờ chạy thử benchmark trên 1 tỷ phần tử để thử xem cái nào tốt hơn, phía dưới là Benchmark Code:

1
constexpr int BENCHMARK_LOOP = 1'000'000'000;
2
volatile long long array_dequeue_sum = 0; // Use volatile to prevent optimization
3
volatile long long ll_dequeue_sum = 0;
4

5
#define BENCHMARK(func, name)                                                  \
6
  [&]() {                                                                      \
7
    auto t1 = high_resolution_clock::now();                                    \
8
    func();                                                                    \
9
    auto t2 = high_resolution_clock::now();                                    \
10
    duration<double, std::milli> ms_double = t2 - t1;                          \
11
    std::cout << name << " run for " << ms_double.count() << "ms\n";           \
12
  }();
13

14
int main(int argc, const char *argv[]) {
15
  using std::chrono::duration;
16
  using std::chrono::high_resolution_clock;
17

18
  QueueArray q_arr;
19
  QueueLinkedList q_ll;
20

21
  BENCHMARK(
22
      [&q_arr]() {
23
        for (int i = 0; i < BENCHMARK_LOOP; i++) {
24
          q_arr.enqueue(i);
25
        }
26
      },
27
      "QueueArray::Enqueue")
28

29
  BENCHMARK(
30
      [&q_arr]() {
31
        for (int i = 0; i < BENCHMARK_LOOP; i++) {
32
          array_dequeue_sum += q_arr.dequeue();
33
        }
34
      },
35
      "QueueArray::Dequeue")
36

37
  BENCHMARK(
38
      [&q_ll]() {
39
        for (int i = 0; i < BENCHMARK_LOOP; i++) {
40
          q_ll.enqueue(i);
41
        }
42
      },
43
      "QueueLinkedList::Enqueue")
44

45
  BENCHMARK(
46
      [&q_ll]() {
47
        for (int i = 0; i < BENCHMARK_LOOP; i++) {
48
          ll_dequeue_sum += q_ll.dequeue();
49
        }
50
      },
51
      "QueueLinkedList::Dequeue")
52

53
  return 0;
54
}

Phía dưới là kết quả benchmark (chạy trên Macbook M2 của mình và không sử dụng bất kỳ compiler optimization nào), có thể thấy thời gian enqueue của một tỷ phần tử của LinkedList gấp gần 6 lần 💀 so với Circular Buffer, ngoài ra không chỉ thời gian enqueue và thời gian dequeue cũng gấp hơn 3 lần. Performance càng cách xa khi càng nhiều phần tử, điều này là do có một chỗ nào đó bị bottleneck.

# 10 triệu phần tử
QueueArray::Enqueue run for 134.672ms
QueueArray::Dequeue run for 92.7956ms
QueueLinkedList::Enqueue run for 190.325ms
QueueLinkedList::Dequeue run for 215.375ms
# 100 triệu phần tử
QueueArray::Enqueue run for 1457.19ms
QueueArray::Dequeue run for 957.006ms
QueueLinkedList::Enqueue run for 2146.44ms
QueueLinkedList::Dequeue run for 2130.74ms
# 1 tỷ phần tử
QueueArray::Enqueue run for 14533.7ms
QueueArray::Dequeue run for 9838.72ms
QueueLinkedList::Enqueue run for 78361.1ms
QueueLinkedList::Dequeue run for 30657ms

Điều này là do đâu ? Time complexity đều bằng nhau mà ! Đây chính là lý do mà mình khá “không thích” việc mọi người tập trung “tối ưu” thuật toán mà bỏ qua các mặt khác của ngôn ngữ đang code hoặc hardware, một câu mà mình luôn nói với mình (đồng thời bao biện cho việc mình ngu thuật toán) chính là mình làm việc với máy tính, mình không làm việc trên giấy.

Dựa vào ảnh trên, có thể thấy phần code nặng nhất nằm ở QueueLinkedList::enqueue khi mà nó chiếm đến $56.2\%$ thời gian code chạy. Vậy chính là, việc new hay allocate bộ nhớ liên tục làm bottleneck code, làm cho code chạy chậm đi rất nhiều, trong khi đó, cùng với một time complexity QueueArray::enqueue chỉ chiếm $7.4\%$ thời gian code chạy. Tương tự như enqueue, dequeue của QueueLinkedList cực kì tốn kém khi chiếm $22.5\%$ (tất cả là do việc new và delete liên tục đấy). Vì vậy (đối với riêng ngôn ngữ C/C++ thôi nhá), việc xem xét đến những khía cạnh của ngôn ngữ, bộ nhớ cực kì quan trọng nếu muốn viết code thật sự tối ưu.

Các bạn có hỏi tại sao lại chọn array chưa, đó chính là tránh đi dynamic allocation ³ (như các bạn thấy ở trên đây là một hàm cực kỳ expensive và kéo performance của Linked List xuống tận đáy). Để tránh đi dynamic allocation ta sẽ thử chọn array và đi qua nhiều bước để tối ưu nó.

1
struct Queue {
2
  float* arr;
3
  size_t size;
4

5
  ~Queue() {
6
    delete[] arr;
7
  }
8
}

Thế nhưng một điều ta thấy là array có một size cố định (gọi là $N$) vì vậy nếu ta muốn thêm phần tử mới (ở operation enqueue) thì khi đó ta phải tạo một array mới có size là $N+1$ và copy toàn bộ phần tử từ array cũ sang array mới và nó chả giúp ích gì khi mà việc tạo array mới chính là dynamic allocation.

1
void Queue::enqueue(float value) {
2
  // tạo array mới với size N + 1
3
  float* tmp = new float[size + 1]{};
4
  // copy array cũ sang
5
  std::memcpy(arr, tmp, size);
6
  tmp[size] = value;
7
  // xóa array cũ và gán giá trị mới
8
  delete[] arr;
9
  arr = tmp;
10
  size += 1;
11

12
  // siêu tốn kém khi mỗi lần enqueue lại là một lần dynamic allocation
13
  // không khác gì linked list và còn phức tạp hơn
14
}

Vậy để tránh nhiều lần dynamic allocation, ta có thêm một biến là capacity, thay vì allocate đúng $N$ phần tử, ta allocate capaciy phần tử, vì vậy sẽ tránh được nhiều lần allocate.

1
void QueueCapacity::enqueue(float value) {
2
  if (size + 1 > capacity) {
3
    // tạo mới array nếu vượt quá capacity
4
    capacity *= 2; // capacity mới gấp đôi cũ
5
    float* tmp = new float[capacity]{};
6
    // tương tự phía trên
7
    // std::memcpy ...
8
    return;
9
  }
10
  size += 1
11
  arr[size] = value;
12
}

Thế nhưng nếu implement bằng array thì một cách để dequeue (hay xóa đi phần tử đầu) đơn giản là bỏ phần tử đó đi, ta vẫn giữ được time complexity là $O(1)$. Thế nhưng sẽ tạo ra một “khoảng trống” phía trước của array (có thể thấy ở hình 2). Do đó ta đến với cấu trúc tối ưu nhất là Circular Buffer đã được nói ở phía trên.

2. For loop chạy bao nhiêu lần ?

Cho bài toán sau ⁴, for loop được chạy bao nhiêu lần ?

1
unsigned char half_limit = 150;
2

3
for (unsigned char i = 0; i < 2 * half_limit; ++i)
4
{
5
    // do something;
6
}

Có thể thấy unsigned char là một kiểu dữ liệu có độ dài là 1 byte, do đó giá trị tối đa mà i có thể có là $255$. Trong khi đó 2 * half_limit là $300$. Hmm, bắt đầu thấy khó. Theo logic thông thường, số $300$ cần đến 9 bit để biểu diễn thế nhưng unsigned char chỉ có 1 byte = 8 bit. Vì vậy việc xảy ra đó chính là wrap-around ⁵ vậy giá trị 2 * half_limit nên là 300 % 256 = 44. Do đó for-loop sẽ chạy $44$ lần, đúng không ? Không.

Việc này là do mình đang có 2 assumption:

• C/C++ sẽ đảm nhận công việc wrap-around khi mà số bị overflow.
• C/C++ thực sự nhân 2 với half_limit với nhau ở kiểu dữ liệu là unsigned char.

Thật ra trường hợp này sẽ gây ra cái gọi là undefined behavior, nó sẽ khác nhau tùy thuộc vào compiler, môi trường, … có thể compiler A sẽ wrap-around, compiler B không làm như thế. Còn assumption thứ 2, trong C/C++ sẽ có một thuật ngữ gọi là type-promoting, sẽ có những type “cao” hơn những type khác (dựa vào số bit cần biểu diễn type đó), ở đây 2 là int (4 bytes = 32 bits) và half_limit là unsigned char (1 bytes = 8 bits) vì vậy C++ sẽ đưa half_limit lên type cao hơn (là int) khi đó, vòng for loop có thể viết lại như sau:

1
unsigned char i = 0;
2
while ((int)i < 2 * (int)half_limit) {
3
  // do something
4
  ++i;
5
}

Do đó khi mà i có giá trị là 255 và ++i (vượt quá 255) thì sẽ dẫn đến wrap-around vậy i = 255 % 256 = 0, lúc này vòng lặp sẽ lặp vô hạn ⁶.

3. Modern C++

Mình khá buồn vì interviewer không hỏi về cái này nên mình sẽ dành chút thời gian để giới thiệu về nó 😚

a. Smart pointer

Ở C/C++, chúng ta có 2 loại bộ nhớ là Heap và Stack, khi tạo một biến như dưới đây:

1
int a = 3;

Thì a sẽ được C tạo trên stack, vùng nhớ này đúng như cái tên nó như 1 stack, có thứ tự và C sẽ đảm nhận việc xoá các biến trên stack nếu không cần tới nữa hoặc ra khỏi scope của nó, à một concept nữa là scope, scope trong C/C++ được biểu thị bằng dấu {}, ví dụ như dưới đây:

1
// các biến ở ngoài đây có scope global
2

3
void func() {
4
    // các biến ở đây có scope là hàm func
5
}
6

7
int main(void) {
8
    // các biến ở đây có scope là hàm main
9
    // ta có thể làm như này luôn
10
    {
11
        // các biến ở đây chỉ có scope trong ngoặc này
12
    }
13
    // sau khi hết scope (ra khỏi dấu })
14
    // các biến sẽ được xoá đi
15
}
16
// tương tự hết scope hàm main

Còn khi tạo một biến trên heap, bằng new (C++) hay malloc (C), thì biến đó sẽ được nằm ngẫu nhiên trên bộ nhớ, không có thứ tự như Stack, ngoài ra C/C++ cũng không đảm nhận việc xoá các biến này đi nếu nó ra khỏi scope. Và điều đặc biệt hơn, pointer là một biến nằm trên stack nhưng biến mà pointer đang trỏ đến nằm trên heap, do đó sẽ xảy ra trường hợp pointer bị out of scope, dẫn đến pointer bị xoá nhưng biến mà pointer trỏ đến trên heap vẫn chưa bị xoá (không ổn đâu), vì vậy ta phải luôn để ý khi nào cần xoá biến mà pointer đang trỏ đến, và để xoá sẽ dùng delete (C++) hoặc free (C).

Thấy vấn đề đó, smart pointer ra đời ở C++ (bản 11 trở lên), bao gồm 2 loại smart pointer là unique_ptr (unique pointer) và shared_ptr (shared pointer). Nếu để ý cái tên của nó, mỗi smart pointer sẽ có owner (người sẽ đảm nhận việc xoá đi biến mà pointer đang trỏ đến hay còn gọi là resource, gọi là người cũng không đúng, thật ra là compiler xoá ấy). Ở unique_ptr, chỉ có duy nhất một owner đảm nhận việc này, còn shared_ptr thì sẽ có nhiều người cùng nhận việc này. Khi các owner bị huỷ (hoặc out of scope) thì nó cũng tự xoá đi resource mà nó đang trỏ đến.

Ở unique_ptr, để đảm bảo tính duy nhất, phép gán bằng = và copy constructor đều không thể dùng được, ta phải dùng đến cái gọi là move constructor (cái này sẽ là một concept mới của C++), bạn có thể hiểu là nó move cái ownership từ biến này sang biến khác. Còn shared_ptr thì gán bằng = hay copy thoải mái và đặc biệt, khi các shared_ptr bị xoá (hoặc out of scope), C++ sẽ xem đến khi nào thằng shared_ptr cuối cùng bị xoá thì nó mới bắt đầu xoá luôn resource.

1
// tạo pointer a trỏ đến biến int = 3
2
std::unique_ptr<int> a = make_unique<int>(3);
3
std::shared_ptr<int> b = make_shared<int>(4);
4
// còn lại tương tự pointer
5
// ta có thể deferencing
6
std::cout << *a; // 3
7
std::cout << *b; // 4

b. Move Semantics

Ở phía trên mình đã nhắc đến std::move vậy bây giờ ta cùng tìm hiểu xem move semantics của C++ là gì nhé ?

🚧 Hope mình có thêm thời gian để viết cái nì

c. Template

🚧 Hope mình có thêm thời gian để viết cái nì