Interview Questions

Implement a firewall prototype:....

Software QA/Tests Interview Questions from Microsoft


(Continued from previous question...)

Implement a firewall prototype:....

Question:
Implement a firewall
prototype:

bool firewall(string url, list IncludedList, List ExcludedList)
Return true if the url is in included list
Return false if the url is in excluded list.
In a ambiguous situation return true\false based on best match.

Included\Excluded Url can contain '*' ex *.com, *.test.com etc...
if input url is www.test.server.com
IncludedLIst contains *.com and if ExcludedList contains *.test.com
Bestmatch in included is .com less then Bestmatch in ExcludedList .test.com..In this case it has to return false..


maybe an answer:


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

(Continued on next question...)

Other Interview Questions