Câu hỏi phỏng vấn Python Developer

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.

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:

• Dựng sẵn (Built in)
• 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.

Để đả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:

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.)

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.

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à:

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

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

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 15-26: bfs theo thuật toán mô tả ở trên:

• Nó kiểm tra và thêm nốt xuất phát vào danh sách visited và danh sách queue.
• 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.
• Việc này tiếp diễn cho đến khi hàng đợi trống rỗng.

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.

Độ 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.

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

Đâ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:

• 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.
• 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.
• 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.
• Cứ thế, các giá trị được gán qua k đều theo thứ tự.
• 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.

Thuật toán cơ bản

• 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 đó.
• 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.
• 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

# 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 đề.

• 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ề.
• 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.
• 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.
• 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ỗ.

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}a0​
chúng ta sẽ tìm phần tử bằng phương pháp nhị phân sao cho

a0a_{0}a0​
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.

Ở đâ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:

[9,2,3,2,6,6]

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).

Ở đâ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).

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.

Ở đâ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.

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.

Ở đâ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}2n​ nốt, nên giải thuật này mất O(nlog(n)) thời gian.

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})O(n2) thời gian.

• Kiểu dữ liệu mutable chuẩn là những giá trị có dữ liệu có thể thay đổi được gồm có: List, Set, Dictionary
• Kiểu dữ liệu immutable chuẩn những giá trị có dữ liệu không thể thay đổi được  gồm có: Chuỗi, Tuple, Số