Câu hỏi phỏng vấn lập trình Python của các các công ty FAANG

Đối với bất kỳ cuộc phỏng vấn nào liên quan đến dữ liệu, lập trình bằng Python là một kỹ năng cần thiết và là một lĩnh vực cần phải chuẩn bị. Có bốn loại câu hỏi lập trình, bao gồm Cấu trúc dữ liệu và Giải thuật, Thuật toán Máy học, Toán học và Thống kê, và Thao tác Dữ liệu.

Bài viết này bao gồm 11 câu hỏi phỏng vấn và chia làm 2 phần: Cấu Trúc dữ liệu và Giải Thuật (Data Structure and Algorithm), Thao tác dữ liệu và trích xuất chuỗi (Data Manipulation and String Extraction). Các câu hỏi phỏng vấn này đều có code bằng ngôn ngữ lập trình Python. Các câu hỏi này được đặt ra bởi các công ty công nghệ lớn, đặc biệt là FAANG (Facebook, Amazon, Apple, Netflix và Alphabet (trước đây là Google)).

Các câu hỏi phỏng vấn về toán học và thống kê với ngôn ngữ lập trình Python

Câu 1: Ai thắng trước? (Microsoft)

Amy và Brad thay phiên nhau thả một con xúc xắc. Ai được số “6” đầu tiên sẽ thắng. Amy là người thả xúc xắc trước. Xác suất Amy thắng là bao nhiêu?

Về câu hỏi

Đây là một câu hỏi mô phỏng cốt lõi, và không có cách nào tốt hơn là mô phỏng quá trình một khoảng thời gian đáng kể và kiểm tra xác suất Amy thắng.

Amy thả xúc xắc đầu tiên. Nếu kết quả là 6, thì trò chơi kết thúc và Amy thắng. Nếu không, đến lượt Brad sẽ tung và thắng trò chơi nếu đó là 6. Nếu không, lượt quay lại với Amy. Lặp lại quá trình cho đến khi ai đó kết thúc trò chơi với số 6.

Ở đây, mấu chốt là phải hiểu được dòng logic: ai thắng và trong những điều kiện nào. Brad có phải thả xúc xắc nếu Amy đạt điểm 6 không? Không.

Giải pháp

Kiểm tra dòng 11: A_6 là phân phối dữ liệu cho Amy và nếu cô ấy có 6, số của cô ấy là +1. Nếu không, Brad có thể tung xúc xắc.

Ở phần cuối (dòng 25), kết quả cuối cùng sẽ là số lần Amy thắng chia cho tổng số lần Amy và Brad thắng. Một sai lầm phổ biến là chia A_count cho tổng số mô phỏng. Điều này không chính xác vì có những lần lặp lại khi cả Amy và Brad không quay được số 6.

Hãy thử nghiệm thuật toán trên.

0.531271015467384

Hóa ra, Amy có ưu thế hơn trong việc giành chiến thắng trong trò chơi này khi cô ấy bắt đầu lăn thả súc sắc trước Brad. Amy có 53% xác suất chiến thắng trong 10.000 lần mô phỏng.

Câu hỏi 2: Số tối đa 69 (hỏi bởi các công ty lớn)

– Cho số nguyên dương chỉ gồm các chữ số 6 và 9.
– Trả lại số tối đa bạn có thể nhận được bằng cách thay đổi nhiều nhất một chữ số (6 thành 9 và 9 thành 6).

Xem câu hỏi phỏng vấn lập trình Python này trên Leetcode

Về câu hỏi

Cho một số nguyên dương, chỉ có một cách để làm cho giá trị lớn hơn, đó là biến ‘6’ thành ‘9’, chứ không phải ngược lại. Ngoài ra, chúng ta phải thay đổi 6 ngoài cùng bên trái; nếu không, nó sẽ không phải là con số tối đa. Ví dụ: chúng ta phải thay đổi ‘6996’ thành ‘9996’, không phải ‘6999.

Một số biến thể của câu hỏi này: bạn thay đổi một lần hoặc thay đổi tất cả ‘6’s.

Giải pháp 1: thay một lần

996666669

Trong dòng 3, chúng ta biến số nguyên thành một chuỗi và thay thế chữ ‘6’ đầu tiên thành ‘9’; biến nó trở lại một số nguyên bằng cách sử dụng int ().

Giải pháp 2: thay thế tất cả

996666669

Đối với trường hợp thứ hai, chúng ta không phải chỉ định k vì phương thức Replace () thay đổi tất cả các giá trị phù hợp theo mặc định. Ta chỉ định giá trị k cho mục đích sư phạm. Một biến thể khác của câu hỏi có thể là thay thế hai hoặc ba, ‘6’ đầu tiên để làm cho con số tối đa.

