Finden Sie den längsten palindromischen Teilstring
Frage zum technischen Interview, die ich vom täglichen Interview Pro bekommen habe
Ein Palindrom ist eine Folge von Zeichen, die das gleiche vorwärts und rückwärts lesen. Finden Sie bei gegebener Zeichenfolge s den längsten palindromischen Teilstring in s.
Beispiel:
Input: "banana"
Output: "anana"
Input: "million"
Output: "illi"
Ich habe mich gefragt, ob es eine Möglichkeit gibt, den Code weiter zu optimieren
Wird die Verwendung von integrierten Funktionen wie join (), index () usw. für ein Codierungsinterview nicht bevorzugt? Weil die Verwendung in Python im Vergleich zu Sprachen wie Java so viel einfacher ist
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
```
Antworten
Nutzen Sie die Sprache voll aus . Sie fragen, ob Sie während eines Codierungsinterviews handliche integrierte Funktionen und Methoden verwenden sollten. Absolut! Interviewer möchten unter anderem sehen, dass Sie die Sprache (n), in der Sie fließend sprechen, fließend sprechen. Schreiben Sie natürlichen, idiomatischen Code - keinen Code, den der Interviewer sehen möchte. Es kann einige ziemlich große Meinungsverschiedenheiten darüber geben, was "guten" Code zwischen verschiedenen Teams und sogar zwischen Interviewern im selben Team ausmacht. Schreiben Sie guten Code so, wie Sie ihn verstehen, es sei denn, sie geben Ihnen spezifische Anweisungen. Und wenn ein Team wirklich Python sehen möchte, das wie Java aussieht, passt es vielleicht sowieso nicht zu Ihnen.
Keine sinnlosen Klassen . Apropos, wozu dient das Solution? Erzwingen Sie keine, bis das Problem eine Klasse erfordert. Schreiben Sie einfach eine gewöhnliche Funktion. Interviewer können jederzeit weitere Fragen stellen, wenn sie möchten, dass Sie eine Klasse aufbauen. Schreiben Sie wieder natürlichen, lesbaren Code nach besten Kräften.
Niemals blind optimieren . Sie fragen auch, ob es "eine Möglichkeit gibt, den Code weiter zu optimieren". Wenn ich Programmierer interviewe, ist eines der wichtigsten Dinge, die ich lernen möchte, ob sie gesunden Menschenverstand haben . Anders als zu Bildungszwecken kann durch abstrakte Optimierung nur sehr wenig gewonnen werden. Eine Person kann viel Zeit und Energie darauf verwenden, für irrelevante Dinge zu optimieren, wenn sie den größeren Kontext nicht schätzt. Optimierung für was - Speicher, Geschwindigkeit, Wartbarkeit? Nehmen Sie während eines Interviews niemals an Optimierungsdiskussionen teil, ohne klarstellende Fragen zu stellen: Was sind die Hauptziele des Codes, wie groß werden die Eingaben sein, wie schnell muss es sein, um die Benutzer zufrieden zu stellen, und so weiter.
Optimieren Sie zuerst die Richtigkeit . Ihre aktuelle Implementierung hängt an vielen Eingabezeichenfolgen (z. B. aabb). Das Problem ist, dass der Algorithmus keine Möglichkeit hat, voranzukommen, wenn sowohl das erste als auch das letzte Zeichen im Überleben lstkeine Singletons sind. Die eine oder andere Art lstmuss sich bei jeder Iteration unter Ihrem aktuellen Design ändern. Dies legt nahe, dass die bedingten Prüfungen am Ende der whileSchleife eine if-elif-elseForm annehmen . Aber es ist nicht klar, was in den elseBlock gesetzt werden soll. Das naive Wegwerfen des ersten oder letzten Zeichens schlägt fehl (berücksichtigen Sie Eingaben wie aaabbund aabbb). Vielleicht kann jemand, der schlauer ist als ich, Ihr aktuelles Design reparieren, aber ich bin nicht hoffnungsvoll.
Entwickeln Sie eine Gewohnheit zum Testen . Sie haben einiges an Aufwand für Ihren Code aufgewendet, aber Ihre Frage enthält keine Beweise für Tests. Wenn ich jemanden interviewe oder einen neuen Code entwickle, möchte ich einen einfachen Weg finden, ihn zu testen. Wenn ich an meinem Computer arbeite, verwende ich ein legitimes Testtool (normalerweise Pytest ). Wenn ich jedoch ein Beispiel oder eine Frage für andere poste , werden die Tests häufig in eine ausführbare Demo umgewandelt. Beispielsweise:
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)
Klassische Lösungen :
- Brute Force mit 3 verschachtelten Schleifen :
O(n^3). - Dynamische Programmierung mit einem Raster von Teillösungen :
O(n^2). - Manachers Algorithmus , der sowohl clever als auch ein Head Scratcher ist :
O(n).
def checkPalindrome(self,lst):
return lst[:] == lst[::-1]
Dies ist eine extrem teure Implementierung. lst[:]erstellt unnötig eine Kopie von lst, lst[::-1]erstellt dann eine zweite vollständige Kopie von lst(aber umgekehrt). Es gibt viele Möglichkeiten, dies zu erreichen, aber ich würde mich für so etwas entscheiden:
def checkPalindrome(self, lst):
return all(start == end
for start, end in zip(lst, reversed(lst)))
Es zips lstmit einer reversedListe Iterator:
>>> lst = "abcd"
>>> list(zip(lst, reversed(lst)))
[('a', 'd'), ('b', 'c'), ('c', 'b'), ('d', 'a')]
Überprüfen Sie dann, ob alldie Paare gleich sind. Wenn ja, ist die Liste ein Palindrom. Diese Methode ist jedoch immer noch ineffizient, da nur jeweils die Hälfte überprüft werden muss. Es kann weiter verbessert werden, indem eingeführt wird itertools.islice, um eine "Ansicht" der ersten Hälfte der komprimierten Listen zu erhalten:
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 ist wie normales Aufteilen von Listen, nur dass Sie anstelle einer Kopie nur einen begrenzten Teil der ursprünglichen iterierbaren Datei durchlaufen können.
Dieser Code ist effizienter, da jede hier beteiligte Funktion "faul" ist: Sie erledigen nur so viel Arbeit, wie sie benötigen. reversed, zip, islice, Und der Generator Ausdruck alle einen Iterator zurück , die Elemente (aber tun wenig Arbeit vorne) produzieren kann. allWird auch beendet, sobald ein Falsey-Ergebnis angezeigt wird. Daher ist es mit einer forSchleife vergleichbar , die breakin einigen Zweigen ein enthält . Dies ist hier der Schlüssel, da wir nur so viel Arbeit leisten möchten, wie erforderlich ist, um festzustellen, ob es sich nicht um Palindrome handelt. Das Erstellen von zwei vollständigen Kopien der Liste ist sehr arbeitsintensiv. weit mehr als erforderlich, um zu überprüfen, ob die Zeichenfolge ein Palindrom ist.
checkOddChars ist ein Lehrbuch-Anwendungsfall für ein Listenverständnis:
def checkOddChars(self, lst):
return [i for i in lst if lst.count(i) == 1]
Wenn Sie jemals feststellen, dass Sie eine leere Liste initialisieren, dann über eine andere iterierbare Datei iterieren und zur Liste hinzufügen, möchten Sie wahrscheinlich ein Verständnis.
Dies ist auch eine ziemlich teure Funktion. countmuss jedes Mal die gesamte Liste durchlaufen; einmal für jedes Element in lst. Dies zählt auch alle wiederholten Elemente doppelt. Ich bin mir nicht sicher, was eine bessere Lösung ist.
del lst[0]
Das ist auch ziemlich teuer. Idealerweise sollten Sie nur ganz am Ende aus einer Liste löschen. Listen unterstützen keine effizienten Löschvorgänge. Je näher am Anfang der Liste, aus der Sie löschen, desto schlechter ist sie. Ich würde auf die Verwendung einer dequeueListe anstelle einer Liste umsteigen, wodurch der Aufwand für das Aufspringen von Anfang an vermieden wird.