1
\$\begingroup\$

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?..

\$\endgroup\$
8
  • \$\begingroup\$ It seems to me that your algorithm does not work. The only subarray in [9, 9, 7, 0, 0, 9, 4, 2, 4, 5] having K=2as the maximum element is [2], so the result should be 2 and not 11. \$\endgroup\$ – Martin R Jan 11 '18 at 12:25
  • \$\begingroup\$ @MartinR yes you were right.. I messed up the order of two lines.. It should be correct now. \$\endgroup\$ – Loser Jan 11 '18 at 12:35
  • \$\begingroup\$ Still looks wrong to me. [9, 9, 2, 0, 3, 6, 0, 1, 5, 6] has no subarray at all with K=4 as the maximum element. \$\endgroup\$ – Martin R Jan 11 '18 at 12:39
  • \$\begingroup\$ @MartinR I am not sure I understand.. In the output example is k=3 And the subarrays are thus {2,0,3} and {0,1} hence max sum is 2+0+3+1+0 = 6 \$\endgroup\$ – Loser Jan 11 '18 at 12:41
  • \$\begingroup\$ Sorry, my fault. But {0, 1} has the maximum 1 and not 3, so that does not count. – Does your code produce the expected results with all the test cases in practice.geeksforgeeks.org/problems/…? \$\endgroup\$ – Martin R Jan 11 '18 at 12:43
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
7
  • \$\begingroup\$ Quick question. Why do you need to make the argument of the lamda functions auto&& and not just auto&? \$\endgroup\$ – Blasco Jan 12 '18 at 12:27
  • 1
    \$\begingroup\$ @WooWapDaBug In the context of template deduction, && is what is called a 'universal reference': it will be deduced as a lvalue reference (e.g const int&) if given a lvalue as argument, or a rvalue reference if the argument is passed by value or rvalue (e.g int or object&&). Basically the compiler chooses the right option for you. \$\endgroup\$ – papagaga Jan 12 '18 at 13:19
  • \$\begingroup\$ But I don't get what's the point there. Isn't find_if passing things by value? can't you just do auto& to get it by reference? I think that the purpose is to avoid a copy, doesn't auto& achieve it? Sorry for my ignorance and thank you for the explanation \$\endgroup\$ – Blasco Jan 12 '18 at 14:26
  • \$\begingroup\$ @WooWapDaBug No point here, you're right, just a good practice. auto&&does it always right, so why bother choosing the right signature by your self? In other places you could find iterators which don't return lvalue references, like move_iterator. \$\endgroup\$ – papagaga Jan 12 '18 at 15:01
  • 1
    \$\begingroup\$ auto& can't bind to a rvalue reference, so it wouldn't compile I guess \$\endgroup\$ – papagaga Jan 12 '18 at 16:28

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.