Câu 3: Bình phương hoàn hảo hợp lệ (Facebook)

– Cho một số nguyên dương, hãy viết một hàm trả về giá trị True nếu số là một bình phương hoàn hảo (perfect square) còn lại là False.
– Nâng cao: Không sử dụng bất kỳ chức năng thư viện tích hợp nào như sqrt.

Xem câu hỏi lập trình Python này trên Leetcode

Về câu hỏi

Nó khá đơn giản: kiểm tra xem một số nguyên dương có căn bậc hai hoàn hảo hay không và trả về True nếu có. Quá trình này có thể được thực hiện trong hai bước.

tìm căn bậc hai.

kiểm tra xem nó có phải là một căn bậc hai hoàn hảo hay không.

Phần khó khăn là chúng ta phải sử dụng một thư viện tích hợp sẵn (ví dụ: toán học, Numpy) để tính căn bậc hai, đây là một câu hỏi dễ ở LeetCode. Nếu chúng ta không thể sử dụng các thư viện này, nó sẽ trở nên khó khăn hơn và lặp đi lặp lại, một câu hỏi ở mức độ trung bình tại LeetCode.

Giải pháp 1: Thư viện tích hợp sẵn

Thuật toán dễ dàng vượt qua trường hợp thử nghiệm. Cần chỉ ra rằng chúng ta cần sử dụng phương thức int () để chỉ lấy phần nguyên của căn bậc hai và bỏ đi bất kỳ phần thập phân nào. Đối với số bình phương hoàn hảo, nó sẽ không tạo ra bất kỳ sự khác biệt nào và phương trình là đúng. Đối với các bình phương không hoàn hảo, phương trình sẽ không giữ và trả về False.

Giải pháp 2: Không có thư viện tích hợp sẵn và tìm kiếm nhị phân

Nếu không có thư viện nào được phép, chúng ta áp dụng tìm kiếm nhị phân. LeetCode chứa một lời giải thích chi tiết tại đây (bạn phải có tài khoản premium để xem). Tóm lại, chúng ta tạo hai con trỏ, trái và phải, và so sánh giá trị trung bình của hai số này với số ban đầu: nếu nó nhỏ hơn số đó, chúng ta tăng giá trị; nếu nó lớn hơn, chúng ta giảm nó; hoặc trả về True nếu chúng khớp.

Các điều kiện này được tự động kiểm tra trong vòng lặp while.

Câu hỏi 4: Các số 0 theo dấu giai thừa (Bloomberg)

– Cho một số nguyên n, trả về số lượng các số 0 ở cuối trong n!
– Nâng cao: Bạn có thể viết một giải pháp hoạt động theo độ phức tạp thời gian logarit không?
– Xem câu hỏi phỏng vấn lập trình Python này trên LeetCode

Về câu hỏi

Có hai bước cho câu hỏi này:

tính giai thừa n, n!
tính toán số lượng các số không ở cuối

Đối với bước đầu tiên, chúng ta sử dụng vòng lặp while để lặp đi lặp lại trên n giai thừa và dừng vòng lặp cho đến 1. Đối với bước thứ hai, mọi thứ trở nên phức tạp hơn một chút.

Câu hỏi yêu cầu dấu theo sau, không phải tổng số, số không. Có một sự khác biệt lớn. 8! là 40,320, có 2 số không nhưng chỉ có 1 số 0 ở cuối. Chúng ta phải hết sức cẩn thận với việc tính toán. Ta có hai giải pháp.

Giải pháp 1: Đọc ngược một chuỗi

Phần đầu tiên của việc tính toán sản phẩm là khá rõ ràng. Đối với phần thứ hai, chúng ta sử dụng một phương thức str () để biến đổi tích thành một chuỗi và sau đó đọc ngược lại: nếu số là 0, chúng ta thêm 1 vào số đếm; nếu không, chúng ta phá vỡ vòng lặp.

Lệnh break là điều cần thiết ở đây. Như đã thảo luận, hàm trên tính toán tổng số các số không mà không cần lệnh break.

Giải pháp 2: Vòng lặp while

Phần đầu tiên giống với giải pháp 1, và điểm khác biệt duy nhất là chúng ta sử dụng vòng lặp while để tính số ở cuối: để tích chia đều cho 10, chữ số cuối cùng phải bằng 0. Vì vậy, chúng ta sử dụng vòng lặp while để cập nhật liên tục vòng lặp while cho đến khi điều kiện không dừng.

