Dies ist eine Interviewfrage, der ich in letzter Zeit gegenüberstand.
Wenn Sie ein Array von 1 und 0 angeben, finden Sie eine Möglichkeit, die Bits in place so zu partitionieren, dass 0s zusammen gruppiert und 1s zusammen gruppiert werden. Es spielt keine Rolle, ob 1s vor Nullen stehen oder Nullen vor 1en sind.
Eine Beispieleingabe ist 101010101 und Ausgabe ist entweder 111110000 oder 000011111 .
Lösen Sie das Problem in weniger als linearer Zeit.
Machen Sie das Problem einfacher. Die Eingabe ist ein Integer-Array, wobei jedes Element entweder 1 oder 0 ist. Output ist das gleiche Integer-Array mit ganzen Partitionen, die gut partitioniert sind.
Für mich ist das eine einfache Frage, wenn sie in O (N) gelöst werden kann. Mein Ansatz besteht darin, zwei Zeiger zu verwenden, die an beiden Enden des Arrays beginnen. Erhöht und verringert jeden Zeiger; Wenn es nicht auf die richtige Ganzzahl zeigt, vertauschen Sie die beiden.
%Vor%Allerdings besteht das Interview darauf, dass es eine sublineare Lösung gibt. Das lässt mich stark nachdenken, bekomme aber immer noch keine Antwort.
Kann jemand bei dieser Interviewfrage helfen?
UPDATE : Da die Antworten in SO anzeigen, dass das Problem nicht in sublinearer Zeit gelöst werden kann, kann ich meine ursprüngliche Idee bestätigen, dass es keine Lösung von sublinearen geben kann.
Ist es möglich, dass der Interviewer einen Trick spielt?
Ich sehe nicht, wie es eine Lösung schneller als lineare Zeit geben kann.
Stellen Sie sich ein Bit-Array vor, das alle Einsen ist. Jede Lösung erfordert, jedes Bit in diesem Array zu untersuchen, bevor es erklärt, dass es bereits partitioniert ist. Die Untersuchung jedes Bits dauert linear.
Es ist nicht möglich. Wenn Sie es in weniger als linearer Zeit tun, bedeutet dies, dass Sie nicht jedes Array-Element (wie eine binäre Suche) betrachten. Da es jedoch keine Möglichkeit gibt zu wissen, was ein Element des Arrays ist, ohne es zu betrachten, müssen Sie jedes Array-Element mindestens einmal betrachten.
Sie können Nachschlagetabellen verwenden, um es schneller zu machen, aber O (n / 8) ist immer noch O (n), also war entweder der Interviewer falsch oder Sie haben die Frage falsch verstanden.
Es ist möglich, schneller als in linearer Zeit, vorausgesetzt, Sie haben genug Speicher, kann es in O (1)
getan werdenVerwenden Sie die Bitmaske als Index in einem Vektor, der der partitionierten Bitmaske zugeordnet ist.
Mit Ihrem Beispiel wird bei Index 341 (101010101) der Wert 496 (111110000) gespeichert.
Vielleicht kommt die Verwirrung von "weniger als linearer Zeit". Zum Beispiel zählt diese Lösung die Anzahl der Bits, die eine Maske bilden, die so viele Bits enthält. Es zählt nur Bits, wenn unzählige On-Bits vorhanden sind:
%Vor%Obwohl dies die Anzahl der zu zählenden Bits minimiert, ist es immer noch linear. Wenn das mit "sublinear" gemeint ist, dann gehen Sie.
Aber wenn sie wirklich sublinear wie logarithmisch oder konstant meinten, sehe ich keinen Weg. Sie könnten für jeden Wert eine Nachschlagetabelle erstellen, aber: /
Nun .. Es kann 'weniger als lineare' Zeit (freche Methode) durchgeführt werden.
%Vor%Also gruppieren Sie die Bits technisch in weniger als linearer Zeit: P
Für mich sind die wahrscheinlichsten Interpretationen:
Die Bits sollen in einem int statt in einem Array sein. In diesem Fall können Sie etwas wie Ссылка oder eine 8-Bit (oder mehr) Lookup-Tabelle.
sie verwendeten "sublinear", um "weniger als n Operationen" und nicht weniger als "O" (n) zu bezeichnen. Aber auch das scheint aus den gleichen Gründen unmöglich zu sein.
In der Frage gibt es ein weiteres Missverständnis
Ansonsten ist die Frage falsch, da alle Elemente des Arrays untersucht werden müssen, um die Antwort zu bestimmen, und das sind mindestens 'n' Operationen.
Nennt zuerst entweder 0s oder 1s, und die Verweise auf Bits statt auf Boole lassen mich denken, dass etwas wie die erste Option gemeint ist, obwohl es, wenn es nur mit einem Wort zu tun hat, keinen großen Unterschied macht. Ich bin neugierig zu wissen, was der Interviewer eigentlich vorhat.
Die Aufteilung dieser Arbeit auf parallele Prozessoren kostet nur dann N / M (oder O (N)), wenn Sie annehmen, dass die Parallelität langsamer zunimmt als die Problemgröße. In den letzten zehn Jahren hat der Paralellismus (über die GPU) schneller zugenommen als typische Problemgrößen, und dieser Trend scheint sich über die nächsten Jahre fortzusetzen. Für eine breite Klasse von Problemen ist es lehrreich, "unendliche Parallelität" oder genauer gesagt "Parallelität größer als jede erwartete Problemgröße" anzunehmen, weil der Fortschrittsmarsch bei GPUs und Cloud Computing so etwas im Laufe der Zeit bietet.
Unter der Annahme unendlicher Parallelität kann dieses Problem in O (logN) -Zeit gelöst werden, da der Additionsoperator, der zum Addieren aller 0 und 1 Bits benötigt wird, assoziativ ist und Es erfordert also mindestens logN Zeitschritte abzuschließen.
Tags und Links c++