Amazon Interview Question
Software EngineersCountry: United States
Amazing complex solutions.
===============
NOTE: When you are given a hammer - everything looks like a nail.
Thus, simply because trie exists, does not need us to use it. :-)
===============
A much practical solution is this:
1. Take the filter string, replace every '*' with '.*' and append '^' in the front and '$' in the back.
2. Thus
ab* ==> ^ab.*$
3. Yes, you guessed it right, now simply store these things as pattern
4. and then loop over and match the patterns.
Cool?
Create a tree structure for O(Log(n))
//C#
class blackList
{
public static void Test()
{
blackList bl = new blackList();
bl.AddFilter("abc");
bl.AddFilter("aa*b");
String str = "aadbcb";
Console.WriteLine(str + ": blackListed? " + bl.IsInBlackList(str).ToString());
}
private class Node
{
public char data;
public Node next;
public Node child;
}
private Node filters = null;
public void AddFilter(string filter)
{
if (filter != null)
{
char[] filterChars = filter.ToCharArray();
AddFilter(ref this.filters, this.filters, filterChars, 0);
}
}
private void AddFilter(ref Node parent, Node filters, char[] filterChars, int index)
{
Boolean matched = false;
for (Node current = filters; current != null; current = current.next)
{
if (current.data == filterChars[index])
{
AddFilter(ref current, current.child, filterChars, index+1);
matched = true;
}
}
if (!matched)
{
Node node = CreateFilterNodes(filterChars, index);
if (parent != null)
{
node.next = filters;
parent.child = node;
}
parent = node;
}
}
private Node CreateFilterNodes(char[] filterChars, int index)
{
if (index < filterChars.Length)
{
Node node = new Node();
node.data = filterChars[index];
node.child = CreateFilterNodes(filterChars, index + 1);
return node;
}
else
{
return null;
}
}
public Boolean IsInBlackList(string str)
{
if (this.filters == null)
{
return true;
}
if (str != null)
{
char[] searchStr = str.ToCharArray();
return IsInBlackList(this.filters, searchStr, 0);
}
return false;
}
private Boolean IsInBlackList(Node filters, char[] searchStr, int index)
{
for (Node current = filters; current != null; current = current.next)
{
if (current.data == searchStr[index])
{
if (index == searchStr.Length - 1)
{
return true; //matched
}
return IsInBlackList(current.child, searchStr, index + 1);
}
else if (current.data == '*')
{
for (int i = index + 1; i < searchStr.Length; i++)
{
if (IsInBlackList(current.child, searchStr, i))
{
return true;
}
}
}
}
return false;
}
}
Good problem, can be done in O(n^2) where n = max filter size.
Since we are expected to receive a mixture of filter types (ones with wildcard, ones without) it makes sense to separate out the 'simple' filters (without wildcards) into a HashSet. That way, checking for those becomes O(1).
For the wildcard filters, we make sure we go through the prefix before the '*' and the suffix after the '*' and carefully compare characters from the input and the filter. We do this for each filter.
There's a more optimized way of doing this, by ingesting the wild card filters into a trie structure, where if a newly added regex has a * then it 'subsumes' all other previously seen filters from that node (e.g. 'a*b' subsumes 'aa*b'). But the solution below is presented in Java and a basic one.
- Killedsteel February 23, 2017