h*******e
发帖数: 125 | 1 两道coding题目:
1. check if a string is a palindrome.
2. find longest palindrome in a string.
然后瞎聊一会儿互相道别 |
w****x
发帖数: 2483 | |
Z*****Z
发帖数: 723 | 3 T家内推意义不大。第一，不觉得能skip掉电面。
第二，他家现在正在grow，所以有很多opening，我在他家网站上直接投了两个职位，
一个1分钟被拒，另外一个1个小时收到电面request。
【在 w****x 的大作中提到】
: 求twitter内退
|
w****f
发帖数: 684 | |
q***y
发帖数: 236 | 5 第二问答出O(n^2)可以吗？是不是一定要背住O(n)解？ |
H****r
发帖数: 2801 | 6 2） 这样的题个人感觉已经不适合放在面试题了...
【在 h*******e 的大作中提到】
: 两道coding题目:
: 1. check if a string is a palindrome.
: 2. find longest palindrome in a string.
: 然后瞎聊一会儿互相道别
|
l*****a
发帖数: 14598 | 7 你当场背得出来
O(n)建trie同时support O(1) to get LCA?
【在 q***y 的大作中提到】
: 第二问答出O(n^2)可以吗？是不是一定要背住O(n)解？
|
h*****3
发帖数: 1391 | 8 这第二题要讲思路还是coding啊？
思路和coding还是不一样的。 |
h*******e
发帖数: 125 | |
c******t
发帖数: 391 | 10 想到两种O(n^2)算法，
1)对每一个子串，判断其是否存在于reverse(str)中，找出符合条件的最长者；
2)从arr[1]开始，对每一个元素往两端拓展，直到越界或者arr[left]!=arr[right]跳
出，找出最长的。
O(n)解法不太了解， 望指点…… |
|
|
h********u
发帖数: 134 | 11 O(n) is kinda difficult.. |
l***m
发帖数: 339 | 12 请问你是fresh吗？
【在 h*******e 的大作中提到】
: 两道coding题目:
: 1. check if a string is a palindrome.
: 2. find longest palindrome in a string.
: 然后瞎聊一会儿互相道别
|
I*********7
发帖数: 125 | |
c******t
发帖数: 391 | 14 coask……
【在 I*********7 的大作中提到】
: 第二题 trie tree电面怎么搞?
|
g*****e
发帖数: 282 | 15 我觉得2）瞬间答出o（n）的基本确定看过题。能看懂记下来很不容易
此外我觉得可以从arr[n/2]开始找，如果当前已经找到长度为l的，则arr[(n-l)/2]和
arr[l/2]之前的就不用再继续搜索了，实际使用时更快
【在 c******t 的大作中提到】
: 想到两种O(n^2)算法，
: 1)对每一个子串，判断其是否存在于reverse(str)中，找出符合条件的最长者；
: 2)从arr[1]开始，对每一个元素往两端拓展，直到越界或者arr[left]!=arr[right]跳
: 出，找出最长的。
: O(n)解法不太了解， 望指点……
|
g*****e
发帖数: 282 | 16 2）现场想出trie还能飞快code出来的是神人，要么就是做过！ lol
【在 c******t 的大作中提到】
: 想到两种O(n^2)算法，
: 1)对每一个子串，判断其是否存在于reverse(str)中，找出符合条件的最长者；
: 2)从arr[1]开始，对每一个元素往两端拓展，直到越界或者arr[left]!=arr[right]跳
: 出，找出最长的。
: O(n)解法不太了解， 望指点……
|
p*****2
发帖数: 21240 | |
l*****a
发帖数: 14598 | 18 似乎给你发过好几次
【在 p*****2 的大作中提到】
: O(n)的code要多少代码？
|
w****x
发帖数: 2483 | |
p*****2
发帖数: 21240 | 20
是吗？估计存哪里了找不着了。
【在 l*****a 的大作中提到】
: 似乎给你发过好几次
|
|
|
l*****a
发帖数: 14598 | 21 所以。。。
你明白了吧？
【在 w****x 的大作中提到】
: 今天才知道这题有O(n)解....
|
e***s
发帖数: 799 | 22 Longest palindromic substring O(n)的解 LeetCode上都有说的，我直接SKIP，能做
出来连我自己都不相信。。。。 |
C***U
发帖数: 2406 | 23 第二题可以用n2时间么?
【在 h*******e 的大作中提到】
: 两道coding题目:
: 1. check if a string is a palindrome.
: 2. find longest palindrome in a string.
: 然后瞎聊一会儿互相道别
|
w***o
发帖数: 109 | 24 最快最好的算法是Leetcode上说的
http://www.leetcode.com/2011/11/longest-palindromic-substring-p
在别的网站看过很多次，只有Leetcode讲的最清楚，我终于看明白了。
除此之外，至少还有一种O（n)的解法，就是用后缀数组加LCP。不过建后缀数组的算法
很难（如果不背的话）当场写出来。 |
b*****e
发帖数: 474 | 25 brutal force O(N*N) answer:
assuming input string a with strlen N.
int begin, end, i;
int len[N], maxlen=0;
for (i=0; i< 2*N-1; i++ ) {
// start from middle
begin = i/2;
end = (i+1)/2;
len[i] = 0;
while ( begin>=0 && end
len[i]+= (begin--==end++)? 1: 2;
if ( len[i] > maxlen ) maxlen = len[i];
}
output maxlen;
may be this can be optimized to reach O(N) |
