100 câu hỏi phỏng vấn thuật toán hàng đầu năm 2022

CÁC CÂU HỎI VỀ NGÔN NGỮ

1) List và tuple khác nhau thế nào?

Khi nào nên sử dụng list, khi nào nên dùng tuple:

Nên dùng tuple để lưu trữ những thông tin bạn không muốn thay đổi trong quá trình thực thi, chẳng hạn như danh sách chọn lựa giới tính của một người, chúng ta có thể định nghĩa dưới dạng một tuple như sau: gender_chocies = ((1, 'Nam'), (2, 'Nữ'), (3, 'Không tiết lộ')). Khi lưu vào database, chúng ta chỉ cần lưu các giá trị 1, 2, hoặc 3 để tiện xử lý. Khi hiện thị, chúng ta có thể dễ dàng hiện thị Nam thay cho giá trị 1, Nữ thay cho giá trị 2, và Không tiết lộ thay cho giá trị 3.

Vì lists có thể thay đổi được sau khi khởi tạo, chúng ta nên dùng nó để chứa các thông tin cần thay đổi trong quá trình thực thi chương trình. Ví dụ: danh sách các mã chứng khoán đáp ứng một tiêu chí lọc. Chúng ta lưu trong list để có thể thay đổi thứ tự của các mã chứng khoán trong danh sách đó theo tên, hoặc theo giá.

2) Làm sao để chuyển một list thành một tuple?

• Cách 1: chuyển toàn bộ list a thành một tuple: tuple(a)
• Cách 2: chuyển một số thành phần của list a = [1, 2, 3, 4, 5] thành tuple b: b = (a[0], a[3], a[4])

3) List và array khác nhau thế nào?

4) Làm sao để chuyển một list thành một array?

Khi lập trình, sẽ có lúc chúng ta cần chuyển list thành array để thực hiện các phép toán trên đó một cách hiệu quả hơn. Để thực hiện việc này, chúng ta sử dụng hàm numpy.array(). Hàm này nhận 1 list làm tham số và trả về một array chứa các thành phần của list. Ví dụ:

import numpy as np

a = [1, 2, 3]

a_array = np.array(a)

5) Python quản lý bộ nhớ thế nào?

• Bộ nhớ Python được quản lý trong không gian nhớ riêng của Python. Tất cả các đối tượng cấu trúc dữ liệu được đặt trong một không gian nhớ riêng. Lập trình viên không truy cập vào vùng nhớ này được mà do Python tự quản lý.
• Việc phân bổ vùng nhớ cho các đối tượng do trình quản lý bộ nhớ của Python đảm nhiệm. API lõi cho các lập trình viên truy cập qua một số công cụ để lập trình.
• Python cũng có trình gom rác tích hợp sẵn để tái chế các vùng nhớ không còn sử dụng đến và giải pháp chúng tạo thêm chỗ cho không gian nhớ.

6) Bạn thực hiện đa luồng (multithreading) trong Python thế nào?

1. Python có một thư viện đa luồng nhưng nếu bạn muốn sử dụng đa luồng để tăng tốc chương trình, sử dụng thư viện này không phải là một ý kiến hay.
2. Python có một cấu trúc gọi là Khoá Phiên Dịch Toàn Cục (Global Interpreter Lock - GIL). GIL đảm bảo rằng tại một thời điểm chỉ có một luồng được thực thi. Một luồng lấy GIL, làm một số công việc, rồi GIL cho luồng kế tiếp.
3. Quá trình này xảy ra rất nhanh, nên dưới ánh mắt con người, nó có vẻ đang thực hiện song song, nhưng thực ra chúng chỉ luân phiên sử dụng cùng một lõi CPU.
4. Tất cả quá trình luân chuyển GIL này làm tăng thêm tải cho quá trình thực thi. Điều này nghĩa là nếu bạn muốn tăng tốc cho chương trình của mình, sử dụng thư viện đa luồng không phải là ý tưởng tốt.

7) Monkey patching là gì?

Trong Python, thuật ngữ monkey patch chỉ việc thay đổi một lớp (class) hay một module trong quá trình thực thi (run-time)

8) Hàm lambda là gì? Cho 1 ví dụ để minh hoạ khi nào nên dùng, khi nào không nên dùng.

Hàm lambda là một hàm nhỏ không có tên và trả về một đối tượng.

Đối tượng do hàm lambda trả về thường được gán cho 1 biến hoặc được sử dụng như một thành phần của một hàm lớn hơn.

Thay vì dùng từ khoá def để định nghĩa hàm như thông thường, hàm lambda được định nghĩa bằng cách dùng từ khoá lambda. Ví dụ, ta có thể tạo hàm lambda để cộng thêm 10 vào biến a như sau:

x = lambda a : a + 10
print(x(5))

Kết quả trả về của x(5) sẽ là 15

Mục tiêu của hàm lambda

Hàm lambda dễ đọc hơn nhiều so voi một hàm thông thường vì nó có thể được viết trên 1 dòng lệnh. Do đó, dùng hàm lambda khi biểu thức hàm nhỏ là một cách thực hành tốt.

Cái đẹp của hàm lambda là nó trả về một đối tượng hàm. Đặc tính này làm cho hàm lambda trở nên hữu dụng khi sử dụng với các hàm map hoặc filter vốn đòi hỏi các đối tượng hàm làm tham số.

Hàm lambda không hữu dụng khi biểu thức hàm vượt quá 1 dòng.

9) Pickling và unpickling là gì?

Module Pickle nhận một đối tượng Python, chuyển nó thành chuỗi đại diện, và lưu nó ra tập tin bằng hàm dump. Quá trình này gọi là pickling. Quá trình ngược lại, nghĩa là chuyển một chuỗi đại diện thành đối tượng Python được gọi là unpickling.

 10) Numpy array có lợi thế gì so với list (hoặc list lồng trong list - nested list)?

1. Python list là những biến tập hợp đa dụng và hiệu quả. Chúng hỗ trợ khá tốt các thao tác chèn (insert,) xoá (deletion,) thêm vào cuối (appending,) và nối list (concatenate.) Cấu trúc duyệt danh sách (list comprehension) giúp cho list dễ xây dựng và thao tác.
2. Tuy nhiên, chúng có một số hạn chế sau: list không hỗ trợ các phép tính vector ('vectorized' operations) như cộng hay nhân theo từng phần tử (elementwise addition and multiplication,) và việc list chứa các phần tử thuộc nhiều kiểu dữ liệu khác nhau cho thấy Python phải lưu kiểu dữ liệu của mỗi phần tử, và phải thực thi lệnh theo kiểu dữ liệu khi thao tác trên mỗi phần tử.
3. NumPy không chỉ hiệu quả hơn; nó cũng tiện hơn. Bạn có thể thực hiện nhiều phép tính theo kiểu vector và ma trận miễn phí, giúp tiết kiệm thời gian làm các việc không cần thiết. Các phép tính này được thực hiện một cách hiệu quả.
4. NumPy array nhanh hơn và bạn có thể sử dụng rất nhiều hàm dựng sẵn (built-in) với Numpy, FFTs, tích chập (convolutions,) tìm nhanh, thống kê cơ bản, đại số tuyến tính, biểu đồ tần suất (histogram) v.v...

11) Giải thích cơ chế kế thừa trong Python và đưa ra một ví dụ minh hoạ:

Kế thừa cho phép một Lớp (Class) thừa hưởng tất cả các thành phần (thuộc tính và hàm) của một Lớp khác. Kế thừa giúp tăng khả năng tái sử dụng mã nguồn, giúp dễ tạo và bảo trì các ứng dụng. Lớp cho kế thừa được gọi là Lớp cha (super class) và lớp kế thừa từ lớp khác được gọi là Lớp con (child class.)

Python hỗ trợ 4 kiểu kế thừa sau:

1. Kế thừa đơn - một lớp kế thừa từ một lớp cha duy nhất.
2. Kế thừa đa lớp - lớp con d1 kế thừa từ lớp Cha 1, và d2 kế thừa từ lớp Cha 2.
3. Kế thừa theo thứ bậc - một lớp cha có thể cho cho nhiều lớp con kế thừa.
4. Đa kế thừa - một lớp con kế thừa từ nhiều hơn một lớp cha.

12) Tính đa hình (Polymorphism) trong Python là gì?

Tính đa hình chỉ khả năng một đối tượng có thể có nhiều hình thức khác nhau. Ví dụ, nếu Lớp cha có một hàm tên ABC, Lớp con có thể có một hàm cùng tên nhưng với các tham số và biến khác nhau. Python hỗ trợ tính đa hình.

13) Hãy giải thích sự khác nhau giữa hàm range() và hàm xrange():

Trong phần lớn các trường hợp range() và xrange() chỉ cùng một tính năng. Chúng đều cho chúng ta tạo ra một Danh sách (List) các số nguyên để sử dụng. Sự khác biệt duy nhất là hàm range trả về một đối tượng Danh sách của Python, còn hàm xrange trả về một đối tượng xrange.

14) Hãy giải thích sự khác nhau giữa Flask và Diango

Django là một khung ứng dụng web (Web framework) mã nguồn mở, trình độ cao giúp "khuyến khích việc phát triển nhanh, thiết kế thực dụng, tinh tế và sạch sẽ." Django chạy nhanh, an toàn, và có khả thể mở rộng (scalable) nhanh. Django có hỗ trợ cộng đồng mạnh mẽ và tài liệu chi tiết.

Django là một gói tổng thể, trong đó bạn sẽ có Bảng điều khiển quản trị (Admin panel,) giao diện cơ sở dữ liệu (CSDL,) và cấu trúc thư mục ngay khi tạo ứng dụng. Ngoài ra, nó còn nhiều tính năng, nên bạn không cần thêm các thư viện riêng và các thư viện phụ thuộc. Một vài tính năng sẵn có là xác thực người dùng, động cơ mẫu (template engine,) định tuyến (routing,) quản lý thay đổi và dịch chuyển thiết kế CSDL (database schema migration,) và rất nhiều tính năng khác.

