Google intern 电面

求求各位先加点分，没分看面经了。加了分有问必答。一个月前的intern电面
[hide=110
1. guess the word. 不同的是，只知道正确

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

/strong>
我觉得加分再问问题应该是论坛礼节。。。

补充内容 (2019-2-13 00:23):
这是帮朋友发的，他说他懒得再回答关于面经的问题了。大家有什么就看楼里的回复吧 基本答案都有。

colored 发表于 2019-1-10 12:32
第二题的思路麻烦能说一下吗？

A: abae
B: eded
麻烦的是这样的字符串，a要变成e，但是一旦变成e，A最后一个字符e就无法单独变成d。这个时候就需要来个备用字符，先把A中的最后一个e变成h，然后再把a变成e，就可以变了。然后每次找一个备用字符就行了，如果找不到就说明A不能变成B

论坛匿名用户 发表于 2019-1-16 09:48
你让我举反例之前，能不能给我一个证明，证明你的算法是正确的？我觉得你写的完全是另外一个题目。。。跟 ...

我没有要argue的意思。我明白你说我的思路是另外一道题的意思（具体是lc哪道题题我也忘记了）。但是我觉得我理解的你关于这道题的描述，感觉就是那道题的另外一种表述。
然后 关于 "一次变化必须把同一字符 全部进行变化"：
  因为 map 每一个key 只允许对应一个value ，目的不就是想表达 每个同样的字符只允许变成另外一个同一个字符。 如果运行过程中发现 同一个字符 ‘A' 需要先变成D， 然后到后面又需要变成‘C' 才能让两个字符串相等， 说明没办法做到 "必须把同一字符 全部进行变化"， 反过来说， 就是如果我要把同一字符进行全部变化， 就没办法做到 字符串的转换，所以return false；

关于证明的话，我不太会证明。不过我可以说下我想到用hash来做的原因，您看我说的是不是make sense：
我觉得这个题的核心就是你提到的那个条件： "一次变化必须把同一字符 全部进行变化"。 我的理解 就是不管怎么变化，变化多少次，在这个字符串里， 所有这个字符只能变化成另外同一个字符， 不可以出现前半段字符‘A'变成’C'， 后半段‘A’变成‘D'这种情况。而“一个字符只可以变化成另外一个字符” 这个想法的实现就需要hash 的key -》 value来做，而且这个限制是单向的，既一个key只可以map一个value， 而同一个value可以被不同的key 来map。

再次谢谢楼主回复

论坛匿名用户 发表于 2019-1-16 06:24
我大概知道你说的是哪个题。在你理解的题目中ABC 可不可以变成 DED？是不是因为发现最后一个C想映射成D的 ...

ABC to DED 是会return true的。 因为检查map冲突只会检查 1个key 不可以map多个value，但不会管多个key map同一个value。 所以 A-》D， B-》E， C-》D 是可以通过验证的。
loop里面大概是这个逻辑：
  if(map.containsKey(aChar)){
    if(map).get(key) != bChar)
      return false;
  }else
    map.put(aChar, bChar);

麻烦楼主看看还有其他case不能验证吗？  谢谢拉

有通知了吗

多谢楼主分享，请问第二题莉蔻有原题嘛

FrancisYL 发表于 2019-1-10 09:32
多谢楼主分享，请问第二题莉蔻有原题嘛

我印象里我是见过这个题的（但是不确定是不是在leetcode上）。我现在在复习我刷过的题，如果我看到了 我会告诉你。你也可以百度一下 应该是有的。

第二题是不是二维DP的那个edit distance？

Husky_wang 发表于 2019-1-10 09:40
第二题是不是二维DP的那个edit distance？

dp[i][j] = A的前i个字符 改成 B的前j个字符所花费的代价？看起来好像不是的。你能找到leetcode原题给我看看具体描述吗 或者你自己详细说一下。

请问正确word长度是啥意思

补充内容 (2019-1-10 10:01):
guess返回的是啥？

请问楼主第一题怎么答的呀

第二题的思路麻烦能说一下吗？