A question on data structures

→ Pay attention

Before contest
Codeforces Round 950 (Div. 3)
26:46:32
Register now »

→ Top rated

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

roycf123's blog

A question on data structures

By roycf123, history, 10 months ago, In English

Today, I was asked in an interview to build a data structure as follows:

Let there be some elements and some groups. Each element associated to 'exactly 1' group has a score. The data structure must support the following operations:

insert(el_id,grp_id,x): Insert element with id el_id with a score x to group with group_id grp_id
set(el_id,x): change the score of element with id el_id to x.
set(grp_id,x): change the score of all elements in the group with id grp_id to x.
print(grp_id): print the max score element's id in that group. (Return any if multiple exist)

Constraints:

1 <= no_of_elements <= 1e6
1 <= no_of_groups <= 5
1 <= score <= 5

I couldn't solve it during the interview and also couldn't think of any solution later. Would someone please help?

data structures

roycf123
10 months ago
10

Comments (10)

Write comment?

EMBailey

10 months ago, # |

+10

Is it possible for one element to be in multiple groups? If so, does each element just have one score, or does each element-group association have its own score?

→ Reply

roycf123

10 months ago, # ^ |

No that is not possible, each element will be associated to one group only.

→ Reply

EMBailey

10 months ago, # ^ |

← Rev. 2 →

It is possible to support each operation in amortized constant time with linear memory, even if the number of groups is much larger. (I'm treating the maximum score as a constant, since it's only 5.)

For each group, we'll maintain a bucket queue, which is a type of priority queue where each score has a "bucket", in this case a circular doubly linked list. Each bucket will start with a sentinel node to make implementation easier.

For insert, add the element's node to its group's bucket with the corresponding score.
For the element version of set, remove the element's node from its group's bucket with the corresponding score.
For the group version of set, splice all of the other buckets onto the end of the bucket with the corresponding score.
For print, scan the buckets in reverse order until you find one that isn't empty and return its first element.

Operations 3 and 4 are linear in the number of buckets, but again, we're treating that as a constant.

Implementation

Here, I'm assuming 1 <= el_id <= no_of_elements and 1 <= grp_id <= no_of_groups to be consistent with score. If this is not true, the code below will need to be changed slightly.

class ds
{
private:
	static int constexpr MAX_SCORE = 5;
	struct element
	{
		int grp_id;
		element *prev, *next;
		element() :
			prev(this),
			next(this)
		{}
	};
	vector<element> elements;
	struct group
	{
		// Each group has a 
		element heads[MAX_SCORE]{};
	};
	vector<group> groups;

	// Append non-empty circular doubly linked lists
	static void append(element *head_a, element *head_b)
	{
		swap(head_a->prev, head_b->prev);
		head_a->prev->next = head_a;
		head_b->prev->next = head_b;
	}
	// Remove a single node from its circular doubly linked list. The resulting list must be nonempty.
	static void remove(element *b)
	{
		b->prev->next = b->next;
		b->next->prev = b->prev;
		b->next = b->prev = b;
	}

public:
	ds(int no_of_elements, int no_of_groups) :
		elements(no_of_elements),
		groups(no_of_groups)
	{}
	void insert(int el_id, int grp_id, int x)
	{
		el_id--;
		grp_id--;
		x--;
		element *el = &elements[el_id];
		el->grp_id = grp_id;
		append(&groups[grp_id].heads[x], el);
	}
	void set_element(int el_id, int x)
	{
		el_id--;
		x--;
		element *el = &elements[el_id];
		remove(el);
		append(&groups[el->grp_id].heads[x], el);
	}
	void set_group(int grp_id, int x)
	{
		grp_id--;
		x--;
		element *head_new = &groups[grp_id].heads[x];
		for (int score = 0; score < MAX_SCORE; score++)
		{
			element *head_old = &groups[grp_id].heads[score];
			element *first = head_old->next;
			if (first == head_old) continue; // Skip empty lists
			remove(head_old);
			append(head_new, first);
		}
	}
	int print(int grp_id) const
	{
		grp_id--;
		for (int score = MAX_SCORE - 1; score >= 0; score--)
		{
			element const *head = &groups[grp_id].heads[score];
			if (head->next != head)
				// head->next - elements.data() is the zero-based index
				return (int)(head->next - elements.data()) + 1;
		}
		assert(false); // Group is empty
	}
};

For an interesting challenge, see if you can figure out how to achieve amortized logarithmic time complexity per operation even when both the number of groups and the maximum score can be large.

→ Reply

roycf123

10 months ago, # ^ |

Thank you so much!

→ Reply

roycf123

10 months ago, # |

Auto comment: topic has been updated by roycf123 (previous revision, new revision, compare).

→ Reply

Gwynbleidd_

10 months ago, # |

Not a very efficient approach but i think it should work: Think of all groups to be max heaps containing the elements. Also remember each elements index in its respective heap or group after each operation. Inserting element in group would simply be heap push operation O(logn), Changing score of element would be using the elements index in its heap and doing decreaseKey() operation in the respective heap 0(logn), changing all elements in a group would be changing each value in heap to O(group size) and printing max score of a group would be heap.top() O(1).

→ Reply

roycf123

10 months ago, # ^ |

← Rev. 4 →

Sorry I read the comment in a hurry...

This is exactly what I did (except for the use of std::set instead of heaps, I performed search operation and changed for 2), But the set(grp_id,x) would take O(group_size) which can be O(1e6) in the worst case, so may be costly (in terms to time taken)...

Is there any way to do it faster, that is any data structure that may support this form of group update fast?

P.S: I think there may be a better way to utilize the constraint 1 <= score <= 5, although not sure...

→ Reply

53846

10 months ago, # ^ |

Timestamps for operations set(el_id,x) and set(grp_id,x). Store changed values of operation set(grp_id,x) for groups instead of elements. Changing all elements in a group could be done in O(1). Each element has two values: one belongs to itself (determined by operations insert(el_id,grp_id,x) and set(el_id,x)), the other belongs to its group (determined by operation set(grp_id,x)). Choose the one that has bigger timestamp when do other operations in the heap.

→ Reply

ibrahim___sultan

10 months ago, # |

a self balancing binary tree? where each node represents a group which is a binary tree of elements, all of the operations can be done in O(log(n) + log(m)) ... set(grp_id,x) will take O(log(n) + m).

→ Reply

roycf123

10 months ago, # ^ |

Yeah same as before, many people use std::multiset instead of std::priority_queue and it does no harm in most cases.

→ Reply