Questions tagged [quick-union]
7 questions
5
votes
3 answers
What is the Time Complexity of Quick Union?
I'm taking the coursera course on Data Structures and Algorithms. The author mentions that Quick Find is O(N^2) which makes sense (given that N union operations on N objects might require N*N array accesses). However, I don't understand why Quick…
user3457614
- 61
- 1
- 5
5
votes
2 answers
Weighted quick-union explanations
I need help understanding the explanations given by the questions about weighted quick union:
Which of the following id[] array(s) could be the result of running the weighted quick union algorithm on a set of 10 items? Check all that apply.
Recall…
template boy
- 10,230
- 8
- 61
- 97
1
vote
0 answers
Finding duplicate users in a user list (Asked in an Interview)
I was recently asked this in an interview for a SDE role.
Suppose you have a list of User objects
class User {
String userId;
String email;
String ip_addr;
}
where userId field is unique among all users, while ip_addr and email are…
Gokay
- 758
- 5
- 9
0
votes
0 answers
How does the Root Method Work in Quick-Union?
I've recently been studying the Princeton Algorithms course on Coursera. The course begins by teaching an algorithm called Quick-Union to solve the Dynamic Connectivity Problem..
While I understand the purpose and implementation of the algorithm -…
0
votes
1 answer
How would the weighted quick-union Algorithm be implemented?
I'm currently enrolled in the Princeton Algorithms course (Part 1) and it talks about an improvement to the quick-union algorithm by maintaining an extra array sz[i] to count the number of objects in the tree rooted i, but it doesn't show how to do…
Abdiel Mendez
- 3
- 2
0
votes
0 answers
Running weighted quick union
So I have to take an ID array
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
And perform weighted quick union on it. I have to perform the operations 9-0, 3-4, 5-8, 7-2, 2-1, 5-7, 0-3, and 4-2. Here's what I did to the array for these operations:
9-0
0 1…
david mah
- 305
- 2
- 12
-1
votes
3 answers
Explaination of this code?
I'm Studying the Quick-Union algorithm but can't exactly understand this code:
#include
#define N 10000
main()
{
int i,p,t,id[N];
for (i = 0; i < N ; i++) id[i]= i;
while (scanf ("%d %d\n" , &p, &q) == 2)
{
for(i =…
DkgMarine
- 59
- 6