C++ Interview preparation questions - Find the maximum sum of subarray in array

Question

I am currently prepping for C++ interview question, by answering some I found on the internet. I don't think my solution is the best, but on the other hand, I am not sure what else would be a better solution, which is why I guess hearing other people's opinion would be great.

Question being:

Given an array of N elements, you are required to find the maximum sum of lengths of all non-overlapping subarrays with K as the maximum element in the subarray.

Example:

Input : arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4} 
        k = 4
Output : 5
{2, 1, 4} => Length = 3
{3, 4} => Length = 2
So, 3 + 2 = 5 is the answer

Here is my solution:

#include <stdio.h>
#include <random>
#include <iostream>
#include <vector>
#include <algorithm>

int main() {

  std::random_device rd;  
  std::mt19937 gen(rd()); 
  std::uniform_int_distribution<int> distribution(0,9);

  int arr[10];

  int  k = distribution(gen);
  for (int i = 0; i < 10; ++i)
  {
      arr[i] = distribution(gen);;
      std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  std::cout << "K: " << k << std::endl; 

  std::vector<int> start_index;
  std::vector<int> end_index;
  std::vector<int> sum;

    for (int i = 0; i<10; ++i)
    {
        int subarray_sum = 0;  
        if(arr[i] <= k)
        {
            start_index.push_back(i);
            subarray_sum += arr[i];
            ++i;
            while(arr[i] <= k && i<10) 
            {
                subarray_sum += arr[i];
                ++i;
            }
            end_index.push_back(i-1);
            sum.push_back(subarray_sum);
            std::cout << "sum: " << subarray_sum << std::endl; 
        }
    }

  std::cout << "length of sums: " << sum.size() << std::endl;
  std::cout << "number of start_index: " << start_index.size() << std::endl; 
  std::cout << "number of end_index: " << end_index.size() << std::endl; 

  std::cout << "-------------Compute max subarray_sum length-----------------" << std::endl; 
  if(sum.size() > 1)
  {
    std::vector<int>::iterator iterator1 = std::max_element(sum.begin(),sum.end());
    int position1 = iterator1 - sum.begin();
    std::cout << position1 << std::endl; 

    int length1 = end_index[position1]- start_index[position1]+1; //+1 because they don't zero-index

    sum.erase(sum.begin() + position1);
    start_index.erase(start_index.begin() + position1);
    end_index.erase(end_index.begin()+position1);

    std::cout << "length of sums: " << sum.size() << std::endl;
    std::cout << "number of start_index: " << start_index.size() << std::endl; 
    std::cout << "number of end_index: " << end_index.size() << std::endl; 


    std::vector<int>::iterator iterator2 = std::max_element(sum.begin(),sum.end());
    int position2 = iterator2 - sum.begin();
    std::cout << position2 << std::endl; 

    int length2 = end_index[position2]- start_index[position2]+1; //+1 because they don't zero-index


    sum.erase(sum.begin() + position2);
    start_index.erase(start_index.begin() + position2);
    end_index.erase(end_index.begin()+position2);

    std::cout << "length1: " << length1 << " " << std::endl 
              << "length2: " << length2 << std::endl 
              << "legnth Sum: " << length1 + length2 << std::endl; 


  }
  else if ( sum.size() == 1)
  {
    std::vector<int>::iterator iterator1 = std::max_element(sum.begin(),sum.end());
    int position1 = iterator1 - sum.begin();
    std::cout << position1 << std::endl; 

    int length1 = end_index[position1]- start_index[position1]+1; //+1 because they don't zero-index
    std::cout << "max length sum: " << length1 << std::endl;

  }

  else
  {
    std::cout << "None fit criteria" << std::endl; 
  }
    return 0;
}

output:

2 3 0 7 5 8 5 5 4 8 
K: 0
sum: 0
length of sums: 1
number of start_index: 1
number of end_index: 1
-------------Compute max subarray_sum length-----------------
0
max length sum: 1

output:

2 3 4 1 8 0 0 0 1 4 
K: 4
sum: 10
sum: 5
length of sums: 2
number of start_index: 2
number of end_index: 2
-------------Compute max subarray_sum length-----------------
0
length of sums: 1
number of start_index: 1
number of end_index: 1
0
length1: 4 
length2: 5
legnth Sum: 9

output:

5 1 7 5 2 6 1 4 0 9 
K: 4
sum: 1
sum: 2
sum: 5
length of sums: 3
number of start_index: 3
number of end_index: 3
-------------Compute max subarray_sum length-----------------
2
length of sums: 2
number of start_index: 2
number of end_index: 2
1
length1: 3 
length2: 1
legnth Sum: 4

Any way I could make the solution better?..

Answer 1

You haven't shown any of the unit tests. In fact, the way the program is structured (with everything in main()) strongly suggests that there are no unit tests. This immediately reduces confidence in the code.

I'd start by restructuring so we have a simple function to call. I'll make it accept an iterator pair, to act like standard algorithms:

#include <cinttypes>

template<typename ForwardIterator, typename Value>
std::size_t total_length_of_segments_having_max_value(ForwardIterator first, ForwardIterator last, const Value& value);

We can then write some tests:

#include <vector>

int main()
{
    const std::vector<int> v1{ 2, 1, 4, 9, 2, 3, 8, 3, 4 };
    auto const first = v1.begin();
    auto const last = v1.end();

    // start by testing an empty input
    TEST_ASSERT_EQUALS(0, total_length_of_segments_having_max_value(first, first, 2));

    TEST_ASSERT_EQUALS(5, total_length_of_segments_having_max_value(first, last, 4));
    TEST_ASSERT_EQUALS(0, total_length_of_segments_having_max_value(first, last, 10));
}

(I leave the implementation of TEST_ASSERT_EQUALS() as an exercise - or you can modify to fit your favourite testing framework.)

With the tests in place, we can write a suitable implementation and refine it as we improve the code, with confidence that we're not breaking anything that previously worked.

Answer 2

Reuse the standard algorithms! It will give your code much more expressiveness, and they are very optimized. For example:

#include <algorithm>
#include <iterator>
template <typename Iterator>
int max_subsets_length_with_max(Iterator first, Iterator last, int k) {
    auto begin_subset = std::find_if(first, last, [k](auto&& elem) { return elem <= k; });
    if (begin_subset == last) return 0;
    auto end_subset = std::find_if(begin_subset, last, [k](auto&& elem) { return elem > k; });
    if (std::find(begin_subset, end_subset, k) != end_subset) {
        //std::cout << "subset [" << *begin_subset << " , " << *end_subset << "]\n";
        return std::distance(begin_subset, end_subset) + max_subsets_length_with_max(end_subset, last, k);
    }
    return max_subsets_length_with_max(end_subset, last, k);
}