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?

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

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.

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

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