f**s
发帖数: 29 | 1 本人在洛杉矶地区，准备入手全画幅相机
故在此贱卖手头上的SONY A350
包括A350相机机身一个，Sony SAL50F14 Lens 50mm F1.4镜头一个, Sigma 18-200mm旅
游镜
头一个，Sony F42AM 外闪一个，遥控快门线一条，外加Sony LCS-SC5 Alpha Series
单反包一
个。
所有设备状况非常好，两个镜头都配有另外买的UV镜。
总价 USD 885.00,价格还可以商议。若要商品图片，我可以提供。
有兴趣者可以站内联系，交易只限洛杉矶地区，可以见面交易。谢谢！ |
|
r********7
发帖数: 42 | 2 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列 |
|
a**********s
发帖数: 588 | 3 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到. |
|
r********7
发帖数: 42 | 4 一个就行。
假设 X=[0,2,0,4,3,1,5,0];
Y sorted by X = [0,0,0,1,2,3,4,5]
如何greedy求LCS？ |
|
b***e
发帖数: 1419 | 5 Easy. Computer LCS of s and reverse of s.
Google Longest Common Sequence, it is standard.
(
expected |
|
a****n
发帖数: 1887 | 6 reverse string
DP calc LCS |
|
H****r
发帖数: 2801 | 7 This almost the same as LCS
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else:
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
Guess hoof is right.
be |
|
|
b******7
发帖数: 79 | 9 sorry, 上面的求LCS of s 和 reverse(s)是对的。我自己没理解。当然他们并没有解
释清楚。我解释一下，因为palindrome是 X X_r (用X_r to represent the reversed
x). If we want to transform X to a palindrome with minimum amount of
insertion(note we cannot use replacement and deletion and thus this is
different from edit distance), we have to take advantage of the palindrome
within X as much as possible. That is, for xyyyz, yyy itself is a Palindrome
, therefore, we do not want to disturbe it (as much as we can) when we
transform X. Therefore, |
|
m*****f
发帖数: 1243 | 10 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
也很容易考到
能,
怎么 |
|
f*********r
发帖数: 68 | 11 请教一下LCS怎么做到O(nlogn), 很容易么? |
|
m*****f
发帖数: 1243 | 12 hint 就是 "比如LIS现在是O(nlogn)了", 把LCS转换成LIS就可以了 |
|
g*******y
发帖数: 1930 | 13 要有额外的条件的吧，比如1...n的两个permutation找LCS |
|
f*********r
发帖数: 68 | 14 我不觉的LCS可以很容易的转换成LIS问题.
能说说你是怎么转化的么? |
|
f*********r
发帖数: 68 | 15 这个也太special了吧, 不过好像也不容易把LCS转换成LIS |
|
m*****f
发帖数: 1243 | 16 LCS转换成LIS：
假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
为一个数组, 求此序列LIS (O(nlogn))
比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
组成序列{7,3,4,2,1,7,3,6,7,3}
LIS 为 1 3 6 7, 即 b a x a |
|
m*****f
发帖数: 1243 | 17 你是说A中每个字母在B中出现次数都是O(n)? 那B本身是不是也是O(n^2)级别了？
我想不太清楚， 能举个例子么?
说LCS = O(n^2) 实际上默认了A, B等长， 否则应该是O(n*m), 就假设A,B等长把， 呵呵 |
|
|
H*****L
发帖数: 5705 | 19 n^2的话就不用sort再lcs了吧，有现成的dp |
|
g*******y
发帖数: 1930 | 20 对，n个state，算每个state用n次操作
LCS比较经典嘛，把新问题转化为经典问题也是个常见的思路了~ |
|
x***y
发帖数: 633 | 21 1. You can use LCS, backtracking and take the one with minimum sequence in B or
using the elements in A(assume A is fixed) as key of hash table, and then
hash elements in B(assume B varies a lot) with the index as the hash value,
and try all the indice in the sequential way to find the answer.( for
example, find the first index of h, then the next possbile index of e, and
go on, find a length and corresponding lower index and upper index of the
subsequence; then starting from next index of h, re |
|
a********a
发帖数: 219 | 22 打回去看书。LCS写的很详细了。不看书是没有用的。
求解不影响空间复杂度。 |
|
m******9
发帖数: 968 | 23 他说的方法挺好的
longest palindrome, 就可以用string 和 reverseed string, 然后DP找LCS, 现场
coding也比较方便.
更好的就是你提到的suffix tree |
|
w******0
发帖数: 43 | 24 1. find longest common continue sequence between two sorted int array
such as
a = {1,2,3,4,5,6,7,8}
b = {0,3,4,5,6,9,10,80}
c = {3,4,5,6}
2 Find a longest common continue sequence in two strings
a = "abcdefghigk";
b = "mytestabcdetesting";
C = "abcde"
Question 2 is not LCS
Thanks. |
|
l*****a
发帖数: 14598 | 25 1.
for O(n^2) just use LCS(the longest common subsequence)
for O(n),create a hashtable for b and scan a to see whether each of
the characters are in the hashtable or not
2.
i can't understand what u want
3.
Rabin-karp
4.
a hash table stores the ocurrance of each word,a minimum heap of size 10
which contain the ten most frequent words.
pay attention once the memory can't hold all the words,need some ways to
solve.
such as divide them into K parts,each part use the same and find the top
10,then |
|
l***i
发帖数: 1309 | 26 The solution to the palindrome problem is incorrect.
Example: abcXYZcba
Using the algorithm to reverse it, you get
abcZYXcba
Then the LCS is abc, but abc is not a palindrome in the input string. |
|
h**6
发帖数: 4160 | 27 楼上没懂啥叫LCS吧，sequence不一定需要连续的，只要每个字符都按顺序出现在两个
字符串中即可。 |
|
d****j
发帖数: 293 | 28 我也同意这个观点，reverse+LCS还不够，需要检查common substring的两个起点是否
关于整个数组的长度对称(i, n-i)
网上找到这样一个方法，O(N^2)，简单巧妙：
http://www.stevekrenzel.com/articles/longest-palnidrome
还会有更快的吗?
发信人: shinedance (昵称), 信区: JobHunting
标 题: Re: Amazon Summer Intern Offer, 发面经
发信站: BBS 未名空间站 (Sat May 8 06:03:54 2010, 美东)
I agree! 我也一直有这个疑问。
不管楼主说的是找longest common substring or longest common subsequence in
string and reversed string, 在下面这个例子中都是不对的。There is NO
palindrome in "abcXYZcba", however the longest common substring is abc or |
|
z***e
发帖数: 5393 | 29 I like your solution, simple, clean, easy to maintain.
yes, DP is common for LCS alike problems. However, this problem, is not the
type for DP. If people try to struggle with DP/Suffix, he is simply waste
time (OK, you will be super if you can do it by DP on whiteboard without ANY
bug within 15 mins).
many ppl like to talk about suffix tree --- can u really code it within 10
mins on whiteboard? |
|
|
|
p********7
发帖数: 549 | 32 最近2主要就在面这2家，本来早想投facebook，但是因为有microstrategy约我面试，
所以就把
FB 放在后面了。
M5是一个纽约的猎头找我的，当天就让我电面了他家的CTO，问了下简单的project情况
，并且发了
源代码给他看，第二日就约我onsite。
公司在Manhattan downtown，下地铁不到一个block，因为上次面了flextrade，看到
flextrade的拥挤办公室环境，以及员工颓废的精神面貌，对这家也不报很大希望。
我去的比较早，先坐那里喝咖啡，公司员工超级热心，看我一个人没人管都来问我需要
什么帮助。我
说我在等某某。这家公司的人精神面貌就不一样，除了一个中国人面色很严峻的样子，
其他人感觉都
心态都很轻松。
先是CTO跟我聊了下我的research，然后就是VP带了一个老印，估计也是高级技术人员
。先让我写
N!我写了递归，然后又让用非递归写了一次。继续问递归的确定。接着问求fib数怎么
写代码，这些
代码早练过了，所以不是问题。本来想给他show下我logN的算法，后来他没要求就不写
了。还问了
些stack里面存了哪些东西，以及顺序... 阅读全帖 |
|
p********7
发帖数: 549 | 33 等了1周，Microstrategy终于给offer了，虽然是口头的，但是待遇还不错77k
base+8kbonus+3k relocation虽然我知道我在VP面前表现过于自信，而且VP
是老印，我连他们公司干啥的都没摸清楚，但是这个老印然还不错，没灭了俺。我
准备去VA享受阳光了。
最近2主要就在面这2家，本来早想投facebook，但是因为有microstrategy约我面试，
所以就把FB 放在后面了。M5是一个纽约的猎头找我的，当天就让我电面了他家的CTO，
问了下简单的project情况，并且发了源代码给他看，第二日就约我onsite。
公司在Manhattan downtown，下地铁不到一个block，因为上次面了flextrade，
看到flextrade的拥挤办公室环境，以及员工颓废的精神面貌，对这家也不报很大希望。
我去的比较早，先坐那里喝咖啡，公司员工超级热心，看我一个人没人管都来问我需要
什么帮助。我说我在等某某。这家公司的人精神面貌就不一样，除了一个中国人面色很
严峻的样子，其他人感觉都心态都很轻松。
先是CTO跟我聊了下我的research，然后就是VP带... 阅读全帖 |
|
d**e
发帖数: 6098 | 34 你这个LCS不是 abccba吗？怎么只有abc？
not |
|
d****j
发帖数: 293 | 35 我就把所有technical的题罗列下来吧。很多都是常见题。
1. 给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-case? (3n/2)
====>
n-1 comparison to find min
两两比较之后再在大的一堆中找大的，小的一堆中找小的
n/2 + n/2 - 1 + n/2 -1 = 3n/2.
记得MIT Algorithm (CLRS)上面有提到这个。
2. 怎么merge两个sorted的array，n 个呢？
====>
两个很容易，n个的话，用每个array的第一个元素构建一个heap，再heap sort，每挑
出一个值，再去对应的array中取一个值添到heap中。具体实现可能要修改数据结构。
3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
下一个同层的node。
====>
见 ihas1337code 的blog：
http://www.ihas1337code.... 阅读全帖 |
|
t****o
发帖数: 31 | 36 把给定的string反转,再与原string做LCS
★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite |
|
h*********n
发帖数: 11319 | 37 LCS("3,0,1,7,2,4,5,9", "0,1,2,3,4,5,7,9") |
|
|
p****e
发帖数: 37 | 39 楼上两个都对。
第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
data structure。
我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
第二题想到用LCS就没什么难度了。。 |
|
|
B*******1
发帖数: 2454 | 41 用suffix tree可以做到o(n),但是现场面试肯定不可能当场写这个suffix tree的。
有另一个解法是lcs(str, reverse(str)），
但是这个方法对于这种string不适合，"abcfghicba"
出来的结果会是abc，是不是这种情况下可以做post-processing,再check得到的这个
substring是不是palindrome啊。
thanks。 |
|
d*******d
发帖数: 2050 | 42 suffix array/ suffix tree都只能找到lcs,
但是没有解决他的问题.
tree |
|
r*******g
发帖数: 1335 | 43 Hi
能否详细说说suffix tree怎么做，如果像你们讨论的那样suffix tree很难O(n)构造出
来，那这个题的复杂度究竟是多少呢？我能想到的就是构造两个suffix tree混在一起
，然后再找LCA。
你这里的lcs是什么意思？
谢谢了 |
|
B*******1
发帖数: 2454 | 44 Thanks, 我也是这么想的，但是觉得这么做还不如用lcs(str,reverse(str)),dp的时候
每次update maximum length的时候check check是不是palindrome. |
|
f*********i
发帖数: 197 | 45 楼主,如果你觉得lcs(str,reverse(str)),dp是一个好方法,那么也就是说,你觉得O(n2)
是一个可以接受的解
请看看我提供的解法,这个也是O(n2)时间的
for(every character in string){
1) in aba case:
keep testing two points on its both sides to see if they are the
same
2) in abba case:
Same approach but in abba format
} |
|
x*******7
发帖数: 223 | 46 考古以前的帖子：
Dynamic programming
1. BST binary search tree?
2. COV
3. ILP
4. KS
5. LCS longest common subsequence?
6. LSP
7. MCM
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP |
|
a****a
发帖数: 186 | 47 你这个题是求最长降序子序列，我第一反应就是用DP求9-0和给定数组的LCS
你给的解法有空研究一下看看时间复杂度是多少。给的链接收藏了..好资源 |
|
|
z*********8
发帖数: 2070 | 49 最后补齐那下怎么做？ 用LCS做palindorm总让我觉得不可靠， 不知道能不能用
longest palindrome substring来做 |
|
h**********l
发帖数: 6342 | 50 他倒过来的LCS，跟你的 longest palindrome substring是一样的意思 |
|
