Da wir im Thread Joel Test... auf das Thema Bewerbungs-Programmieraufgaben kamen, fiel mir ein Schmöker ein, in dessen Anhang einige beliebte Fragen aufgeführt sind.

<ad>
Wen es interessiert: es handelt sich um "Expert C Programming - Deep C Secrets" von Peter van der Linden, einer meiner all-time-favorites, uneingeschränkt auch für erfahrene C-Programmierer zu empfehlen. Van der Linden ist einer der C-Compilerschreiber bei Sun und plaudert genüßlich und sehr unterhaltsam ein bisschen aus dem Nähkästchen. ISBN 0-13-177429-8.
</ad>

So, kann gleich mit Frage 1 losgehen. Es handelt sich um ein Problem, vor das MS Mitte der 80er Bewerber gern gestellt hat. Geht harmlos los, und wird durch nachträgliche Einschränkungen ziemlich schnell relativ gemein 😄. Es geht NICHT um Code, es geht um den Algorithmus.

Frage 1, Stufe 1 (hier sollte wirklich noch JEDER mithalten können):
Beschreiben Sie einen Algorithmus, der aus einer Datei von Zeichenkette eine Zeichenkette zufällig auswählt.

Sollte fix gelöst sein. Stufe 2 ist dann schon etwas haariger.

LaTino

Hallo LaTino,

also wie genau jetzt?

Zufallszahl = zwischen 0 und länge der Datei.
Dann an Position der Zufallszahl lesen

Sowas oder is das anders gemeint?

Mit einer Zufallszahl allein wird das nicht funktionieren, denn du landest höchstwahrscheinlich nicht genau auf einem eine Zeichenkette begrenzenden Zeichen.

LaTino

Achso meinst du dass.
Na dann brauch ich noch eine Zufallszahl die zwischen 0 und (Zufallszahl1 - Länge der Datei) ist. Und dann lass ich von Position der Zufallszahl1 bis Position Zufallszahl2 lesen.

Hallo zusammen,

ich würde sagen Zufallszahl zwischen 0..AnzahlZeilen-1

herbivore

Um das nicht allzusehr in die Länge zu ziehen:
Schritt eins: Länge der Datei ermitteln
Schritt zwei: Zufallszahl zwischen 0 und Länge der Datei
Schritt drei: von Position der Zufallszahl bis zum ersten Zeichentrenner vorwärts lesen
Schritt vier: vom Beginn des nächsten Zeichens bis zum seinem Ende -> fertig.

Man könnte den Filepointer auch in Schritt drei zurueck laufen lassen, bis er auf einen Trenner trifft, und dann wieder vorwaerts.

Diese Methode benötigt zwei Lesezugriffe (Länge der Datei ermitteln + eigentlicher Lesevorgang).

Alternativ:
Datei einmal lesen und die Anfangspositionen aller Worte in einem Feld (Array) speichern. Einen Wert des Feldes zufällig aussuchen,an die Position springen, und auslesen bis zum nächsten Trennzeichen.

Ok, das war noch easy.
Stufe 2 ist eine leichte Steigerung von Stufe 1:
Einschränkung: es ist nur ein sequentieller Lesezugriff auf die Datei gestattet.

LaTino

EDIT: herbivore, deine Variante ist quasi Variante zwei, mit der Annahme, dass der Zeilenvorschub das Trennzeichen ist.

Da ja nicht sicher ist ob wirklich nur eine Zeichenkette je zeile Vorhanden ist würde ich die Datei in eine List<string> Parsen
und dann einen Eintrag Zufällig Auswählen

Edit:
War ich wohl zu langsamm

Edit2:
Könnte doch wieder zu Stufe 2 Passen

Hallo LaTino,

das macht es ja noch leichter. Datei komplett einlesen und dann alles im Speicher machen. So hätte ich das schon bei Schritt 1 gemacht.

herbivore

Jupp. Und jetzt EInschränkung drei (ihr ahnt es...):

Es darf nur ein sequentieller Lesevorgang stattfinden, und es dürfen keine zusätzlichen Metainformationen gespeichert werden: keine Kopie der Datei im Speicher, kein Array von Offsets, oder ähnliches.

Tip: der Algorithmus unterscheidet sich radikal von den Ansätzen in den ersten beiden. Das macht es so schwierig, weil man in dem Moment vernagelt ist...

LaTino

sollte doch so gehen:

