29.9.2021 |

Coding interview à la Google

Die folgenden Abschnitte beziehen sich auf das YouTube Video “How to: Work at Google — Example Coding/Engineering Interview” und wird etwas einfacher dargestellt. In diesem Video wird ein Vorstellungsgespräch von zwei Google-Ingenieuren demonstriert und es werden die besten Praktiken für ein Vorstellungsgespräch bei Google erläutert.

Aufgabe: Gegeben ist ein Array mit Zahlen. Gibt es ein Paar aus zwei Zahlen, welche gemeinsam die Summe einer gesuchten Zahl ergibt?

Schritt 1 (Im Kopf überlegen was überhaupt verlangt wird bzw. Was das konkret bedeutet) [1, 2, 3, 9] Sum = 8 —> No

[1, 2, 4, 4] Sum = 8 —> Yes

Erster (intuitiver) Ansatz: Jede Zahl mit jeder anderen einmal addieren und gucken ob die gewünschte Summe bei raus kommt.
public static boolean hasPairWithSum(int dataArray[], int sum){
    for(int i=0; i < dataArray.length-1; i++){
        for(int j=i+1; j< dataArray.length; j++){
            if(dataArray[i]+dataArray[j] == sum) return true;
        }
    }
    return false;
}
Komplexität? Komplexität der Zeit: O(n^2)

Komplexität des Raums: 1

Funktioniert, ist aber nicht schön und bei vielen Zahlen leidet die Performance. Wie gehts also besser?

Folgende Fragen könnte man stellen:

  • Um was für Zahlen handelt es sich? bsp. Positive, Negative, Ganz oder Kommazahlen?
  • Was ist die kleinste Zahl, was kann die größte Zahl sein (Edge Cases)?
  • Können Zahlen beliebig oft vorkommen?
  • Sind die Zahlen beliebig oder sortiert?

Antworten: Positive und Negative, ganze Zahlen, Zahlen können doppelt vorkommen, kleinste Zahl = 1, größte Zahl = “beliebig” groß, sortierte Reinfolge.

Besserer Ansatz: Durch die Informationen, dass die Zahlen sortiert sind könnte man auf eine Art “Binäre-Suche” kommen. Dies verbessert die Laufzeit auf Komplexität der Zeit: O(n*log(n)). Allerdings kann der Algorithmus sogar noch schneller sein! Wenn das Array sortiert ist könnte man ja immer ein kleines + ein großes Element mit der gesuchten Summe vergleichen.
public static boolean hasPairWithSum(int dataArray[], int sum) {
    int low = 0;
    int high = dataArray.length - 1;
    while (low < high) {
        if (sum < dataArray[low] + dataArray[high]) {
            high = high - 1;
        } else{
            low = low + 1;
        }
        if(dataArray[low] + dataArray[high] == sum){
            return true;
        }
    }
    return false;
}
Komplexität? Komplexität der Zeit: O(n)

Komplexität des Raums: 1

Quintessenz aus dem Video:

  1. Lass deine Kollegen/ Interviewpartner/ Mitmenschen/ etc. an deinen Gedanken teil haben
  2. Frag soviel wie nötig über die Aufgabe und mach dir Gedanken über die Randfälle
  3. Überprüfe deinen Code für alle Testfälle
  4. Mach dir bewusst wo die Vorteile und Nachteile gewisser Algorithmen und Datenstrukturen sind
Zur Übersicht
Patrick Schaper

Mehr vom Devsquad...

Adrian Görisch

Domain Driven Design in Angular

Jonathan Zbick

Wireless debugging Android

Hallo

Wir sind für Sie da und freuen uns auf Ihre Fragen oder Ihr Feedback.

* Pflichtfeld