Amazon on site 01/15/2015加油

第一题是O(n)吧，从前往后扫，stack存index，如果当前元素比stack[peek()]小，就push，否则，[pop()] = 当前元素值，然后一直pop()到当前元素比stack[peek()]小，再push当前元素。最后留在stack中index的元素没有比它大的。

Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment 这本书，楼主能发一份吗？zhaokai0213@gmail.com

楼主考的好难啊，感觉一道leetcode和cc上的题都没有

lz第二题能稍微详细解释一下不？按照你的意思应该输出anana啊？还是我理解的有问题？多谢多谢！

shire1989 发表于 2015-1-21 07:24
lz有这本书的电子版吗?Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment

我也木有，因为每次都是看的在线版本。但是今天突然上去在线的发现后面部分也看不了。

cvfox4fun 发表于 2015-1-21 10:23
擦，我觉得自己上，也是挂...
第一题时间复杂度是O(n)吧？
每个元素只会被更改一次。

对，就是O(n)。烙印就是想稍微为难一下你，不要被他绕进去就好了

xiaoxin213 发表于 2015-1-21 14:58
第一题是O(n)吧，从前往后扫，stack存index，如果当前元素比stack小，就push，否则， = 当前元素值，然后一 ...

对，第一题就是你那样做的。是O(n)

鱼吃鱼翅 发表于 2015-1-21 16:06
lz第二题能稍微详细解释一下不？按照你的意思应该输出anana啊？还是我理解的有问题？多谢多谢！

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
anana只出现了一次，题目说要至少出现两次的longest substring。
Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)

ran784388220 发表于 2015-1-21 16:00
楼主考的好难啊，感觉一道leetcode和cc上的题都没有

其实感觉主要就是第二轮三姐出的以前没见过，其他感觉面试前好好准备应该能cover掉。剩下的真的就靠人品了！已经move on了

姑爷圈 发表于 2015-1-21 11:30
要求楼主当场建suffix tree??

补充内容 (2015-1-21 11:32):

面试的时候丫的她就没提suffix tree。就让我干想怎么优化。

cgdong2012 发表于 2015-1-21 08:58
三姐问你的题跟去年问我的一模一样， 我当时用 hashmap  做的。她说最好用 suffix tree ， 最后跪了

卧槽，杀人题啊！