Câu hỏi 5: Perfect Number (Amazon)

– Một số hoàn hảo là một số nguyên dương có giá trị bằng tổng các ước số dương của nó, không kể số chính nó.
– Ước của số nguyên x là số nguyên có thể chia x đều.
– Cho số nguyên n, trả về true nếu n là số hoàn hảo, ngược lại, trả về false.
– Xem câu hỏi phỏng vấn lập trình Python về perfect number trên LeetCode

Về câu hỏi

Với câu hỏi này ta có thể chia thành ba bước thực hiện:

tìm các ước số dương
tính tổng

quyết định: hoàn hảo hay không

Các bước 2 và 3 là hiển nhiên và không có nhiều hơn một one-liners. (Python trên 1 dòng). Tuy nhiên, phần khó là tìm các ước số dương. Để làm như vậy, chúng ta có thể áp dụng phương pháp brutal force và lặp lại trên toàn bộ chuỗi từ 1 đến số nguyên.

Về mặt lý thuyết, nó sẽ hoạt động với một số nguyên nhỏ nhưng vượt quá giới hạn thời gian nếu chúng ta chạy với số lớn. Nó không hiệu quả về mặt thời gian.

Giải pháp 1: brutal force

Phương pháp này sẽ không hoạt động tốt đối với các giá trị lớn. Người phỏng vấn của bạn có thể yêu cầu một giải pháp hiệu quả hơn.

Giải pháp 2: sqrt (n)

Để tìm các ước số của nó, chúng ta không phải kiểm tra các giá trị lên đến số nguyên. Ví dụ: để tìm ước cho 100, chúng ta không phải kiểm tra các số từ 1 đến 100. Thay vào đó, chúng ta chỉ phải kiểm tra cho đến khi căn bậc hai của 100, là 10 và tất cả các giá trị có sẵn khác đã được bao gồm.

Đây là một thuật toán tối ưu giúp chúng ta tiết kiệm rất nhiều thời gian.

Các câu hỏi phỏng vấn lập trình Python về Thao tác dữ liệu và trích xuất chuỗi

Câu hỏi 6: Xác minh địa chỉ IP (Amazon)

– Cung cấp một địa chỉ IP (IPv4) hợp lệ, hãy trả về phiên bản đã được xác minh của địa chỉ IP đó.
– Địa chỉ IP bị xóa dấu hiệu thay thế mỗi dấu chấm “.” với “[.]”.
– Xem câu hỏi về xác minh địa chỉ IP trên LeetCode

Về câu hỏi

Đây là một câu hỏi khởi động. Nó yêu cầu chúng ta thay thế “.” với “[.]” cho một chuỗi. Nếu bạn đã quen với chuỗi trong Python, điều đầu tiên bạn nghĩ đến là xử lý “.” như một dấu phân cách và phân chia chuỗi. Sau đó, nối lại một chuỗi trống và chọn “[.]” Làm dấu phân tách.

Giải pháp đầu tiên là cách tiếp cận từng bước tiêu chuẩn cho những câu hỏi như thế này. Tuy nhiên, nó không phải là một giải pháp tối ưu.

Một giải pháp theo triết lý Python (Pythonic) khác là sử dụng phương thức Replace () để thay đổi trực tiếp “.” với “[.]”, được hiển thị như sau.

Giải pháp

'1[.]1[.]1[.]1'

Trong thực tế thường xuyên của mình, tôi cố gắng viết giải pháp đầu tiên nhiều hơn giải pháp thứ hai vì nó liên quan đến hai phương thức chuỗi phổ biến: tách và nối. Tôi khuyên bạn nên thực hành cả hai giải pháp bất kể hiệu quả hay không hiệu quả của chúng.

Câu hỏi 7: Fizz Buzz (Microsoft, Bloomberg)

– Viết chương trình in số từ 1 đến 50, đối với bội số của 2 in ‘fizz’ thay vì một số, đối với các số bội của 3 in ‘buzz’, đối với các số là bội của cả 2 và 3 ‘fizzbuzz. ‘
– Xem câu hỏi phỏng vấn lập trình Python này trên LeetCode

Về câu hỏi

Câu hỏi này có thể được viết lại thành nhiều câu “if… then…”, nhắc nhở chúng ta về luồng điều khiển. Cụ thể, chúng ta có thể làm điều gì đó như: “nếu điều kiện A đáp ứng, thì kết quả xuất ra A…”

Chỉ có một vấn đề: có những số là bội số của 2 và 3, vì vậy chúng ta phải quyết định ở đầu luồng điều khiển.

