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.
The simplest solution that I can think of is to divide the given string into four parts and compare the individual parts. You don't know how long a
or b
is, but both a
s are of the same length as well as b
s are. So the number of ways how to divide the given string is not very large.
Example:
pattern = [a b a b]
, given string = redblueredblue
(14 characters in total)
|a|
(length of a
) = 1, then that makes 2 characters for a
s and 12 characters is left for b
s, i.e. |b|
= 6. Divided string = r edblue r edblue
. Whoa, this matches right away!|a| = 2, |b| = 5
-> divided string = re dblue re dblue
-> matchExample 2:
pattern = [a b a b]
, string = redbluebluered
(14 characters in total)
|a| = 1, |b| = 6
-> divided string = r edblue b luered
-> no match|a| = 2, |b| = 5
-> divided string = re dblue bl uered
-> no match|a| = 3, |b| = 4
-> divided string = red blue blu ered
-> no matchThe rest is not needed to be checked because if you switched a
for b
and vice versa, the situation is identical.
What is the pattern that has [a b c a b c] ?