def match(text, pattern): """ Given a string and a pattern, where: '.' - matches any single character. '*' - matches zero or more of the preceding element. Find the first substring matching this pattern. Tests: >>> match('alex', 'le') le >>> match('alexandra', 'al.*a') # an alexa >>> match('alexandru', 'al.*a.dru*') alexandru >>> match('alex', '.') 'a' >>> match('alex', '.*') 'alex' >>> match('aleex', 'e*') 'ee' >>> match('alex', 'alex*') 'alex' >>> match('alex', '*alex') Error >>> match('alex', 'alex.') '' >>> match('alex', '**') Error """ END = '$' class Automaton(object): """ Builds a new automaton for matching strings. """ def __init__(self, pattern): self.start = {} state = self.start symbols = self.extract_symbols(pattern) for (index, symbol) in enumerate(symbols): if len(symbol) == 1: state[symbol] = {} state = state[symbol] else: [x, y, z] = symbol state[x] = state if z != None: state[z] = {} state = state[z] state[END] = None def extract_symbols(self, pattern): """ Returns: list, of string, format ([A-z.]|([A-z.]\*[A-z]) """ out = [] i = 0 while i < len(pattern): c = pattern[i] n = pattern[i+1] if i+1 < len(pattern) else None nn = pattern[i+2] if i+2 < len(pattern) else None if c == '*' and i == 0: raise Exception('Pattern does not support * in first position') if c == '*' and n == '*': raise Exception('Pattern does not support successive *') if n == '*': out.append([c, n, nn]) i += 3 else: out.append(c) i += 1 return out def check(self, text, index): """ Checks if the string matches the automaton. """ text += END state = self.start while index < len(text): char = text[index] index += 1 if char in state: state = state[char] elif '.' in state: state = state['.'] else: return False return True a = Automaton(pattern) for i in range(len(text)): is_match = a.check(text, i) if is_match == True: return True return False
Could you please post clearer code? Or is it Glassdoor comments that are taking the whitespace away? I got the same two questions, but the second one was onsite. I cleared the interview at Facebook's Menlo Park office, but joined Google instead because they gave me a better team to join. (Aside: I got trained at InterviewKickstart.com. Check it out. Very legit. They are like a mini-CS school, with mock interviews)