C++ Interview Fragen

[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?

[wernerschwarz]

bitset?

#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>

void find_missing_numbers(std::vector<unsigned int> &vec) {
	auto N = *max_element(vec.begin(), vec.end());
	std::bitset<100> map; // 100 sollte eigentlich N sein

	for(auto i = 0; i < vec.size(); i++) {
		map.set(vec[i]);
	}

	for(auto i = 1; i <= N; i++) {
		if(map.test(i) == 0) {
			std::cout << "missing number: " << i << std::endl;
		}
	}
}

int main() {
	std::vector<unsigned int> vec = {1, 4, 5};

	find_missing_numbers(vec);

	return 0;
}

[wernerschwarz]

@Arcoth: ich hatte vergessen zu sagen, dass die zahlen im array nicht sortiert sein muessen

[Columbo]

Scheisse, ich bin in der Schule und kann nicht mitmachen :sad:

Ich haette allerdings auch auf ein Bitset getippt (P.S.: nimm einfach vector<bool> )

[camper]

volkard schrieb:

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ß.

Und das lässt sich dann auch schön erweitern zumindest bist zu 5 fehlenden Zahlen, indem man höhere Potenzen verwendet. Ab 6 Zahlen wird es evtl. etwas schierig, die entsprechenden Gleichungen zu lösen, vielleicht kann man noch etwas machen, weil man weiss, dass es ganze Zahlen sein müssen (bin mit diophantischen Gleichungssystemen nicht besonders gut vertraut).

Ich überlege, ob man evtl. auch eine xor-Verknüpfung verwenden kann.
1²3^...N ist ja auch trivial zu ermitteln.

Allerdings bin ich etwas unsicher, ob ein System der Form
x + y = a
x ^ y = b
für gegebene a,b eindeutig und einfach zu ermitteln ist.

[volkard]

camper schrieb:

Allerdings bin ich etwas unsicher, ob ein System der Form
x + y = a
x ^ y = b
für gegebene a,b eindeutig und einfach zu ermitteln ist.

Kam mit dieser Überlegung auch nicht weiter, bis Du sie hier nochmal angesprochen hast. Gegenbeispiel:

x+y=15
x^y=15

Aha, kein Übertrag passiert, hier sind + und ^ leider gleich, alle 0<=x<=15 sind möglich.