北美公司：Uber

自从 Uber 上市暴雷后，不知道还有多少人想去 Uber ？

科普一下，Uber 的面试流程（社招）大致是： 5 轮 VO，两轮 coding，一轮系统设计，一轮 hiring manager，一轮 bar raiser 。

不过 Uber 的题库很大，基本没有重复的题。

这道题，感兴趣的小伙伴可以练练手。

给定一个 pattern 和一个字符串 str，查找 str 是否遵循相同的模式。

这里遵循的意思是一个完整的匹配，在一个字母的模式和一个非空的单词 str 之间有一个双向连接的模式对应。(如果 a 对应 s，那么 b 不对应 s 。例如，给定的模式= “ab”，str = “ss”，返回 false ）。

样例 1

输入: pattern = "abab" str = "redblueredblue" 输出: true 说明: "a"->"red","b"->"blue" 

样例 2

输入: pattern = "aaaa" str = "asdasdasdasd" 输出: true 说明: "a"->"asd" 

样例 3

输入: pattern = "aabb" str = "xyzabcxzyabc" 输出: false 

题解：

用深度优先搜索算法。 这个题不能使用动态规划或者记忆化搜索，因为参数列表中 mapping 和 used 无法记录到记忆化的哈希表中。

class Solution:     """     @param pattern: a string,denote pattern string     @param str: a string, denote matching string     @return: a boolean     """     def wordPatternMatch(self, pattern, string):         return self.is_match(pattern, string, {}, set())      def is_match(self, pattern, string, mapping, used):         if not pattern:             return not string                      char = pattern[0]         if char in mapping:             word = mapping[char]             if not string.startswith(word):                 return False             return self.is_match(pattern[1:], string[len(word):], mapping, used)                      for i in range(len(string)):             word = string[:i + 1]             if word in used:                 continue                          used.add(word)             mapping[char] = word                          if self.is_match(pattern[1:], string[i + 1:], mapping, used):                 return True                          del mapping[char]             used.remove(word)                      return False 

上面是一道原题，再分享一道没见过的，感兴趣的可以自己解一下(只有大概印象了，不知道题目描述是否有误）

给一个 contact matrix, contact[j] == 1 说明 i j 是 connected, contact[j] == 0 说明 i j 不是 connected; initial 是最开始的感染的人, 返回最后所有感染的人

example:

contact = [[1,1,1], [1,1,1], [1,1,1]] initial = [0] 返回 [0, 1, 2] 解释: 0 1 2 互相 connected, 0 感染, 所以 0 认识的所有人感染, 返回 [0, 1, 2] 

大佬有話說 (0)