1. Zufallszahl ermitteln
2. Lesen bis zufalszahl und weiter bis zu erstem Trenzeichen
   3.String zwischen Trenzeichen und nächstemtrenzeichen Ausgeben
3. Fertig

Du meinst sicherlich eine Zufallszahl, die zwischen 0 und (Länge der Datei) liegt. Umn die Länge der Datei zu ermitteln, ist bereits ein Zugriff auf die Datei notwendig, dh du hast den einen verbraucht.

So wird's also nix.

LaTino

PS: zur Info: die Länge einer Datei ermittelt sich so: datei öffnen - Zeiger auf Ende der Datei - Zeigerposition ermitteln. C kann ganz hilfreich sein, um über Betriebssystemsvorgänge was zu lernen ...

darf man einen einzigen String Speichern?

Ohne jetzt zuviel verraten zu wollen: zwei Strings werden benötigt, allerdings sind die beiden je höchstens so lang, wie die längste Zeichenkette in der Datei (irgendwo muss man ja sein Ergebnis speichern).

LaTino

Ich gebe Auf mir Fallen auf anhieb nur ein Paar möglichkeiten ein die keine 100% zufälligkeit erzeugen

Hallo LaTino.

PS: zur Info: die Länge einer Datei ermittelt sich so: datei öffnen - Zeiger auf Ende der Datei - Zeigerposition ermitteln. C kann ganz hilfreich sein, um über Betriebssystemsvorgänge was zu lernen ...

Die Länge der Datei steht im Verzeichnis/Directory. Es ist nicht nötig, die Datei zu öffnen.

herbivore

Nichtsdestotrotz hast du einen Dateizugriff, auch wenn du auf das Directory zugreifst 🙂.

Der gesuchte Algorithmus arbeitet mit der Datei, ohne ihre Groesse zu kennen.

LaTino
Edit: selbst wenn man die Groesse der Datei kennen würde, koennte man immer noch nicht in einem sequentiellen Lesevorgang einen Zufallsstring auslesen (eben weil man den Start nicht kennt). Dieser Gedankengang führt in die Irre 🙂.

Wenn die Wahrscheinlichkeit nicht homogen verteilt sein muss:

1. String lesen
2. Zufallszahl zwischen 0 und 1 ermitteln
3. Wenn Zahl > 0.5 oder die Datei ist zuende: den aktuellen String nehmen
4. ansonsten wieder zu 1

Wie gesagt ist die Wahrscheinlichkeit nicht mehr mehr homogen sondern geometrisch verteilt, aber in der Hinsicht gab es ja auch keine Informationen in der Aufgabe 🙂

Grüße,
Andre

Ist richtig, so ist die Wahrscheinlichkeit geometrisch verteilt, und das ist nicht das, was wir im Allgemeinen als zufällig betrachten.

Aber du bist so nah dran an einer arithmetischen Verteilung. Nur noch überlegen, was du beim n-ten eingelesenen String für eine Wahrscheinlichkeit haben musst, um ihn zu behalten.

(ersten einlesen: Wahrscheinlichkeit ist ...
zweiten einlesen: wahrscheinlichkeit ist... und so weiter.)

LaTino
*g* war genau der Weg, wie ich auch drauf gekommen bin. In einer Bewerbungssituation allerdings hätte ich Tipps gebraucht.

Hallo LaTino,

Dieser Gedankengang führt in die Irre

mein Gedankengang war auch nicht im Sinne einer Lösung gemeint, sondern weil du geschrieben hast, dass man was über Betriebssystemsvorgänge lernen kann. Und da ging wohl dein Gedankengang in die Irre. 🙂

Es darf nur ein sequentieller Lesevorgang stattfinden, und es dürfen keine zusätzlichen Metainformationen gespeichert werden: keine Kopie der Datei im Speicher, kein Array von Offsets, oder ähnliches.

Also ohne Metainformationen geht es m.E. nicht. Wie du schon andeutest, muss man wissen, die wievielte Zeile man gerade liest. Die Wahrscheinlichkeit diese Zeile zu wählen muss 1/i sein. Also bei der erste Zeile ist die Wahrscheinlichkeit 1. Daraus ergibt sich, dass man erst fertig ist, wenn man alle Zeilen gelesen hat und nicht aufhört, sobald man eine Zeile gewählt hat.

herbivore

Natürlich, die aktuelle Position muss man wissen - aber die sagt genau gar nichts über die Struktur der Datei aus (ausser, wie gross sie mindestens ist), ist also keine Meta-Information.

