Google Interview Question for SDE1s

Country: United States

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

- 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

- 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 =; // copies the vector, not so nice

		// print result (should be put into a seperate function) 
		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;
		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.weight_loss += sinput[current.last_excluded].second;
			current.excluded[current.last_excluded] = true;

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);

- Chris December 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
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.

- Alex December 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
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

- Ari December 11, 2017 | Flag Reply

Add a Comment

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


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

Learn More


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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More