› 看板 Oversea_Job 關於我們 聯絡資訊
作者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
推 Aristippus:根據經驗有的面試官准、有的會叫我現場implement 03/10 03:46
→ RockLee:了解 順便問一下 舉例的這個問題有比較容易實作的算法嗎? 03/10 21:56
推 neutrino:這個問題想成suffix array會比suffix tree 更直覺吧 03/12 22:29
→ neutrino:而且suffix array等於是把S'=SS 的所有suffix都排序好了 03/12 22:30
→ neutrino:這題等於是只要找SS的suffix裡面當中長度>=len(S)的lexic 03/12 22:31
→ neutrino:lexical min, 應該還可以比作suffix array更快 03/12 22:31
→ neutrino:至於當場實做suffix array, 如果用 03/12 22:32
→ neutrino:Karkainen, Sanders, Burkhardt (2006) 的方法, 應該很好 03/12 22:33
→ neutrino:implement, 用C寫一百行吧我想. 03/12 22:34
→ neutrino:不過我有點好奇如果不是相關背景(我之前工作sequence, 03/12 22:35
→ neutrino:string的東西碰比較多), 現在一般CS出身會知道這個suffix 03/12 22:36
→ neutrino:array 的演算法(2006)嗎? (要當場想出來的話更是..程度 03/12 22:36
→ neutrino:超強!) 03/12 22:37
推 neutrino:sorry剛剛說得suffix array Karkkainen et al 2006是在 03/12 22:42
→ neutrino:JACM, but a preliminary version was published 2003 03/12 22:42
→ RockLee:感謝n大的回應 03/14 18:12