Entwurf eines Algorithmus für große Daten

Question

Entwurf eines Algorithmus für große Daten

8

Ich lese eine dieser Fragen, die für ein Vorstellungsgespräch des Softwareentwicklers gestellt werden.

Wenn es 1000 Webseiten und 1000 Benutzer gibt, schreibe ein Programm und eine Datenstruktur, so dass ich in Echtzeit die folgenden Anfragen abfragen kann: 1. Wenn ich einen Benutzer besuche, erhalte ich die Liste aller von ihm besuchten Seiten 2 Bei jeder Website bekomme ich die Liste aller Benutzer, die sie besucht haben.

Ich denke, sie wollten eine Art Pseudo-Code oder Design-Algorithmus.

Können Sie mir irgendwelche Tipps dafür geben?

algorithm c data-structures

rain 04.07.2012, 06:43

quelle

5 Antworten

1

Hier finden Sie eine Zusammenfassung der veröffentlichten Antworten .

Sei m die Anzahl der Seiten, n die Anzahl der Benutzer. Für jede Datenstruktur geben wir die Komplexität für update, resp. bekommen.

zwei Arrays von verknüpften Listen. O (1), resp. O (len (antworten)).

eine m × n-Matrix. O (1), resp. O (m) oder O (n). Die geringste Speicherbelegung, wenn die meisten Benutzer die meisten Websites besuchen, aber nicht optimal in Bezug auf Zeit und Raum, wenn die meisten Benutzer nur wenige Websites besuchen.

zwei Arrays von Mengen. O (log m) oder O (log n) bzw. O (len (antworten)).

izomorphius 'Antwort ist sehr nah an verknüpften Listen.

O (len (antwort)) ist die Zeit, die benötigt wird, um die ganze Antwort zu lesen, aber für Mengen und Listen kann man einen Iterator in 0 (1) bekommen, der eine next -Methode hat, die auch O ( 1).

jrouquie 05.07.2012 07:54
quelle

Tags und Links algorithm c data-structures

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Seltsames Verhalten der CASE-Konstruktion

score 3 · Answer 1

Eins ist sicher - um beide Abfragen beantworten zu können, müssen Sie alle Paare speichern, die bedeuten, dass der Benutzer die angegebene Website besucht hat. Was ich vorschlage, ist folgendes:

Sie haben eine Struktur:

%Vor%

nextForUser zeigt auf das nächste Paar für den angegebenen Benutzer oder NULL, wenn für den angegebenen Benutzer kein nächstes Paar vorhanden ist. nextForWebsite zeigt dann auf das nächste Paar für den webSite. Benutzer und Website sehen etwa so aus:

%Vor%

Ich gehe davon aus, dass sowohl Website-s als auch Benutzer in Arrays gespeichert sind, sagen wir, dass diese Arrays websites und users sind. Das Hinzufügen eines neuen visitPair ist relativ einfach:

%Vor%

Drucken aller Benutzer für eine Website und alle Websites für einen Benutzer erfolgt durch einfaches Iterieren über eine Liste, so dass Sie in der Lage sein sollten, dies zu tun.

Kurz gesagt, was ich erstelle, ist eine Struktur, die zwei Listen integriert hat. Ich glaube nicht, dass es eine Lösung mit einer besseren Komplexität geben kann, da diese eine lineare Komplexität in Bezug auf die Antwort und eine konstante Komplexität für das Hinzufügen eines Paares aufweist.

Hoffe, das hilft.

score 3 · Answer 2

Da sowohl die Anzahl der Sites als auch die Anzahl der Benutzer vorab festgelegt und bekannt sind, können Sie ein 2D-Array mit einer Größe von 1000 x 1000 verwenden, wobei der Benutzer eine Dimension und die Website eine andere Dimension ist. Das Array wäre ein boolesches Array.

%Vor%

Wenn Benutzer x Website y besucht, wird er als 1 (wahr) markiert.

%Vor%

Um alle Benutzer zurückzugeben, die Website J besucht haben, gebe alle Werte in Spalte J zurück, die den Wert 1 haben,

Geben Sie alle von Benutzer i besuchten Websites zurück, und geben Sie alle Werte in Zeile i mit dem Wert 1 zurück.

Die Komplexität der Suche ist O (n), aber dieser Ansatz ist platzsparend, und Aktualisierungen sind 0 (1), Im Gegensatz zu einer verketteten Liste, die O (n) -Komplexität erfordert, um einen Benutzer zu der mit der Website verknüpften Liste hinzuzufügen, oder eine Webseite zu der verknüpften Liste des Benutzers hinzuzufügen. (Dies ergibt jedoch eine O (1) -Komplexität beim Suchen.)

score 3 · Answer 3

Halten Sie für jede Website und jeden Benutzer eine verknüpfte Liste für besuchte Besucher bzw. Websites bereit. Wenn ein Benutzer eine Website besucht, fügen Sie einen Eintrag in die Benutzerliste sowie in die verknüpfte Website hinzu.

Dies hat minimalen Speicheraufwand und schnelle Aktualisierungen und Abfragen zur Folge.

score 1 · Answer 4

Im Allgemeinen haben Benutzer mit N und M zwei Maps für Abfragen wie

%Vor%

Wenn der Nutzer die Website s besucht, aktualisieren Sie dies mit

%Vor%

set wird hier verwendet, um Doppelungen zu vermeiden. Wenn die Duplizierung in Ordnung ist (oder Sie sich später darum kümmern), können Sie nur die Liste verwenden und die Aktualisierungszeit um ein weiteres Protokoll verringern .
In diesem Fall dauert die Aktualisierung O (logN + logM) Zeit (oder nur O (logN) , siehe oben) und die Abfrage dauert O (logN) Zeit.

In Ihrem speziellen Fall, wenn die maximale Anzahl von Seiten und Benutzern nicht zu viel ist und vorher bekannt ist (sagen wir es K ), können Sie einfach zwei Arrays wie
haben %Vor%
Hier erhalten Sie O (logN) Zeit für die Aktualisierung (oder O (1) wenn doppelte Informationen kein Problem darstellen und Sie Liste oder ein anderer linearer Container) und O (1) Zeit für die Abfrage.

score 1 · Answer 5

Hier finden Sie eine Zusammenfassung der veröffentlichten Antworten .

Sei m die Anzahl der Seiten, n die Anzahl der Benutzer. Für jede Datenstruktur geben wir die Komplexität für update, resp. bekommen.

zwei Arrays von verknüpften Listen. O (1), resp. O (len (antworten)).
eine m × n-Matrix. O (1), resp. O (m) oder O (n). Die geringste Speicherbelegung, wenn die meisten Benutzer die meisten Websites besuchen, aber nicht optimal in Bezug auf Zeit und Raum, wenn die meisten Benutzer nur wenige Websites besuchen.
zwei Arrays von Mengen. O (log m) oder O (log n) bzw. O (len (antworten)).

izomorphius 'Antwort ist sehr nah an verknüpften Listen.

O (len (antwort)) ist die Zeit, die benötigt wird, um die ganze Antwort zu lesen, aber für Mengen und Listen kann man einen Iterator in 0 (1) bekommen, der eine next -Methode hat, die auch O ( 1).