Google Intern新鲜面经

nemoleoliu 发表于 2015-12-9 09:46
rotate是每个character rotate一下 不是整体string rotate   a-b-c-d-e-f-g-h-...x-y-z 按照字母表顺序 r ...

是不是可以这样做 ?: 每次判断 if str1[i]-'a'==str2[i]-'a'-n , n is rotation number

补充内容 (2015-12-9 11:13):
str1.charAt(i)-'a'==str2.charAt(i)-'a'-n

wtcupup 发表于 2015-12-9 11:12
是不是可以这样做 ?: 每次判断 if str1-'a'==str2-'a'-n , n is rotation number

补充内容 (2015-12-9 1 ...

n是unknown的，你不知道每个string是从base case rotate了几次

最简单的方法就是 将每个string 都做一下旋转操作 使得第一个字母是a

gisonrg 发表于 2015-12-9 10:01
哈哈恭喜！楼主第一个人的题和我的第二个小哥出的题一模一样的，估计是同一个人吧。。。
然而为什么我都一 ...

ez  我同学也是等了一个星期才出的结果 他也过了

第一题是，所有数组都以string的实行存在在以个list里面？ 比如 ［ “abcd","bacd","cccc","ddds"....］这样？
然后找出所有pair,满足上面的要求？每个词都rotate相同的次数，然后可以到另外以个词？

如果我理解对了，这题可以这么做么。

  走2个for loop遍历每以个词的pair组合，然后covert每个词tochararry, charAt[index1] - charAt[index2]。如果每个char相减的数相同，那么说明这个pair满足要求。
比如，
abcd, bcde.   'b'-'a' = 'c'-'b'='d-c' = 'e'-'d' = 1 所以，这个pair是对的。



补充内容 (2016-1-7 10:37):
这个不是optimal solution

第2轮的第1题是卖萌么。还是有什么特殊的follow-up？

补充内容 (2015-12-9 12:10):
有空间和时间复杂度的特殊要求么？

xiaozhuxiaozhu 发表于 2015-12-9 12:09
第2轮的第1题是卖萌么。还是有什么特殊的follow-up？

补充内容 (2015-12-9 12:10):

O(m+n) no additional memory

xiaozhuxiaozhu 发表于 2015-12-9 12:08
第一题是，所有数组都以string的实行存在在以个list里面？ 比如 ［ “abcd","bacd","cccc","ddds"....］这 ...

我和你的思路差不多，找出char之间的distance, 但是用不着两个for loop
比如abcd，不管怎么rotate，char之间的distance总是['b'-'a','c'-'b','d'-'c'] = [1,1,1],把这个distance弄成一个string，比如abcd就成了“111”, cab 就成了"-21"（如果是single char肯定都是同一组），用一个hashmap把有着相同distance的string都放在一起就好了
不过题主的全部转成’a'开头是个很好的点子呀！当时我咋没想到，还是先给的brute force再被小哥提示一下才想到这么做的
总之这题的思路就是pre-process一下把所有的string都map去它的group,就可以用O(n)的时间解出来了

nemoleoliu 发表于 2015-12-9 13:26
O(m+n) no additional memory

那就是用merge sorted array那种，比较每个index上面的数，根据大，小，等于三种情况增加index么

gisonrg 发表于 2015-12-9 13:26
我和你的思路差不多，找出char之间的distance, 但是用不着两个for loop
比如abcd，不管怎么rotate，char ...

我以为pair是指必须2个2个放在一起。
翻转a确实是很好的方法。