Rekursion oder Iterative Lösung?

[Barista]

In meiner letzten Firma mussten Bewerber eine Aufgabe dieses Schwierigkeitsgrades innerhalb eines Vorstellungsgesprächs lösen.

 

[fhoffmann]

Aus jedem Element des Zwischenergebnisses musst du nun die 8 neuen Elemente hinzufügen

Das ist falsch, aus jedem Element müssen nur vier neue Elemente gemacht werden; die Klammerung um "b" existiert ja schon.

 

[kneitzel]

Das ist falsch, aus jedem Element müssen nur vier neue Elemente gemacht werden; die Klammerung um "b" existiert ja schon.

Ja, das ist natürlich richtig, danke für die Verbesserung. Falls die Erläuterung von @fhoffmann noch nicht ausreichend war:
Wir haben zwei Schritte: ersten Buchstaben mit und ohne Klammern
und dann die entstandendenen Ergebnisse mit und ohne Klammern.
==> Zwei Verdoppelungen, d.h. 4 Elemente.

Jetzt sollten wir aber diese gefundene (vermeintliche) Lösung noch etwas verifizieren. Wir haben die Idee von @fhoffmann aus #6 umgesetzt, aber die Idee wurde bisher noch nicht verifiziert. Das hätte man schon an seinem Beispiel machen können/sollen aber das wurde irgendwie versäumt.

Er hat das Beispiel xab gebracht und da gibt es nur die Ergebnisse von ab für die jeweils die Elemente:
xt
(x)t
(xt)
((x)t)
für alle t Element aus der Menge aller Lösungen aus dem Aufruf aus "ab".

Was dabei auffallen sollte ist nun, dass z.B. "(xa)b" eine gültige Klammerung ist, aber diese in der Lösungsmenge nicht auftaucht.

Somit ist die bisherige Lösung noch nicht korrekt und somit zu erweitern. Wenn ich also 3 Zeichen habe, muss ich nicht nur das erste Zeichen mal abtrennen sondern auch mal 2 Zeichen. Bei n Zeichen habe ich dann einfach eine Schleife, die dann alles in alle möglichen zwei Teile trennen könnte.

Und dann ist da noch das wichtige Thema:

Wichtig aber ist, dass kein Element in der Ergebnisliste mehrmals vorkommt

Ohne Grund wird da ja das HashSet nicht explizit erwähnt worden sein 🙂

In meiner letzten Firma mussten Bewerber eine Aufgabe dieses Schwierigkeitsgrades innerhalb eines Vorstellungsgesprächs lösen.

Aber das ist keine Aufgabe für einen Junior würde ich sagen. Das ist eine Aufgabe, die bei den Codility-Tests, auf die wir z.B. zugreifen, als schwere Aufgabe geführt werden dürfte.

 

[fhoffmann]

Was dabei auffallen sollte ist nun, dass z.B. "(xa)b" eine gültige Klammerung ist, aber diese in der Lösungsmenge nicht auftaucht.

Oh Gott, das habe ich nicht gesehen - nun wird es ja richtig komplizert.
Dann ist ja auch "(x(ab))c" oder "(x(a)b)c" nicht in der Lösungsmenge enthalten.

 

[kneitzel]

Oh Gott, das habe ich nicht gesehen - nun wird es ja richtig komplizert.
Dann ist ja auch "(x(ab))c" oder "(x(a)b)c" nicht in der Lösungsmenge enthalten.

Ja genau, ich selbst sehe daher als rekursiven Algorithmus derzeit, dass man eine Schleife hat in der man dann alle Möglichkeiten aufruft, mit denen man es in zwei Teile teilen kann.
- Also wenn ich abcd habe, dann rufe ich rekursiv auf für a + bcd, ab + cd und abc + d und erhalte so jedes Mal zwei Array (Mengen) zurück. (Die weiteren Unterteilungen kommen dann ja automatisch).
- Bei den Ergebnissen, die man erhält, erstellt man dann sozusagen das "Kreuzprodukt" und fügt jedes Ergebnis dann hinzu (2 Mal, geklammert und nicht geklammert)
- Beim hinzufügen wird aber erst geprüft, ob das hinzuzufügende Element bereits vorhanden ist. Ist dies der Fall, wird nicht eingefügt.

Das wäre meine erste Implementation um dann die Ergebnisse zu betrachten.... Wenn man sich anschaut, was alles doppelt gemacht wird, dann findet sich hoffentlich noch die eine oder andere Optimierung. Aber das exponentielle Laufzeitverhalten hat man auf jeden Fall 🙂

 

[fhoffmann]

Wenn man sich anschaut, was alles doppelt gemacht wird, dann findet sich hoffentlich noch die eine oder andere Optimierung.

Es wäre auch mein Ehrgeiz, doppelte Elemente durch die Programmierung zu verhindern (und diesen Job nicht einer Menge (java.util.Set) zu überlassen).