CareerCup

The interviewer was expecting some Datastructure implementation,I started saying all the datastructures i know:)..I used N-ary tree for Included and excluded list

root
.com .net
.test .abc .xyz .*

I would create a tree from input string and would find if the tree is subtree of the Included and Excluded trees and respective heights which determine the best match..I am sure this is the worst way of doing it, any other DS implementations here..

How do you know the interviewer was expecting some data structure implementation?

Create 2 suffix tree(1 for inclusion and other for exclusion) with all these inputs in reverse order
eg
Suffix tree input will be
moc. [this is for .com]
moc.tset. [this is for test.com]
ni.oc

Reverse the input and check for its presence in this suffix tree and calculate the length matched as well.

Search for string in suffix tree will be taking O(n) time, n being the length of the input to be searched

maintain two table one for inclusion and one for exclusion
then check url's extension (.com,.test.com etc) so complexity will be O(n1)+O(n2) which will be O(n) if n1=n2=n

according to the question, *.com < *.test.com when matching to xxx.test.server.com

so the best match is *.test.com instead of *.com

if you use a trie you can't find the match *.test.com