# pseudo code for i in range(1,51):
     if condition 1 met: 
          print('fizzbuzz')
     elif condition 2 met: 
          print('fizz')
     elif condition 3 met: 
          print('buzz') 
     else: 
          print(i)

Vì chỉ có ba điều kiện để kiểm tra, chúng ta có thể viết một luồng điều khiển. Tuy nhiên, có những trường hợp khi đó số lượng điều kiện phụ quá nhiều và không thể liệt kê hết chúng (ví dụ: câu hỏi 1 phân phối đồng đều). Người phỏng vấn của bạn có thể yêu cầu bạn sử dụng các phương pháp khác ngoài việc kiểm soát luồng.

Với ý nghĩ đó, chúng ta tạo hai điều kiện và nhân các từ khóa ‘Fizz’ và ‘Buzz’ nếu một hoặc cả hai điều kiện đáp ứng.

# pseudo code
condition_1 = (num%2 ==0) # for fizz
condition_2 = (num%3 ==0) # buzzif condition_1 or condition_2: 
     return (condition_1*'Fizz') + (condition_2*'Buzz')

Giải pháp

Kết quả

1
fizz
buzz
fizz
5
fizzbuzz
7
fizz
buzz
fizz
11
fizzbuzz
13
fizz
buzz
fizz
17
fizzbuzz
.
.
.

Câu hỏi 8: Số Palindrome (Google, Facebook và Microsoft)

– Xác định tất cả các từ là palindromes trong câu sau “To be or not to be a data scientist, this is not a question. Ask your mom, lol” (Để trở thành một nhà khoa học dữ liệu, đây không phải là một câu hỏi. Hãy hỏi mẹ của bạn, lol.)
– Nếu cùng một từ xuất hiện nhiều lần, hãy trả lại từ đó một lần (điều kiện 1)
– Palindromes: các từ trả về cùng một kết quả khi bạn đọc từ đầu đến cuối hoặc từ cuối đến đầu (điều kiện 2)
– Xem câu hỏi phỏng vấn về số Palindrome trên Leetcode

Về câu hỏi

Có nhiều biến thể của Số Palindrome. Phần khó khăn với phiên bản này là mỗi câu chứa một ràng buộc.
Ví dụ: nếu một từ xuất hiện nhiều lần, chỉ cần trả lại từ đó một lần, điều này đề xuất được đặt trong Python làm kiểu dữ liệu đầu ra (điều kiện 1).

Palindrome là một kết quả trả về cùng một kết quả cho dù bạn đọc từ đầu đến cuối hay ngược lại (điều kiện 2). Làm thế nào về kiểu chữ cái? Nó có phân biệt chữ hoa chữ thường hay không? Ở đây, bạn nên hỏi các câu hỏi làm rõ.

Ngoài ra, có một điều kiện ẩn, đó là chúng ta nên loại bỏ các dấu chấm câu khi quyết định một từ có phải là palindrome hay không. Đừng lo lắng nếu bạn không đạt được tất cả các điều kiện này cùng một lúc, vì những người phỏng vấn của bạn sẽ cung cấp cho bạn những gợi ý.

Giải pháp

Kết quả:

{'a', 'lol', 'mom'}

Câu hỏi 9: Ký tự duy nhất đầu tiên trong một chuỗi (FAANG)

– Cho một chuỗi, tìm ký tự không lặp lại đầu tiên trong đó và trả về chỉ số của nó.
– Nếu nó không tồn tại, trả về -1.
– Xem câu hỏi phỏng vấn Python này trên LeetCode

Về câu hỏi

Câu hỏi yêu cầu ký tự không lặp lại đầu tiên trong một chuỗi, ký tự này tương đương với ký tự đầu tiên chỉ xuất hiện một lần. Trong chuỗi, chúng ta có thể tính toán số lần xuất hiện của chuỗi con bằng phương pháp đếm.

Tôi (tác giả bài viết, xem cuối bài) đã khá bối rối trước câu hỏi này và không thể tìm ra giải pháp. Tôi đã thử sử dụng từ điển để lưu trữ cặp khóa-giá trị và trả về chỉ mục của giá trị không lặp lại đầu tiên, giá trị này không hoạt động.

Giải pháp

Kết quả:

0

Ký tự duy nhất đầu tiên là chuỗi là “I” (vị trí 0).

Câu hỏi 10: Địa chỉ email duy nhất (Google, Amazon và Adobe)

