Algorithmus zum Durchlaufen aller kürzesten Ketten?

Question

Ich mache einen URL-Shortener, und ich möchte für jede URL die kürzest mögliche Zeichenfolge verwenden. Jede URL hat ein anderes Ablaufdatum.

Zum Beispiel, lassen Sie uns URLs einreichen, die der folgenden Liste verkürzt erhalten:

a, b, c, ..., z, 0 ..., 9, aa, ab, ac, ... a9, ba

Dann sagen c abläuft, so dass die nächste URL sollte statt bb zu c verkürzt werden, da c kürzer ist und wird nicht genommen.

Welche Datenstruktur wäre gut, um den Überblick zu behalten?

Answer 1

Dies ist ein lustiges Problem. Sie benötigen dazu mehrere Datenstrukturen. Das würde ich tun.

1) Eine Hash-Tabelle mit kurzen URLs als Schlüssel und allen URL-Informationen (vollständige URLs, Ablaufzeiten usw.) als Werte.

2) Ein Min-Heap abgelaufener URLs. Auf diese Weise können Sie die kürzeste verfügbare URL schnell abrufen und wiederverwenden.

3) Eine Zeichenfolge, um die längste verwendete kurze URL zu verfolgen. Auf diese Weise können Sie schnell eine neue URL generieren, wenn keine abgelaufenen kürzer sind.

4) Etwas zum Verfolgen der Ablaufzeiten, damit Sie URLs effizient ablaufen lassen können. Es könnte Hash-Tabelle in Form von Date -> ShortURL sein, mit den geordneten Schlüsseln, so dass Sie leicht die URLs bekommen können, die als nächstes ablaufen.

Answer 2

Ich würde eine Prioritätswarteschlange verwenden, deren Komparator verschachtelte Regeln hat, wobei die erste ein Flag ist, das leer ist oder genommen wird, und das zweite auf der Zeichenfolge steht. Denken Sie daran, dass ein PQ Ihre meistgesuchten Objekte an der Spitze der Warteschlange hält. Ihr Objekt sollte daher eine Zusammensetzung aus dem String-Namen und einem booleschen Flag sein.

Answer 3

Ich würde 2 Haufen verwenden.

1. Ein Min-Heap für nicht verwendete URLs, wobei der Min-Wert die URL ist.
2. Ein Min-Heap für gebrauchte URLs, wobei der Mindestwert die Anzahl der Sekunden seit dem 1.1.1970 (Long-Wert) ist.

Wenn Sie eine neue URL benötigen, ziehen Sie aus der Spitze des Haufens 1. Wenn eine URL abläuft, ziehen die URL aus dem Heap 2 und legen Sie sie in Haufen 1.