Statistics

Problem Statement for "Clusters"

Problem Statement

The World Wide Web (WWW), as we all know, is a collection of pages, which are linked together to form a very large graph, where each page represents a node in the graph, and each link represents a directed edge. Since there are billions of pages on the WWW, it is important to be able to search through them, and have good methods to determine which ones are relevant.

One statistic about a page that might be of interest to a search engine is its clustering coefficient. To find the clustering coefficient of a page, p, first we find all of the pages that p links directly to. Then, we count the total number of links between all of those pages and divide by the total number of possible links between those pages (for our purposes, a pages may not be linked multiple times to the same page). If p links to zero or one pages, then its clustering coefficient is undefined. Note that clustering coefficients are usually used in conjunction with undirected graphs, but that we are expanding them here to be used on directed graphs (since the links in the WWW are directed).

Your task is, given a list of pages, and how they are linked together, determine the pages with the maximal (defined) clustering coefficient. You will be given a String[], links, where each element is a single-space delimited list of the names of the pages. The first term represents the page that the links are on, and the remaining terms represent the pages that it links to. So, "A B C D" would mean that page "A" has a link to pages "B", "C", and "D". You are to return a String[] that contains all of the pages which have the maximal clustering coefficient sorted in lexicographic order. If all of the pages have an undefined clustering coefficient, return an empty String[].

Definition

Class:
Clusters
Method:
mostClustered
Parameters:
String[]
Returns:
String[]
Method signature:
String[] mostClustered(String[] links)
(be sure your method is public)

Notes

  • Assume that the same name always describes the same page.

Constraints

  • links has between 1 and 20 elements inclusive
  • each element of links will contain between 1 and 50 characters inclusive.
  • each element of links consists only of upper-case letters ('A'-'Z') and spaces
  • each element of links doesn't contain leading/trailing spaces
  • each element of links consists of single-space delimited names
  • no element of links contains duplicate name
  • no two elements of links start with the same name
  • no page links to itself