Django rất linh động. Bạn có thể dùng Django để làm các ứng dụng tối thiểu (MVP - Minimum Viable Product) cho đến các ứng dụng cho các công ty lớn. Để tiện hình dung, một số công ty lớn sử dụng Django là Instagram, Dropbox, Pinterest, và Spotify.

Flask là một khung ứng dụng web vi mô (microframework.) Nó không bao gồm sẵn các thư viện cần thiết cho việc phát triển web toàn tập như Django. Flask tiếp cận theo hướng tối giản, nghĩa là bạn sẽ thêm các thư viện trong quá trình lập trình thay vì đóng gói chúng sẵn trong khung ứng dụng. Triết lý của Flask là Flask chỉ cung cấp những thành phần bạn cần để xây dựng một ứng dụng để bạn có sự linh hoạt và kiểm soát. Nói cách khác, Flask không giả định bạn sẽ cần thư viên này hay thư viên khác và đóng gói chúng sẵn. Thay vào đó, Flask để bạn chọn lựa và thêm các thư viện khi mình cần. Một số tính năng Flask cung cấp là Máy chủ phục vụ web (dành cho quá trình phát triển,) xử lý yêu cầu RESTFUL, http, và rất nhiều tính năng khác.

15) PYTHONPATH là gì?

Đó là một biến môi trường được sử dụng khi một đơn nguyên ứng dụng (module) được nhập (import) vào chương trình. Khi nhập một module, PYTHONPATH sẽ được tìm kiếm để kiểm tra sự có mặt của module được yêu cầu nhập trong các thư mục khác. Trình phiên dịch dùng biến PYTHONPATH để xác định module nào sẽ được tải vào bộ nhớ.

Nguồn: lược dịch từ https://dev.to/educative/50-python-interview-questions-and-answers-nh2#q12

16) PEP 8 là gì?

PEP là chữ viết tắt của Python Enhancement Proposal (Đề xuất tăng cường Python.) Đó là một bộ các quy ước về cách viết, định dạng mã nguồn, một bộ các đề xuất về cách viết mã nguồn Python để dễ đọc hơn.

17) Vật trang trí (decorator) Python là gì?

Vật trang trí là một mẫu thiết kế (design pattern) trong Python cho phép người dùng thêm tính năng cho một đối tượng sẵn có mà không cần sửa đổi cấu trúc của nó. Vật trang trí thường được gọi trước định nghĩa hàm chúng ta muốn trang trí.

18) Init là gì?

__init__ là một hàm tạo dựng (constructor) trong Python. Hàm này tự động được gọi để phân chia bộ nhớ khi một đối tượng hay một thực thể (instance) của một Lớp được khởi tạo. Tất cả các Lớp đều có hàm __init__

19) Toán tử bộ ba là gì?

Toán tử bộ ba là một cách viết câu lệnh điều kiện trong Python. Như từ 'bộ ba' trong tên gợi ý, toán tử này bao gồm 3 thành phần:

• Giá trị điều kiện đúng: Giá trị sẽ được gán cho biến nếu biểu thức điều kiện trả về giá trị True
• Điều kiện: một biểu thức trả về kết quả True hoặc False
• Giá trị điều kiện sai: Giá trị sẽ được gán cho biến nếu biểu thức điều kiện trả về giá trị Sai

Toán tử bộ ba có thể được xem như một phiên bản đơn giản hoá, 1 dòng của câu lệnh if-else với một điều kiện.

var = true_val if condition else false_val

Biến var bên tay trái của toán tử gán sẽ có giá trị: 

• true_val nếu điều kiện là True
• false_val nếu điều kiện là False

20) Biến toàn cục (global) và biến địa phương (local) trong Python là gì?

Biến toàn cục là các biến được khai báo bên ngoài phạm vi một hàm hoặc được khai báo trong không gian toàn cục. Các biến này có thể được truy xuất bởi bất kỳ hàm nào trong chương trình.

Biến địa phương là các biến được khai báo trong phạm vi của một hàm. Các biến địa phương tồn tại trong không gian địa phương, và không tồn tại trong không gian toàn cục. Biến địa phương chỉ có thể được truy xuất trong phạm vi hàm mà nó được khai báo.

21) @property trong Python là gì?

@property là một vật trang trí trong Python. @property trước định nghĩa một hàm cho phép truy xuất hàm đó như cách truy xuất một thuộc tính (không cần cặp ngoặc đơn sau tên hàm.)

22) try / except được sử dụng thế nào trong Python?

Một "ngoại lệ" (exception) là một lỗi xảy ra trong quá trình thực thi một chương trình. Khi lỗi này phát sinh, chương trình sẽ dừng lại và tạo ra một "ngoại lệ" và chuyển những "ngoại lệ" này qua bộ xử lý riêng để ngăn chương trình bị dừng thực thi do lỗi (crash.)

Những ngoại lệ được tạo ra bởi một chương trình có thể được bắt trong khối lệnh try và xử lý trong khối lệnh except.

• Try: hãy thử thực thi khối lệnh sau đây để xem có bị lỗi không
• Except: nếu lỗi xảy ra ở đoạn lệnh trên, hãy xử lý nó bằng khối lệnh dưới đây

23) Hãy giải thích sự khác biệt giữa Python 2 và Python 3

24) Hàm join trong Python là gì?

Hàm join trong Python nhận một biến có cấu trúc khả lặp (iterable) và nối chúng lại với nhau sử dụng một giá trị chuỗi.

Cách join làm việc?

array = ['H','E','L','L','O']
connector = ""
joined_string = connector.join(array)
print(joined_string)

Output:
HELLO

25) Toán tử tạo từ điển từ biến khả lặp (dictionary comprehension) là gì?

Đây là một cách tạo 1 từ điển trong Python. Nó tạo ra một từ điển bằng cách sáp nhập 2 bộ dữ liệu ở dạng danh sách (list) hoặc mảng (array.)

Dữ liệu của một trong hai list / array sẽ trở thành 'từ khoá' của từ điển, cái còn lại là giá trị. Mỗi 'từ khoá' sẽ là khoá nhận dạng duy nhất cho 1 giá trị, và do đó, kích thước của 2 list/array nên bằng nhau.

Cú pháp chung:

tu_dien_moi = {key:value for (key, value) in bien_kha_lap}

Ví dụ:

Ví dụ dưới đây áp dụng cho CSDL của trường đại học và sử dụng phương pháp sáp nhập đơn giản (không có điều kiện.) Giả sử CSDL chưa nhiều dữ liệu như địa chỉ, điểm, học phí, mã số SV, v.v... Bây giờ chúng ta cần xác định mỗi SV duy nhất và tạo ra một từ điển chỉ chứa thông tin các sinh viên. Quyết định của chúng ta đơn giản dựa vào 2 câu hỏi:

Từ khoá (key) nên là thông tin nào?

Giá trị (value) nên là thông tin nào?

Ở đây chúng ta chọn Mã số SV làm từ khoá và tên sinh viên là giá trị, vì mã số SV là duy nhất, còn tên có thể bị trùng.

rollNumbers =[122,233,353,456]
names = ['alex','bob','can', 'don'] 
NewDictionary={ i:j for (i,j) in zip (rollNumbers,names)}
print(NewDictionary)

Output:
{456: 'don', 233: 'bob', 122: 'alex', 353: 'can'}

26) Làm sao để tạo ra bản sao sâu (deep copy) trong Python?

Tạo bản sao sâu chỉ việc sao chép một đối tượng. Khi dùng toán tử gán (=,) chúng ta không tạo ra bản sao của một đối tượng, mà thay vào đó, chúng ra chỉ trỏ biến của mình vào cùng một đối tượng (tạo bản sao nông.) Điều này nghĩa là thay đổi giá trị của một biến cũng sẽ ảnh hưởng đến giá trị của biến kia, vì nó cùng trỏ về một đối tượng. Sự khác biệt giữa bản sao sâu và bản sao nông chỉ áp dụng với các đối tượng chứa các đối tượng khác như danh sách (list) và các biến thực thể của Lớp.

Phương pháp

Để tạo bản sao sâu của một đối tượng, chúng ta nhập vào chương trình module copy trong Python. Module này có chứa hàm deepcopy() giúp đơn giản hoá công việc của chúng ta.

Cú pháp

Hàm này nhận đối tượng chúng ta muốn tạo bản sao làm tham số, và trả về bản sao của đối tượng đó.

import copy

# Using '=' operator
x = [1, 2, 3]
y = x
x[0] = 5    # value of 'y' also changes as it is the SAME object
x[1] = 15
print "Shallow copy: ", y

# Using copy.deepcopy()
a = [10, 20, 30]
b = copy.deepcopy(a)
a[1] = 70   # value of 'b' does NOT change because it is ANOTHER object
print "Deep copy: ", b

Output:
Shallow copy: [5, 15, 3]
Deep copy: [10, 20, 30]

27) Làm sao để kiểm tra xem một từ điển có chứa một từ khoá nào đó?

Kiểm tra xem một từ khoá có trong từ điển hay không trước khi truy xuất giá trị của từ khoá đó trong từ điển là một cách thực hành an toàn. Để làm việc này, Python cung cấp 2 hàm sẵn có (built-in):

• Hàm has_key():
• Câu lệnh if-in

Hàm has_key() trả về kết quả True nếu từ khoá có trong từ điển, và False trong trường hợp ngược lại.

Fruits = {'a': "Apple", 'b':"Banana", 'c':"Carrot"}
key_to_lookup = 'a'
if Fruits.has_key(key_to_lookup):
  print "Key exists"
