6hz7vif 发表于 2024-9-4 06:56:56

Google 经典面试题解析


    <div style="color: black; text-align: left; margin-bottom: 10px;">
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">在这篇<span style="color: black;">文案</span>中,作者将介绍其过去在Google面试时采用的面试题,<span style="color: black;">不外</span><span style="color: black;">因为</span>题目泄漏<span style="color: black;">此刻</span><span style="color: black;">已然</span>禁止在面试中<span style="color: black;">运用</span>了。然而,失之东隅收之桑榆,<span style="color: black;">由于</span>这些题目已被泄漏,<span style="color: black;">因此</span>笔者<span style="color: black;">期盼</span>透过问题看本质,分享Google面试值得<span style="color: black;">重视</span>的细节,<span style="color: black;">期盼</span>对<span style="color: black;">大众</span>有所裨益。</p>
      <div style="color: black; text-align: left; margin-bottom: 10px;"><img src="https://p3-sign.toutiaoimg.com/pgc-image/7c2e0f158dd44b38a41e8b525ed95c91~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725974647&amp;x-signature=uA0JYHzpSC3HuMQ40BQOF0%2BVIBw%3D" style="width: 50%; margin-bottom: 20px;"></div>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">作者 | Alex Golec</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">译者 | 弯月</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">责编 | 屠敏</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">出品 | CSDN(ID:CSDNnews)</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">在深入问题之前,有一个令人振奋的<span style="color: black;">信息</span>:我离开了Google!我激动地宣布,我<span style="color: black;">已然</span>加入了Reddit,并在纽约市担任项目经理!</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">声明:虽然面试候选人是我的职责,但这篇<span style="color: black;">文案</span>仅<span style="color: black;">表率</span>我个人的观察、轶事和观点。请不要把本文当成Google、Alphabet、Reddit,或其他个人或组织的官方声明。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">问题</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">想象一下,你在操作一个流行的搜索引擎,<span style="color: black;">况且</span>你在日志中看到了两则<span style="color: black;">查找</span>,<span style="color: black;">例如</span>说“奥巴马的支持率”和“奥巴马的流行度”。(<span style="color: black;">倘若</span>我没记错的话,这些是数据库面试中<span style="color: black;">实质</span><span style="color: black;">运用</span>的例子,虽然这个问题的日期有点过时了……)这两个<span style="color: black;">查找</span>是<span style="color: black;">区别</span>的字符串,<span style="color: black;">然则</span>我认为(相信你<span style="color: black;">亦</span>会同意)从<span style="color: black;">基本</span>上说它们<span style="color: black;">查询</span>的都是同一个东西,在计数<span style="color: black;">查找</span>、<span style="color: black;">表示</span>结果等方面<span style="color: black;">能够</span>将这两个<span style="color: black;">查找</span>视作等价。<strong style="color: blue;"><span style="color: black;">那样</span>,<span style="color: black;">咱们</span><span style="color: black;">怎样</span><span style="color: black;">才可</span><span style="color: black;">晓得</span>两个<span style="color: black;">查找</span>是同义词呢?</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">让<span style="color: black;">咱们</span>用正式语言描述一下。假设你有两个输入。<span style="color: black;">第1</span>个是一个列表,其中<span style="color: black;">每一个</span>元素都是成对的两个字符串,<span style="color: black;">况且</span>它们是同义词。第二个<span style="color: black;">亦</span>是一个列表,<span style="color: black;">每一个</span>元素都是一<span style="color: black;">构成</span>对的字符串,<span style="color: black;">表率</span>两个<span style="color: black;">查找</span>。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">为了<span style="color: black;">详细</span>起见,我<span style="color: black;">经过</span>以下示例输入<span style="color: black;">来讲</span>明:</p>SYNONYMS = [
      (rate, ratings),
      (approval, popularity),
      ]
      QUERIES = [
      (obama approval rate, obama popularity ratings),
      (obama approval rates, obama popularity ratings),
      (obama approval rate, popularity ratings obama)
      ]<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">你的任务是输出一组布尔值,其中的每一个值说明相应的一对<span style="color: black;">查找</span><span style="color: black;">是不是</span>是同义词。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">问题,问题</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">从表面上看,这是一个很简单的问题。然而,你越细想,就会觉得它越<span style="color: black;">繁杂</span>。<span style="color: black;">首要</span>很<span style="color: black;">显著</span>,这个问题的定义并不完善。<span style="color: black;">每一个</span>单词<span style="color: black;">能够</span>有多个同义词吗?单词的<span style="color: black;">次序</span><span style="color: black;">相关</span>系吗?同义词关系<span style="color: black;">是不是</span><span style="color: black;">拥有</span>传递性,<span style="color: black;">亦</span><span style="color: black;">便是</span>说<span style="color: black;">倘若</span>A与B是同义词,而B与C是同义词,<span style="color: black;">那样</span><span style="color: black;">是不是</span><span style="color: black;">寓意</span>着A与C<span style="color: black;">亦</span>是同义词?多个单词<span style="color: black;">构成</span>的词语<span style="color: black;">亦</span>是同义词吗?例如,“USA”与“United States of America”或“United States”是不是同义词?</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">优秀的候选人会立刻将这种模糊性当作机会,让自己脱颖而出。优秀的候选人会做的<span style="color: black;">第1</span>件事<span style="color: black;">便是</span>找出这类的歧义,并设法<span style="color: black;">处理</span>它们。<span style="color: black;">怎样</span>做到这一点因人而异:有些人会到白板前设法手动<span style="color: black;">处理</span><span style="color: black;">详细</span>的问题;有些人则看一眼立即就能看出其中的猫腻。不管<span style="color: black;">怎么样</span>,尽早<span style="color: black;">发掘</span>这些问题至关重要。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">我非常<span style="color: black;">注重</span>这个问题的“问题理解”<span style="color: black;">周期</span>。我<span style="color: black;">爱好</span>将软件工程<span style="color: black;">叫作</span>为分形学科,这<span style="color: black;">寓意</span>着它与分形学有<span style="color: black;">类似</span>之处,即放大问题就<span style="color: black;">能够</span>显现出额外的<span style="color: black;">繁杂</span>性。就在你以为你理解了某个问题的时候,走近一看才<span style="color: black;">发掘</span>你忽略了一个微妙之处,<span style="color: black;">或</span><span style="color: black;">能够</span>改进的实施细节,<span style="color: black;">或</span>找到一种新的看待这个问题的<span style="color: black;">办法</span>从而洞悉<span style="color: black;">更加多</span>细节。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">工程师的能力在很大程度上取决于<span style="color: black;">她们</span>对问题的理解程度。将一个模糊的问题<span style="color: black;">描述</span>转换成一组<span style="color: black;">仔细</span>的<span style="color: black;">需要</span>是这个过程的<span style="color: black;">第1</span>步,有目的地定义问题是我<span style="color: black;">评定</span>候选人处理新<span style="color: black;">状况</span>能力的依据。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">顺便说一句,还有一些不重要的问题,例如“<span style="color: black;">是不是</span>需要<span style="color: black;">思虑</span><span style="color: black;">体积</span>写”,这些问题即使候选人不<span style="color: black;">晓得</span><span style="color: black;">亦</span>不会影响核心算法问题。<span style="color: black;">针对</span>这些问题,<span style="color: black;">通常</span><span style="color: black;">状况</span>下我会给出最简单的答案(就这个例子而言,我会说“假设所有内容都已预处理为小写了”)。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">第1部分:(并非)简单的例子</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">每当候选人遇到这些问题时,<span style="color: black;">她们</span>总是会问我答案,而我总是会从最简单的<span style="color: black;">状况</span><span style="color: black;">起始</span>:单词<span style="color: black;">能够</span>有多个同义词,<span style="color: black;">次序</span>很重要,同义词不可传递,<span style="color: black;">况且</span>同义词只能从一个单词映射到另一个。<span style="color: black;">因此</span>放到搜索引擎中则功能非常有限,但它的细微之处会给面试带来<span style="color: black;">非常多</span>问题。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">这个问题的<span style="color: black;">处理</span><span style="color: black;">方法</span><span style="color: black;">能够</span>高度概括为:将<span style="color: black;">查找</span>分解成单词(用空格分割就<span style="color: black;">能够</span>),并比较相应成对的单词,<span style="color: black;">瞧瞧</span>它们<span style="color: black;">是不是</span>完全相同<span style="color: black;">或</span>是同义词。如下图所示:</p>
      <div style="color: black; text-align: left; margin-bottom: 10px;"><img src="https://p3-sign.toutiaoimg.com/pgc-image/575cb5fa037645db9f97feb665999139~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725974647&amp;x-signature=DxfQQ8lE7VpXGLSEMGPRhi%2FGIkg%3D" style="width: 50%; margin-bottom: 20px;"></div>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">实现大致如下:</p>def synonym_queries(synonym_words, queries):

      synonym_words: iterable of pairs of strings representing synonymous words
      queries: iterable of pairs of strings representing queries to be tested for
      synonymous-ness

      output = []
      for q1, q2 in queries:
      q1, q2 = q1.split(), q2.split()
      if len(q1) != len(q2):
      output.append(False)
      continue
      result = True
      for i in range(len(q1)):
      w1, w2 = q1, q2
      if w1 == w2:
      continue
      elif words_are_synonyms(w1, w2):
      continue
      result = False
      break
      output.append(result)
      return output<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">请<span style="color: black;">重视</span>:<span style="color: black;">这儿</span>我故意<span style="color: black;">无</span>定义words_are_synonyms</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">很简单,对不对?从算法上讲,这非常简单。<span style="color: black;">无</span>动态规划,<span style="color: black;">无</span>递归,<span style="color: black;">无</span>棘手的数据结构等等。只是非常简单的标准库操作,以及线性时间算法,对吧?</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">你可能会这么想,<span style="color: black;">然则</span><span style="color: black;">这儿</span>面比你<span style="color: black;">第1</span>眼看到的更微妙。到<span style="color: black;">日前</span>为止,这个简单的算法中最棘手的部分是同义词比较。虽然易于理解和描述,但同义词比较这部分有可能会出<span style="color: black;">非常多</span>错。下面我来介绍一下我看到的<span style="color: black;">有些</span><span style="color: black;">平常</span>的问题。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">首要</span>声明,在我看来候选人不会<span style="color: black;">由于</span>这些错误而遭遇面试失败;<span style="color: black;">倘若</span>候选人做出来的实现有错,<span style="color: black;">那样</span>我会指出来,<span style="color: black;">她们</span>会<span style="color: black;">调节</span><span style="color: black;">她们</span>的<span style="color: black;">处理</span><span style="color: black;">方法</span>,<span style="color: black;">而后</span>面试继续。<span style="color: black;">然则</span>,面试是一个分秒必争的过程。犯错,<span style="color: black;">发掘</span>错误,改正错误,这些<span style="color: black;">行径</span>都是意料之中的,<span style="color: black;">然则</span><span style="color: black;">因此呢</span>而浪费掉的时间本<span style="color: black;">能够</span>用来干别的,<span style="color: black;">例如</span>找到更优的<span style="color: black;">处理</span><span style="color: black;">方法</span>等。不犯错的候选人很少,<span style="color: black;">然则</span>犯错少的候选人就<span style="color: black;">能够</span>做得更好,<span style="color: black;">由于</span><span style="color: black;">她们</span>花费在清理错误上的时间更少。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">这<span style="color: black;">便是</span>我<span style="color: black;">爱好</span>这道题目的<span style="color: black;">原由</span>:上一篇<span style="color: black;">文案</span>中的题目需要在灵光闪现之际找到一个算法,<span style="color: black;">而后</span>再找到一个简单的实现。这道题目与之<span style="color: black;">区别</span>,它需要在正确的方向上一步步前行。每一步都<span style="color: black;">表率</span>着一个很小的<span style="color: black;">阻碍</span>,候选人<span style="color: black;">能够</span>优雅地跳过去,<span style="color: black;">或</span>被绊倒再站起来。优秀的候选人会利用<span style="color: black;">她们</span>的经验和直觉来避免这些小陷阱,并找到更加详实和正确的<span style="color: black;">处理</span><span style="color: black;">方法</span>,而实力比较弱的人会浪费时间和精力去处理错误,<span style="color: black;">况且</span><span style="color: black;">一般</span>最后只会留下错误累累的代码。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">每次面试我都会看到有人优雅地跳过去了,而有人却摔得鼻青脸肿,但<span style="color: black;">这里</span>我只想举几个例子说明<span style="color: black;">平常</span>的几个小错误。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">意外的运行时杀手</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">首要</span>,有些候选人会<span style="color: black;">经过</span>简单地遍历同义词列表来实现同义词的检测:</p>...
      elif (w1, w2) in synonym_words:
      continue
      ...
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">从表面上看,这似乎很<span style="color: black;">恰当</span>。但仔细观察,你就会<span style="color: black;">发掘</span>这是一个非常非常糟糕的主意。我想跟<span style="color: black;">哪些</span>不<span style="color: black;">认识</span>Python的人解释一下:关键字in是contains<span style="color: black;">办法</span>的语法糖,适用于所有标准的Python容器。<span style="color: black;">这儿</span>的问题在于synonym_words是一个列表,它<span style="color: black;">经过</span>线性搜索实现了关键字in。Python用户<span style="color: black;">尤其</span>容易受到这种错误的影响,<span style="color: black;">由于</span>这种语言会<span style="color: black;">隐匿</span>类型,但C ++和Java用户偶尔<span style="color: black;">亦</span>会犯<span style="color: black;">一样</span>的错误。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">在我的<span style="color: black;">全部</span>职业生涯中,编写这类线性搜索代码的次数屈指可数,<span style="color: black;">况且</span>每次<span style="color: black;">触及</span>的列表都不会超过二十多个元素,即便如此,我还是会写一大篇注释告诉读者<span style="color: black;">为何</span>我<span style="color: black;">选取</span>了这种看似不太理想的<span style="color: black;">办法</span>。我<span style="color: black;">可疑</span>有些候选人在<span style="color: black;">这儿</span><span style="color: black;">运用</span>线性搜索的<span style="color: black;">原由</span>是<span style="color: black;">由于</span><span style="color: black;">她们</span>对Python标准库的<span style="color: black;">认识</span><span style="color: black;">不足</span>,<span style="color: black;">她们</span>不<span style="color: black;">晓得</span><span style="color: black;">怎样</span>在列表上实现关键字in。这是很容易犯的一个错误,虽然这并不致命,<span style="color: black;">然则</span>你对<span style="color: black;">选取</span>的语言<span style="color: black;">不足</span><span style="color: black;">熟悉</span>似乎<span style="color: black;">亦</span>不太好看。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">至于<span style="color: black;">实质</span>的<span style="color: black;">意见</span><span style="color: black;">吗</span>,其实很容易避免这种错误。<span style="color: black;">首要</span>,在你<span style="color: black;">运用</span>python这种无类型的语言时,永远不要忘记对象的类型!其次,请记住,<span style="color: black;">倘若</span>你对列表<span style="color: black;">运用</span>关键字in,<span style="color: black;">那样</span>就会形成线性搜索。除非你<span style="color: black;">能够</span><span style="color: black;">保准</span>这个列表始终非常小,否则它就会<span style="color: black;">作为</span>性能杀手。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">一般</span>,提醒候选人这个输入结构是一个列表就<span style="color: black;">能够</span>让<span style="color: black;">她们</span>反应过来。在我给出提示后就有好戏看了。优秀的候选人会立即想到以某种方式预处理同义词,这是一个不错的开端。然而,这种<span style="color: black;">办法</span><span style="color: black;">亦</span>并非<span style="color: black;">无</span>陷阱......</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;"><span style="color: black;">运用</span>正确的数据结构</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">从上面的代码<span style="color: black;">能够</span>看出,为了在线性时间内实现这个算法,<span style="color: black;">咱们</span>需要一个常数时间的同义词<span style="color: black;">查询</span>。<span style="color: black;">况且</span>在每次常数时间的<span style="color: black;">查询</span>后面都应该有一个hashmap或hashset。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">我感兴趣的不是候选人会从这两个中<span style="color: black;">选取</span>哪一个,而是<span style="color: black;">她们</span>会在里面存什么。(顺便说一句,永远不要<span style="color: black;">运用</span>返回True或False的dict / hashmap。这叫做集合。)大<span style="color: black;">都数</span>的候选人都会<span style="color: black;">选取</span>某种dict / hashmap。我最<span style="color: black;">平常</span>到的错误是一种潜<span style="color: black;">认识</span>的假设,即<span style="color: black;">每一个</span>单词最多<span style="color: black;">仅有</span>一个同义词:</p>...
      synonyms = {}
      for w1, w2 in synonym_words:
      synonyms = w2
      ...
      elif synonyms == w2:
      continue<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">我并不会<span style="color: black;">由于</span>这个错误而<span style="color: black;">处罚</span>候选人。这个示例的输入是有意设计成让人想不起单词<span style="color: black;">能够</span>有多个同义词,而有些候选人<span style="color: black;">基本</span>想不到这种边界<span style="color: black;">状况</span>。在我指出这个错误后,大<span style="color: black;">都数</span>人都会快速改正。优秀的候选人会在<span style="color: black;">初期</span><span style="color: black;">重视</span>到这个问题,从而避免这种麻烦,但<span style="color: black;">一般</span>这不会<span style="color: black;">导致</span><span style="color: black;">海量</span>的时间流逝。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">一个稍微严重的问题是,<span style="color: black;">无</span><span style="color: black;">认识</span>到同义词关系是双向的。你可能<span style="color: black;">重视</span>到<span style="color: black;">以上</span>代码会这么做。然而,改正这个问题可能会出错。请<span style="color: black;">思虑</span>如下实现这个属性的<span style="color: black;">办法</span>:</p>...
      synonyms = defaultdict(set)
      for w1, w2 in synonym_words:
      synonyms.append(w2)
      synonyms.append(w1)
      ...
      elif w2 in synonyms.get(w1, tuple()):
      continue<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">倘若</span>你<span style="color: black;">能够</span>不消耗额外的内存只需执行两次<span style="color: black;">检测</span>,<span style="color: black;">那样</span><span style="color: black;">为何</span>要用两个<span style="color: black;">插进</span>来消耗双倍内存呢?</p>...
      synonyms = defaultdict(set)
      for w1, w2 in synonym_words:
      synonyms.append(w2)
      ...
      elif (w2 in synonyms.get(w1, tuple()) or
      w1 in synonyms.get(w2, tuple())):
      continue<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">提示:始终要问问你自己<span style="color: black;">是不是</span><span style="color: black;">能够</span>减少工作量!事后看来,对<span style="color: black;">查询</span>进行<span style="color: black;">摆列</span><span style="color: black;">显著</span>是一种节省时间的<span style="color: black;">办法</span>,<span style="color: black;">然则</span><span style="color: black;">运用</span>非最优的实现则<span style="color: black;">显示</span>候选人<span style="color: black;">无</span><span style="color: black;">思虑</span>寻找优化的<span style="color: black;">办法</span>。再次重申,我<span style="color: black;">能够</span>给出提示,<span style="color: black;">然则</span>无需我提示不是更好吗?</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">排序?</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">有些很聪明的候选人认为<span style="color: black;">能够</span>对同义词列表进行排序,<span style="color: black;">而后</span><span style="color: black;">运用</span>折半<span style="color: black;">查询</span>法来<span style="color: black;">检测</span>两个单词<span style="color: black;">是不是</span>是同义词。<span style="color: black;">实质</span>上这种<span style="color: black;">办法</span>的<span style="color: black;">重点</span>优点在于,除了输入的同义词列表外,不占用任何额外的空间(假定<span style="color: black;">能够</span>修改输入列表)。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">不幸的是,时间<span style="color: black;">繁杂</span>度并不是很大:对同义词列表进行排序需要花费的时间为Nlog(N),而<span style="color: black;">查询</span>每对同义词的时间为log(N),而<span style="color: black;">以上</span>预处理<span style="color: black;">处理</span><span style="color: black;">方法</span>是线性的,接下来才是<span style="color: black;">查询</span>的常数时间。<span style="color: black;">另一</span>,我并不想让候选人在白板上实现排序和折半<span style="color: black;">查询</span>法,<span style="color: black;">由于</span>(1)排序算法众所周知,<span style="color: black;">因此</span>我<span style="color: black;">晓得</span>候选人可能只是做机械的重复;<span style="color: black;">况且</span>(2)想要写正确这些算法其实还是<span style="color: black;">特别有</span>难度,<span style="color: black;">一般</span>即使最优秀的候选人偶尔<span style="color: black;">亦</span>会犯错,难道你能说<span style="color: black;">她们</span>的编程能力有问题吗?</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">每当候选人<span style="color: black;">供给</span>这种<span style="color: black;">处理</span><span style="color: black;">方法</span>时,我都会询问运行时的<span style="color: black;">繁杂</span>性,并问<span style="color: black;">她们</span>有<span style="color: black;">无</span>更好的<span style="color: black;">办法</span>。顺便提一句:<span style="color: black;">倘若</span>面试官问你有<span style="color: black;">无</span>更好的<span style="color: black;">办法</span>,<span style="color: black;">那样</span>绝大<span style="color: black;">都数</span><span style="color: black;">状况</span>下的答案都是“是”。<span style="color: black;">倘若</span>我问过你这个问题,<span style="color: black;">那样</span>答案肯定是“是”。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">最后的<span style="color: black;">处理</span><span style="color: black;">方法</span></strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">期盼</span>到<span style="color: black;">这儿</span>候选人<span style="color: black;">已然</span>得出了正确且最优的结果。以下是这道题目线性时间线性空间的实现:</p>def synonym_queries(synonym_words, queries):

      synonym_words: iterable of pairs of strings representing synonymous words
      queries: iterable of pairs of strings representing queries to be tested for
      synonymous-ness

      synonyms = defaultdict(set)
      for w1, w2 in synonym_words:
      synonyms.add(w2)
      output = []
      for q1, q2 in queries:
      q1, q2 = q1.split(), q2.split()
      if len(q1) != len(q2):
      output.append(False)
      continue
      result = True
      for i in range(len(q1)):
      w1, w2 = q1, q2
      if w1 == w2:
      continue
      elif ((w1 in synonyms and w2 in synonyms)
      or (w2 in synonyms and w1 in synonyms)):
      continue
      result = False
      break
      output.append(result)
      return output<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">以下是<span style="color: black;">有些</span>简要说明:</p><span style="color: black;">重视</span>dict.get()的<span style="color: black;">运用</span>。你<span style="color: black;">能够</span>采用“先<span style="color: black;">检测</span>key<span style="color: black;">是不是</span>在dict中再获取”的实现,但那样你就失去了展示你对标准库的<span style="color: black;">认识</span>的机会。我个人并不太<span style="color: black;">爱好</span>用了<span style="color: black;">非常多</span>continue的代码,<span style="color: black;">况且</span>有些编程风格指南禁止或不<span style="color: black;">意见</span>这么<span style="color: black;">运用</span>。其实,我最初的代码中有一个bug——<span style="color: black;">查找</span>长度<span style="color: black;">检测</span>后面省略了continue。这个bug不是很糟糕,<span style="color: black;">然则</span>要<span style="color: black;">晓得</span>它很容易出错。<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">第2部分:加大难度!</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">在面试优秀的候选人时,我常常<span style="color: black;">发掘</span>最后还剩下10-15分钟的时间。幸运的是,我<span style="color: black;">能够</span>提出<span style="color: black;">非常多</span>后续的问题,<span style="color: black;">然则</span><span style="color: black;">咱们</span>不太可能在那段时间内编写<span style="color: black;">非常多</span>代码。尽管在一天结束后,我觉得自己<span style="color: black;">不必</span><span style="color: black;">那样</span>做,但我想<span style="color: black;">认识</span>候选人两方面的能力:<span style="color: black;">她们</span>能够设计算法吗?还有<span style="color: black;">她们</span>能够写代码吗?我上一篇<span style="color: black;">文案</span>中的问题<span style="color: black;">首要</span>回答了算法设计的问题,<span style="color: black;">而后</span>还<span style="color: black;">能够</span><span style="color: black;">检测</span>代码,而本文中的这道题目得到答案的<span style="color: black;">次序</span>正好相反。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">等到候选人完<span style="color: black;">成为了</span>这道题目的<span style="color: black;">第1</span>部分后,<span style="color: black;">她们</span>就<span style="color: black;">处理</span>了(这个非常有难度的)编程问题。<span style="color: black;">此时</span>,我<span style="color: black;">能够</span>很自信地说<span style="color: black;">她们</span>具备设计基本算法的能力,还<span style="color: black;">能够</span>将<span style="color: black;">她们</span>的想法转化为代码,<span style="color: black;">况且</span><span style="color: black;">她们</span>还很<span style="color: black;">熟练</span>自己<span style="color: black;">爱好</span>的语言和标准库。接下来这个问题就变得更加有趣了,<span style="color: black;">由于</span>编程<span style="color: black;">需求</span><span style="color: black;">已然</span><span style="color: black;">能够</span>了,<span style="color: black;">咱们</span><span style="color: black;">能够</span>深入<span style="color: black;">科研</span>算法部分了。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">为此,让<span style="color: black;">咱们</span>回到<span style="color: black;">第1</span>部分的基本假设:单词的<span style="color: black;">次序</span>很重要,同义词关系<span style="color: black;">无</span>传递性,同义词<span style="color: black;">不可</span><span style="color: black;">包括</span>多个单词。随着面试的进行,我会改变这些约束,<span style="color: black;">况且</span>在这个编程后的<span style="color: black;">周期</span>里,我和候选人<span style="color: black;">能够</span>只讨论纯粹的算法。我会<span style="color: black;">经过</span><span style="color: black;">有些</span>代码示例<span style="color: black;">来讲</span>明我的观点,但在<span style="color: black;">实质</span>面试中,我会<span style="color: black;">运用</span>纯粹的算法术语进行讨论。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">在深入说明之前,我想说从我的期望值来看后面的面试基本上都属于“加分项”。我个人对这个问题的处理<span style="color: black;">办法</span>是,挑选<span style="color: black;">第1</span>部分考察完全“合格”的候选人,<span style="color: black;">而后</span><span style="color: black;">经过</span>下一个环节的考察从“合格”的候选人挑选“强力”的候选人。“合格”的候选人<span style="color: black;">已然</span>很厉害了,<span style="color: black;">表率</span>了“我相信这个人<span style="color: black;">能够</span>很好地胜任工作”,而“强力”的候选人则<span style="color: black;">暗示</span>“我相信这个人非常优秀,聘用<span style="color: black;">她们</span><span style="color: black;">能够</span>为<span style="color: black;">机构</span>带来巨大的利益。”</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">传递性:朴素的<span style="color: black;">办法</span></strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">我想讨论的<span style="color: black;">第1</span>个问题是<span style="color: black;">相关</span>传递性,<span style="color: black;">亦</span><span style="color: black;">便是</span>说<span style="color: black;">倘若</span>单词A与B是同义词,而单词B与C是同义词,<span style="color: black;">那样</span>单词A与C<span style="color: black;">亦</span>是同义词。反应灵敏的候选人<span style="color: black;">火速</span>会<span style="color: black;">认识</span>到<span style="color: black;">她们</span><span style="color: black;">能够</span><span style="color: black;">调节</span>之前的<span style="color: black;">处理</span><span style="color: black;">方法</span>来<span style="color: black;">处理</span>这个问题,<span style="color: black;">由于</span><span style="color: black;">她们</span>仍然觉得应该<span style="color: black;">检测</span>简单的一对单词<span style="color: black;">是不是</span>是同义词,而有的人则认为之前的算法的核心<span style="color: black;">规律</span><span style="color: black;">已然</span>没用了。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">那样</span><span style="color: black;">到底</span><span style="color: black;">咱们</span>该怎么做呢?一种<span style="color: black;">平常</span>的<span style="color: black;">办法</span>是<span style="color: black;">按照</span>传递关系为<span style="color: black;">每一个</span>单词<span style="color: black;">守护</span>一组完整的同义词。每当<span style="color: black;">咱们</span>向同义词集合中<span style="color: black;">插进</span>一个单词时,<span style="color: black;">同期</span><span style="color: black;">亦</span>把它<span style="color: black;">插进</span>到该集合当前所有单词相应的集合中:</p>synonyms = defaultdict(set)
      for w1, w2 in synonym_words:
      for w in synonyms:
      synonyms.add(w2)
      synonyms.add(w2)
      for w in synonyms:
      synonyms.add(w1)
      synonyms.add(w1)<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">请<span style="color: black;">重视</span>,<span style="color: black;">经过</span>以上代码<span style="color: black;">咱们</span><span style="color: black;">已然</span>深入到我<span style="color: black;">准许</span>候选人<span style="color: black;">选择</span>的这个<span style="color: black;">处理</span><span style="color: black;">方法</span>中了。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">这个<span style="color: black;">处理</span><span style="color: black;">方法</span><span style="color: black;">特别有</span>效,但它远非最佳<span style="color: black;">处理</span><span style="color: black;">方法</span>。想<span style="color: black;">晓得</span><span style="color: black;">为何</span>吗?让<span style="color: black;">咱们</span>来<span style="color: black;">思虑</span>一下这个<span style="color: black;">处理</span><span style="color: black;">方法</span>的空间<span style="color: black;">繁杂</span>性。每当添加一个同义词,<span style="color: black;">咱们</span>不仅要添加到<span style="color: black;">初始</span>单词的集合,还要添加到该单词的所有同义词的集合。<span style="color: black;">倘若</span>该单词有一个同义词,<span style="color: black;">那样</span>就需要添加一条数据。<span style="color: black;">倘若</span>该单词有50个同义词,<span style="color: black;">那样</span>我就需要添加50条数据。如下图所示:</p>
      <div style="color: black; text-align: left; margin-bottom: 10px;"><img src="https://p3-sign.toutiaoimg.com/pgc-image/010f7269222e4dc1a90eeb61733f1888~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725974647&amp;x-signature=PT%2BGnLq76Cg4euYdyq4l04dhrWM%3D" style="width: 50%; margin-bottom: 20px;"></div>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">请<span style="color: black;">重视</span>,<span style="color: black;">咱们</span><span style="color: black;">已然</span>从3个键和6个数据项扩展到了4个键和12个数据项。<span style="color: black;">倘若</span>一个单词有50个同义词,<span style="color: black;">那样</span>就需要50个键和将近2500个数据项。<span style="color: black;">暗示</span>一个单词所需的空间与其同义词集的<span style="color: black;">体积</span>呈二次方式增长,这是巨大的浪费。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">还有其他<span style="color: black;">处理</span><span style="color: black;">方法</span>,但<span style="color: black;">思虑</span>到篇幅有限,我就不<span style="color: black;">这里</span>赘述了。其中最有趣的一种<span style="color: black;">办法</span>是<span style="color: black;">运用</span>同义词的数据结构来构造有向图,<span style="color: black;">而后</span><span style="color: black;">运用</span>广度优先搜索来<span style="color: black;">查询</span>两个单词之间<span style="color: black;">是不是</span>存在路径。这是一个很好的<span style="color: black;">处理</span><span style="color: black;">方法</span>,但<span style="color: black;">查询</span>就变<span style="color: black;">成为了</span>单词同义词集<span style="color: black;">体积</span>的线性。<span style="color: black;">因为</span><span style="color: black;">每一个</span><span style="color: black;">查找</span><span style="color: black;">咱们</span>都需要执行多次<span style="color: black;">查询</span>,<span style="color: black;">因此</span>这个<span style="color: black;">办法</span>并不是最优<span style="color: black;">处理</span><span style="color: black;">方法</span>。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">传递性:<span style="color: black;">运用</span>不相交集</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">事实证明,<span style="color: black;">咱们</span><span style="color: black;">能够</span><span style="color: black;">经过</span><span style="color: black;">运用</span>名为“不相交集”的数据结构在常数时间内<span style="color: black;">查询</span>同义词关系。这种结构<span style="color: black;">叫作</span>为集合,但它<span style="color: black;">供给</span>的功能与大<span style="color: black;">都数</span>人想象中的单词“集合”有所<span style="color: black;">区别</span>。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">平常</span>的集合结构(hashset,treeset)是一个容器,<span style="color: black;">准许</span>你快速<span style="color: black;">查询</span>集合中<span style="color: black;">是不是</span><span style="color: black;">包括</span>某个对象。不相交集(disjoint set)<span style="color: black;">处理</span>的是另一个<span style="color: black;">区别</span>的问题:它并不关注某个集合本身<span style="color: black;">是不是</span><span style="color: black;">包括</span>某个特定项,而是<span style="color: black;">准许</span>你<span style="color: black;">检测</span>两项<span style="color: black;">是不是</span>属于同一个集合。更重要的是,它完成这项操作所花费的时间非常短,只需O(a(n)),其中a(n)是Ackerman函数的相反数。除非你曾经上过高级算法的课程,否则即便你不<span style="color: black;">晓得</span>这个功能<span style="color: black;">亦</span>无需自责,<span style="color: black;">针对</span>所有<span style="color: black;">恰当</span>的输入<span style="color: black;">来讲</span>,这<span style="color: black;">实质</span>上<span style="color: black;">能够</span>在常数时间内完成。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">该算法的操作大体如下。树<span style="color: black;">表率</span>集合,其中每一项都有父项。<span style="color: black;">因为</span><span style="color: black;">每一个</span>树都有一个根(<span style="color: black;">寓意</span>着有一项目的父项是它本身),<span style="color: black;">那样</span><span style="color: black;">咱们</span><span style="color: black;">能够</span><span style="color: black;">经过</span>查看父项来确定两个项目<span style="color: black;">是不是</span>属于同一个集合,直到找到<span style="color: black;">每一个</span>项目的根元素。<span style="color: black;">倘若</span>两个元素<span style="color: black;">持有</span>同一个根元素,则它们必然属于同一个集合。连接这些集合<span style="color: black;">亦</span>很容易:<span style="color: black;">咱们</span>只需找到根元素并将其中一个<span style="color: black;">做为</span>另一个元素的根。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">到<span style="color: black;">这儿</span>为止,一切都很顺利,但在性能方面依然<span style="color: black;">无</span>突破性的<span style="color: black;">发展</span>。这种结构的天才之处在于一种名为“压缩”的过程。假设你有以下树:</p>
      <div style="color: black; text-align: left; margin-bottom: 10px;"><img src="https://p3-sign.toutiaoimg.com/pgc-image/e953188a6ab44270a49c5d3521a31bb0~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725974647&amp;x-signature=s5UXzIvXQ7UNMUqcEreCIcw1g34%3D" style="width: 50%; margin-bottom: 20px;"></div>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">假设你想<span style="color: black;">晓得</span>“speedy”和“hasty”<span style="color: black;">是不是</span>是同义词。从<span style="color: black;">每一个</span>节点<span style="color: black;">起始</span>遍历父关系,直到你<span style="color: black;">发掘</span>它们<span style="color: black;">持有</span>同一个根节点“fast”,<span style="color: black;">因此呢</span>它们肯定是同义词。<span style="color: black;">此刻</span>假设你想<span style="color: black;">晓得</span>“speedy”和“swift”<span style="color: black;">是不是</span>是同义词。你会在一次从<span style="color: black;">每一个</span>节点<span style="color: black;">起始</span>遍历,直到你找到“fast”,<span style="color: black;">然则</span>这一次你<span style="color: black;">重视</span>到你重复了“speedy”的遍历。你<span style="color: black;">能够</span>避免这种重复工作吗?</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">事实证明,你<span style="color: black;">能够</span>。在某种程度上,这棵树中的<span style="color: black;">每一个</span>元素都注定会找到“fast”节点。与其多次遍历这棵树,<span style="color: black;">为何</span>不简单地将<span style="color: black;">每一个</span>元素的父元素改为“fast”呢,如此一来不是就<span style="color: black;">能够</span>减轻工作量了吗?这个过程被<span style="color: black;">叫作</span>作“压缩”,而在不相交的集合中,“压缩”的构建<span style="color: black;">便是</span><span style="color: black;">查询</span>根的操作。例如,在<span style="color: black;">咱们</span>确定“speedy”和“hasty”是同义词之后,上面的树就变<span style="color: black;">成为了</span>下面<span style="color: black;">这般</span>:</p>
      <div style="color: black; text-align: left; margin-bottom: 10px;"><img src="https://p26-sign.toutiaoimg.com/pgc-image/609899b3696c49f48a415bb99d1a2be3~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725974647&amp;x-signature=pdq070eSTWG0KX1XZ6ZA1Fj4FpM%3D" style="width: 50%; margin-bottom: 20px;"></div>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">“speedy”和“fast”之间的<span style="color: black;">每一个</span>单词的父节点都被更新了,“hasty”的父节点<span style="color: black;">亦</span>被更新<span style="color: black;">成为了</span>“fast”。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">如此一来,所有后续<span style="color: black;">拜访</span>都<span style="color: black;">能够</span>在常数时间内完<span style="color: black;">成为了</span>,<span style="color: black;">由于</span>这棵树中的<span style="color: black;">每一个</span>节点都指向了“fast”。分析这种结构的时间<span style="color: black;">繁杂</span>度非常重要:它并非真正的常数,<span style="color: black;">由于</span>它取决于树的深度,<span style="color: black;">然则</span>它并不比常数差,<span style="color: black;">由于</span>它<span style="color: black;">火速</span>就能摊销成常量时间。<span style="color: black;">针对</span><span style="color: black;">咱们</span>的分析,<span style="color: black;">咱们</span>偷懒<span style="color: black;">叫作</span>其为常量时间。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">有了这个概念后,<span style="color: black;">咱们</span>来<span style="color: black;">瞧瞧</span>不相交集合的实现,它<span style="color: black;">供给</span>了<span style="color: black;">咱们</span><span style="color: black;">处理</span>这个问题所需的功能:</p>class DisjointSet(object):
      def __init__(self):
      self.parents = {}
      def get_root(self, w):
      words_traversed = []
      while self.parents != w:
      words_traversed.append(w)
      w = self.parents
      for word in words_traversed:
      self.parents = w
      return w
      def add_synonyms(self, w1, w2):
      if w1 not in self.parents:
      self.parents = w1
      if w2 not in self.parents:
      self.parents = w2
      w1_root = self.get_root(w1)
      w2_root = self.get_root(w2)
      if w1_root &lt; w2_root:
      w1_root, w2_root = w2_root, w1_root
      self.parents = w1_root
      def are_synonymous(self, w1, w2):
      return self.get_root(w1) == self.get_root(w2)<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">有了这种结构,<span style="color: black;">咱们</span>就<span style="color: black;">能够</span>预处理同义词,并在线性时间内<span style="color: black;">处理</span>这个问题了。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;"><span style="color: black;">评定</span>和说明</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">到<span style="color: black;">这儿</span>,<span style="color: black;">咱们</span>就到达了在40-45分钟的面试时间内能做的所有事情的极限了。我挑出了<span style="color: black;">第1</span>部分考查“合格”的候选人,并<span style="color: black;">经过</span>描述(不<span style="color: black;">包含</span>实现)不相交集合的<span style="color: black;">处理</span><span style="color: black;">方法</span>挑出了“强力”的候选人,最后<span style="color: black;">能够</span>让<span style="color: black;">她们</span>向我提问了。我从来没遇到过一个候选人<span style="color: black;">能够</span><span style="color: black;">步行到</span>这一步,还有时间向我提问。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">接下来还有<span style="color: black;">有些</span>后续工作要做:这道题目的一个版本是单词的<span style="color: black;">次序</span>无关紧要,还有同义词<span style="color: black;">能够</span>是多个单词。<span style="color: black;">每一个</span>问题的<span style="color: black;">处理</span><span style="color: black;">方法</span>都富有挑战且令人期待,<span style="color: black;">然则</span>受篇幅所限,我会在后续的<span style="color: black;">文案</span>中讨论。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">这个问题很实用,<span style="color: black;">由于</span>它<span style="color: black;">准许</span>候选人犯错误。<span style="color: black;">平常</span>的软件工程工作<span style="color: black;">包含</span>永无止境的分析、执行和细化。这个问题为候选人<span style="color: black;">供给</span>了机会,<span style="color: black;">能够</span>让<span style="color: black;">她们</span>展示<span style="color: black;">每一个</span><span style="color: black;">周期</span><span style="color: black;">她们</span>的做法。<span style="color: black;">倘若</span>你想<span style="color: black;">经过</span>这个问题<span style="color: black;">作为</span>“强力”的候选人,<span style="color: black;">那样</span>需要如下的技术力:</p>分析问题的描述,找出模糊与不<span style="color: black;">知道</span>的<span style="color: black;">地区</span>,澄清必要的<span style="color: black;">地区</span><span style="color: black;">创立</span><span style="color: black;">知道</span>的问题描述。继续这种做法<span style="color: black;">持续</span>寻找<span style="color: black;">处理</span><span style="color: black;">方法</span>,并遇到新问题。为了最大化效率,在该<span style="color: black;">周期</span>尽可能早地展开这种做法,<span style="color: black;">由于</span>随着工作的<span style="color: black;">发展</span>,改正错误的代价会越来越大。<span style="color: black;">经过</span>易于接近和<span style="color: black;">处理</span>问题的方式重新构建问题。在<span style="color: black;">咱们</span>的这道题中,最重要的一点是观察你<span style="color: black;">能够</span>在<span style="color: black;">查找</span>中<span style="color: black;">摆列</span>相应的单词。实现你的<span style="color: black;">处理</span><span style="color: black;">方法</span>。这<span style="color: black;">触及</span><span style="color: black;">选取</span>最佳数据结构和算法,以及设计出可读且将来易于修改的<span style="color: black;">规律</span>。回过头来设法找到bug和错误。代码中可能会有<span style="color: black;">有些</span><span style="color: black;">实质</span>的bug,<span style="color: black;">例如</span><span style="color: black;">以上</span>我忘记<span style="color: black;">插进</span>“continue”语句,<span style="color: black;">或</span><span style="color: black;">因为</span><span style="color: black;">运用</span>不正确的数据结构等<span style="color: black;">引起</span>的性能问题。当问题定义<span style="color: black;">出现</span>变化时,请重复<span style="color: black;">以上</span>过程,并在适当的时候<span style="color: black;">调节</span>你的<span style="color: black;">处理</span><span style="color: black;">方法</span>,<span style="color: black;">倘若</span>不适用则需要弃用。无论是在面试中,还是在现实世界中,把握<span style="color: black;">机会</span>是一项关键的技能。多多学习数据结构和算法知识。不相交集合的数据结构并不是一种普通的结构,但<span style="color: black;">亦</span>不是非常罕见或完美无缺。<span style="color: black;">保证</span>自己<span style="color: black;">认识</span>工作中的工具的<span style="color: black;">独一</span><span style="color: black;">办法</span><span style="color: black;">便是</span>尽可能地学习。<p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">这些技术都不是能从课本上学来的(除了数据结构和算法)。<span style="color: black;">得到</span>这些技术的<span style="color: black;">独一</span>途径是<span style="color: black;">连续</span>和广泛的实践,这与<span style="color: black;">机构</span>的<span style="color: black;">期盼</span>一致:候选人<span style="color: black;">把握</span>了<span style="color: black;">她们</span>的技术力,并且有<span style="color: black;">海量</span>的实践经验可以有效地<span style="color: black;">运用</span>这些技术。寻找<span style="color: black;">这般</span>的人才是面试的真正目的,而这道题目我<span style="color: black;">运用</span>了很长一段时间。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><strong style="color: blue;">期待</strong></p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">经过</span>本文的阅读,可能你<span style="color: black;">已然</span>看出来这道题目<span style="color: black;">亦</span>被<span style="color: black;">泄密</span>了。从那以后,我还用过几个问题,<span style="color: black;">按照</span>我的心情和<span style="color: black;">初期</span>的候选人提出的问题挑一个(<span style="color: black;">始终</span>问一个问题很无聊)。其中有些问题仍在<span style="color: black;">运用</span>,<span style="color: black;">因此</span>我会保守<span style="color: black;">奥密</span>,但有些<span style="color: black;">已然</span>没人用了!所以,你<span style="color: black;">能够</span>期待在今后的<span style="color: black;">文案</span>中看到这些题目。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">原文:https://medium.com/@</p>alexgolec/google-interview-problems-synonymous-queries-36425145387c

      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">作者:Alex Golec,工程经理@ Reddit NYC,前 Google 员工。</p>
      <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">本文为 CSDN 翻译,如需转载,请注明<span style="color: black;">源自</span>出处。</p>
    </div>




j8typz 发表于 2024-10-12 14:06:06

认真阅读了楼主的帖子,非常有益。

1fy07h 发表于 2024-11-13 02:00:07

你的话语如春风拂面,让我心生暖意。
页: [1]
查看完整版本: Google 经典面试题解析