A friend of mine just had his interview at Google and got rejected because he couldn't give a solution to this question.
I have my own interview in a couple of days and can't seem to figure out a way to solve it.
Here's the question:
You are given a pattern, such as [a b a b]. You are also given a string, example "redblueredblue". I need to write a program that tells whether the string follows the given pattern or not.
A few examples:
Pattern: [a b b a] String: catdogdogcat returns 1
Pattern: [a b a b] String: redblueredblue returns 1
Pattern: [a b b a] String: redblueredblue returns 0
I thought of a few approaches, like getting the number of unique characters in the pattern and then finding that many unique substrings of the string then comparing with the pattern using a hashmap. However, that turns out to be a problem if the substring of a is a part of b.
It'd be really great if any of you could help me out with it. :)
UPDATE:
Added Info: There can be any number of characters in the pattern (a-z). Two characters won't represent the same substring. Also, a character can't represent an empty string.
Don't you just need to translate the pattern to a regexp using backreferences, i.e. something like this (Python 3 with the "re" module loaded):
>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>
>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>
>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None
The regexp looks pretty trivial to generate. If you need to support more than 9 backrefs, you can use named groups - see the Python regexp docs.