s****a
发帖数: 528 | 1 NUANCE的，我做了3天，给出的解法据面试的说是最好的，为此拿到OFFER
做的不比我差的可以拿20个包子，欢迎讨论
下礼拜给答案
The Fibonacci palindrome problem |
s*****e
发帖数: 16824 | 2 这个题我想过一会，似乎可以搜索a==c，然后向两边延伸，但是我不知道复杂度是多少
，反正应该小于O(n^2).
【在 s****a 的大作中提到】
: NUANCE的，我做了3天，给出的解法据面试的说是最好的，为此拿到OFFER
: 做的不比我差的可以拿20个包子，欢迎讨论
: 下礼拜给答案
: The Fibonacci palindrome problem
|
s*****n
发帖数: 5488 | 3 same idea like DP. for lengtth in 3 to n for i = 1 to n.
O(N^2) but this is too obvious.
【在 s*****e 的大作中提到】
: 这个题我想过一会，似乎可以搜索a==c，然后向两边延伸，但是我不知道复杂度是多少
: ，反正应该小于O(n^2).
|
t*****j
发帖数: 1105 | 4 这个第一个条件 是说明sequence对称是吗？也就是说必须是回文sequence对吗？
口。 |
g*******y
发帖数: 1930 | 5 好久没做题了，为了20个包子，我来试试吧。
从左边开始，看第一个3-tuple,{a0, a1, a2}
maintain the following info:
current best solution length: 0
hash each new number's first occurrence: a0~0, a1~1
case1: current 3-tuple is valid
find a2 in hash table:
if (found) {
current_best = MAX(current_best, |hash[a2] - current index of a2|;
} else {
hash[a2] = current index of a2; // insert a2 into hash table.
}
case2: current 3-tuple is invalid:
possible_best = solution of (a1 ... an);
return MAX(current_best, possible_best);
【在 s****a 的大作中提到】
: NUANCE的，我做了3天，给出的解法据面试的说是最好的，为此拿到OFFER
: 做的不比我差的可以拿20个包子，欢迎讨论
: 下礼拜给答案
: The Fibonacci palindrome problem
|
x***y
发帖数: 633 | 6 First of all, find Longest Common extension of sequence(which uses matching
statistics in suffix tree and constant time LCA to find length of longest
substring that start from any positions at 2 string in constant time after
linear preprocsing)
2nd, find all maximal palindromes (which means that if A[i:j] is palindrome,
then A[i-1:j+1] can not be palindrome) in linear time with the help of
suffix tree and Longest Common extension.
3rd, find the segments in the original sequnce that satisfes the 2nd
requirement.
Finally, find segments intersection of the results of 2nd step and 3rd step
that has the middle(1 element or 2) of max palindromes in 2nd step as the
middle of the segment in linear time. We find the intersection segment with
longest length in linear time.
So, total time is linear as each step is linear.
PS: If I'm right, I will donate the baozi to the jobhunting...
【在 s****a 的大作中提到】
: NUANCE的，我做了3天，给出的解法据面试的说是最好的，为此拿到OFFER
: 做的不比我差的可以拿20个包子，欢迎讨论
: 下礼拜给答案
: The Fibonacci palindrome problem
|
s****a
发帖数: 528 | 7 Solution is linear O(n).
but how to achieve the best within linear is another question. |
E********a
发帖数: 124 | 8 其实答案就是两句话，
一，找满足条件2的连续的segments。
二，在这些segments中找最长回文 (O(n), prefix-tree + LCA)
【在 s****a 的大作中提到】
: Solution is linear O(n).
: but how to achieve the best within linear is another question.
|
d*********i
发帖数: 628 | |
b***e
发帖数: 1419 | 10 I guess the trick you value is that you compress the array:
1. Discard the numbers but only remember the 3 cases by 0, 1 and 2.
2. Compact the array by counting the 3 symbols to form a much short array.
3. Find palindome on the shorter array.
【在 s****a 的大作中提到】
: Solution is linear O(n).
: but how to achieve the best within linear is another question.
|
s****a
发帖数: 528 | 11 Is there any better solution than prefix tree and also linear?
Without internet and book, I cannot actually code the prefix-tree |
I*********g
发帖数: 93 | |
