4
\$\begingroup\$

Please review my answer for this interview question:

#include <iostream>
#include <vector>

std::vector<int> merge2Sorted ( std::vector<int> left, std::vector<int> right )
{
  //finger matching algo

  auto itLeft = left.begin();
  auto itRight = right.begin();

  auto itLeftEnd = left.end();
  auto itRightEnd = right.end();

  std::vector<int> result;
  result.reserve(std::max(left.size(),right.size())); 

  while ( itLeft != itLeftEnd && 
          itRight != itRightEnd )
  {
    if ( *itLeft < *itRight )
      result.push_back( *itLeft++ );
    else
      result.push_back( *itRight++ );
  }

  // copy rest of left array
  while ( itLeft != itLeftEnd )
    result.push_back(*itLeft++);

  // copy rest of right array
  while ( itRight != itRightEnd )
    result.push_back(*itRight++);

  return result;
}

int main ()
{
  std::vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
  std::vector<int> v2 = { -1,-2,0,3,7,9,11,12 };

  std::vector<int> v3 ( merge2Sorted ( v1, v2 ) );

  for ( auto& i: v3 )
    std::cout << i << std::endl;
}
\$\endgroup\$
7
\$\begingroup\$

Pass your parameters by const reference to avoid a copy:

std::vector<int> merge2Sorted(std::vector<int> const& left, std::vector<int> const& right)
//                                             ^^^^^^                        ^^^^^^

You are not reservng enough

result.reserve(std::max(left.size(),right.size()));

The result size will eventually be the size of the sum of the two input arrays.

result.reserve(left.size() + right.size());

Your test for left and right can be simplified:

if ( *itLeft < *itRight )
  result.push_back( *itLeft++ );
else
  result.push_back( *itRight++ );
}

// Simplified
// Though I am 50/50 on this one.
result.push_back( ( *itLeft < *itRight ) ? *itLeft++ : *itRight++);

No point in flushing the stream after every print:

std::cout << i << std::endl;

                  ^^^^^^^^^^  prefer '\n' unless you really want to force a flush.

std::cout << i << '\n';
\$\endgroup\$
0
2
\$\begingroup\$

In addition to Loki's answer you can also simplify copying the rest of the left and right arrays like so:

// Copy rest of left and right vectors
result.insert(result.end(), itLeft, itLeftEnd);
result.insert(result.end(), itRight, itRightEnd);

Oh and if you were doing this in production and not for an interview you could instead use std::merge:

#include <algorithm>

std::vector<int> merge2Sorted ( const std::vector<int>& left, const std::vector<int>& right ) {
    std::vector<int> output;
    std::merge(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(output));
    return output;
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.