else:
  print "Key does not exist"

Output: Key exists

Câu lệnh if-in kiểm tra xem một từ khoá có trong từ điển hay không

Fruits = {'a': "Apple", 'b':"Banana", 'c':"Carrot"}
key_to_lookup = 'a'
if key_to_lookup in Fruits:
  print "Key exists"
else:
  print "Key does not exist"

Output: Key exists

28) Bạn thực hiện kỹ thuật nhớ kết quả tạm (memoization) trong Python thế nào?

Memoization là một kỹ thuật cải thiện tốc độ tính toán của các chương trình sử dụng thuật toán đệ quy (recursive.) Kỹ thuật Memoization lưu các kết quả tính toán của các bước trung gian trong một mảng, và truy xuất chúng trong các bước đệ quy sau, thay vì phải tính lại kết quả của các bước trước đó.

Để minh hoạ, hãy xem đoạn mã rất tốn kém về mặt tính toán sau:

# Fibonacci Numbers
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fib(num - 1) + fib(n - 2)

Ứng dụng kỹ thuật nhớ tạm (memoization) có thể được thực hiện qua việc dùng vật trang trí Python như sau:

import timeit

def memoize_fib(func):
    cache = {}
    def inner(arg):
        if arg not in cache:            
            cache[arg] = func(arg)
        return cache[arg]
    return inner


def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fib(num-1) + fib(num-2)

fib = memoize_fib(fib)


print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))

Output:

4.9035000301955733e-05
1.374000021314714e-06
1.2790005712304264e-06

29) Bạn xếp thứ tự từ điển trong Python thế nào?

Chúng ta có thể xếp thứ tự từ điển theo 'từ khoá' hoặc theo 'giá trị' dùng hàm sorted(). Trước hết, chúng ta cần biết cách lấy dữ liệu từ từ điển để truyền vào hàm sorted. Có 3 cách lấy dữ liệu từ từ điển:

• tu_dien.keys(): trả về các từ khoá theo thứ tự bất định.
• tu_dien.values(): trả về một danh sách các giá trị.
• tu_dien.items(): trả về dữ liệu dưới dạng một danh sách các cặp từ khoá - giá trị.

Cú pháp:

Sorted(data[bắt buộc], key[tuỳ chọn], reverse[tuỳ chọn])

Hàm sorted nhận một tham số bắt buộc và 2 tham số tuỳ chọn.

• Data (mandatory): Dữ liệu cần xếp thứ tự. Dữ liệu truyền vào sẽ được lấy từ 1 trong 3 cách ở trên.
• Key (optional): Một hàm (hay tiêu chuẩn) chúng ta muốn xếp thứ tự theo. Chẳng hạn, sắp xếp thứ tự các chuỗi theo độ dài của chúng, hoặc theo một hàm tuỳ ý. Hàm này sẽ được áp dụng với từng thành phần trong danh sách và kết quả của chúng sẽ được sử dụng để xếp thứ tự. Nếu tham số này trống, hàm sorted sẽ xếp thứ tự theo giá trị ban đầu của dữ liệu.
• Reverse (optional): Tham số thứ ba là True sẽ trả về kết quả theo thứ tự giảm dần (descending.) Để trống sẽ trả về kết quả theo thứ tự tăng dần (ascending)

keys()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'pango'

lst = dict.keys()

# Sorted by key
print("Sorted by key: ", sorted(lst))

values()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'pango'

lst = dict.values()

#Sorted by value
print("Sorted by value: ", sorted(lst))

items()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'strawberry'

lst = dict.items()

# Sorted by key
print("Sorted by key: ", sorted(lst, key = lambda x : x[0]))

#Sorted by value
print("Sorted by value: ", sorted(lst, key = lambda x : x[1]))

30) Bạn dùng hàm any() và all() thế nào và khi nào?

Hàm any() là gì?

any() là một hàm nhận một biến khả lặp (iterable) như 1 danh sách (list), 1 danh sách cố định (tuple,) 1 bộ (set,) làm tham số và trả về kết quả True nếu bất kỳ thành phần nào trong biến khả lặp đó có giá trị True, nhưng trả về giá trị False nếu tất cả các thành phần có giá trị False.

Truyền biến khả lặp cho hàm any() để kiểm tra xem có thành phần nào có giá trị True hay không có thể được thực hiện như sau:

one_truth = [True, False, False]
three_lies = [0, '', None]

print(any(one_truth))

print(any(three_lies))

Output:
True
False

Lệnh in đầu tiên trả về kết quả True vì một trong những thành phần của biến one_truth có giá trị True.

Trong khi đó, lệnh in thứ hai trả về kết quả False vì không một thành phần nào trong biến three_lies có giá trị True.

Dùng hàm any() để kiểm tra một chuỗi dài các điều kiện or

Hàm all() là gì?

all() là một hàm Python khác nhận một biến khả lặp và trả về kết quả True nếu tất cả các thành phần trong biến có giá trị True. Nếu bất kỳ thành phần nào trong biến khả lặp có giá trị False, hàm all() sẽ trả về kết quả False.

all_true = [True, 1, 'a', object()]
one_true = [True, False, False, 0]
all_false = [None, '', False, 0]

print(all(all_true))
print(all(one_true))
print(all(all_false))

Output:
True
False
False

Câu lệnh đầu tiên trả về kết quả True vì all_true bao gồm tất cả các thành phần có giá trị True.

Truyền biến one_true cho hàm all() trả về kết quả False vì tham số có 1 chứa 1 hoặc nhiều hơn một giá trị False.

Và sau cùng, truyền biến all_false cho hàm all(), chúng ta nhận được kết quả False vì tham số bao gồm một hoặc nhiều hơn giá trị False.

Dùng hàm all() khi cần kiểm tra một chuỗi dài các điều kiện and

31) Python Docstring là gì?

Python docstrings là một cách thích hợp để gắn tài liệu thuyết minh mã lập trình với:

• Đơn nguyên (modules) Python
• Hàm Python
• Lớp (Class) Python

Nó là đoạn văn bản nhất định cho đoạn mã gắn liền với nó. Không như những lời bình lập trình (code comments,) docstring mô tả việc mà một hàm thực hiện, không phải cách nó thực hiện.

docstring có thể được truy xuất bằng cách gọi hàm:

• __doc__ của đối tượng
• help

32) Missing question?

To be filled out later

33) Hãy giải thích sự khác nhau giữa Bộ tạo (generator) và Bộ lặp (iterator) trong Python.

Bộ lặp (iterator) trong Python đóng vai trò như một kẻ giữ chỗ cho các đối tượng để nó có thể duyệt qua; Bộ tạo (generator) tạo điều kiện dễ dàng cho việc tạo một bộ lặp tuỳ biến. Như vậy, một bộ tạo luôn luôn là một bộ lặp, nhưng không phải lúc nào một bộ lặp cũng là một bộ tạo.

Ngoài những khác biệt về cú pháp, còn có các khác biệt đáng kể sau:

Ví dụ về một Bộ lặp

# Hàm tạo tất cả các số không âm
# nhỏ hơn hoặc bằng một số không âm cho trước.
class UpTo:
    # gán cho tham số giá trị mặc định 0 
    def __init__(self, max = 0):
        self.max = max
    def __iter__(self):
        self.n = 0
        return self
    def __next__(self):
        # Hàm next sẽ tạo một ngoại lệ 
        # khi gặp phải điều kiện kết thúc.
        if self.n > self.max:
            raise StopIteration
        else:
            result = self.n
            self.n += 1
            return result
for number in UpTo(5):
    print(number)

Output:
0
1
2
3
4
5

Ví dụ về Bộ tạo

# Hàm tạo tất cả các số nguyên không âm 
# nhỏ hơn hoặc bằng một số nguyên không âm cho trước
def upto(n):
  for i in range(n+1):
    # Câu lệnh yield là điều làm cho đoạn mã này trở thành 1 hàm
    # một bộ tạo 
    yield i
for number in upto(5):
  print(number)

Output:
0
1
2
3
4
5

34) defaultdict trong Python là gì?

Từ điển Python, dict, chứa các từ và nghĩa như các cặp từ khoá - giá trị của bất kỳ kiểu dữ liệu gì. defaultdict là một loại dữ liệu con của lớp dict dựng sẵn trong Python.

defaultdict khác chỗ nào?

defaultdict là kiểu dữ liệu con của lớp dict. Sự quan trọng của nó nằm ở chỗ nó cho phép mỗi từ khoá mới có một giá trị mặc định dựa vào kiểu từ điển được tạo.

Một defaultdict có thể được tạo bằng cách khai báo, một tham số có có thể có 3 giá trị; list, set, hoặc int. Tuỳ theo loại dữ liệu khai báo, từ điển sẽ được tạo và khi bất kỳ từ khoá nào chưa có trong default dict sẽ được thêm vào hoặc truy xuất. Nó sẽ được gán một giá trị mặc định thay vì báo lỗi KeyError.

Ví dụ

Đoạn mã nhỏ dưới đây minh hoạ cách khởi tạo một từ điển đơn giản và khi truy xuất từ điển với một từ khoá không tồn tại, nó báo lỗi thế nào.

dict_demo = dict()
print(dict_demo[3])

Đoạn mã nhỏ dưới đây minh hoạ một biến defaultdict và hãy xem chuyện gì xảy ra.

from collections import defaultdict

defaultdict_demo = defaultdict(int)
print(defaultdict_demo[3])

Output: 0

Trong trường hợp này, chúng ta đã truyền int làm tham số quy định kiểu dữ liệu cho defaultdict. Do đó, khi truy xuất một từ khoá chưa tồn tại, từ khoá đó sẽ được thêm vào và được gán giá trị 0.

Ghi chú: Bạn cũng có thể truyền set hoặc list làm tham số cho defaultdict.

35) Đơn nguyên (modules) Python là gì?

Một đơn nguyên Python là tập tin Python bao gồm một bộ các hàm và biến để sử dụng trong một ứng dụng. Các biến có thể thuộc bất kỳ kiểu dữ liệu nào. Đơn nguyên có thể thuộc 1 trong 2 dạng:

1. Dựng sẵn (Built in)

2. Do người dùng định nghĩa (User-defined)

Lợi ích của đơn nguyên trong Python

Có một số lợi ích chủ chốt trong việc tạo và sử dụng đơn nguyên trong Python:

• Mã nguồn có cấu trúc

  • Mã nguồn được tổ chức mạch lạc bằng cách nhóm chúng vào một tập tin Python. Việc này giúp cho quá trình phát triển trở nên dễ hơn, và ít bị lỗi hơn.
  • Dễ hiểu và sử dụng mã nguồn hơn.

• Tái sử dụng

  • Các tính năng định nghĩa trong một đơn nguyên có thể dễ dàng được sử dụng lại ở những phần khác của ứng dụng. Qua đó, chúng ta không phải viết lại các đoạn mã nguồn đã viết ở chỗ khác.

CÁC CÂU HỎI VỀ KỸ THUẬT LẬP TRÌNH

Trong phần này chúng ta sẽ điểm qua các câu hỏi phỏng vấn về lập trình thông dụng liên quan đến danh sách (list), danh sách liên kết (linked list), biểu đồ (graph,) cây (trees,) đa luồng, thực thi đồng thời và hơn thế nữa. Hãy cũng bắt đầu khám phá nào.

36) Hãy đảo ngược một chuỗi

Hãy đảo ngược chuỗi "Python" dùng phương pháp cắt lát (slicing.) Để đảo ngược một chuỗi, chúng ta tạo ra một lát cắt bắt đầu với độ dài chuỗi, và kết thúc tại ví trí index 0.

Để đảo ngược một chuỗi bằng phương pháp cắt lát, chúng ta có thể dùng một trong các cách sau:To reverse a string using slicing, write:

stringname[stringlength::-1] # method 1 

Hoặc viết mà bỏ trống tham số độ dài chuỗi như sau:

stringname[::-1] # method2

Câu lệnh cắt lát có nghĩa bắt đầu tại vị trí độ dài chuỗi, và kết thúc tại vị trí index 0, mỗi bước dịch chuyển một bước có giá trị -1 (một bước lùi về phía sau.)

str="Python" # initial string
stringlength=len(str) # calculate length of the list
slicedString=str[stringlength::-1] # slicing 
print (slicedString) # print the reversed string

Output: nohtyP

Đây là một cách để đảo ngược chuỗi. Các cách khác bao gồm phương pháp lặp và dùng lệnh join để nối chuỗi.

37) Kiểm tra xem một chuỗi có chứa một chuỗi con khác hay không

Có vài cách để thực hiện việc này. Trong phần này, chúng ta dùng hàm find. 

Hàm find kiểm tra xem chuỗi có chứa một chuỗi con hay không. Nếu có, nó trả về vị trí index đầu tiên của chuỗi con trong chuỗi cha. Nếu không, nó trả về -1.

Cú pháp chung là:

string.find(substring)

Ví dụ: 

a_string="Python Programming" 
substring1="Programming" 
substring2="Language" 
print("Check if "+a_string+" contains "+substring1+":")
print(a_string.find(substring1)) 
print("Check if "+a_string+" contains "+substring2+":")
print(a_string.find(substring2))

Output:
Check if Python Programming contains Programming: 7
Check if Python Programming contains Language: -1

Các phương pháp khác là dùng toán tử in hoặc hàm count.

38) Hãy thực hiện thuật toán Tìm kiếm Độ Rộng Trước Hết (Breadth First Search - BFS) bằng Python

Hãy xem xét sơ đồ dưới đây qua đoạn mã bên dưới:

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

Output: A B C D E F

Giải thích

Dòng 3-10: Sơ đồ trên được đại diện bằng một danh sách các điểm liền kề. Một cách dễ dàng để thực hiện việc này là dùng cấu trúc dữ liệu kiểu từ điển, trong đó mỗi đỉnh chứa một danh sách các điểm liền kề.

Dòng 12: visited là một danh sách để lưu trữ các nốt đã đi qua.

Dòng 13: queue là một danh sách để lưu trữ các nốt hiện đang trong hàng đợi.

Dòng 29: Tham số của hàm bfs là danh sách visited, sơ đồ dưới dạng 1 từ điển, và nốt xuất phát A.

Dòng 15-26: bfs theo thuật toán mô tả ở trên:

1. Nó kiểm tra và thêm nốt xuất phát vào danh sách visited và danh sách queue.
2. Kế đến, trong khi biến queue còn chứa các phần tử, nó tiếp tục lấy các phần tử đó ra khỏi hàng đợi, thêm nốt lân cận của nốt đó vào hàng đợi nếu nó chưa được đi qua, trong danh sách unvisited, và đánh dấu chúng là đã đi qua.
3. Việc này tiếp diễn cho đến khi hàng đợi trống rỗng.

Độ phức tạp về thời gian (Time Complexity)

Vì tất cả các nốt và đỉnh đều được đi qua, độ phức tạp về thời gian cho thuật toán BFS trên 1 sơ đồ là O(V + E) trong đó V là số đỉnh, và E là số cạnh.

Question 39: Hãy thực hiện thuật toán Độ Sâu Trước Hết (Depth First Search - DBS) bằng Python

Hãy xem sơ đồ này, và thực thi đoạn mã nguồn dưới đây:

# Using a Python dictionary to act as an adjacency list
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

Output: A B D E F C

Explanation

Dòng 2-9: Sơ đồ trên được đại diện bằng một danh sách các điểm liền kề. Một cách dễ dàng để thực hiện việc này là dùng cấu trúc dữ liệu kiểu từ điển, trong đó mỗi đỉnh chứa một danh sách các điểm liền kề.

Dòng 11: visited là một bộ (set) được dùng để lưu các nốt đã đi qua.

Dòng 21: Hàm dfs được gọi và truyền tham số là bộ chứa các nốt đã đi qua, sơ đồ ở dạng từ điển, và nốt xuất phát A.

Dòng 13-18: dfs theo thuật toán được mô tả dưới đây:

1. Trước hết, thuật toán kiểm tra xem nốt hiện hành đã được đi qua hay chưa. Nếu có, nó sẽ được thêm vào bộ visited.
2. Kế đến, cho mỗi nốt lân cận của nốt hiện hành, hàm dfs lại được gọi.
3. Tình huống cơ sở được kích hoạt khi tất cả các nốt đã được đi qua, sau đó hàm trả về kết quả cuối cùng.

Độ phức tạp về thời gian

Vì tất cả các nốt và các cạnh đều được viếng thăm, độ phức tạp về thời gian bình quân để thực thi thuật toán DFS trên 1 sơ đồ là O(V + E), trong đó V là số đỉnh và E là số cạnh. Trong trường hợp DFS trên 1 cây, độ phức tạp về thời gian là O(V), trong đó V là số nốt.

40) Hãy thực thi ký tự đại diện (wildcards) bằng Python

Trong Python, bạn có thể thực thi ký tự đại diện bằng thư viện regex (regular expressions - biểu thức thông thường.)

Ký tự chấm . được dùng thay cho dấu chấm hỏi ?. Do đó, để tìm tất cả các từ phù hợp với mẫu màu, mã có thể trông như sau:

# Regular expression library
import re

# Add or remove the words in this list to vary the results
wordlist = ["color", "colour", "work", "working",
            "fox", "worker", "working"]

for word in wordlist:
        # The . symbol is used in place of ? symbol
        if re.search('col.r', word) : 
                print (word)

Output: color

 41) Hãy thực thi thuật toán sắp xếp sáp nhập (merge sort) bằng Python

Đây là mã chương trình cho thuật toán sắp xếp sáp nhập:

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0

        # Iterator for the main list
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)

Output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

Giải thích

Đây là cách tiếp cận đệ quy trong việc thực hiện thuật toán sắp xếp qua sáp nhập. Các bước cần để có được một mảng đã sắp xếp bằng phương pháp này có thể được mô tả dưới đây:

1. Danh sách được chia thành 2 nửa left (trái) và right (phải) trong mỗi bước lặp đệ quy, cho đến khi chỉ còn 2 thành phần kế cận nhau.

2. Bây giờ bắt đầu quá trình xếp thứ tự. Biến lặp i và j lần lượt duyệt qua 2 nửa trong mỗi lần gọi. Biến lặp k duyệt qua toàn bộ danh sách và thực hiện các thay đổi dọc theo quá trình lặp.

3. Nếu giá trị ở vị trí i nhỏ hơn giá trị ở vị trí j, left[i] được gán cho myList[k] và tăng i lên một bước. Nếu không, then right[j] sẽ được chọn.

4. Cứ thế, các giá trị được gán qua k đều theo thứ tự.

5. Vào cuối vòng lặp, một trong hai nửa có thể chưa được lặp qua tất cả các nốt. Các giá trị của nó chỉ đơn giản được gán vào chỗ trống còn lại của danh sách.

Độ phức tạp về thời gian

Thuật toán thực thi trong O(n.logn). Đó là vì danh sách được chia thành log(n) lần gọi và quá trình sáp nhập mất một khoảng thời gian tuyến tính trong mỗi lần gọi hàm.

42) Hãy thực thi thuật toán Dijkstra bằng Python

Thuật toán cơ bản

