C++ Interview Fragen

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.

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?

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)

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?

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;
}

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

@volkard: wie unterscheidet sich dein algo von der bitset loesung bezueglich performance?

volkard

wernerschwarz schrieb:

@volkard: wie unterscheidet sich dein algo von der bitset loesung bezueglich performance?

Mache mir nicht die Mühe, es zu messen. Geraten hat eine Multiplikation 6 Takte und dafür kannste locker im bitset fummeln, aber wenns bitset größer wird als der Cache, wirds Malnehmen wirder besser. Kannst dann aber bei uint32 doch nur bis 60000 oder so gehen, das würde eh passen. Oder auf uint64 sammeln, dann gehts vom Zahlenbereich schon ok. Mhhm, darf man die Eingabezahlen auch zweimal sehen, Array zweimal durchlaufen, Datei zweimal lesen, dann könnte man in beiden Läufen sich auf sqrt(N) Bits bescheiden.
Also das Multiplizieren halte ich nicht für angebracht, hab's als Spaßantwort rausgehauen.

irgendwelche anderen fragen?

Dobi

Wenns wirklich C++-spezifisch sein muss, dann vielleicht sowas

- Was sind pure virtual functions?
- Warum keine exceptions im Dtor werfen?
- Was ist RAII?
- Was für Probleme kann man sich mit virtual inheritance einhandeln?

(Sorry wenn die Sachen schon hier im Thread vorkamen.)

Ansonsten würd ich aber eher versuchen, allgemeinere Skills rauszufinden.

- Was ist eine closure?
- Erfahrung mit Versionsverwaltung?
- Was hast du so in der letzten Zeit gelesen? Bücher? Blogs? Foren? /r/programming? etc
- Was für andere Programmiersprachen kennst du? (Gucken, ob du aus Spaß auch mal was neues lernst.)
- Erzähl mal was über funktionale und imperative Programmierung.
- Und über statische und dynamische typisierung.
- Schonmal TDD ausprobiert?
- Erzähl was mal zu nem Design-Pattern deiner Wahl.
- Wann smellt code für dich?
- Kennst du den Joel-Test?
- Zeig mal irgendein Projekt von dir.

Und dann natürlich so soft-skill/Persönlichkeits-Zeug, was aber nicht spezifisch für Programmierer-Vorstellungsgespräche ist.

Das ist jetzt aber mehr so spontan hingeschrieben. Für ein tatsächliches Gespräch würde ich mir wahrscheinlich mehr Gedanken machen.

Achja, und vielleicht einfach vor irgendeine codility-Aufgabe oder so setzen und dich dabei erklären lassen und zugucken.

Hier scheints auch einiges nettes zu geben. Hab aber noch nicht alles gelesen: http://www.reddit.com/r/cscareerquestions/wiki/index

Dobi schrieb:

...

gut, dass ihr alles nichts zu entscheiden habt

Dobi

Wie angedeutet. Ich bin kein Interviewer, sondern hab nur spontan auf die Frage geantwortet. Um tatsächlich herausfinden zu können, ob ein Kandidat was drauf hat, müsste ich mich vermutlich mehr mit dem Thema auseinandersetzen.
Gibt es irgendwas spezielles an meinem Post, was dir besonders schlecht gefallen hat, oder war in deinen Augen einfach alles Müll?

volkard

qweasdyxc schrieb:

Dobi schrieb:

...

gut, dass ihr alles nichts zu entscheiden habt

Dobi

Lol, dann sagt doch mal bitte, was daran doof ist und wie man es besser machen könnte. Nicht, dass tatsächlich irgendwann der unwahrscheinliche Fall eintritt, dass ich in die Situation komme und nur Unfug frage.