– Mọi email bao gồm tên địa phương và tên miền, được phân tách bằng dấu @.
– Ví dụ, trong alice@leetcode.com, alice là tên cục bộ và leetcode.com là tên miền.
– Bên cạnh các chữ cái viết thường, những email này có thể chứa ‘.’s hoặc‘ + ’s.
– Nếu bạn thêm dấu chấm (‘.’) Giữa một số ký tự trong phần tên địa phương của địa chỉ email, thư được gửi đến đó sẽ được chuyển tiếp đến cùng một địa chỉ mà không có dấu chấm trong tên địa phương. Ví dụ: “alice.z@leetcode.com” và “alicez@leetcode.com” chuyển tiếp đến cùng một địa chỉ email. (Lưu ý rằng quy tắc này không áp dụng cho tên miền.)
– Nếu bạn thêm dấu cộng (‘+’) trong tên địa phương, mọi thứ sau dấu cộng đầu tiên sẽ bị bỏ qua. Điều này cho phép một số email nhất định được lọc, ví dụ: m.y+name@email.com sẽ được chuyển tiếp đến my@email.com. (Một lần nữa, quy tắc này không áp dụng cho tên miền.)
– Có thể sử dụng đồng thời cả hai quy tắc này.
– Đưa ra một danh sách các email, chúng ta gửi một email đến mỗi địa chỉ trong danh sách. Có bao nhiêu địa chỉ khác nhau thực sự nhận được thư?
– Xem câu hỏi phỏng vấn Python này trên LeetCode

Về câu hỏi

Sau cái nhìn đầu tiên, đây là một câu hỏi khá dài, dài và khó khăn. Nó chỉ chứa quá nhiều thông tin, và não của bạn sẽ quá tải. Trên thực tế, đây là một câu hỏi đơn giản sau khi chúng ta loại bỏ những thông tin không quan trọng.

Sau khi chia nhỏ, chỉ có ba phần:

1. Một email có hai phần: tên cục bộ và miền, được phân tách bằng “@.”
2. Đối với tên địa phương, “.” không có hiệu lực và chúng ta nên bỏ qua nó; bất cứ điều gì sau “+” không quan trọng và bỏ nó đi.
3. Có bao nhiêu địa chỉ email duy nhất?

Đối với mỗi bước, chúng ta có các chiến lược đối phó tương ứng. Vì đầu vào là một danh sách các chuỗi, chúng ta có thể lặp lại nó cho các phần tử (chuỗi) và chia nó thành hai phần cho mỗi phần tử (Bước 1).

Chúng ta xóa “.” từ tên địa phương và giữ tên miền ban đầu và đọc chuỗi đến vị trí giữ “+” (Bước 2).

Ta sử dụng một tập hợp () để tính số phần tử duy nhất.

Giải pháp

Kết quả:

2

Câu hỏi 11: Thành phố Điểm đến (Yelp)

– Bạn được cung cấp các array paths, trong đó paths[i] = [cityAi, cityBi] có nghĩa là tồn tại một đường dẫn trực tiếp đi từ cityAi đến cityBi.
– Trả lại thành phố đích, tức là thành phố không có bất kỳ con đường nào đi đến thành phố khác.
– Đảm bảo rằng đồ thị của các đường dẫn tạo thành một đường thẳng không có bất kỳ vòng lặp nào, do đó, sẽ có chính xác một thành phố đích.
– Xem câu hỏi phỏng vấn Python này trên LeetCode

Về câu hỏi

Câu hỏi này được đặt ra bởi Yelp, rất hay. Đây là lý do tại sao.

Đối với mỗi đường đi, paths[i] có hai phần [cityAi, cityBi]: cityAi là thành phố khởi hành và thành phốBi là thành phố hạ cánh. Điều quan trọng là phải hiểu định nghĩa của một thành phố đích: đó là thành phố không có thành phố khởi hành. Nói cách khác, thành phố đích chỉ nên xuất hiện trong cột thứ hai của paths[i] chứ không bao giờ xuất hiện ở cột đầu tiên.

Sau khi hiểu rõ điểm này, phần còn lại trở nên hiển nhiên là chúng ta có thể loại bỏ các thành phố đổ bộ khỏi các thành phố khởi hành.

Giải pháp

Kết quả

'Sao Paulo'

Nguồn bài viết

Các câu hỏi về phỏng vấn Python của các công ty FAANG được viết bởi Leihua Ye, Tiến sĩ, Nhà nghiên cứu tại Đại học California, Santa Barbara và Top Writer về Trí tuệ nhân tạo, Giáo dục và Công nghệ. Bạn có thể xem bài gốc tại:

1/ https://towardsdatascience.com/5-python-coding-questions-asked-at-faang-59e6cf5ba2a0

2/ https://towardsdatascience.com/6-python-questions-you-should-practice-before-coding-interviews-f958af55ad13