Temukan substring Palindromik terpanjang
pertanyaan wawancara teknis yang saya dapatkan dari wawancara harian pro
Palindrom adalah urutan karakter yang membaca maju dan mundur yang sama. Diberikan sebuah string, s, temukan substring palindromik terpanjang di s.
Contoh:
Input: "banana"
Output: "anana"
Input: "million"
Output: "illi"
saya bertanya-tanya apakah ada cara untuk lebih mengoptimalkan kode
Juga apakah menggunakan fungsi bawaan seperti join (), index () dan sebagainya tidak disukai untuk wawancara pengkodean? Karena dengan menggunakannya membuat python jauh lebih mudah dibandingkan dengan bahasa seperti 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
```
Jawaban
Manfaatkan bahasa sepenuhnya . Anda bertanya apakah seseorang harus menggunakan fungsi dan metode built-in yang praktis selama wawancara pengkodean. Benar! Pewawancara ingin melihat, antara lain, bahwa Anda fasih dalam bahasa yang Anda klaim sebagai kefasihan. Tulis kode yang alami dan idiomatis - bukan kode yang menurut Anda ingin dilihat pewawancara. Mungkin ada beberapa perbedaan pendapat yang cukup besar tentang apa yang merupakan kode "baik" di tim yang berbeda dan bahkan di antara pewawancara di tim yang sama. Kecuali mereka memberi Anda instruksi khusus, tulis kode yang baik seperti yang Anda pahami. Dan jika sebuah tim benar-benar ingin melihat Python yang terlihat seperti Java, mungkin itu tidak cocok untuk Anda.
Tidak ada kelas yang tidak berguna . Ngomong-ngomong, apa tujuannya Solution? Sampai masalah memanggil kelas, jangan paksakan. Tulis saja fungsi biasa. Pewawancara selalu dapat mengajukan pertanyaan lanjutan jika mereka ingin melihat Anda membangun kelas. Sekali lagi, tulis kode yang alami dan dapat dibaca dengan kemampuan terbaik Anda.
Jangan pernah mengoptimalkan secara membabi buta . Anda juga bertanya apakah ada "cara untuk lebih mengoptimalkan kode". Ketika saya mewawancarai programmer, salah satu hal utama yang ingin saya pelajari adalah apakah mereka memiliki akal sehat . Selain untuk tujuan pendidikan, sangat sedikit yang bisa diperoleh dari pengoptimalan secara abstrak. Seseorang dapat menghabiskan banyak waktu dan energi untuk mengoptimalkan hal-hal yang tidak relevan jika mereka tidak menghargai konteks yang lebih luas. Optimasi untuk apa - memori, kecepatan, kemudahan perawatan? Selama wawancara, jangan pernah terlibat diskusi pengoptimalan tanpa mengajukan pertanyaan klarifikasi: apa tujuan utama kode, seberapa besar masukannya, seberapa cepat yang dibutuhkan untuk membuat pengguna senang, dan sebagainya.
Optimalkan ketepatan dulu . Implementasi Anda saat ini bergantung pada banyak string input (misalnya, aabb). Masalahnya adalah bahwa algoritme tidak memiliki cara untuk maju jika karakter pertama dan terakhir yang bertahan lstbukan tunggal. Dengan satu atau lain cara, lstharus berubah pada setiap iterasi di bawah desain Anda saat ini. Itu menunjukkan bahwa pemeriksaan bersyarat di akhir whileperulangan mengambil if-elif-elsebentuk. Tapi tidak jelas apa yang harus dimasukkan ke dalam elseblok. Membuang karakter pertama secara naif atau karakter terakhir akan gagal (pertimbangkan input seperti aaabbdan aabbb). Mungkin seseorang yang lebih pintar dari saya dapat memperbaiki desain Anda saat ini, tetapi saya tidak berharap.
Kembangkan kebiasaan untuk menguji . Anda menghabiskan sedikit usaha pada kode Anda, tetapi pertanyaan Anda tidak memiliki bukti pengujian. Saat saya mewawancarai seseorang atau mengembangkan kode baru, saya ingin cara mudah untuk mengujinya. Saat bekerja di komputer, saya akan menggunakan alat pengujian yang sah (biasanya pytest ), tetapi saat memposting contoh atau pertanyaan untuk orang lain, saya akan sering menggulung pengujian menjadi semacam demo yang dapat dijalankan. Sebagai contoh:
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)
Solusi klasik :
- Brute force dengan 3 loop bersarang:
O(n^3). - Dinamis pemrograman menggunakan grid solusi parsial:
O(n^2). - Manacher Algoritma , yang baik pintar dan scratcher kepala:
O(n).
def checkPalindrome(self,lst):
return lst[:] == lst[::-1]
Ini adalah implementasi yang sangat mahal. lst[:]tidak perlu membuat salinan lst, kemudian lst[::-1]membuat salinan lengkap kedualst (tetapi dibalik). Ada banyak cara untuk mendekati ini, tetapi saya akan melakukan sesuatu seperti ini:
def checkPalindrome(self, lst):
return all(start == end
for start, end in zip(lst, reversed(lst)))
Ini zips lstdengan reverseddaftar iterator:
>>> lst = "abcd"
>>> list(zip(lst, reversed(lst)))
[('a', 'd'), ('b', 'c'), ('c', 'b'), ('d', 'a')]
Kemudian periksa untuk melihat apakah allpasangannya sama. Jika ya, daftarnya adalah palindrome. Metode ini masih tidak efisien karena hanya setengah dari masing-masing yang perlu diperiksa. Ini dapat lebih ditingkatkan dengan memperkenalkan itertools.isliceuntuk mendapatkan "tampilan" dari paruh pertama dari daftar zip:
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 seperti pemotongan daftar biasa kecuali daripada membuat salinan, ini hanya memungkinkan Anda untuk mengulang bagian terbatas dari iterable asli.
Kode ini lebih efisien karena setiap fungsi yang terlibat di sini bersifat "malas": mereka hanya melakukan pekerjaan sebanyak yang mereka perlukan. reversed, zip, islice, Dan generator ekspresi semua mengembalikan iterator yang dapat menghasilkan elemen (tapi melakukan sedikit pekerjaan di depan). alljuga keluar segera setelah mendapat hasil Falsey, jadi ini sebanding dengan forloop yang berisi a breakdi beberapa cabang. Ini adalah kuncinya di sini karena kami hanya ingin melakukan pekerjaan sebanyak yang diperlukan untuk menentukan apakah itu palindrome. Membuat dua salinan lengkap dari daftar tersebut melakukan banyak pekerjaan; jauh lebih dari yang dibutuhkan untuk memeriksa apakah string tersebut adalah palindrome.
checkOddChars adalah kasus penggunaan buku teks untuk pemahaman daftar:
def checkOddChars(self, lst):
return [i for i in lst if lst.count(i) == 1]
Jika Anda pernah menemukan diri Anda menginisialisasi daftar kosong, kemudian mengulang iterable lainnya dan menambahkan ke daftar, Anda mungkin menginginkan pemahaman.
Ini juga merupakan fungsi yang cukup mahal. countperlu mengulang seluruh daftar setiap kali; sekali untuk setiap elemen di lst. Ini juga menghitung dua kali elemen yang berulang. Saya tidak yakin di atas kepala saya solusi apa yang lebih baik itu.
del lst[0]
Ini juga cukup mahal. Idealnya, Anda tidak boleh menghapus dari daftar kecuali di bagian paling akhir. Daftar tidak mendukung penghapusan yang efisien, dan semakin dekat ke awal daftar yang Anda hapus, semakin buruk. Saya akan beralih menggunakan dequeuealih - alih daftar, yang menghindari overhead bermunculan dari awal.