Interview Questions

Implement a firewall prototype:....

Software QA/Tests Interview Questions from Microsoft

(Continued from previous question...)

Implement a firewall prototype:....

Implement a firewall

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, * etc...
if input url is
IncludedLIst contains *.com and if ExcludedList contains *
Bestmatch in included is .com less then Bestmatch in ExcludedList 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
Suffix tree input will be
moc. [this is for .com]
moc.tset. [this is for]

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