Tìm chuỗi con Palindromic dài nhất

Sep 08 2020

câu hỏi phỏng vấn kỹ thuật tôi nhận được từ cuộc phỏng vấn chuyên nghiệp hàng ngày

Palindrome là một chuỗi các ký tự đọc ngược và xuôi giống nhau. Cho một chuỗi, s, tìm chuỗi con palindromic dài nhất trong s.

Thí dụ:


Input: "banana"
Output: "anana"

Input: "million"
Output: "illi"

Tôi đã tự hỏi liệu có cách nào để tối ưu hóa mã hơn không

Ngoài ra, việc sử dụng các hàm tích hợp sẵn như join (), index (), v.v. không được ưu tiên cho một cuộc phỏng vấn viết mã? Bởi vì bằng cách sử dụng nó, việc sử dụng python dễ dàng hơn rất nhiều so với các ngôn ngữ như java

class Solution: 

    
    def checkOddChars(self,lst):
        ls = []
        for i in lst:
            if lst.count(i) == 1:
                ls.append(i)
        return ls  

    def checkPalindrome(self,lst):
        return lst[:] == lst[::-1]



    def longestPalindrome(self, s):
      lst = list(s)
      
      while lst:
        if self.checkPalindrome(lst) :
            return(''.join(lst))

        oddChars = self.checkOddChars(lst)

        if lst[0] in oddChars:
            del lst[0]
        if lst[len(lst)-1] in oddChars:
            del lst[len(lst)-1]

      return('List is empty')

       
