Disqus Interview Question: Write a Unix glob implementat... | Glassdoor

Interview Question

Senior Python Software Engineer Interview San Francisco, CA

Write a Unix glob implementation in python. Globbing lets

  you use * for zero or more characters, ? for a single character, [] for a character range.
Tags:
difficult, recursive algorithm
Answer

Interview Answer

1 Answer

1

The key to this problem is recursion and avoiding quadratic complexities, so you need to convert your text into words and then compose those words into a trie (not tree) of indexed characters. You then traverse that trie, recursing as necessary, to produce a list of matching words and their indices into the original text.

Note: I made the whole search corpus into a trie, and I shouldn't have for maximum points. I should have only trie-d the first three or four characters and used linear matching for the rest of the words into order to save on memory.

Interview Candidate on May 4, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.