1. Từ mỗi đỉnh chưa đi qua, hãy chọn đỉnh với khoảng cách nhỏ nhất và đi tới điểm đó.
2. Cập nhật khoảng cách cho mỗi đỉnh lân cận, của các đỉnh đã đi qua mà khoảng cách hiện hành lớn hơn tổng của nó, và trọng số của cạnh giữa 2 đỉnh.
3. Lập lại bước 1 và 2 cho đến khi tất cả các đỉnh được đi qua.

Dưới đây là đoạn mã thực hiện thuật toán trên

import sys

# Function to find out which of the unvisited node 
# needs to be visited next
def to_be_visited():
  global visited_and_distance
  v = -10
  # Choosing the vertex with the minimum distance
  for index in range(number_of_vertices):
    if visited_and_distance[index][0] == 0 \
      and (v < 0 or visited_and_distance[index][1] <= \
      visited_and_distance[v][1]):
        v = index
  return v

# Creating the graph as an adjacency matrix
vertices = [[0, 1, 1, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 1],
            [0, 0, 0, 0]]
edges =  [[0, 3, 4, 0],
          [0, 0, 0.5, 0],
          [0, 0, 0, 1],
          [0, 0, 0, 0]]

number_of_vertices = len(vertices[0])

# The first element of the lists inside visited_and_distance 
# denotes if the vertex has been visited.
# The second element of the lists inside the visited_and_distance 
# denotes the distance from the source.
visited_and_distance = [[0, 0]]
for i in range(number_of_vertices-1):
  visited_and_distance.append([0, sys.maxsize])

for vertex in range(number_of_vertices):
  # Finding the next vertex to be visited.
  to_visit = to_be_visited()
  for neighbor_index in range(number_of_vertices):
    # Calculating the new distance for all unvisited neighbours
    # of the chosen vertex.
    if vertices[to_visit][neighbor_index] == 1 and \
     visited_and_distance[neighbor_index][0] == 0:
      new_distance = visited_and_distance[to_visit][1] \
      + edges[to_visit][neighbor_index]
      # Updating the distance of the neighbor if its current distance
      # is greater than the distance that has just been calculated
      if visited_and_distance[neighbor_index][1] > new_distance:
        visited_and_distance[neighbor_index][1] = new_distance
    # Visiting the vertex found earlier
    visited_and_distance[to_visit][0] = 1

i = 0 

# Printing out the shortest distance from the source to each vertex       
for distance in visited_and_distance:
  print("The shortest distance of ",chr(ord('a') + i),\
  " from the source vertex a is:",distance[1])
  i = i + 1

Output:
The shortest distance of a from the source vertex a is: 0
The shortest distance of b from the source vertex a is: 3
The shortest distance of c from the source vertex a is: 3.5
The shortest distance of d from the source vertex a is: 4.5

43) Hãy sáp nhập 2 danh sách đã xếp thứ tự

# Merge list1 and list2 and return resulted list
def merge_lists(lst1, lst2):
    index_arr1 = 0
    index_arr2 = 0
    index_result = 0
    result = []

    for i in range(len(lst1)+len(lst2)):
        result.append(i)
    # Traverse Both lists and insert smaller value from arr1 or arr2
    # into result list and then increment that lists index.
    # If a list is completely traversed, while other one is left then just
    # copy all the remaining elements into result list
    while (index_arr1 < len(lst1)) and (index_arr2 < len(lst2)):
        if (lst1[index_arr1] < lst2[index_arr2]):
            result[index_result] = lst1[index_arr1]
            index_result += 1
            index_arr1 += 1
        else:
            result[index_result] = lst2[index_arr2]
            index_result += 1
            index_arr2 += 1
    while (index_arr1 < len(lst1)):
        result[index_result] = lst1[index_arr1]
        index_result += 1
        index_arr1 += 1
    while (index_arr2 < len(lst2)):
        result[index_result] = lst2[index_arr2]
        index_result += 1
        index_arr2 += 1
    return result


print(merge_lists([4, 5, 6], [-2, -1, 0, 7]))

Output: [-2, -1, 0, 4, 5, 6, 7]

Giải thuật trên là một cách trực quan hơn để giải quyết vấn đề.

1. Bắt đầu bằng danh sách rỗng. Danh sách sẽ được lấp đầy bằng tất cả các phần tử trong cả 2 danh sách theo thứ tự đã sắp xếp và trả về.

2. Kế đến khởi tạo 3 biến có giá trị 0 để lưu số chỉ mục (index) của mỗi danh sách.

3. Sau đó, so sánh các phần tử của 2 danh sách tại vị trí chỉ mục hiện hành, thêm số nhỏ hơn vào danh sách mới và tăng số chỉ mục lên 1 bước.

4. Lặp lại quá trình trên cho đến cuối các danh sách và thêm danh sách còn lại vào cuối danh sách đã sáp nhập.

Độ phức tạp về thời gian
Độ phức tạp về thời gian của thuật toán này là O(n+m)O(n+m) trong đó nn and mm là độ dài của các danh sách. Đó là vì cả 2 danh sách được duyệt qua ít nhất 1 lần.

Lưu ý: vấn đề này cũng có thể được giải quyết bằng cách sáp nhập tại chỗ.

44) Tìm 2 số trong danh sách có tổng là 'k'

def binarySearch(a, item, curr):
    first = 0
    last = len(a) - 1
    found = False
    index = -1
    while first <= last and not found:
        mid = (first + last) // 2
        if a[mid] == item:
            index = mid
            found = True
        else:
            if item < a[mid]:
                last = mid - 1
            else:
                first = mid + 1
    if found:
        return index
    else:
        return -1


def findSum(lst, k):
    lst.sort()
    for j in range(len(lst)):
        # find the difference in list through binary search
        # return the only if we find an index
        index = binarySearch(lst, k -lst[j], j)
        if index is not -1 and index is not j:
            return [lst[j], k -lst[j]]



print(findSum([1, 5, 3], 2))
print(findSum([1, 2, 3, 4], 5))

Output:
None
[1,4]

Bạn có thể giải quyết vấn đề này bằng cách trước hết xếp thứ tự danh sách. Sau đó, với mỗi phần tử trong danh sách, dùng thuật toán tìm nhị phân để tìm số chênh lệch giữa tổng và phần tử đó. Nói cách khác, nếu tổng cho trước là k và phần tử đầu tiên của danh sách đã xếp thứ tự trong danh sách là

a0a_{0}

chúng ta sẽ tìm phần tử bằng phương pháp nhị phân sao cho

a0a_{0}

Việc tìm kiếm được lặp lại cho đến khi một phần tử được tìm thấy. Bạn có thể thực thi hàm binarySearch() theo bất kỳ cách nào bạn muốn, đệ quy hay lặp lại.

Độ phức tạp về thời gian

Vì hầu hết các hàm xếp thứ tự dựa trên so sách tối ưu nhất mất O(nlogn), hãy giả định rằng hàm .sort() của Python mất khoản thời gian tương tự. Hơn nữa, vì tìm nhị phân mất O(logn) thời lượng cho việc tìm ra một phần tử duy nhất, do đó, việc tìm tất cả n phần tử sẽ mất O(nlogn) thời lượng.

 45) Tìm số nguyên không lặp lại trong một danh sách

Ở đây bạn có thể dùng từ điển Python để lưu số lần lặp lại của các phần tử.

Sample input:

def findFirstUnique(lst):
    counts = {}  # Creating a dictionary
    # Initializing dictionary with pairs like (lst[i],(count,order))
    counts = counts.fromkeys(lst, (0,len(lst)))
    order = 0
    for ele in lst:
        # counts[ele][0] += 1  # Incrementing for every repitition
        # counts[ele][1] = order
        counts[ele] = (counts[ele][0]+1 , order)
        order += 1 # increment order
    answer = None
    answer_key = None
    # filter non-repeating with least order
    for ele in lst:
        if (counts[ele][0] is 1) and (answer is None):
            answer = counts[ele]
            answer_key = ele
        elif answer is None:
            continue
        elif (counts[ele][0] is 1) and (counts[ele][1] < answer[1]):
            answer = counts[ele]
            answer_key = ele
    return answer_key


print(findFirstUnique([1, 1, 1, 2]))

Output: 2

Các từ khoá trong từ điển counts là các phần tử của danh sách được cho và các giá trị là số lần phần tử đó xuất hiện trong danh sách. Chúng ta trả về phần tử xuất hiện nhiều nhất 1 lần ở dòng 23. Chúng ta cần duy trì thứ tự của các giá trị cập nhật cho mỗi từ khoá trong 1 giá trị danh sách cố định (tuple.)

Độ phức tạp về thời gian

Vì danh sách chỉ được duyệt qua 2 lần, và từ điển counts được khởi tạo với độ phức tạp thời gian biến đổi tuyến tính, độ phức tạp về thời gian của giải thuật này là tuyến tính, nghĩa là O(n).

46) Tìm giá trị ở giữa của một danh sách liên kết (linked list)

Để xem lời giải bằng mã chương trình, hãy đến original post.

Ở đây bạn có thể dùng 2 con trỏ làm việc đồng thời. Hãy nghĩ về chúng theo cách này:

• Con trỏ nhanh di chuyển 2 bước 1 lần cho đến cuối danh sách.
• Con trỏ chậm di chuyển 1 bước 1 lần.
• Khi con trỏ nhanh đến cuối danh sách, con trỏ chậm sẽ ở ngay giữa danh sách.

Dùng thuật toán này, bạn có thể làm cho quá trình nhanh hơn vì việc tính toán độ dài và việc duyệt đến điểm giữa cùng diễn ra đồng thời.

Độ phức tạp về thời gian

Bạn duyệt qua danh sách liên kết gấp đôi tốc độ, vì thế chắc chắn là nó nhanh hơn. Tuy nhiên, độ phức tạp của chỗ nghẽn cổ chai vẫn là O(n).

47) Hãy đảo ngược k phần tử đầu tiên trong một hàng đợi.