Examples

  1. {"A B C D", "B A E D"}

    Returns: { "A", "B" }

    "A" is linked to three pages, "B", "C", and "D". There are 6 different possible links between these three pages (B->C, B->D, C->B, C->D, D->B, D->C). Only one of these links (B->D) actually exists, so the clustering coefficient of "A" is 1/6. "B" is also linked to three pages, which have 6 possible links between them. Only one of the possible links exists though (A->D) so its clustering coefficient is also 1/6. All of the other pages have undefined clustering coefficients, since they do not link to any pages. Thus, both "A" and "B" have the maximal clustering coefficient of 1/6, and we return then in sorted order.

  2. {"A", "B"}

    Returns: { }

    A and B are not linked to any other pages.

  3. {"A B C D", "B A C D", "C D A B", "D A B C"}

    Returns: { "A", "B", "C", "D" }

  4. {"A B C D", "B A C", "C D A B", "D A C"}

    Returns: { "B", "D" }

  5. {"A B C D", "B A C", "C A B", "D B C"}

    Returns: { "B", "C", "D" }

  6. {"Z A B C D E F G H I J K L M N O P Q R S T U V W X", "G H AA BB CC DD FF"}

    Returns: { "Z" }

  7. {"Z A B C D E F G H I J K L M N O P Q R S T U V W X","G H"}

    Returns: { "Z" }

  8. {"SEARCH SCHOOL NEWS", "NEWS FINANCE WORLD", "FINANCE WORLD"}

    Returns: { "NEWS" }

  9. {"A B C D E F", "B A C D E F", "C A B D E F", "D A B C E F", "E A B C D F", "F A B C D E"}

    Returns: { "A", "B", "C", "D", "E", "F" }

    Every page links to every other page here.

  10. {"A B C D E F G H I J K L N O P Q R S T", "B C D E F G H I J K L M N O P Q R S T", "C D E F G H I J K L M N O P Q R S T", "D E F G H I J K L M N O P Q R S T", "E F G H I J K L M N O P Q R S T", "F G H I J K L M N O P Q R S T","G H I J K L M N O P Q R S T", "H I J K L M N O P Q R S T","I J K L M N O P Q R S T", "J K L M N O P Q R S T","K L M N O P Q R S T", "L M N O P Q R S T","M N O P Q R S T","N O P Q R S T", "O P Q R S T","P Q R S T","Q R S T","R S T","S T"}

    Returns: { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R" }

  11. {"A B C D E F G H I J K N O P Q R S T", "B C D E F G H I J K L M N Q R S T", "C D E F G H I J K L M N O P S T", "D E F G H I J K L M N O P Q R", "E F G H I J K L M N O P Q R S T", "F G H I J K L M N O P Q R S T","G H I J M N O P Q R S T", "H I J K L M N O P Q R S T","I J K L M N Q R S T", "J K L M N O P S T","K L M N O P Q R S T", "L M N O P Q R S T","M N O P Q R S T","N O P Q R S T", "O P Q R S T","P Q R S T","Q R S T","R S T","S T"}

    Returns: { "J", "K", "L", "M", "N", "O", "P", "Q", "R" }

  12. {"A B C D E F G H I J K N O P", "B C D E F G H I J K L M N Q R S T", "C D E F G H I J K L M N O P S T", "D E F G H I J K L M N O P Q R", "E F G H I J K L M N O P Q R S T", "F G H I J K L M N O P Q R S T","G H I J M N O P Q R S T", "H I J K L M N O P Q R S T","I J K L M N Q R S T", "J K L M N O P S T","K L M N O P Q R S T"}

    Returns: { "A" }

  13. {"Z Y X","Y X"}

    Returns: { "Z" }

  14. {"Z Y X","Y X Z","X Y Z"}

    Returns: { "X", "Y", "Z" }

  15. {"Z Y X"}

    Returns: { "Z" }

  16. {"A", "B C"}

    Returns: { }

  17. {"A C D E F G H I J K L M N O P Q R S T", "B C D E F G H I J K L M N O P Q R S T", "C D E F G H I J K L M N O P Q R S T", "D E F G H I J K L M N O P Q R S T", "E F G H I J K L M N O P Q R S T", "F G H I J K L M N O P Q R S T","G H I J K L M N O P Q R S T", "H I J K L M N O P Q R S T","I J K L M N O P Q R S T", "J K L M N O P Q R S T","K L M N O P Q R S T", "L M N O P Q R S T","M N O P Q R S T","N O P Q R S T", "O P Q R S T","P Q R S T","Q R S T","R S T"}

    Returns: { "A", "B" }

  18. {"A B C D E F G H I J K L M N O P Q R S T", "B A C D E F G H I J K L M N O P Q R S T", "C A B D E F G H I J K L M N O P Q R S T", "D A B C E F G H I J K L M N O P Q R S T", "E A B C D F G H I J K L M N O P Q R S T", "F A B C D E G H I J K L M N O P Q R S T", "G A B C D E F H I J K L M N O P Q R S T", "H A B C D E F G I J K L M N O P Q R S T", "I A B C D E F G H J K L M N O P Q R S T", "J A B C D E F G H I K L M N O P Q R S T", "K A B C D E F G H I J L M N O P Q R S T", "L A B C D E F G H I J K M N O P Q R S T", "M A B C D E F G H I J K L N O P Q R S T", "N A B C D E F G H I J K L M O P Q R S T", "O A B C D E F G H I J K L M N P Q R S T", "P A B C D E F G H I J K L M N O Q R S T", "Q A B C D E F G H I J K L M N O P R S T", "R A B C D E F G H I J K L M N O P Q S T", "S A B C D E F G H I J K L M N O P Q R T", "T A B C D E F G H I J K L M N O P Q R S"}

    Returns: { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T" }

  19. {"A B C D E F G H I J K L M N O P Q R S T", "B A C D E F G H I J K L M N O P Q R S T", "C A B D E F G H I J K L M N O P Q R S T", "D A B C E F G H I J K L M N O P Q R S T", "E A B C D F G H I J K L M N O P Q R S T", "F A B C D E G H I J K L M N O P Q R S T", "G A B C D E F H I J K L M N O P Q R S T", "H A B C D E F G I J K L M N O P Q R S T", "I A B C D E F G H J K L M N O P Q R S T", "J A B C D E F G H I K L M N O P Q R S T", "K A B C D E F G H I J L M N O P Q R S T", "L A B C D E F G H I J K M N O P Q R S T", "M A B C D E F G H I J K L N O P Q R S T", "N A B C D E F G H I J K L M O P Q R S T", "O A B C D E F G H I J K L M N P Q R S T", "P A B C D E F G H I J K L M N O Q R S T", "Q A B C D E F G H I J K L M N O P R S T", "R A B C D E F G H I J K L M N O P Q S T", "S A B C D E F G H I J K L M N O P Q R T"}

    Returns: { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S" }

  20. {"A B C D E F G H I J K L M N O P Q R S", "B A C D E F G H I J K L M N O P Q R S T", "C A B D E F G H I J K L M N O P Q R S T", "D A B C E F G H I J K L M N O P Q R S T", "E A B C D F G H I J K L M N O P Q R S T", "F A B C D E G H I J K L M N O P Q R S T", "G A B C D E F H I J K L M N O P Q R S T", "H A B C D E F G I J K L M N O P Q R S T", "I A B C D E F G H J K L M N O P Q R S T", "J A B C D E F G H I K L M N O P Q R S T", "K A B C D E F G H I J L M N O P Q R S T", "L A B C D E F G H I J K M N O P Q R S T", "M A B C D E F G H I J K L N O P Q R S T", "N A B C D E F G H I J K L M O P Q R S T", "O A B C D E F G H I J K L M N P Q R S T", "P A B C D E F G H I J K L M N O Q R S T", "Q A B C D E F G H I J K L M N O P R S T", "R A B C D E F G H I J K L M N O P Q S T", "S A B C D E F G H I J K L M N O P Q R T"}

    Returns: { "A" }

  21. {"A B C D E F G H I J K L M N O P Q R S T", "B A C D E F G H I J K L M N O P Q R S T", "C A B D E F G H I J K L M N O P Q R S T", "D A B C E F G H I J K L M N O P Q R S T", "E A B C D F G H I J K L M N O P Q R S T", "F A B C D E G H I J K L M N O P Q R S T", "G A B C D E F H I J K L M N O P Q R S T", "H A B C D E F G I J K L M N O P Q R S T", "I A B C D E F G H J K L M N O P Q R S T", "J A B C D E F G H I K L M N O P Q R S T", "K A B C D E F G H I J L M N O P Q R S T", "L A B C D E F G H I J K M N O P Q R S T", "M A B C D E F G H I J K L N O P Q R S T", "N A B C D E F G H I J K L M O P Q R S T", "O A B C D E F G H I J K L M N P Q R S T", "P A B C D E F G H I J K L M N O Q R S T", "Q A B C D E F G H I J K L M N O P R S T", "R A B C D E F G H I J K L M N O P Q S T", "S A B C D E F G H I J K L M N O P Q R T", "T A B C D E F G H I J K L M N O P Q R"}

    Returns: { "S", "T" }

  22. {"A C D E F G H I J K L M N O P Q R S T", "B A C D E F G H I J K L M N O P Q R S T", "C A B D E F G H I J K L M N O P Q R S T", "D A B C E F G H I J K L M N O P Q R S T", "E A B C D F G H I J K L M N O P Q R S T", "F A B C D E G H I J K L M N O P Q R S T", "G A B C D E F H I J K L M N O P Q R S T", "H A B C D E F G I J K L M N O P Q R S T", "I A B C D E F G H J K L M N O P Q R S T", "J A B C D E F G H I K L M N O P Q R S T", "K A B C D E F G H I J L M N O P Q R S T", "L A B C D E F G H I J K M N O P Q R S T", "M A B C D E F G H I J K L N O P Q R S T", "N A B C D E F G H I J K L M O P Q R S T", "O A B C D E F G H I J K L M N P Q R S T", "P A B C D E F G H I J K L M N O Q R S T", "Q A B C D E F G H I J K L M N O P R S T", "R A B C D E F G H I J K L M N O P Q S T", "S A B C D E F G H I J K L M N O P Q R T", "T A B C D E F G H I J K L M N O P Q R"}

    Returns: { "B", "S" }

  23. {"A"}

    Returns: { }

  24. { "ABRA CA DABRA", "DABRA CA", "CA DABRA", "D A B", "A B C" }

    Returns: { "ABRA" }

  25. {"YAHOO GOOGLE CNN", "GOOGLE CNN YAHOO", "CNN GOOGLE YAHOO"}

    Returns: { "CNN", "GOOGLE", "YAHOO" }

  26. { "A B C D E F G H I J K L M N O P Q R S T U V W X", "Y Z AA AB AC AD AE AF AG AH AI AJ AK AL AM AN AO", "AP AQ AR AS AT AU AV AW AX AY AZ BA BB BC BD BE", "BF BG BH BI BJ BK BL BM BN BO BP BQ BR BS BT BU", "BV BW BX BY BZ CA CB CC CD CE CF CG CH CI CJ CK", "CL CM CN CO CP CQ CR CS CT CU CV CW CX CY CZ DA", "DB DC DD DE DF DG DH DI DJ DK DL DM DN DO DP DQ", "DR DS DT DU DV DW DX DY DZ EA EB EC ED EE EF EG", "EH EI EJ EK EL EM EN EO EP EQ ER ES ET EU EV EW", "EX EY EZ FA FB FC FD FE FF FG FH FI FJ FK FL FM", "FN FO FP FQ FR FS FT FU FV FW FX FY FZ GA GB GC", "GD GE GF GG GH GI GJ GK GL GM GN GO GP GQ GR GS", "GT GU GV GW GX GY GZ HA HB HC HD HE HF HG HH HI", "HJ HK HL HM HN HO HP HQ HR HS HT HU HV HW HX HY", "HZ IA IB IC ID IE IF IG IH II IJ IK IL IM IN IO", "IP IQ IR IS IT IU IV IW IX IY IZ JA JB JC JD JE", "JF JG JH JI JJ JK JL JM JN JO JP JQ JR JS JT JU", "JV JW JX JY JZ KA KB KC KD KE KF KG KH KI KJ KK", "KL KM KN KO KP KQ KR KS KT KU KV KW KX KY KZ LA", "LB LC LD LE LF LG LH LI LJ LK LL LM LN LO LP LQ" }

    Returns: { "A", "AP", "BF", "BV", "CL", "DB", "DR", "EH", "EX", "FN", "GD", "GT", "HJ", "HZ", "IP", "JF", "JV", "KL", "LB", "Y" }

  27. { "C D E F", "A B C", "B C", "D E F", "E D" }

    Returns: { "A", "C" }

  28. { "B A C", "A C B" }

    Returns: { "A", "B" }

  29. { "B A E D", "A B C D" }

    Returns: { "A", "B" }

  30. { "B A E D", "A B C E" }

    Returns: { "A", "B" }

  31. { "A B C", "O P Q", "F G H" }

    Returns: { "A", "F", "O" }

  32. { "A B CC DD", "EE FF GG HH" }

    Returns: { "A", "EE" }

  33. { "A B C D E F G H I J K L M N O P Q R S T U", "B A C D E F G H I J K L M N O P Q R S T U", "C A B D E F G H I J K L M N O P Q R S T U", "D A B C E F G H I J K L M N O P Q R S T U", "E A B C D F G H I J K L M N O P Q R S T U", "G A B C D E F H I J K L M N O P Q R S T U", "F A B C D E G H I J K L M N O P Q R S T U", "H A B C D E F G I J K L M N O P Q R S T U", "I A B C D E F G H J K L M N O P Q R S T U", "J A B C D E F G H I K L M N O P Q R S T U", "K A B C D E F G H I J L M N O P Q R S T U", "L A B C D E F G H I J K M N O P Q R S T U", "M A B C D E F G H I J K L N O P Q R S T U", "N A B C D E F G H I J K L M O P Q R S T U", "O A B C D E F G H I J K L M N P Q R S T U", "P A B C D E F G H I J K L M N O Q R S T U", "Q A B C D E F G H I J K L M N O P R S T U", "R A B C D E F G H I J K L M N O P Q S T U", "S A B C D E F G H I J K L M N O P Q R T U", "T A B C D E F G H I J K L M N O P Q R S U" }

    Returns: { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T" }

  34. { "B A D", "A B D" }

    Returns: { "A", "B" }

  35. { "A B C", "Y X Z", "E F G" }

    Returns: { "A", "E", "Y" }

  36. { "B A C D", "A B E D" }

    Returns: { "A", "B" }

  37. { "A B C D E F G H I J K L M N O P Q R S T U V W X Y", "B AA BB CC DD EE FF GG HH II JJ KK LL MM NN OO", "C QQ RR SS TT UU VV WW XX YY ZZ" }

    Returns: { "A", "B", "C" }

  38. { "Z Y X", "D A B C", "Y A B C" }

    Returns: { "D", "Y", "Z" }

  39. { "A B C D", "B C", "E F G H I", "F G", "I H" }

    Returns: { "A", "E" }

  40. { "A B C", "O P Q", "E F G" }

    Returns: { "A", "E", "O" }

  41. { "AA A B C D E F G H I J K L M N O P Q R S T U V W X", "BB A B C D E F G H I J K L M N O P Q R S T U V Y", "X A B C D E F G H I J K L M N O P Q R S T U V", "W A B", "Y A" }

    Returns: { "AA" }

  42. { "B A C", "A B C", "C A B" }

    Returns: { "A", "B", "C" }

  43. { "A B C D", "B C", "E F G H I", "F G", "G H" }

    Returns: { "A", "E" }

  44. { "Z Y X" }

    Returns: { "Z" }

  45. { "A B C D E F G H I J K L M N O P Q R S T U V W X Y", "AA BB CC DD EE FF GG HH II JJ KK LL MM", "AB AC AD AE AF AG AH AI AJ AK AL AM AN", "BA BB BC BD BE BF BG BH BI BJ BK BL BM BN", "CA CB CC CD CE CF CG CH CI CJ CK CL CM CN", "DA DB DC DD DE DF DG DH DI DJ DK DL DM DN" }

    Returns: { "A", "AA", "AB", "BA", "CA", "DA" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: