作者RockLee (Now of all times)
看板Oversea_Job
标题[北美] (CS)想请教面试时可以用自备的library吗?
时间Sat Mar 9 19:19:16 2013
例如说像这个问题:
http://www.careercup.com/question?id=14711684
Write the code to find lexicographic minimum in a circular array,
e.g. for the array BCABDADAB, the lexicographic mininum is ABBCABDAD.
一个可能的 Linear time algorithm: (copy from CareerCup)
Given string S.
For String S' = SS (append S to itself).
Compute suffix tree (ST) of S'.
Now do a depth first search of ST,
picking the children in lexicographic order.
Pick the first node you find, at depth |S|.
建 suffix tree 可以在 linear time 做到,
不过像 Java 本身的 library 似乎不包含建 suffix tree,
要在不到一个小时的时间 implement 建 suffix tree 的 function,
至少对我而言应该做不到 Orz...
这种情况是否一定要想出其它的解法,
可以跟 interviewr 说假设已经有个建 suffix tree 的 function,
然後 balabala... 吗? 有机会被接受吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.243.4.124
1F：推 Aristippus:根据经验有的面试官准、有的会叫我现场implement 03/10 03:46
2F：→ RockLee:了解 顺便问一下 举例的这个问题有比较容易实作的算法吗? 03/10 21:56
3F：推 neutrino:这个问题想成suffix array会比suffix tree 更直觉吧 03/12 22:29
4F：→ neutrino:而且suffix array等於是把S'=SS 的所有suffix都排序好了 03/12 22:30
5F：→ neutrino:这题等於是只要找SS的suffix里面当中长度>=len(S)的lexic 03/12 22:31
6F：→ neutrino:lexical min, 应该还可以比作suffix array更快 03/12 22:31
7F：→ neutrino:至於当场实做suffix array, 如果用 03/12 22:32
8F：→ neutrino:Karkainen, Sanders, Burkhardt (2006) 的方法, 应该很好 03/12 22:33
9F：→ neutrino:implement, 用C写一百行吧我想. 03/12 22:34
10F：→ neutrino:不过我有点好奇如果不是相关背景(我之前工作sequence, 03/12 22:35
11F：→ neutrino:string的东西碰比较多), 现在一般CS出身会知道这个suffix 03/12 22:36
12F：→ neutrino:array 的演算法(2006)吗? (要当场想出来的话更是..程度 03/12 22:36
13F：→ neutrino:超强!) 03/12 22:37
14F：推 neutrino:sorry刚刚说得suffix array Karkkainen et al 2006是在 03/12 22:42
15F：→ neutrino:JACM, but a preliminary version was published 2003 03/12 22:42
16F：→ RockLee:感谢n大的回应 03/14 18:12