Kinh nghiệm làm bài test, phỏng vấn VNG Fresher

[Thien_Nguyen7 (Thiên Nguyễn)]

Hi, chào mọi người, chuyện là sắp tới mình có tham gia chương trình VNG Tech Fresher, không biết trong group có bạn hay anh chị nào đã từng phỏng vấn có thể cho mình xin ít kinh nghiệm với , nghe nói phỏng vấn khó, với phỏng vấn có Graph nữa hay sao ạ ( Có câu hỏi ví dụ thì càng tốt ạ )

[huy_ngoc (huy ngọc)]

đây là những gì t nhớ sau đợt bài test, đừng ôn kỹ quá 1 cái gì đó, nắm chắc cơ bản, đặc biệt là lý thuyết và cách hoạt động là được:

1. stack, queue : cơ bản push(), pop(), enqueue(), dequeue() . À ôn thêm tiền-trung-hâu tố (kinh điển của stack )
2. DSLK đơn : có 2-3 câu gì đó, t chỉ nhớ 1 câu là về reverse linked list c++ (search trên geek ra 1 câu y xì thế), ôn cả độ phức tạp nữa.
3. Đồ thị : cho 1 cái đồ thị có hướng (A->B->…) viết Danh sách duyệt BFS (quá dễ)
4. Ôn mấy cái toán tử bit : dịch bit (<<) , AND (&),… có 2,3 câu cho code và chọn đáp án đoạn code trên làm gì ?
5. Có 1 câu chọn đoạn code đúng in ra số đảo ngược hay thuận nghịch gì đó : đọc kĩ nhá t sai cmn nó câu này vì chọn nhầm : res += res10 + n%10 , phải chọn là res = res10 + n%10
6. Cho 1 đoạn code đoán xem đoạn code làm gì :
   t nhớ có 1 câu đáp án đúng là tìm dãy con có tổng lớn nhất sd thuật toán kanden algorithm (cái này dễ )
7. Các thuật toán sắp xếp (cái này nhiều nhất trong đề) : ôn kỹ cái độ phức tạp và code : buble sort, interchane sort, selection sort, insertion sort, merge sort, quick sort, heap sort

• t có nhớ 1 vài câu như sau :

• khi nào thì quick_sort xảy ra TH xấu nhất O(n^2) : chọn là khi dãy đã được sx sẵn trc nhé
• chọn dãy có độ phức tạp tăng dần trong TH tốt nhất : chọn là insertionsort-> quick sort -> selection sort
• chọn 1 trong 4 đoạn code miêu tả thuật toán buble sort : để ý kỹ chỉ số i, j
• tìm độ phức tạp tốt nhất của bài toán tìm a, b sao cho |a-b| = k : cái này hình như là O(nlogn) vì phải áp dụng tìm kiếm nhị phân ( mà tknp phải sort trc mới tìm dc)
• chọn thuật toán sd chia để trị : quicksort, merge sort
• heapsort : findMin trong MaxHeap độ phức tạp là bao nhiêu : chọn O(n) nhé trên geek , t chọn O(logn) tại cứ tg vì MaxHeap là cây nhị phân nên nó thế

7. Cây nhị phân

• Ôn duyêt trước-giữa-sau và duyệt theo mức (level) của cây

• cho 1 cây chọn đáp án đúng về thứ tự duyệt cây ( cái này dễ )
• cho 2 thứ tự duyệt tìm thứ tự duyệt còn lại của cây
• chọn CTDL khi duyệt cây theo level : chọn queue vì sd BFS

• Chọn chiều cao cây đúng : đề cho cây có 1 node thì h = 0 lên cứ đếm tổng số cạnh lớn nhất có thể đạt dc từ node gốc tới node lá (trên geek)
• Cân bằng cây AVL

8. Đệ quy : chọn code đúng cho bài toán tháp HN, …vv
9. Còn mấy câu cho code chọn đáp dúng với tìm đoạn code còn thiếu nữa thì t chưa đọc tới vì ko kịp thời gian (60 phút - 25 câu)
10. Nếu là trường khác thì lấy mấy đề thi CTDL của Bách khoa , UET ra ôn và làm ( chọn cái nào có đáp án ấy) vì kiến thức bài thi nó la lá vậy chỉ khác 1 bên trường tự luận, còn VNG là trắc nghiệm. T học bưu chính miền Bắc thì CTDL phải submit code mới qua môn chứ ko học kiểu lý thuyết.

[noname00 (HK boy)]

@huy_ngoc

khi nào thì quick_sort xảy ra TH xấu nhất O(n^2) : chọn là khi dãy đã được sx sẵn trc nhé

Nếu dãy arr có dạng tăng dần/giảm dần và bạn đặt pivot là 1 phần tử bất kì (không phải arr[(left + right) / 2]) thì có rơi vào trường hợp xấu nhất không?