ProgrammingProblemSearchPart1
Instructions
Solvetheproblemdescribedbelowusing aProgrammingLanguage [Link]
objectiveoftheproblemistoallowyoutodemonstratetwoaspects:
Abilitytosolveaproblemtocompletiongivenanylanguage.
Programminganddesignskills,preferableObjectoriented.
Theproblemisprovidedwithsampledatatobeusedfortestingandyoushouldbeableto
demonstratethesolutionusingthesupplieddataeitherthroughafunctionwhichhasallthe
inputdatausedasaharness(whichprintsthesolutionassoonasitisrun)ORthroughasimple
commandinterfacewhereitshouldbepossibletoentertheinputsasmentionedbelowandsee
theoutput.
[Link]
onsolvingtheproblemfirst.
Resultingsolutionfilesshouldbeaddedtoazipfileandemailedwithinthedeadline
[Link]
[Link]
solvethesecondpartoftheproblemwhichisnotherebutwillbesharedbyusduringthe
interview.
ProblemBackground
CompanyLcmeisparticularlyinterestedinimprovingthevolumeandqualityoftraffictothe
[Link]
sophisticated,usingadvancedalgorithmsandparallelsearchingtechniquestoprovidefast,
[Link],somewhatsimpler.
Agroupofwebpageshasbeenclassifiedbyassociatingalistofkeywords,givenindecreasing
orderofrelevance,witheachpage(i.e.,theorderofkeywordsisfromthemostspecifickeyword
totheleastspecific).Forexample,ontheTopGearwebsiteapageonreviewsofFordcarsmay
havethekeywords:Ford,Car,ReviewinthatorderthemostrelevantkeywordisFord.
Queriesalsoincludealistofkeywords,[Link],ina
queryconsistingofthekeywordFordfollowedbythekeywordCar,Fordismoreimportantthan
Car.
Inthisproblemyouaretodeterminethetopfive(orfewer)pagesthatmatcheachofan
arbitrarynumberofqueries.
Todeterminethestrengthoftherelationshipbetweenaqueryandawebpage,assumethe
keywordsforeachpageandeachqueryareassignedintegerweights,indescending
order,startingwithN,whereNisthemaximumnumberofkeywordsallowedforawebpageand
query.
Thestrengthoftherelationshipisthesumoftheproductsoftheweightsassociatedwith
eachkeywordthatappearsbothinthewebpagelistandthequerylist.
Forexample,assumethefollowingwebpagesandkeywordlists:
Page1:Ford,Car,Review
Page2:Toyota,Car
Page3:Car,Ford
ForNequal8,aquerywithkeywordsFordandCarinthatorderyieldsthefollowingstrength
ratings.
Page1:(8x8+7x7)=113
Page2:(7x7)=49
Page3:(8x7)(7x8)=112.
Similarly,aquerywithkeywordsFordandReviewyieldsthefollowingstrengthratings.
Page1:(8x8+7x6)=106
Page2:=0
Page3:(8x7)=56
Input
[Link]
[Link]
[Link].
[Link]
[Link],casebeing
[Link].
Output
Foreachquery,identifythe5(orfewer)pagesstoredthatarethemostrelevanttothequery.
Printasinglelinecontainingthequeryidentifier,acolon,andthepageidentifiersofthefive
[Link]
[Link]
[Link],[Link]
notlistpagesthathavenorelationship(zerostrength),eveniffewerthanfivepagesare
identified.
AdditionalConsiderations
Althoughthesearchstrengthalgorithmdescribedhereisquitesimple,developersshouldmake
provisionforsubstitutingamorecomplexmethodinthefutureandconsidertheimpactof
nestedpages.
SampleInput
PFordCarReview
PReviewCar
PReviewFord
PToyotaCar
PHondaCar
PCar
QFord
QCar
QReview
QFordReview
QFordCar
QcookingFrench
OutputfortheSampleInput
Q1:P1P3
Q2:P6P1P2P4P5
Q3:P2P3P1
Q4:P3P1P2
Q5:P1P3P6P2P4
Q6:
Endofproblem