Để xem lời giải bằng mã chương trình, hãy đến original post

Giải thích

Kiểm tra để phát hiện dữ liệu đầu vào không hợp lệ, chẳng hạn như hàng đợi rỗng, và nếu k âm trên Dòng 2. Nếu dữ liệu đầu vào hợp lệ, bắt đầu bằng việc tạo ra một Stack. Các hàm stack là:

• Hàm dựng (Constructor): myStack()
• Thêm phần tử (Push Elements): push(int) để thêm phần tử vào stack.
• Lấy phần tử ra (Pop elements): pop() xoá phần tử khỏi stack.
• Kiểm tra rỗng (Check if empty): isEmpty() trả về True nếu stack rỗng, và False trong trường hợp ngược lại.
• Trả về sau (Return back): back() trả về phần tử được thêm vào cuối stack mà không loại bỏ nó ra khỏi stack.
• Trả về trước (Return front): front() trả về phần tử ở đầu stack mà không loại bỏ nó ra khỏi stack.

Hàm reverseK(queue, k) của chúng ta nhận một hàng đợi làm tham số đầu vào. k đại diện cho số phần tử muốn đảo ngược. Các hàm hàng đợi sẵn có là:

• Hàm dựng (Constructor): myQueue(size) size should be an integer specifying the size of the queue.

• Hàm xếp hàng (Enqueue): enqueue(int)

• Hàm loại bỏ ra khỏi hàng (Dequeue): dequeue()

• Kiểm tra rỗng isEmpty()

• Kiểm kích thước: size()

Bây giờ, hay chuyển qua logic thực sự, lấy ra khỏi hàng k phần tử đầu tiên từ phía trước hàng đợi và đẩy chúng vào stack chúng ta đã tạo trước đó dùng hàm stack.push(queue.dequeue()) ở dòng 8.

Khi tất cả k phần tử đã được đẩy vào stack, bắt đầu lấy chúng ra và xếp hàng chúng vào cuối hàng đợi một cách tuần tự. Chúng ta sẽ làm việc này bằng hàm queue.enqueue(stack.pop()) ở dòng 12. Ở cuối bước này, chúng ta chỉ còn một stack rỗng và k phần tử đảo ngược sẽ được thêm vào phía sau của hàng đợi.

Bây giờ chúng ta phải dịch chuyển những phần tử đảo ngược này lên phía đầu của hàng đợi. Để làm việc này, chúng ta dùng hàm queue.enqueue(queue.dequeue()) ở đòng 16. Mỗi phần tử trước hết được lấy ra khỏi hàng đợi ở phía sau.

48) Hãy tìm chiều cao của một Cây tìm nhị phân (Binary Search Tree - BST)

Ở đây bạn có thể dùng đệ quy để tìm chiều cao của cây con bên phải và bên trái.

Để xem đoạn mã chương trình thực thi giải thuật này, bấm vào đây: original post.

Giải thích

Ở đây, chúng ta trả về -1 nếu nốt là None. Kế đến, chúng ta gọi hàm findHeight() trên cây con bên trái và bên phải, và sau đó trả về giá trị lớn hơn + 1. Chúng ta sẽ không trả về 0 nếu nốt là None vì nốt lá sẽ có độ cao là 0.

Độ phức tạp về thời gian

Độ phức tạp về thời gian của đoạn mã trên là O(n)O(n) vì tất cả các nốt của toàn bộ cây phải được duyệt qua.

49) Hãy chuyển đổi chồng lớn nhất (max heap) thành chồng nhỏ nhất (min heap)

Ở đây chúng ta sẽ tối thiểu hoá chồng (Min Heapify) tất cả các nốt cha.

def minHeapify(heap, index):
    left = index * 2 + 1
    right = (index * 2) + 2
    smallest = index
    # check if left child exists and is less than smallest
    if len(heap) > left and heap[smallest] > heap[left]:
        smallest = left
    # check if right child exists and is less than smallest
    if len(heap) > right and heap[smallest] > heap[right]:
        smallest = right
    # check if current index is not the smallest
    if smallest != index:
        # swap current index value with smallest
        tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        # minHeapify the new node
        minHeapify(heap, smallest)
    return heap


def convertMax(maxHeap):
    # iterate from middle to first element
    # middle to first indices contain all parent nodes
    for i in range((len(maxHeap))//2, -1, -1):
        # call minHeapify on all parent nodes
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap


maxHeap = [9, 4, 7, 1, -2, 6, 5]
print(convertMax(maxHeap))

Output: [-2, 1, 5, 9, 4, 6, 7]

Giải thích

Hãy nhớ rằng chúng ta có thể xem xét tham số được truyền maxHeap là một danh sách các số phần tử và xếp thứ tự chúng lại sao cho chúng đại diện một chồng nhỏ nhất một cách chính xác. Chúng ta là chính xác việc đó trong giải thuật này. Hàm convertMax() phục hồi các thuộc tính chồng trên tất cả các nốt từ nốt cha thấp nhất bằng cách gọi hàm minHeapify() trên mỗi phần tử.

Độ phức tạp về thời gian
Hàm minHeapify() được gọi cho nửa số nốt trong chồng. Hàm này mất O(log(n)) thời gian, và nó được gọi trên n2\frac{n}{2}O(nlog(n)) thời gian.

50) Hãy phát hiện vòng lặp trong một danh sách liên kết

Để xem lời giải cho vấn đề này trong thực tế, hãy xem bài viết gốc ở đây: original post.

Giải thích

Duyệt qua toàn bộ danh sách liên kết, và thêm mỗi nốt đã đi qua vào bộ visited_nodes. Ở mỗi nốt, chúng ta kiểm tra xem nốt đã được đi qua chưa. Theo nguyên tắc, nếu nốt đã được đi qua, một chu kỳ tồn tại.

Độ phức tạp về thời gian

Chúng ta duyệt qua danh sách 1 lần. Trung bình, truy tìm trong một bộ mất O(1) thời gian. Do đó, trung bình thời gian thực thi của thuật toán này là O(n). Tuy nhiên, trong trường hợp xấu nhất, việc tìm kiếm có thể tăng lên tới O(n), làm cho thuật toán mất O(n2)O(n^{2})

Cấu trúc dữ liệu và câu hỏi thuật toán là một phần quan trọng của bất kỳ cuộc phỏng vấn công việc lập trình nào, có thể là một cuộc phỏng vấn Java, một cuộc phỏng vấn C ++ hoặc bất kỳ ngôn ngữ lập trình nào khác. Vì các cấu trúc dữ liệu là các khái niệm lập trình cốt lõi, nên bắt buộc đối với tất cả các lập trình viên, phải biết các cấu trúc dữ liệu cơ bản như ngăn xếp, danh sách được liên kết, hàng đợi, mảng, cây và đồ thị. Mặc dù cây và đồ thị ở phía khó khăn hơn, tôi vẫn thấy các lập trình viên quen thuộc sẽ làm quen với tất cả những điều này. Bất kỳ danh sách các câu hỏi phỏng vấn công việc lập trình là không đầy đủ mà không có câu hỏi từ các cấu trúc dữ liệu và thuật toán. Tương tự, trong khi thực hiện các câu hỏi từ cấu trúc dữ liệu, bạn cũng có thể nhận được một số bài tập lập trình, ví dụ: Trao đổi số mà không có biến nhiệt độ. Danh sách và mảng được liên kết là các chủ đề yêu thích trong bất kỳ cuộc phỏng vấn cấu trúc dữ liệu nào, các câu hỏi như đảo ngược danh sách được liên kết, vượt qua danh sách được liên kết hoặc xóa các nút khỏi danh sách được liên kết, liên quan đến thuật toán và cấu trúc dữ liệu khá phổ biến. & NBSP;t of programming job interview questions is incomplete without questions from data structures and algorithms. Similarly, while going on questions from data structure you may get some programming exercise as well e.g. swapping numbers without temp variable.

The linked list and array are favorite topics in any data structure interview, questions like reversing a linked list, traversing a linked list, or deleting nodes from the linked list, which involves algorithm and data structures that are quite common. 

Tương tự, việc tìm kiếm các bản sao trong một mảng, tìm các số bị thiếu, phân loại mảng rất phổ biến. Bạn cũng có thể mong đợi các câu hỏi từ ngăn xếp, hàng đợi, mảng, danh sách liên kết, cây, đồ thị và bảng băm là phổ biến nhất trong bất kỳ cuộc phỏng vấn cấu trúc dữ liệu nào.

Trong hướng dẫn này, & nbsp; chúng ta sẽ thấy một vài câu hỏi về cấu trúc dữ liệu câu trả lời từ các chủ đề này. Hãy cho chúng tôi biết nếu bạn có bất kỳ câu hỏi thú vị nào từ các cấu trúc dữ liệu và thuật toán mà bạn phải đối mặt trong bất kỳ cuộc phỏng vấn Java nào. we will see a couple of data structure questions answers from these topics. Let us know if you have any interesting questions from data structures and algorithms, which you faced during any Java interviews.

15 Cấu trúc dữ liệu và câu hỏi phỏng vấn thuật toán cho các lập trình viên Java

Đây là danh sách kết hợp các câu hỏi từ các cấu trúc dữ liệu khác nhau, ví dụ: Mảng, danh sách liên kết, ngăn xếp, hoặc hàng đợi. Nó cũng bao gồm một số câu hỏi mã hóa, gel có cấu trúc dữ liệu. & NBSP;

Câu 1: Làm thế nào để tìm phần tử giữa của danh sách được liên kết trong một lần vượt qua?

Một trong những câu hỏi phổ biến nhất từ ​​các cấu trúc dữ liệu và thuật toán hầu hết được hỏi trong một cuộc phỏng vấn qua điện thoại. Vì nhiều lập trình viên biết rằng, để tìm độ dài của một danh sách được liên kết, chúng tôi cần phải đi qua danh sách được liên kết cho đến khi chúng tôi tìm thấy nút cuối cùng, chỉ vào NULL, và sau đó trong lần thứ hai, chúng tôi có thể tìm thấy một phần tử giữa Bằng cách chỉ đi qua một nửa chiều dài. & nbsp; họ bị nhầm lẫn khi người phỏng vấn yêu cầu anh ta thực hiện cùng một công việc trong một lần vượt qua, mà không đi qua danh sách được liên kết một lần nữa. Bạn cần duy trì hai con trỏ, một lần tăng ở mỗi nút trong khi các nút khác sau hai nút tại một thời điểm, có sự sắp xếp này, khi con trỏ thứ nhất đạt đến kết thúc, con trỏ thứ hai sẽ trỏ đến phần tử giữa của danh sách được liên kết. Xem thủ thuật này để tìm phần tử giữa của danh sách được liên kết trong một lần vượt qua để biết thêm chi tiết.

They get confused when the interviewer asks him to do the same job in one pass i.e. without traversing the linked list again. 

In order to find the middle element of the linked list in one pass, you need to maintain two-pointer, one increment at each node while the other increments after two nodes at a time, having this arrangement, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list. See this trick to find the middle element of the linked list in a single pass for more details.

Câu 2: Làm thế nào để tìm nếu một danh sách được liên kết có một vòng lặp?

Câu hỏi này có một chút tương đồng với thuật toán trước đó và câu hỏi phỏng vấn cấu trúc dữ liệu. Tôi có nghĩa là chúng ta có thể sử dụng hai cách tiếp cận con trỏ để giải quyết vấn đề này. được trỏ đến cùng một nút. & nbsp; điều này sẽ chỉ xảy ra nếu một danh sách được liên kết có một vòng lặp hoặc chu kỳ. Bạn có thể kiểm tra danh sách liên kết bài viết của tôi với các chu kỳ để biết thêm chi tiết. & NBSP;

If we maintain two pointers, and we increment one pointer after processing two nodes and the other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node. 

This will only happen if a linked list has a loop or cycle. You can check my article linked list with cycles for more details. 

Câu 3: Làm thế nào để tìm phần tử thứ ba từ cuối trong một danh sách được liên kết trong một lần vượt qua?

Đây là một câu hỏi phỏng vấn danh sách liên kết thường xuyên khác. Câu hỏi này hoàn toàn giống với việc tìm phần tử giữa của danh sách được liên kết trong một lần vượt qua. & NBSP; Con trỏ thứ nhất đạt đến phần cuối của danh sách được liên kết, con trỏ thứ hai sẽ chỉ vào phần tử thứ 3 từ cuối cùng trong danh sách được liên kết. Đôi khi, người phỏng vấn cũng có thể khái quát vấn đề này và yêu cầu anh ta tìm phần tử KTH từ đuôi, kết thúc hoặc Cuối cùng. Chỉ cần sử dụng cùng một logic, thay thế 3 bằng k và bạn có thể giải quyết vấn đề. Pluralsight.to finding the middle element of a linked list in a single pass. 

If we apply the same trick of maintaining two-pointers and increment another pointer, when first has moved up to the 3rd element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the 3rd element from last in a linked list.

Sometimes, interviewers can also generalize this problem and ask him to find the kth element from the tail, end, or last. Just use the same logic, replace 3 with k and you can solve the problem.  

If you want to learn more about the linked list, you can also check out Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight.

Câu 4: Trong một mảng số nguyên, có 1 đến 100 số, trong số một là trùng lặp, làm thế nào để tìm?

Đây là một câu hỏi cấu trúc dữ liệu khá đơn giản, đặc biệt là cho loại này. Trong trường hợp này, bạn chỉ cần thêm tất cả các số được lưu trữ trong một mảng và tổng số tiền phải bằng n (n+1)/2. Bây giờ chỉ cần trừ tổng số thực tế vào tổng dự kiến ​​và đó là số trùng lặp của bạn. 2) Điều này không tốt. & NBSP; Nhân tiện, thủ thuật này sẽ không hoạt động nếu một mảng có nhiều bản sao, hoặc nó không được đánh số tạo thành một tiến trình số học. Dưới đây là một ví dụ về một cách để tìm một số trùng lặp trong mảng.n(n+1)/2. Now just subtract the actual sum to the expected sum, and that is your duplicate number. 

Of course, there is a brute force way of checking each number against all other numbers, but that will result in the performance of O(n^2) which is not good. 

By the way, this trick will not work if an array has multiple duplicates, or it's not numbered forming an arithmetic progression. Here is an example of one way to find a duplicate number in the array.

Câu 5: Làm thế nào để đảo ngược chuỗi trong Java?

Đây là một trong những câu hỏi yêu thích của tôi. Vì chuỗi là một trong những loại lập trình quan trọng nhất, bạn mong đợi rất nhiều câu hỏi liên quan đến chuỗi trong bất kỳ cuộc phỏng vấn cấu trúc dữ liệu nào. & NBSP; có nhiều cách để đảo ngược chuỗi trong Java hoặc bất kỳ ngôn ngữ lập trình nào khác và người phỏng vấn sẽ buộc Bạn để giải quyết vấn đề này bằng cách sử dụng mà không cần API, mà không cần sử dụng phương thức & nbsp; Reverse () của StringBuffer. & NBSP; Trong lần theo dõi, anh ta cũng có thể yêu cầu đảo ngược chuỗi bằng cách sử dụng đệ quy. Xem 3 cách để đảo ngược chuỗi trong Javato Học cách đảo ngược chuỗi bằng cả vòng lặp và đệ quy trong Java.String is one of the most important types of programming, you expect a lot of question-related to String in any data structure interview. 

There are many ways to reverse String in Java or any other programming language, and the interviewer will force you to solve this problem by using without API i.e. without using the reverse() method of StringBuffer. 

In the follow-up, he may ask to reverse String using recursion as well. See 3 ways to reverse String in Javato learn to reverse String using both loops and recursion in Java.

Câu 6: Viết chương trình Java để sắp xếp một mảng bằng thuật toán Sắp xếp bong bóng?

Tôi đã luôn gửi một vài câu hỏi từ việc tìm kiếm và sắp xếp trong các cuộc phỏng vấn cấu trúc dữ liệu. Bubble Sort là một trong những thuật toán sắp xếp đơn giản nhất nhưng nếu bạn yêu cầu bất cứ ai thực hiện nó ngay tại chỗ, nó sẽ cho bạn cơ hội để đánh giá các kỹ năng lập trình của một ứng cử viên. Xem cách sắp xếp một mảng bằng cách sử dụng Sắp xếp bong bóng trong Java cho A & NBSP; Giải pháp hoàn chỉnh cho câu hỏi phỏng vấn cấu trúc dữ liệu này.e How to sort an array using Bubble Sort in Java for a complete solution to this data structure interview question.

Câu 7: Sự khác biệt giữa cấu trúc dữ liệu ngăn xếp và hàng đợi là gì?

Một trong những câu hỏi về cấu trúc dữ liệu cổ điển. Tôi đoán mọi người đều biết, không? Dù sao, sự khác biệt chính là Stack là LIFO (lần cuối cùng trong cấu trúc dữ liệu đầu tiên) trong khi hàng đợi là cấu trúc dữ liệu FIFO (đầu tiên trong lần đầu tiên). Bạn có thể xem thêm bài viết của tôi Stack vs xếp hàng trong Java để biết thêm chi tiết. & NBSP;

Câu 8: Làm thế nào để bạn tìm thấy các bản sao trong một mảng nếu có nhiều hơn một bản sao? (dung dịch)

Đôi khi điều này được hỏi một câu hỏi tiếp theo về các câu hỏi phỏng vấn cấu trúc dữ liệu trước đó, liên quan đến việc tìm kiếm các bản sao trong mảng. Một cách để giải quyết vấn đề này là sử dụng cấu trúc dữ liệu Hashtable hoặc Hashmap. & NBSP; bạn có thể đi qua mảng và lưu trữ từng số dưới dạng khóa và số lần xuất hiện dưới dạng giá trị. Vào cuối của Traversal, bạn có thể tìm thấy tất cả các số trùng lặp, trong đó xảy ra nhiều hơn một. & NBSP; trong Java nếu một số đã tồn tại trong HashMap sau đó gọi GET (INDEX) sẽ trả về một số nếu không nó sẽ trả về NULL. Thuộc tính này có thể được sử dụng để chèn hoặc cập nhật số trong Hashmap.a Hashtable or HashMap data structure. 

You can traverse through the array, and store each number as a key and the number of occurrences as a value. At the end of traversal, you can find all duplicate numbers, for which occurrence is more than one. 

In Java if a number already exists in HashMap then calling get(index) will return a number otherwise it returns null. this property can be used to insert or update numbers in HashMap.

Câu 9: Sự khác biệt giữa danh sách được liên kết đơn và cấu trúc dữ liệu danh sách được liên kết gấp đôi là gì?

Đây là một câu hỏi phỏng vấn cổ điển khác về cấu trúc dữ liệu, chủ yếu được hỏi về các vòng điện thoại. Sự khác biệt chính giữa danh sách được liên kết đơn và danh sách được liên kết gấp đôi là khả năng đi qua. không quay trở lại trong một danh sách được liên kết đơn lẻ. & nbsp; Mặt khác, danh sách được liên kết gấp đôi duy trì hai con trỏ, về phía nút tiếp theo và trước đó, cho phép bạn điều hướng theo cả hai hướng trong bất kỳ danh sách được liên kết nào. & NBSP; nếu bạn đang chuẩn bị Đối với các cuộc phỏng vấn thì tôi cũng khuyên bạn nên tìm hiểu một số mẫu mã hóa thiết yếu như hai điểm, con trỏ nhanh và chậm, cửa sổ trượt và thời gian hợp nhất có thể giúp bạn giải quyết nhiều vấn đề mã hóa thường gặp. & NBSP; ; Grokking Cuộc phỏng vấn mã hóa: Các mẫu cho câu hỏi mã hóa khóa học về giáo dục. Đó là một khóa học tương tác nơi bạn có thể thử mẫu này trong chính trình duyệt. & NBSP;

