Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

Assumptions:
- There is no negative weight
- Multiple weights can occure as in the smaple given
- I assume first k-weight means max the top-k, according to summed weight

Approach:
- clearly, if the input was sorted according to weight, the highest is the one with all
balls (if no neg. weights)
- the next lower is when excluding the element with least weight
- the next lower is excluding the 2nd lowest weight
- the third is either excluding the 3rd lowest or the 2nd and lowest

The basic idea is pretty straight forward:
- sort input as described above
- maintain a priority queue with the highest combination on top
- When picking an element from that queue, calculate the next options, where it is
not straight forward to decide which will be the next higher one. Put all of them into
the queue, then next loop the highest is picked etc. That is similar to Dijkstra
shortest path. But in order to be efficient, I only calculate next elements when an
item gets picked and this needs a bith of thought, but I can create a tree, similar to
a Fenwick on the fly ...
When an item is picked there are at most two new options, one is to take the next
element, the other is to take the current element and the lowest possible
- For the time complexity, there is the issue we need to produce the results which is
O(n*k). Then there is the sort which is O(n*lg(n)) and the maintenance of the queue which
is O(k*lg(k)). The queue component is irrelevant since always smaller than the sort. Then
there are some copy operations inside the algo, which are executed at most 2k times, thus
resulting in O(k*n). Overall it is O(n*k + n*lg(n)) - depending on the input one or the
other term dominiates.

Cool question, never saw this one, really nice! Although a bit hard to come up with the
"next element" algorithm in 30 minutes together with all the rest.

``````#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
using uint = unsigned int;

void print_top_k_subsets(const vector<pair<string, uint>>& input, uint k)
{
if (input.size() < 1 || k < 1) return;
uint result_count = 0;

// sort
auto sinput(input); // sorted input, smallest weight first
sort(sinput.begin(), sinput.end(),
[](const pair<string, uint>& a, const pair<string, uint>& b) {
return a.second < b.second;
});

// queue with queitem having least loss on top
struct QueueItem {
int weight_loss;
int last_excluded;
int last_excludable;
vector<bool> excluded;
};
auto qcomp = [](const QueueItem& a, const QueueItem& b) {
return a.weight_loss > b.weight_loss;
};
priority_queue<QueueItem, vector<QueueItem>, decltype(qcomp)> q(qcomp);
q.push(QueueItem({0, -1, static_cast<int>(sinput.size() - 1), vector<bool>(sinput.size(), false)}));

while (!q.empty() && result_count < k) {
QueueItem current = q.top(); // copies the vector, not so nice
q.pop();

// print result (should be put into a seperate function)
result_count++;
cout << result_count << "th: {";
int sum = 0;
bool first = false;
for (int i = 0; i < sinput.size(); ++i) {
if (!current.excluded[i]) {
sum += sinput[i].second;
cout << (first ? ", " : "") << sinput[i].first;
first = true;
}
}
cout << "} sum=" << sum << endl;

// get next potential candidates and put it into the queue
if (current.last_excluded > 0) {
QueueItem new_item(current);
new_item.weight_loss += sinput[0].second;
new_item.last_excludable = current.last_excluded - 1;
new_item.last_excluded = 0;
new_item.excluded[0] = true;
q.push(new_item);
}
if (current.last_excluded < current.last_excludable) {
if (current.last_excluded >= 0) {
current.weight_loss -= sinput[current.last_excluded].second;
current.excluded[current.last_excluded] = false;
}
current.last_excluded++;
current.weight_loss += sinput[current.last_excluded].second;
current.excluded[current.last_excluded] = true;
q.push(current);
}
}
}

int main()
{
cout << "sample 1" << endl << "-----------------------------" << endl;
print_top_k_subsets({ {"red", 4}, {"yellow", 1}, {"green", 2}, {"blue",  2} }, 5);
cout << "sample 2" << endl << "-----------------------------" << endl;
print_top_k_subsets({ { "red", 4 },{ "yellow", 1 },{ "green", 2 },{ "blue",  2 }, {"amber", 1}, {"black", 2}, {"white", 1} }, 15);``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Ari. For the example in the description, it would look like:
4, 2, 2, 1, sum = 9
4, 2, 2, , sum = 8
4, 2, , 1, sum = 7
4, 2, , , sum = 6
4, , 2, 1, sum = 7
, which is not correct.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the set.
Now the set of subsets can be manifested by 2to the power n - 1.( Let's say the number is C)
So the combinations are C -k +1 to C in binary format and sum where positions are 1

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.