phỏng vấn Embedded C và C++?

Có vài điểm rất nhỏ, các bạn không để ý có thể dẫn đến bất lợi (nếu không muốn nói là rớt) ở vòng hồ sơ hoặc khi đi phỏng vấn.
Mình liệt kê rất cụ thể ra những chuyện mình đã thấy qua nhiều lần (người thật, việc thật), hy vọng cho các bạn thêm kinh nghiệm.
Lưu ý: Những chuyện này rất chủ quan, có thể chỉ đúng trong môi trường của mình và hoàn toàn không đúng trong môi trường khác.

• Gửi email CV đến không có Cover Letter, chỉ đính kèm mỗi file PDF là cái CV.
• CV ghi :tiếng Anh: Trung Bình, C: Trung Bình,...nhưng bên dưới lại ghi ưu điểm_: là người ham học hỏi...
• CV bằng tiếng Việt và lại viết sai chính tả tiếng Việt.
• CV ghi quá nhiều về các hoạt động tình nguyện, hiến máu, blah blah... nhưng phần kĩ thuật lại có 3 dòng thôi.
• Mặc đồ thể dục của trường và đi dép lê đến PV.
• Đến muộn PV (em ấy bảo bị kẹt xe).
• Đưa yêu cầu, em ấy không hiểu đề nhưng ngại không dám hỏi lại, dẫn đến viết hoàn toàn sai.
• Hỏi ngay câu căn bản đầu tiên em ấy đã nói không biết và đổ do trường không dạy (cụ thể câu hỏi như: union là gì ? hoặc sao phải dùng inline ? hoặc sao phải dùng bitfield ...)
• Viết hết code vào main thay vì dùng function.
• Không đặt tên cho biến, dùng i, t, x thay vì count, get_time_ui, set_time_ui...
• Tất cả các biến đều khai báo dưới kiểu int một cách vô tội vạ.
• void main() thay vì int main()
• Dùng printf trong trong code c++ và hầu như không phân biệt được c và c++
• Khẳng định trường không dạy pure virtual function
• Không biết làm sao để 2 file source có thể cùng chạy trong một project
• Do you know stack? Which one will be allocated in stack? (variables below)
  int a=5;
  int b[5];
  void elloh(char *c, char *d)
  {
  char e[5];
  char *g=NULL;
  g = (char*) malloc(10);
  g = "hello hello";
  printf("%d", sizeof(g));
  printf("%d", sizeof(*g));
  }
  void f(char *a, char *b)
  {
  b=a;
  }
  char *p_a, *p_b;
  int main (void)
  {
  p_a = "hello";
  f(p_a,p_b);
  printf("%s", p_a);
  printf("%s", p_b);
  getchar();
  }

12 câu hỏi kinh điển về cấu trúc dữ liệu của mình.

#1  Tìm phần tử ở giữa Linked List sau 1 lần duyệt

Sau 2 lần thì như thế này: duyệt tuần tự trong lần đầu tiên, lưu độ dài vào một biến đếm, và lần thứ hai thì duyệt với độ dài bằng một nửa lần 1. 

Không ít lập trình viên bối rối khi họ chỉ được giới hạn trong 1 lần duyệt duy nhất.

Mẹo để giải quyết câu hỏi này: thay vì dùng 2 lần với 1 con trỏ, hãy dùng 2 con trỏ trong 1 lần duyệt. Con trỏ 1 duyệt tuần tự từng nút, con trỏ 2 duyệt nhảy cóc 2 nút một lần. Như vậy, khi con trỏ 1 dừng lại, con trỏ 2 sẽ duyệt đến phần tử ở giữa linked list.

#2: Làm thế nào đế xác định một danh sách liên kết vòng?

Với 2 con trỏ có bước nhảy khác nhau, ta có thể xác định được một danh sách liên kết có phải là danh sách liên kết vòng hay không.

Khi 2 con trỏ có bước nhảy khác nhau (một nút và hai nút), nếu sau một số lượt duyệt nhất định, chúng trỏ tới cùng một nút thì danh sách đó là danh sách liên kết vòng

Danh sách liên kết vòng đơn (bên trên) và kép (bên dưới)

#3 Xác định giá trị 2 phần tử trùng nhau trong một mảng các số nguyên (từ 1-100)

Câu hỏi này được liệt hạng ez.

Bạn sẽ làm kiểu xôi thịt, so sánh từng cặp một phải không? Được đấy, nhưng không hay. Nếu áp dụng cách này, độ phức tạp của thuật toán bạn đang chọn sẽ là O(n^2), không ổn!

Thay vào đó, ta sẽ tính tổng của cả dãy, rồi trừ đi tổng các số từ 1 đến 100, phần chệnh lệch sẽ là giá trị cần tìm. Với lựa chọn này, độ phức tạp còn O(n). 

#4 Đảo một xâu ký tự trong Java

Đây là một trong nhiều câu hỏi yêu thích của tôi. 