In a singly linked list, a node only points towards the next node, and there is no pointer to the previous node, which means you can not traverse back on a singly linked list. 

On the other hand, the doubly linked list maintains two pointers, towards the next and previous node, which allows you to navigate in both directions in any linked list. 

If you are preparing for interviews then I also suggest you learn some essential coding patterns like two points, fast and slow pointers, sliding window, and merge interval which can help you to solve many frequently asked coding problems. 

If you need a course, I highly recommend Grokking the Coding Interview: Patterns for Coding Questions course on Educative. It's an interactive course where you can try out this pattern in the browser itself. 

Câu 10: Viết chương trình Java để in loạt Fibonacci?

Đây không phải là một câu hỏi về cấu trúc dữ liệu, mà là một chương trình, nhiều lần xuất hiện trong cuộc phỏng vấn cấu trúc dữ liệu. Sê -ri Fibonacci là một chuỗi toán học, trong đó mỗi số là tổng của hai số trước, ví dụ: 1,1, 2, 3, 5, 8, 13, 21. & nbsp; Một người phỏng vấn thường quan tâm đến hai điều, một hàm trả về số thứ n trong loạt Fibonacci và giải quyết vấn đề này bằng cách sử dụng đệ quy trong Java. & NBSP; Đó là một câu hỏi dễ dàng, phần đệ quy thường nhầm lẫn người mới bắt đầu. Xem liên kết này để tìm số Fibonacci thứ n trong Java.

An interviewer is often interested in two things, a function that returns an nth number in the Fibonacci series and solving this problem using recursion in Java. 

Though it's an easy question, the recursion part often confuses beginners. See this link to find the nth Fibonacci number in Java.

Câu 11: Viết chương trình Java để kiểm tra xem một số có phải là palindrom hay không? (dung dịch)

Điều này tương tự như câu hỏi trước đó, không liên quan trực tiếp đến cấu trúc dữ liệu, nhưng khá phổ biến cùng với các câu hỏi khác. Một số được gọi là palindrom nếu mặt trái của số bằng với chính số. & Nbsp; một người phỏng vấn yêu cầu giải quyết vấn đề này mà không cần trợ giúp từ API Java hoặc bất kỳ thư viện nguồn mở nào. Dù sao, đó là một câu hỏi đơn giản, bạn có thể sử dụng toán tử phân chia (/) và toán tử còn lại (%) để giải quyết câu hỏi này. & NBSP; Chỉ cần nhớ, toán tử phân chia có thể được sử dụng để loại bỏ chữ số cuối cùng, ví dụ: 1234/10 sẽ cung cấp cho bạn 123 và toán tử mô đun có thể cung cấp cho bạn chữ số cuối cùng, ví dụ: 1234%10 sẽ trở lại 4. Nhân tiện, đây là chương trình Java để kiểm tra xem số này có phải là palindrom hay không.

An interviewer asks to solve this problem without taking help from Java API or any open source library. Anyway, it’s a simple question, you can use the division operator (/) and remainder operator (%) to solve this question. 

Just remember, the division operator can be used to get rid of the last digit e.g. 1234/10 will give you 123, and the modulus operator can give you the last digit e.g. 1234%10 will return 4. By the way, here is a Java program to check if the number is palindrome or not.

Câu 12: Cây tìm kiếm nhị phân là gì? (dung dịch)

Đây là một câu hỏi cấu trúc dữ liệu từ các cấu trúc dữ liệu cây. Cây tìm kiếm nhị phân có một số thuộc tính đặc biệt như các nút bên trái chứa các mục có giá trị nhỏ hơn rễ, cây con bên phải chứa các phím có giá trị nút cao hơn rễ và không nên có bất kỳ bản sao nào trong cây. & NBSP; Ngoài định nghĩa, một cuộc phỏng vấn Có thể yêu cầu bạn thực hiện một cây tìm kiếm nhị phân trong Java và các câu hỏi trên cây, ví dụ: Theo thứ tự, đặt hàng trước và truyền tải bưu điện là các câu hỏi cấu trúc dữ liệu khá phổ biến.

Apart from the definition, an interview can ask you to implement a binary search tree in Java, and questions on tree traversal e.g. in order, preorder, and postorder traversals are quite popular data structure questions.

Câu 13: Làm thế nào để đảo ngược một danh sách được liên kết bằng cách sử dụng đệ quy và lặp lại? (dung dịch)

Đây là một câu hỏi hay khác về cấu trúc dữ liệu. Có nhiều thuật toán để đảo ngược danh sách được liên kết và bạn có thể tìm kiếm chúng bằng Google. Tôi đang nghĩ đến việc viết một bài đăng trên blog khác để giải thích sự đảo ngược danh sách được liên kết và sẽ chia sẻ nó với bạn sau. Một trong những độc giả của tôi đã đề cập, tôi đã viết về nó và liên kết nó vào liên kết giải pháp, bạn có thể kiểm tra giải pháp của tôi nhưng Tôi thực sự khuyên bạn nên tự mình thử nó trước khi xem xét giải pháp. & NBSP;

As one of my readers mentioned, I have already written about it and linked it into the solution link, you can check out my solution but I strongly suggest you try it yourself before looking at the solution. 

Câu 14: Viết chương trình Java để thực hiện Stack trong Java? (dung dịch)

Bạn có thể thực hiện ngăn xếp bằng cách sử dụng một mảng hoặc danh sách được liên kết. Câu hỏi này mong đợi bạn thực hiện một phương thức tiêu chuẩn được cung cấp bởi cấu trúc dữ liệu ngăn xếp, ví dụ: đẩy () và pop (). & nbsp; Cả Push () và pop () sẽ xảy ra ở đầu ngăn xếp, mà bạn cần theo dõi. Nó cũng tốt nếu bạn có thể triển khai các phương thức tiện ích như chứa (), isempty (), v.v. Bạn cũng có thể kiểm tra & NBSP; Sách Java hiệu quả, trong đó Josh Bloch đã giải thích cách thực hiện không chính xác của ngăn xếp có thể gây rò rỉ bộ nhớ trong Java.push() and pop().  Both push() and pop() should be happening at top of the stack, which you need to keep track of. It’s also good if you can implement utility methods like contains(), isEmpty() etc. 

By the way, JDK has a java.util.Stack class and you can check its code to get an idea. You can also check the Effective Java book, where Josh Bloch has explains how an incorrect implementation of the stack can cause a memory leak in Java.

Tôi cũng đề nghị xem xét cấu trúc dữ liệu và câu hỏi thuật toán trên & nbsp; bẻ khóa sách phỏng vấn mã hóa, vì cuốn sách này chứa một số câu hỏi hay với những giải thích thích hợp. Điều đó chắc chắn sẽ giúp bạn làm tốt hơn trong các cuộc phỏng vấn việc làm. & NBSP;Cracking the Coding Interview book, as this book contains some good questions with proper explanations. That will certainly help you to do better in programming job interviews. 

Một gợi ý nữa tôi phải đưa ra là bất cứ khi nào bạn có được một thời gian, chỉ cần đọc & nbsp; Giới thiệu về Thuật toán của Thomas Cormen, nếu bạn chưa đọc nó. Cuốn sách này là Kinh thánh của các thuật toán và IMHO Mỗi lập trình viên nên đọc cuốn sách này. & NBSP;some time, just read the Introduction to Algorithm by Thomas Cormen, if you have not read it already. This book is the bible of algorithms and IMHO every programmer should read this book. 

Đó là tất cả trong danh sách các câu hỏi và câu trả lời phỏng vấn cấu trúc dữ liệu này. Đây là một chủ đề, luôn được hỏi trong bất kỳ cuộc phỏng vấn lập trình nào, không quan trọng nếu bạn là nhà phát triển C, C ++ hay Java, kiến ​​thức cơ bản về cấu trúc dữ liệu như một mảng, danh sách được liên kết, xếp hàng, hàng đợi, cây là phải Xóa bất kỳ cuộc phỏng vấn lập trình.list of data structure interview questions and answers. This is one topic, which is always asked in any programming interview, doesn't matter if you are C, C++, or Java developer, basic knowledge of data structure like an array, linked list, stack, queue, the tree is must to clear any programming interview.

Cảm ơn rất nhiều vì đã đọc bài viết này cho đến nay. Nếu bạn thích cấu trúc dữ liệu này và thuật toán & nbsp; Câu hỏi phỏng vấn và câu trả lời sau đó xin vui lòng chia sẻ chúng với bạn bè và đồng nghiệp của bạn. Nếu bạn có bất kỳ câu hỏi hoặc phản hồi thì xin vui lòng bỏ một ghi chú.

P. S. - Nếu bạn nghĩ rằng cấu trúc dữ liệu và kỹ năng thuật toán của bạn không ngang bằng và bạn muốn dành thời gian để mài giũa kỹ năng của mình thì bạn có thể bắt đầu với các khóa học thuật toán miễn phí này.- If you think that your data structure and algorithm skill are not par and you want to spend some time sharpening your skill then you can start with these free Algorithm courses.

Các thuật toán quan trọng nhất cho các cuộc phỏng vấn là gì?

Câu hỏi phỏng vấn thuật toán nào tốt nhất là gì?

Làm thế nào để bạn giải quyết câu hỏi phỏng vấn thuật toán?

Câu hỏi DSA là gì?