C++ Interview Fragen

[wernerschwarz]

nettest video
https://www.youtube.com/watch?v=WdwaPUWtT-Y

[TyRoXx]

Wenn man nur jemanden sucht, der Java mit Sternchen produzieren kann, reichen Kindergartenaufgaben und dämliche Quizfragen.

Wenn man selbst nur mit Ach und Krach Java mit Sternchen kann, ist es egal was man im Interview fragt. Bei so jemandem würde Bjarne Stroustrup als Bewerber nicht unbedingt besser abschneiden als Hans Wurst, der mal ein PHP-Videotutorial gesehen hat.

wernerschwarz schrieb:

nettest video
https://www.youtube.com/watch?v=WdwaPUWtT-Y

void repeat_n(unsigned int n, std::function<void ()> const &f)
{
    for (auto i = 0; i < n; ++i) {
        f();
    }
}

Der hat C++ so ungefähr verstanden. Aber er achtet nicht gut genug auf Details. Wenn er Warnungen aktiviert hätte, wüsste er, dass der Vergleich i < n nicht portabel ist. Denn i hat er signed gemacht und n unsigned . Es gibt Werte für n , bei denen ++i überlaufen wird, was undefiniertes Verhalten hat.
Vor allem ist f viel zu teuer für so einen trivialen Algorithmus. Da hätte ein guter C++-Programmierer ein Template benutzt.
Er könnte function vermutlich nicht korrekt implementieren. (EDIT: OK, bei 5:56 sagt er immerhin, dass er das nicht könnte.)

[nwp3]

Ich hab was wieder gefunden: Deep C. Diesmal habe ich besser abgeschnitten, aber immernoch voreilig und falsch geantwortet

[hustbaer]

simple schrieb:

Trotzdem kann man an der Art wie diese Frage beantwortet wird schon eine Menge über den Bewerber erfahren.

Jain.
Die richtige Antwort wäre nämlich: nix.

[Qwertiop]

Zitat:
Hab erstmal Minuten einen Schrecken gekriegt, weil ich dachte, Rechtecke sollten gezählt werden.

Ist doch beides in O(1) Zeit lösbar? Also wozu rekursive Lösungen abfragen?

Ja, aber die Summenformel hat kaum jemand (mich ein geschlossen) auswendig parat. Bis jetzt ist im interview auch noch niemnd darauf gekommen. Sollte das doch mal der Fall sein, frage ich trotzdem nach einem iterativen/rekursiven Ansatz!

[Columbo]

Bis jetzt ist im interview auch noch niemnd darauf gekommen.

Ist doch echt nicht schwer...

für Quadrate ist es sogar trivial. Ich würde so anfangen: Jede Quadratgröße durchgehen. Wenn das große Quadrat Seitenlänge N hat, dann gibt es von Quadraten der Seitenlänge $1 \leq n \leq N$ genau $(N - n + 1)^2$.
Also:
$\sum \limits_{n = 1}^{N} (N - n + 1)^2 ~=~ \sum \limits_{n = 1}^{N} (N^2 + 2N - 2nN + n^2 -2n + 1)$
$~=~ N^3 + 2N^2 - 2N\frac{N(N+1)}{2} + \sum \limits_{n = 1}^{N} (n^2 -2n + 1)$
$~=~ N^3 + 2N^2 - 2N\frac{N(N+1)}{2} + \frac{1}{6}N(N+1)(2N+1) - N(N+1) + N$
Ist sicher falsch, habe das ohne Stift&Papier gemacht... :p

Edit: Die Summenformel für $N^2$ kannte ich nur auswending weil wir das gerade in der Schule nebenbei angesprochen haben.

[volkard]

$\sum \limits_{n = 1}^{N} (N - n + 1)^2 ~=~ \sum \limits_{n = 1}^{N} n^2 ~=~$

Arcoth schrieb:

Edit: Die Summenformel für N2 kannte ich nur auswending weil wir das gerade in der Schule nebenbei angesprochen haben.

Deswegen das Schleifchen, falls man gerade keine Formelsammlung zur Hand hat.

[Columbo]

volkard schrieb:

$\sum \limits_{n = 1}^{N} (N - n + 1)^2 ~=~ \sum \limits_{n = 1}^{N} n^2 ~=~$

Whups.

Wie peinlich.

[Columbo]

Gut, für Rechtecke ist es dann praktisch genauso trivial:
$\sum \limits_{a = 1}^{N} \sum \limits_{b = 1}^{N} ((N - a + 1)(N - b + 1))~=~ \sum \limits_{a = 1}^{N} \sum \limits_{b = 1}^{N} ab ~=~ (\frac{N(N+1)}{2})^2$
(oder?)

Also ich hätte mich längst rausgeschmissen

[Qwertiop]

Arcoth schrieb:

Also ich hätte mich längst rausgeschmissen

Nein, eben nicht. Gerade darum geht es ja: Kenntnisse strukturiert anwenden (Am Whiteboard ist das einfacher, wenn man sich ein Schachbrett aufmalt). Aber genau da scheitern schon viele - von einer Implementierung ganz zu schweigen.

[wernerschwarz]

Folgende Aufgabe ist auch nett:

Gegeben ist ein Array mit Zahlen von 1 bis N. Insgesamt gibt es N-2 Elemente. Finde die 2 fehlenden Zahlen.
Beispiel:
Input: 1, 4, 5
Der Algo soll als Ouput liefern: 2, 3

[Columbo]

Also wenn eine Reihe von Zahlen gegeben ist, und die nächsten gefragt wären, hätte ich Lagrange Interpolating Polynomial vorgeschlagen. Allerdings sind hier nur lineare Verhältnisse vorhanden, daher: Zu einfach.

Warum wird nicht mal was mit Zahlentheorie gefragt? Ich meine, so für Uni-Absolventen?

[wernerschwarz]

@Arcoth: kannst du den algo zu meiner aufgabe schreiben? Lagrange Interpolating Polynomial scheint mir doch etwas overhead dafuer?

[volkard]

wernerschwarz schrieb:

Gegeben ist ein Array mit Zahlen von 1 bis N. Insgesamt gibt es N-2 Elemente. Finde die 2 fehlenden Zahlen.

Ich könnte Summe und Produkt ausrechnen.

[wernerschwarz]

@volkard: yes!

[camper]

wernerschwarz schrieb:

Folgende Aufgabe ist auch nett:

Gegeben ist ein Array mit Zahlen von 1 bis N. Insgesamt gibt es N-2 Elemente. Finde die 2 fehlenden Zahlen.
Beispiel:
Input: 1, 4, 5
Der Algo soll als Ouput liefern: 2, 3

Erinnert mich an eine Aufgabe von volkard in einem Coding-Contest vor einigen Jahren.

Was wenn N ein bisschen größer werden kann und keine Bignums zur Verfügung stehen und auch nicht nachgebaut werden sollen?

[qweasdyxc]

Arcoth schrieb:

Warum wird nicht mal was mit Zahlentheorie gefragt? Ich meine, so für Uni-Absolventen?

Ich glaube du hast eine falsche Vorstellung davon, was man nach Uni-Abschluss über Mathevorlesungen im Grundstudium noch so im Kopf hat. Ich könnte spontan nichtmal mehr den Erweiterten Euklidischen Algorithmus ausführen...

[volkard]

Für 1+2+3+...+N und 1²⁺²2+3^2+...+N2 hat arcoth ja schon die Summenformeln herbeigezaubert.
Statt des Produkts reicht die Summe der Quadrate, die wird nicht so elend groß. Das Produkt frisst ja mehr Speicher und viel mehr Zeit als jedes Bitfield.

Der Algo soll als Ouput liefern: 2, 3

a^2+b2=13
a+b=5

(a+b)^2=**5**2
a^2+2ab+b2=5^2
2ab=5^2-13
ab=(5^2-13)/2
(weiter wie gehabt)

[qweasyxc]

Qwertiop schrieb:

Arcoth schrieb:

Also ich hätte mich längst rausgeschmissen

Nein, eben nicht. Gerade darum geht es ja: Kenntnisse strukturiert anwenden (Am Whiteboard ist das einfacher, wenn man sich ein Schachbrett aufmalt). Aber genau da scheitern schon viele - von einer Implementierung ganz zu schweigen.

Es erzeugt ja auch eine ungute Prüfungssituation wenn jemand hinter einem steht und man eben mal unter Beobachtung und Leistungsdruck eine Aufgabe lösen soll. Auch bei so einer ansonsten einfachen Aufgabe setzt das Hirn gerne mal aus unter solchen Bedingungen.

[Columbo]

Warum nicht einfach durchgehen und pruefen, wo die Zahlen fehlen? Ich missverstehe die Aufgabe.

Edit: Kann mal jemand einen nichttrivialen Input aufzeigen?