CODEWITHSUNDEEP
c++algorithm
Failed Software Developer
Failed Software Developer

Reputation: 401

Good C++ solutions to the "Bring all the zeros to the back of the array" interview challenge

I had an interview for a Jr. development job and he asked me to write a procedure that takes an array of ints and shoves the zeroes to the back. Here are the constraints (which he didn't tell me at the beginning .... As often happens in programming interviews, I learned the constraints of the problem while I solved it lol):

Setup:

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 */

My answer: 

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

What are some other good answers?

Upvotes: 6

Views: 483

Answers (3)

PaulMcKenzie
PaulMcKenzie

Reputation: 35454

Maybe the interviewer was looking for this answer:

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

If the order needs to be preserved, then std::stable_partition should be used:

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

For pre C++11:

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

Live Example

Basically, if the situation is that you need to move items that satisfy a condition to "one side" of a container, then the partition algorithm functions should be high up on the list of solutions to choose (if not the solution to use).

Upvotes: 16

Jonathan Mee
Jonathan Mee

Reputation: 38939

This is O(n) so it may be what he's looking for:

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

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726879

An approach that sorts is O(N*Log2N). There is a linear solution that goes like this:

  • Set up two pointers - readPtr and writePtr, initially pointing to the beginning of the array
  • Make a loop that walks readPtr up the array to the end. If *readPtr is not zero, copy to *writePtr, and advance both pointers; otherwise, advance only readPtr.
  • Once readPtr is at the end of the array, walk writePtr to the end of the array, while writing zeros to the remaining elements.

Upvotes: 2

Related Questions