02/26 Amazon Intern Phone Interview新鲜跪经

Yasuo 发表于 2016-2-27 05:01
似乎第二个pass不用全扫一遍？直接把string从后往前扫，return第一个出现次数是twice的character就好了？

average running -time compexity都是o(n)。
你从后忘前扫，假如每次都是最前面2个char是结果，那么和最后2个char是结果，没有区别。

这个题可能可以考虑用ascii码做。先声明一个ref＝int[128]，全部放0，从后往前扫，每遇到一个char就把ref里的值改成1。如果遇到1就返回。这个方案虽然也是O(n) ，但是空间复杂度更小

xiaozhuxiaozhu 发表于 2016-2-27 04:13
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

我想问下万一string里说会出现unicode的字符时候，array table还好用吗还是得老老实实上HashMap了？
或者说面试一般就玩玩ascii或者UTF-8这种，可以在一个字节内解决呢？

AlexPinhead 发表于 2016-2-27 06:30
我想问下万一string里说会出现unicode的字符时候，array table还好用吗还是得老老实实上HashMap了？
或 ...

int[256]
应该可以handle unicode的字符的吧。

xiaozhuxiaozhu 发表于 2016-2-27 06:48
int[256]
应该可以handle unicode的字符的吧。

unicode不是一般16bit吗，请教下怎么用2^8来解决呢？

AlexPinhead 发表于 2016-2-27 06:54
unicode不是一般16bit吗，请教下怎么用2^8来解决呢？

不懂你说的啥意思
你原本意思是如果 char = '!' 或者‘＃’ 这种，能不能array table?

xiaozhuxiaozhu 发表于 2016-2-27 06:58
不懂你说的啥意思
你原本意思是如果 char = '!' 或者‘＃’ 这种，能不能array table?

我的意思是说如果string里有“Ё”或者“խ”这种怎么办，前者U+0401，后者U+056D，超出256了

AlexPinhead 发表于 2016-2-27 09:06
我的意思是说如果string里有“Ё”或者“խ”这种怎么办，前者U+0401，后者U+056D，超出256了

你想的好多啊。。。。

xiaozhuxiaozhu 发表于 2016-2-27 09:15
你想的好多啊。。。。

在hashmap里放的时候不就可以知道了吗，不用第二个遍历，hashmap里放的时候一遇到2就记录到变量res里，下次再遇到更新一下，最后返回res

xiaozhuxiaozhu 发表于 2016-2-27 06:58
不懂你说的啥意思
你原本意思是如果 char = '!' 或者‘＃’ 这种，能不能array table?

你好 请问 ascii 和 unicode 这两2个 到底 int[128] int[256] 够不够用啊 ..