Bleiben wir mal bei der Annahme, dass die Zeichenketten zeilenweise untereinander stehen, das macht das ganze in der Beschreibung einfacher 😉.

An sich hast du die Lösung schon hingeschrieben.

Wir brauchen Speicherplatz für einen temporär ausgewählten String (nennen wir ihn mal "Survivior"), sowie eine Variable, die die Nummer des aktuell gelesenen String festhält.

Der n-te gelesene String wird mit einer Wahrscheinlichkeit von 1/n zum Survivor. Also:

• Datei lesen bis Zeilenende
• Zaehler eins hoch
• frisch gelesener String ersetzt den vorhandenen Survivor mit einer Wahrscheinlichkeit von 1/Zähler.
• weitermachen bis Dateiende (GANZ wichtig).

So haben alle Zeichenketten am Ende die gleiche Wahrscheinlichkeit, gezogen zu werden.

Das (für mich) überraschende war beim testen, dass dieser Algorithmus nur unwesentlich langsamer ist als die auf der Hand liegenden Alternativen, für lange Dateien sogar schneller (wenn auch zunehmend ungenauer wegen der double-Ungenauigkeit, aber das Problem teilen sich alle Algorithmen).

Hätte noch ein paar, auch aus der theoretischen Informatik (Stichwort Komplexizitätstheorie). Interesse?

LaTino

Hallo LaTino,

Interesse?

warum nicht? Aber von mir aus erst morgen. Gehe jetzt ins Bett. Und vielleicht jede (echt) neue Aufgabe in einen neuen Thread.

herbivore

ja warum nicht aber erst Nacher gehe jetzt auch erst mal schlafen

Original von LaTino
Der n-te gelesene String wird mit einer Wahrscheinlichkeit von 1/n zum Survivor. Also:

• Datei lesen bis Zeilenende
• Zaehler eins hoch
• frisch gelesener String ersetzt den vorhandenen Survivor mit einer Wahrscheinlichkeit von 1/Zähler.
• weitermachen bis Dateiende (GANZ wichtig).

So haben alle Zeichenketten am Ende die gleiche Wahrscheinlichkeit, gezogen zu werden.

Entschuldige - für Dummies - aber wo ist hier die Zufälligkeit?

Im übrigen finde ich die Idee einer "Quizreihe" nicht schlecht.

Das ist nicht für Dummies, es erfordert aber ein bisschen einfache Mathematik (deshalb find' ich persönlich die Lösung so gut, immer schön, mal 'ne praktische Anwendung zu sehen). Nichts Hochkompliziertes, eigentlich nur Bruchrechnung 😉.

Ich mach es an einem Beispielfile mit nur drei Worten.

Survivor = "";
Schritt 1:
i = 1;
Auswahl "wort1";
Auswahl wird mit 1/1 Wahrscheinlichkeit zum Survivor -> Auswahl wird Survivor.

Schritt 2:
i = 2;
Auswahl "wort2";
Auswahl wird mit 1/2 Wahrscheinlichkeit zum Survivor: insgesamt also 50% chance für wort1, und 50% für wort2

Schritt 3:
i = 3;
Auswahl "wort3"
Auswahl wird mit 1/3 Wahrscheinlichkeit zum Survivor. Das bedeutet im Gegenschluß, dass der Survivor mit 2/3 Wahrscheinlichkeit bestehen bleibt.
Also:
nach Schritt2 hatte "wort1" eine 50%ige Wahrscheinlichkeit, Survivor zu sein. Multipliziert mit 2/3 (es muss ja bestehen bleiben), bleibt es ingesamt also mit 1/3 ( = 1/2 * 2/3) Wahrscheinlichkeit im Rennen.
"wort2" hatte nach Schritt2 ebenfalls 1/2 Wahrscheinlichkeit, da gilt also auch 1/2 * 2/3 = 1/3.
Na, und "Wort3" wird eben mit 1/3 Wahrscheinlichkeit zum Survivor.

Und da wir nach Runde 3 schon am Ende der Datei sind, besteht für jedes Wort eine 33,33%ige Wahrscheinlichkeit, gezogen worden zu sein. Perfekter Zufall.

Die Wahrscheinlichkeit, aus einer Menge mit n Elementen das k-te Element zu ziehen, ist mit dieser Methode:

