作者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