diogonlucena
BAN USERI'm not sure aboout variables and constraints
- diogonlucena May 02, 20201.
Create a class with the name of the person and the number of people this person knows.
Create a hash where the key would be the person name and the value would be an instance of the class.
this is O(m) in time because you need to loop trough all the pairs and O(n) in memory because you'll have one entry on the hash for each person.
Then you could all all the values to an array (O(n) in memory), sort the array (O(nlog(n) in time) and get the k latest (O(k)) or just add all the values to a priority queue and get the top k times (complexity won't change)
so time complexity would be MAX(O(m), O(nlogn)) and memory would be O(n)
2. I could only think of a O(m * n^2) solution
create a class that represents and edge and for each entry on the lsit of people who know each other, create an instance and add to set. By doing this, you can easily know if there's an edge between 2 nodes. (O(n) in time and memory to create the set and O(1) to check an edge)
now you can loop trough the orinal list again and each entry would represent a group (you could use an array to represent this group).
eg: (1, 6) means we have a group with 2 people inside: 1 and 6.
now, for each possible node, check if they can be added to that group. To do this, you'll need to check if the given node has an edge for evey person in the group.
Once you finished the checking for each node, you'll have a full group and you know its size.
by having the size of all the groups, you have the greatest of them (you don't need to save every size. You can just store the greatest)
- diogonlucena May 02, 2020