CareerCup

Assuming we had an array of Ad objects that contained their url, img and the number of keywords wasn't great enough to really need a Trie, you could store the keywords for an Ad object in a hash. Since a hash retrieves in O(1). In Ruby it would look like {{{ class Ad @url // "ursite.com" @img // "adimage.png" @keywords = Hash.new(false) // any key that is queried for that does not exist will // return false end }} This way if we had an array of Ad objects we wanted to pull with the most keywords we would only need to walk through the array once and the time complexity would be O(n*m) Where n is the number of ads in the array and m is the number of keywords you are checking for within each Ad. Which would probably be negligible compared to the number of Ads you are searching through. (*Note: if using an array or BST you still would have an additional Big O time complexity, rather then Hash's O(1) look up time. So it would be O(n*m*(other data structures look up time)) ) In Ruby it would look like: {{{ def findAdWithMostK (adList, keyList) topAd = nil maxK = 0 currK = 0 adList.each do |ad| currK = 0 keyList.each do |k| // increment current count if key is in the ad's keyword hash // keyword hash elements are added as ("yourkeyword" => true) currK += 1 if ad.keywords(k) end // check if current ad has most keywords from list if currk > maxK topAd = ad end end return topAd end }}} - Anonymous November 05, 2013 | Flag Reply

If there is a frequent access or check for particular words than Trie datastructure should be used.

- Stupid Developer November 05, 2013 | Flag Reply

Assuming we had an array of Ad objects that contained their url, img and the number of keywords wasn't great enough to really need a Trie, you could store the keywords for an Ad object in a hash. Since a hash retrieves in O(1). In Ruby it would look like {{{ class Ad @url // your site link @img // adimage.png @keywords = Hash.new(false) // any key that is queried for that does not exist will // return false end }} This way if we had an array of Ad objects we wanted to pull with the most keywords we would only need to walk through the array once and the time complexity would be O(n*m) Where n is the number of ads in the array and m is the number of keywords you are checking for within each Ad. Which would probably be negligible compared to the number of Ads you are searching through. (*Note: if using an array or BST you still would have an additional Big O time complexity, rather then Hash's O(1) look up time. So it would be O(n*m*(other data structures look up time)) ) In Ruby it would look like: {{{ def findAdWithMostK (adList, keyList) topAd = nil maxK = 0 currK = 0 adList.each do |ad| currK = 0 keyList.each do |k| // increment current count if key is in the ad's keyword hash // keyword hash elements are added as ("yourkeyword" => true) currK += 1 if ad.keywords(k) end // check if current ad has most keywords from list if currk > maxK topAd = ad end end return topAd end }}} - Anonymous November 05, 2013 | Flag Reply

If the question is just that from a list of keywords, whichever ad contains most words is the right one, why not just iterate all the adds and depending on the number of hits for keywords, assign it an integer and use this integer as a key for the the ad in a dictionary. If there is already a key with this integer, ignore the current one since our only criterion is to find the one with most keywords. So even if its a tie, its still the max.

- Tahir November 06, 2013 | Flag Reply

I wudnt build tries for all those candidates.

I'd preprocess the keywords a la boyer moore horspool and substring match in all candidates (case insensitive). Define objective function on a candidate as something that takes into account total macthes and total different matches from pool of keywords.

- urik on bb November 06, 2013 | Flag Reply

Its similar to search engine in a way that we have to associate the query string with the best possible ad(or webpage).
for each keywords populate a graph having edge between keyword node and ad node. the weight age of edge is calculated based on various factors like similarity, occurrences etc.

When getting best ad to be displayed, parse the request content which will contain keywords. based on these keywords get all the ads with minimum weight age cutoff from the graph. using the weight between different keyword and ad determine a cumulative weight age between request content and ads. get the max cumulative weight age ad and display it.

- hinax July 21, 2014 | Flag Reply

I will use a splay stack with random balanced insertion guarantees. It is asymptotically optimal for this problem.

- hprem999 November 06, 2013 | Flag Reply