Ngày nay, các cuộc phỏng vấn của Google đang thịnh hành. Nhưng đôi khi, các cuộc phỏng vấn có thể mang lại điều tốt nhất cho chúng ta. Đặc biệt nếu nó dành cho một vị trí mà chúng ta thực sự muốn
Tôi đã rất vui khi được phỏng vấn tại nhiều công ty hàng đầu khi còn là sinh viên và tìm được việc làm ở Thung lũng Silicon với tư cách là Kỹ sư phần mềm
Mục tiêu của tôi là giúp bạn có được công việc mơ ước mà bạn hằng mong muốn
Chúng ta sẽ xem xét một câu hỏi cổ điển có thể xuất hiện trong Cuộc phỏng vấn Google tiếp theo của bạn
Cảnh báo. nếu bạn là một người viết mã kỳ cựu, có thể bạn đã biết cách giải câu hỏi này
Nếu bạn đang cố gắng để có được một vị trí Thực tập hoặc một công việc Toàn thời gian vào năm tới, thì bài viết này chắc chắn sẽ giúp ích cho bạn. ???
CÂU HỎI. Đưa ra một chuỗi làm đầu vào của bạn, xóa bất kỳ ký tự lặp lại nào và trả về chuỗi mới
Nếu bạn muốn một video để giải thích câu hỏi, tôi đã tạo một video ở đây
Như chúng ta có thể thấy từ ví dụ trên, đầu ra là “abc” vì chúng ta xóa chữ 'a', 'b' và 'c' thứ hai
Trước tiên, hãy thiết lập chức năng của chúng ta trong Python 2. 7
def deleteReoccurringCharacters[string]:Để giải quyết câu hỏi này, chúng tôi sẽ sử dụng một cấu trúc dữ liệu cụ thể được gọi là HashSet
Một bộBạn có thể coi một tập hợp tương tự như một mảng, với hai ngoại lệ chính
- Nó hoàn toàn không có thứ tự
- Nó không thể chứa các bản sao
Vì nó không có thứ tự nên chúng ta cũng cần một chuỗi trống để lưu trữ các ký tự mà chúng ta đã thêm vào tập hợp theo thứ tự. Đây sẽ là chuỗi chúng tôi trả về
Hãy thiết lập cả hai điều đó
def deleteReoccurringCharacters[string]: seenCharacters = set[] outputString = ''Bây giờ chúng tôi đã thiết lập cấu trúc dữ liệu mà chúng tôi cần, hãy nói về thuật toán của chúng tôi
Do cách một tập hợp hoạt động trong bộ nhớ nên nó có độ phức tạp về thời gian tra cứu là 0[1]
Điều này có nghĩa là chúng ta có thể sử dụng nó để kiểm tra xem chúng ta đã đến thăm một nhân vật hay chưa
thuật toán của chúng tôi
Lặp qua tất cả các ký tự trong chuỗi ban đầu và thực hiện như sau
Bước 1. Kiểm tra xem nhân vật đã có trong bộ của chúng tôi chưa
Bước 2. Nếu nó không có trong bộ, hãy thêm nó vào bộ và nối nó vào chuỗi
Hãy xem nó trông như thế nào trong mã ???
for char in string: if char not in seenCharacters: seenCharacters.add[char] outputString += charChúng tôi không phải lo lắng về trường hợp "khác", bởi vì chúng tôi không làm bất cứ điều gì với chính ký tự tái diễn
Bây giờ tất cả những gì còn lại phải làm là trả lại outputString
Đây là mã hoàn thành trông như thế nào
def deleteReoccurringCharacters[string]: seenCharacters = set[] outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add[char] outputString += char return outputStringVà bạn có nó rồi đấy
Bây giờ, nếu đây là một cuộc phỏng vấn, nhà tuyển dụng của bạn sẽ hỏi bạn về sự phức tạp về thời gian và không gian
Hãy làm một phân tích nhỏ
Thời gian phức tạp
Lặp qua toàn bộ chuỗi đầu vào có độ phức tạp về thời gian là O[n], vì có n ký tự trong chính chuỗi đó
Đối với mỗi ký tự đó, chúng tôi phải kiểm tra xem chúng tôi đã nhìn thấy hay chưa… Tuy nhiên, vì HashSet có thời gian tra cứu là O[1], nên độ phức tạp về thời gian của chúng tôi không bị ảnh hưởng
Để lại cho chúng tôi độ phức tạp thời gian cuối cùng của O[n]
Độ phức tạp không gian
Trường hợp xấu nhất, chúng tôi nhận được một chuỗi có tất cả các ký tự duy nhất. Ví dụ: “abcdef”
Trong trường hợp đó, chúng tôi sẽ lưu trữ tất cả n phần tử trong chuỗi và tập hợp của chúng tôi
Tuy nhiên, chúng tôi cũng bị giới hạn về kích thước của bảng chữ cái tiếng anh
Đây là cơ hội tốt để hỏi người phỏng vấn của chúng tôi loại ký tự nào được tính là duy nhất trong chuỗi [chữ hoa/chữ thường/số/ký hiệu]
Giả sử rằng chuỗi ban đầu sẽ chứa các chữ cái viết thường trong bảng chữ cái, vì bảng chữ cái là hữu hạn, nên chuỗi đầu ra và tập hợp của chúng ta không bao giờ được lớn hơn 26 ký tự
Để lại cho chúng tôi độ phức tạp không gian trong trường hợp xấu nhất là O[1]
Bây giờ bạn đã biết cách giải câu hỏi phỏng vấn của Google
Câu hỏi này có thể xuất hiện trong giai đoạn đầu của cuộc phỏng vấn do tính thẳng thắn của nó… Giống như bài kiểm tra trực tuyến hoặc cuộc gọi điện thoại đầu tiên
Nếu bạn là người học trực quan như tôi, hãy xem video này, tôi đã giải thích thêm về giải pháp. Tôi tạo một video hướng dẫn mới hàng ngày xoay quanh việc bắt đầu sự nghiệp của bạn trong phần mềm
Tôi cũng đã đăng mã đã hoàn thành trên Github tại đây
Cảm ơn đã xem, chúc may mắn
#33
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Nếu bài viết này hữu ích, hãy tweet nó
Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu