## Samsung Interview Question

Nones**Country:**India

**Interview Type:**Written Test

O(S^2 * N) time, where S is sum of the input pipes' lengths, and N is number of the pipes.

```
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void LargestPipes(vector<int> const &a, vector<int> &p1, vector<int> &p2, vector<int> &p1_out,
vector<int> &p2_out, int16_t &len_out, unordered_set<uint64_t> &memo,
int16_t len1 = 0, int16_t len2 = 0, int idx = 0)
{
if (idx < 0 ||
idx > a.size())
{
return;
}
if (len1 == len2 &&
len1 > len_out)
{
len_out = len1;
p1_out = p1;
p2_out = p2;
}
if (idx == a.size()) {
return;
}
uint64_t memo_key = (static_cast<uint64_t>(len1) << 48) | (static_cast<uint64_t>(len2) << 32) | idx;
if (memo.find(memo_key) != memo.end()) {
return;
}
memo.insert(memo_key);
p1.push_back(a[idx]);
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1 + a[idx], len2, idx + 1);
p1.pop_back();
p2.push_back(a[idx]);
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2 + a[idx], idx + 1);
p2.pop_back();
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2, idx + 1);
}
int main()
{
vector<int> p1, p2, p1_out, p2_out;
int16_t len_out;
unordered_set<uint64_t> memo;
LargestPipes({1, 2, 3, 4, 6}, p1, p2, p1_out, p2_out, len_out, memo);
for (int n : p1_out) {
cout << n << ", ";
}
cout << "\n";
for (int n : p2_out) {
cout << n << ", ";
}
cout << "\n";
}
```

- NoName December 12, 2017