Gute C++-Lösungen für die Interview-Herausforderung „Bring all the zeros to the back of the array“.

Lesezeit: 4 Minuten

Benutzer-Avatar
Gescheiterter Softwareentwickler

Ich hatte ein Vorstellungsgespräch für einen Jr.-Entwicklungsjob und er bat mich, eine Prozedur zu schreiben, die eine Reihe von Ints nimmt und die Nullen nach hinten schiebt. Hier sind die Einschränkungen (die er mir am Anfang nicht gesagt hat … Wie so oft in Programmierinterviews habe ich die Einschränkungen des Problems gelernt, während ich es gelöst habe, lol):

  • Muss es an Ort und Stelle tun; kein Erstellen von temporären Arrays, neuen Arrays usw.
  • Muss die Reihenfolge der Nicht-Null-Zahlen nicht beibehalten (ich wünschte, er hätte mir das am Anfang gesagt)

Konfiguration:

int arr[] = {0, -2, 4, 0, 19, 69}; 
/* Transform arr to {-2, 4, 19, 69, 0, 0} or {69, 4, -2, 19, 0, 0} 
   or anything that pushes all the nonzeros to the back and keeps
   all the nonzeros in front */

Meine Antwort:

bool f (int a, int b) {return a == 0;}
std::sort(arr, arr+sizeof(arr)/sizeof(int), f);

Was sind einige andere gute Antworten?

  • Ich finde deine Antwort super. Was hat der Interviewer gesagt?

    – Bartlomiej Lewandowski

    18. November 2014 um 20:46 Uhr

  • “Ich möchte Sachen auf diese Seite legen und die anderen Sachen auf diese Seite.” Das ist std::partition, Hände runter. Siehe meine Antwort.

    – Paul McKenzie

    18. November 2014 um 20:49 Uhr

  • Ihr Anruf an std::sort ist ungültig, weil Ihre Vergleichsfunktion a nicht herstellt strikte schwache Ordnung.

    – Benjamin Lindley

    18. November 2014 um 20:53 Uhr


  • @barakmanos: std::partition kann und garantiert O(n).

    – Benjamin Lindley

    18. November 2014 um 20:57 Uhr

  • Klugscheißer-Antwort: Überschreiben Sie jeden Eintrag im Array mit 0. Dies verstößt nicht gegen die aufgeführten Einschränkungen. O(n) Algorithmus.

    – Zeychin

    18. November 2014 um 21:03 Uhr

Benutzer-Avatar
Paul McKenzie

Vielleicht hat der Interviewer nach dieser Antwort gesucht:

#include <algorithm>
//...
std::partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

Wenn die Ordnung erhalten bleiben muss, dann std::stable_partition sollte benutzt werden:

#include <algorithm>
//...
std::stable_partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

Für Pre-C++11:

#include <functional>
#include <algorithm>
//...
std::partition(arr, arr + sizeof(arr)/sizeof(int), 
               std::bind1st(std::not_equal_to<int>(), 0));

Live-Beispiel

Wenn Sie Elemente, die eine Bedingung erfüllen, grundsätzlich auf “eine Seite” eines Containers verschieben müssen, sollten die Funktionen des Partitionsalgorithmus ganz oben auf der Liste der zu wählenden Lösungen stehen (falls nicht das zu verwendende Lösung).

  • Ist nicht partition immer noch O(NlogN)?

    – Jonathan Mei

    18. November 2014 um 20:54 Uhr

  • @JonathanMee – en.cppreference.com/w/cpp/algorithm/partition Für stable_partition wird es im schlimmsten Fall logarithmisch. en.cppreference.com/w/cpp/algorithm/stable_partition

    – Paul McKenzie

    18. November 2014 um 20:59 Uhr


  • Im Falle eines Interviews könnte es besser sein, das Lambda als zu schreiben [](const int &n){return n!=0;} oder vielleicht sogar [](const int &n)->bool{return n;}während Sie bereit sind, über die relativen Vorzüge von zu sprechen const int & gegenüber gerecht int. In beiden Fällen müssen keine Variablen erfasst werden.

    – Eduard

    18. November 2014 um 21:07 Uhr

  • Dies ist der klarste Weg. OTOH, seit std::partition() in Bezug auf Swaps implementiert ist, verursacht es einen konstanten Wert von unnötigem Kopieren.

    – j_random_hacker

    18. November 2014 um 21:11 Uhr

  • @j_random_hacker-Code für Klarheit vor Optimalität. Es ist jedoch gut zu wissen, wo sich CPU-Zyklen verstecken könnten.

    – Tim Seguine

    18. November 2014 um 21:17 Uhr


Ein sortierender Ansatz ist O(N*Log2N). Es gibt eine lineare Lösung, die wie folgt aussieht:

  • Richten Sie zwei Zeiger ein – readPtr und writePtrdie anfänglich auf den Anfang des Arrays zeigt
  • Machen Sie eine Schleife, die geht readPtr das Array bis zum Ende hoch. Wenn *readPtr nicht Null ist, kopieren Sie nach *writePtr, und beide Zeiger vorrücken; andernfalls nur vorab readPtr.
  • Einmal readPtr ist am Ende des Arrays, zu Fuß writePtr an das Ende des Arrays, während Nullen in die restlichen Elemente geschrieben werden.

  • Es sind noch weniger Schreibvorgänge erforderlich, wenn Sie Folgendes tun: Starten readPtr am Ende und laufe es rückwärts, bis es auf ein Element ungleich Null trifft oder writePtr (die wie bisher am Start beginnt). Wenn readPtr trifft writePtr, du bist fertig. Andernfalls traf es auf ein Element ungleich Null, also geh writePtr vorwärts, bis es auf ein Nullelement trifft oder readPtr. Wenn es trifft readPtr dann bist du fertig. Andernfalls trifft es auf ein Nullelement, also setzen Sie es auf *readPtreinstellen *writePtr auf Null und wiederholen. Nur die “out-of-position” Nullen und Nicht-Nullen müssen auf diese Weise kopiert werden.

    – j_random_hacker

    18. November 2014 um 21:07 Uhr

  • Das klingt sehr nach std::remove gefolgt von std::fill.

    – Benjamin Lindley

    18. November 2014 um 21:21 Uhr

Das ist O(n), also könnte es das sein, wonach er sucht:

auto arrBegin = begin(arr);
const auto arrEnd = end(arr);

for(int i = 0; arrBegin < arrEnd - i; ++arrBegin){
    if(*arrBegin == 0){
        i++;
        *arrBegin = *(arrEnd - i);
    }
}
std::fill(arrBegin, arrEnd, 0);

1018960cookie-checkGute C++-Lösungen für die Interview-Herausforderung „Bring all the zeros to the back of the array“.

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy