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
|