Google intern 电面

论坛匿名用户 发表于 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不能验证吗？  谢谢拉

fxctm2311 发表于 2019-1-16 09:14
ABC to DED 是会return true的。 因为检查map冲突只会检查 1个key 不可以map多个value，但不会管多个key  ...

你让我举反例之前，能不能给我一个证明，证明你的算法是正确的？我觉得你写的完全是另外一个题目。。。跟题目最重要的条件"一次变化必须把同一字符 全部进行变化"完全没关系，完全没考虑。。。我觉得面试官也会问这样的问题吧。。。

论坛匿名用户 发表于 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。

再次谢谢楼主回复

fxctm2311 发表于 2019-1-17 03:23
我没有要argue的意思。我明白你说我的思路是另外一道题的意思（具体是lc哪道题题我也忘记了）。但是我觉 ...

补充：
刚刚又想到另外一个理解方式， 关于“一次变化必须把同一字符 全部进行变化”：
对于同一个字符‘A’ 实际上只会运行进行一次变化，否则的话， 第二次变化是一定会影响到前一次变化的结果的。或者说，在第一个字符串里， 通过变化得来的字符， 是不允许再次进行变化的。
之前的那个例子 ABA -》 DFG， 第一个A如果已经变成D了， 会要求后边第三个A进行同样的变化，成为D， 所以第三个字符是不会被允许进行再次变化的操作的

intern是全面电面吗 还是需要onsite啊  一共几轮呢

fxctm2311 发表于 2019-1-17 03:37
补充：
刚刚又想到另外一个理解方式， 关于“一次变化必须把同一字符 全部进行变化”：
对于同一个字 ...

你看下这个例子呢
ABCD.....XYZ
ZYX........CBA
能建立一一映射 但是应该返回false

论坛匿名用户 发表于 2019-1-17 04:46
你看下这个例子呢
ABCD.....XYZ
ZYX........CBA

为什么会返回false？这个例子每个字母都只会map一次不是吗？ map里最后是A -》Z 同时 Z-》 A， 但是这并不影响判断啊。

fxctm2311 发表于 2019-1-17 12:53
为什么会返回false？这个例子每个字母都只会map一次不是吗？ map里最后是A -》Z 同时 Z-》 A， 但是这并 ...

这样吧 假设只有两个字符 AB可以选择，而不是有26个字母。 AB 可以变化到BA吗？ 不可以。
step1 把AB中的A变成B -> BB
step2 无法从BB变到BA， 因为当把B变成A的时候，所有B都跟着变成A，即是BB变成AA。

论坛匿名用户 发表于 2019-1-17 13:04
这样吧 假设只有两个字符 AB可以选择，而不是有26个字母。 AB 可以变化到BA吗？ 不可以。
step1 把AB中 ...

感觉我终于知道你的点在哪了。 谢谢

fxctm2311 发表于 2019-1-17 13:53
感觉我终于知道你的点在哪了。 谢谢

Finally!