n einem Interview wurde ich gebeten, eine Datenstruktur zu entwickeln, die Millionen von Mustern enthalten kann und eine schnelle Suche ermöglicht, um die am längsten passende zu finde

Zum Beispiel sind Muster wie:

1- 8876 8893 87          | true
2- 8876 889              | false
3- 8876 8                | false
4- 887                   | true

Die Eingabe ist eine Zahl mit mindestens 2 und höchstens 18 Stellen. Wir müssen das längste übereinstimmende Muster aus der Datenstruktur finden und den Booleschen Wert am Ende extrahieren.

Zum Beispiel,8876 8893 9943 53 würde mit dem @ übereinstimm1 undtrue ist zurück gekommen.8876 8397 5430 74 würde mit dem @ übereinstimm3 undfalse ist zurück gekommen

Meine Antwort war, einen Baum zu benutzen und eine Liste von @ zu habkey value Paar auf jeder Ebene. Der Schlüssel, der aus Ziffern und Wert besteht, ist entweder null oder gleich boolesch, je nachdem, ob es sich um das Ende eines Musters handelt oder nicht. Mögen

# matching 8875
# start the search by first digit
[..., (7, null), (8, null), (9, null)] 
                  ^
                 [..., (7, null), (8, null), (9, null)] 
                                   ^
                                   [..., (7, true), (8, null), ...]
# at the last step because we don't have a pattern 
# to match the digit 5, we return the `true` from (7, true)

Das Herausfordernde ist, dass die Muster ziemlich viel sind. Millionen von ihnen. Ist das gut Wenn nicht, was ist Ihr Vorschlag.