# Test program
s = "tracecars"
print(str(Solution().longestPalindrome(s)))
# racecar
```

Trả lời

8 FMc Sep 08 2020 at 03:10

Tận dụng tối đa ngôn ngữ . Bạn hỏi liệu người ta có nên sử dụng các chức năng và phương pháp tích hợp tiện dụng trong một cuộc phỏng vấn viết mã hay không. Chắc chắn rồi! Người phỏng vấn muốn biết, trong số những điều khác, rằng bạn thông thạo (các) ngôn ngữ mà bạn cho là thông thạo. Viết mã tự nhiên, mang tính thành ngữ - không phải mã bạn nghĩ người phỏng vấn muốn xem. Có thể có một số khác biệt khá lớn về quan điểm về điều gì tạo nên mã "tốt" giữa các nhóm khác nhau và thậm chí giữa những người phỏng vấn trong cùng một nhóm. Trừ khi họ cung cấp cho bạn hướng dẫn cụ thể, hãy viết mã tốt khi bạn hiểu nó. Và nếu một nhóm thực sự muốn thấy Python trông giống Java, có lẽ dù sao thì nó cũng không phù hợp với bạn.

Không có lớp học vô nghĩa . Nhắc mới nhớ, mục đích là Solutiongì? Cho đến khi vấn đề yêu cầu một lớp, đừng ép buộc một lớp. Chỉ cần viết một hàm thông thường. Người phỏng vấn luôn có thể hỏi những câu hỏi tiếp theo nếu họ muốn thấy bạn xây dựng một lớp học. Một lần nữa, hãy viết mã tự nhiên, dễ đọc với khả năng tốt nhất của bạn.

Đừng bao giờ tối ưu hóa một cách mù quáng . Bạn cũng hỏi liệu có "cách nào để tối ưu hóa mã hơn". Khi tôi phỏng vấn các lập trình viên, một trong những điều quan trọng mà tôi muốn học là liệu họ có hiểu biết chung không . Ngoài mục đích giáo dục, có rất ít điều thu được từ việc tối ưu hóa trong phần tóm tắt. Một người có thể dành nhiều thời gian và năng lượng để tối ưu hóa cho những thứ không liên quan nếu họ không đánh giá cao bối cảnh rộng lớn hơn. Tối ưu hóa cho cái gì - bộ nhớ, tốc độ, khả năng bảo trì? Trong một cuộc phỏng vấn, đừng bao giờ tham gia vào các cuộc thảo luận về tối ưu hóa mà không đặt các câu hỏi làm rõ: mục tiêu chính của mã là gì, đầu vào sẽ lớn như thế nào, tốc độ cần thiết để giữ cho người dùng hài lòng, v.v.

Trước hết hãy tối ưu hóa tính đúng đắn . Triển khai hiện tại của bạn bị treo trên nhiều chuỗi đầu vào (ví dụ aabb:). Vấn đề là thuật toán không có cách nào để nâng cao khi cả ký tự đầu tiên và ký tự cuối cùng trong những ký tự sống sót lstkhông phải là ký tự đơn. Bằng cách này hay cách khác, lstphải thay đổi trên mỗi lần lặp lại theo thiết kế hiện tại của bạn. Điều đó cho thấy rằng các kiểm tra có điều kiện ở cuối whilevòng lặp có if-elif-elsedạng. Nhưng không rõ ràng những gì để đưa vào elsekhối. Cố ý vứt bỏ ký tự đầu tiên hoặc ký tự cuối cùng sẽ không thành công (xem xét các đầu vào như aaabbvà aabbb). Có lẽ ai đó thông minh hơn tôi có thể sửa chữa thiết kế hiện tại của bạn, nhưng tôi không hy vọng.

Phát triển một thói quen để kiểm tra . Bạn đã dành một chút công sức cho mã của mình, nhưng câu hỏi của bạn thiếu bằng chứng kiểm tra. Khi tôi phỏng vấn ai đó hoặc phát triển một đoạn mã mới, tôi muốn có một cách dễ dàng để kiểm tra nó. Khi làm việc trên máy tính của mình, tôi sẽ sử dụng một công cụ kiểm tra hợp pháp (thường là pytest ), nhưng khi đăng một ví dụ hoặc câu hỏi cho người khác, tôi thường cuộn các bài kiểm tra thành một bản demo có thể chạy được. Ví dụ:

def main():
    TESTS = {
        'abba': 'abba',
        '': None,           # Free thinkers say it should be ''
        'x': 'x',
        'banana': 'anana',
        'tracecars': 'racecar',
        'aabbb': 'bbb',
        'aaabb': 'aaa',
    }
    for word, expected in TESTS.items():
        got = longest_palindrome(word)
        print(got == expected, got, expected)

Các giải pháp cổ điển :

Brute force với 3 vòng lồng nhau: O(n^3).
Năng động, lập trình sử dụng một mạng lưới các giải pháp phần: O(n^2).
Manacher của thuật toán , mà là cả hai khéo léo và một scratcher đầu: O(n).

8 Carcigenicate Sep 08 2020 at 00:59

def checkPalindrome(self,lst):
    return lst[:] == lst[::-1]

Đây là một cách thực hiện cực kỳ tốn kém. lst[:]là tạo một bản sao của lst, sau đó lst[::-1]tạo bản sao hoàn chỉnh thứ hai của lst(nhưng bị đảo ngược). Có nhiều cách để tiếp cận vấn đề này, nhưng tôi sẽ chọn một cái gì đó như sau:

def checkPalindrome(self, lst):
    return all(start == end
               for start, end in zip(lst, reversed(lst)))

Đó ziplà lstvới một reversediterator danh sách:

>>> lst = "abcd"
>>> list(zip(lst, reversed(lst)))
[('a', 'd'), ('b', 'c'), ('c', 'b'), ('d', 'a')]

Sau đó kiểm tra xem allcác cặp có bằng nhau không. Nếu có, danh sách là một palindrome. Mặc dù vậy, phương pháp này vẫn không hiệu quả vì chỉ một nửa trong số mỗi phương pháp cần được kiểm tra. Nó có thể được cải thiện hơn nữa bằng cách giới thiệu itertools.isliceđể có được "cái nhìn" về nửa đầu của danh sách nén:

from itertools import islice

def checkPalindrome(self, lst):
    half_pair_view = islice(zip(lst, reversed(lst)), len(lst) // 2 + 1)
    return all(start == end for start, end in half_pair_view)

islice giống như việc cắt danh sách bình thường ngoại trừ việc thay vì tạo một bản sao, nó chỉ cho phép bạn lặp qua một phần giới hạn của phần có thể lặp lại ban đầu.

Mã này hiệu quả hơn vì mọi chức năng liên quan ở đây là "lười biếng": chúng chỉ làm nhiều việc khi cần. reversed, zip, islice, Và các biểu hiện phát tất cả trả về một iterator rằng có thể tạo ra các yếu tố (nhưng làm chút công việc lên phía trước). allcũng thoát ngay khi nhận được kết quả Falsey, vì vậy nó có thể so sánh với một forvòng lặp có chứa a breaktrong một số nhánh. Đây là chìa khóa ở đây bởi vì chúng tôi chỉ muốn làm nhiều việc cần thiết để xác định xem chúng có phải là bệnh palindromes hay không. Tạo hai bản sao đầy đủ của danh sách thực hiện một lượng lớn công việc; nhiều hơn mức cần thiết để kiểm tra xem chuỗi có phải là palindrome hay không.

checkOddChars là một trường hợp sử dụng sách giáo khoa để hiểu danh sách:

def checkOddChars(self, lst):
    return [i for i in lst if lst.count(i) == 1]

Nếu bạn từng thấy mình đang khởi tạo một danh sách trống, sau đó lặp lại qua một danh sách có thể lặp lại khác và thêm vào danh sách, bạn có thể muốn hiểu.

Đây cũng là một chức năng khá đắt tiền. countcần lặp lại toàn bộ danh sách mỗi lần; một lần cho mọi phần tử trong lst. Điều này cũng đếm gấp đôi bất kỳ phần tử lặp lại nào. Tôi không chắc đâu là giải pháp tốt hơn.

 del lst[0]

Điều này cũng khá tốn kém. Tốt nhất, bạn không nên xóa khỏi danh sách ngoại trừ ở phần cuối. Danh sách không hỗ trợ tính năng xóa hiệu quả và bạn xóa càng gần đầu danh sách, tình trạng càng tồi tệ hơn. Tôi sẽ chuyển sang sử dụng một dequeuethay vì một danh sách, điều này tránh được chi phí xuất hiện ngay từ đầu.