Amazon Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

public class RestrictedWildcardMatch {

    static final Set<String> simpleFilters = new HashSet<>();
    static final List<String> wildcardFilters = new ArrayList<>();

    public static void main(String[] args) {
        addFilter("a*b");
        addFilter("aa*b");
        addFilter("abc");
        addFilter("abdr*");

        System.out.println(isInBlackList("accb"));
        System.out.println(isInBlackList("ab"));
        System.out.println(isInBlackList("ax"));            // false
        System.out.println(isInBlackList("aaxvfbb"));
        System.out.println(isInBlackList("abc"));
        System.out.println(isInBlackList("aa"));            // false
        System.out.println(isInBlackList("bb"));            // false
        System.out.println(isInBlackList("abdreee"));       // true
    }

    public static void addFilter(String filter) {
        if(filter.contains("*")) {
            wildcardFilters.add(filter);
        } else {
            simpleFilters.add(filter);
        }
    }

    public static boolean isInBlackList(String input) {
        if(simpleFilters.contains(input)) return true;

        for(String wildcardFilter : wildcardFilters) {
            if(innerCheck(input, wildcardFilter)) return true;
        }
        return false;
    }

    private static boolean innerCheck(String input, String wildcardFilter) {
        if(input.length() < wildcardFilter.length()-1) return false;
        int i=0;
        boolean passedFirst = true;

        // make sure the filter prefix until the '*'
        // matches with the input
        while(wildcardFilter.charAt(i) != '*') {
            if(wildcardFilter.charAt(i) !=
                    input.charAt(i)) {
                passedFirst = false;
                break;
            }
            i++;
        }

        if(!passedFirst) return false;  // no point checking further

        // we're able to swing to the last char of the wildcard
        // filter and compare from there BECAUSE there is only
        // one '*' guaranteed from the problem statement
        int k = input.length() - 1;
        for (int j = wildcardFilter.length() - 1; j > i; j--) {
            if (wildcardFilter.charAt(j) !=
                    input.charAt(k)) {
                return false;
            }
            k--;
        }
        return true;
    }
}

- Killedsteel February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

tries to manage the front and end of wildcard it would become O(log(n)) - where n is max length of filter, space is the same

- Arron February 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- NoOne February 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- IC February 25, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More