1/k * (k/k+1) * (k+1/k+2) * (k+2) / (k+3) * ... * (n-1) / n

((k+1) * (k+2) * (k+3) * ... * (n-1)) / ((k+1) * (k+2) * (k+3) * ... * (n-1) * n )

1/n

Das sieht ja schon in der Vorschau seltsam aus...naja - wenn dich die letzten Zeilen zu sehr verwirren, ignorier sie 😉.

LaTino

Original von LaTino
Ich mach es an einem Beispielfile mit nur drei Worten.

Ups - jetzt hast Du Dir so viel Mühe gegeben 🙂

Meine Frage ist aber eher: warum wird einmal nach Schritt 1 abgebrochen und ein anderes Mal nach Schritt 3?
Es wird ja auf jeden Fall bis zum Dateiende gelesen, daher kann ich jetzt nur erkennen, daß man immer bis zu Schritt 3 kommt und immer das letzte Wort gewählt wird. Das kann's aber nicht sein, soviel ist mir klar 😉

Hallo Bini,

das Wort i wird ja nur mit einer Wahrscheinlichkeit 1/i zum (momentanen) Survivor. Warum dann alle Worte am Ende gleichwahrscheinlich sind, hat ja LaTino ausführlich begündet.

Beim Wort 1 ist die Wahscheinlichkeit, dass es zum (momentanen) Survivor wird, eins. Wenn man immer abbrechen würde, sobald man einen Survivor hat, würde immer das erste Wort gewählt.

herbivore

Genau. Das Ergebnis-Wort ist im wahrsten Sinn des Wortes der "letzte Überlebende". Daher die Wortwahl "survivor" 😄.

LaTino

So Jungs, jetzt hab ich mal das Brett vor'm Kopf abgemacht und in die Ecke gestellt 😉 Also, ich hab jetzt kapiert, daß der Quotient 1/i (im Beispiel) die Wahrscheinlichkeit ("den Zufall") enthält. Heute Mittag konnte ich den Wald vor Bäumen nicht sehen.

Und auf die Gefahr hin, mich zum Forumsdepp zu machen: wie setzt man das jetzt ganz konkret in Quellcode um? Also wie setzt man diesen Wahrscheinlichkeits-Quotienten ein, um den Survivor-String zu bestimmen?

Hallo Bini,

ungefähr so: random.NextDouble () < 1.0/(double)i

herbivore

Original von herbivore
ungefähr so: random.NextDouble () < 1.0/(double)i

Danke!

Hallo

Als Nicht-Professioneller und Freizeitprogrammierer möchte ich immer noch die Frage stellen, wie das funktionieren soll. Gesucht war ja ein zufällig ausgesuchter String und nicht bloß die Formel. Meiner Meinung nach geht das in nur einem Durchlauf nicht. Es sind mindestens zwei Durchläufe erforderlich, einer, um die Gesamtzahl der Strings, bzw das Dateiende zu finden, denn das Dateiende braucht man, um bei jeweils gleicher Chance auf den zufällig ausgewählten Sting zu kommen. Einen zweiten Durchlauf, um dann den ausgewählten String anzusprechen und in den 'Survivor' String zu packen.

Übrigens, hätte die Datei kein Ende, würde also ein anderer Prozess am Ende über Append ständig was dazupacken, wäre die Aufgabe gänzlich unlösbar, da der erste Durchlauf nie zum Schluss käme.

viele Grüße

Hallo gespannter_Bogen,

natürlich geht es in einem Durchlauf! Der Algorithmus wurde in Pseudocode angegeben und lässt sich 1:1 in C# umsetzen. Warum der Algorithmus die gewünschte Gleichverteilung bewirkt, wurde auch begründet. Ich verstehe nicht, was da noch unklar ist. 🙂

herbivore

Bei einem nicht determinierten Ablauf (wie von dir beschrieben, eine quasi-unendlich lange Datei) kann der Algorithmus natürlich kein Ergebnis liefern. Was er aber sehr gut kann (und wofür ich ihn in der Praxis auch einsetze) ist, zu einem beliebigen Zeitpunkt des Ablaufs bereits ein Ergebnis zu liefern, dass alle bis dahin gelesenen Datensätze (Zeichenketten) berücksichtigt. Den mathematischen Hintergrund, wieso das funktioniert, habe ich ja schon gepostet.

Bin grad von 'ner unverhofften Dienstreise zurück und poste nachher Aufgabe 2 🙂.

LaTino