String là một kiểu dữ liệu quan trọng trong lập trình, chắc chắn buổi phỏng vấn của bạn sẽ có kha khá vấn đề liên quan đến String. Và quan trọng hơn, người phỏng vấn bạn sẽ không cho sử dụng các API liên quan đến String, ví dụ hàm reverse() sẽ bị cấm sử dụng... Họ cũng có thể bắt bạn trình bày cách đảo String kiểu đệ quy.

#5 Stack vs Queue?

Stack hoạt động theo nguyên lý LIFO - Last In First Out

Queue thì là FIFO - First In First Out 

Tuy đây là kiến thức căn bản nhưng tôi đã gặp không ít thanh niên ngắc ngứ ở câu hỏi này.

Stack vs Queue

#6 Xác định nhiều phần tử trùng giá trị trong mảng số nguyên?

Câu hỏi này là một level khác của câu #4. 

Một cách để giải quyết vấn đề này là dùng một trong hai cấu trúc dữ liệu Hashtable hoặc Hashmap. 

Với Hashmap, ta duyệt mảng, lưu mỗi giá trị ứng với một key và số lần xuất hiện của chúng ứng với values. Sau khi duyệt hết mảng, ta dễ dàng kiểm tra được phần tử trùng nhau thông qua giá trị của các values tương ứng trong Hashmap. 

Trong Java, với cấu trúc dữ liệu Hashmap, nếu tồn tại các giá trị trùng nhau thì method get(index) sẽ trả về null.

#7 Singly Linked List - Danh sách liên kết đơn VS Doubly Linked List - Danh sách liên kết kép

Lại một câu hỏi kinh điển khác về cấu trúc dữ liệu.

Sự khác biệt lớn nhất giữa hai loại danh sách liên kết này là khả năng duyệt các phần tử thuộc danh sách. 

Với danh sách liên kết đơn, đó là nguyên tắc một đi không trở lại, tại một nút xác định, chỉ tồn tại một con trỏ tới nút kế tiếp. Do đó, ta chỉ có thể đi tới nút kế tiếp, không thể quay lại nút trước nó.

Với danh sách liên kết kép, tại một nút tồn tại 2 con trỏ, nhờ 2 con trỏ này ta có thể đi đến nút trước và nút sau. 

#8 Viết một chương trình in ra màn hình dãy Fibonacci

Đây không phải là một câu hỏi liên quan tới Cấu trúc dữ liệu nhưng luôn xuất hiện ở các buổi phỏng vấn về cầu trúc dữ liệu!

Fibonacci là một dãy số đặc biệt với tính chất số sau bằng tổng hai số trước nó. Trong buổi phỏng vấn, người ta sẽ xoáy vào 2 thứ, một là hàm trả về số thứ i trong dãy, hai là cách viết hàm đó bằng đệ quy trong Java.

Mặc dù câu hỏi này không khó nhưng các thanh niên gà mờ sẽ lúng túng ở phần đệ quy.

#9 Viết chương trình kiểm tra một số có phải là Palindrome không?

Số Palindrome là số trước sau như một - viết xuôi hay ngược đều giống nhau.

Đây cũng là câu hỏi không liên quan tới Cấu trúc dữ liệu tương tự như câu số 9. Tất nhiên, bạn không được tiếp cận với các sự trợ giúp từ API, trong tay bạn chỉ có các phép toán số học, các lệnh rẽ nhánh và lặp.

Gợi ý: dùng phép chia lấy phần dư và phép chia lấy phần nguyên.

#10 Trình bày về cây nhị phân tìm kiếm - Binary search tree 

"Cây nhị phân là một cấu trúc dữ liệu. Mọi nút của cây nhị phân có tối đa 2 nút con, các node bên phải luôn lớn hơn root node, còn các nút bên trái thì nhỏ hơn root node. Giá trị các node không trùng nhau"

Điều quan trọng là nhà tuyển dụng sẽ bắt bạn cài đặt cây nhị phân và viết thêm vài đoạn code để duyệt các node thay vì nghe bạn chém lý thuyết.

#11 Đảo vị trí các phần tử trong danh sách liên kết sử dụng đệ quy và duyệt tuần tự?

Một câu hỏi cơ bản nhưng cũng tương đối thú vị về cấu trúc dữ liệu.

Hãy tham khảo ở đây 

#12 Cài đặt Stack

Bạn có thể cài đặt Stack thông qua array - mảng hoặc Linked List - Danh sách liên kết. Các hàm cơ bản như push() và pop() là bắt buộc. Việc thêm các hàm tiện ích như contains() hay isEmpty() cũng rất cần thiết. JDK có hẳn một class về Stack: java.util.Stack, bạn có thể tham khảo code của class này.

Một lưu ý nho nhỏ, việc cài đặt stack sai cách có thể gây ra memory leak trong Java, hãy tham khảo cuốn Effective Java book của Josh Bloch để hiểu rõ hơn và tránh được lỗi này.