[請益] Interview問題
遇到一個interview的問題，請教一下神通廣大的版友
輸入一個序列（陣列）
e.g. 0 14 887 3 x 2 y 4 4 3 a 1 1 8 4 3 b 1 2 3 1 2 3 c
x, y, a, b, c是方便我舉例，反正就是一個非數字0-9的
要求，傳回一個array or list or whatever，order不重要
Output是一個Collection（任何type，你自己決定）
但其裡面每個元素, 是一個pair （用python講，tuple，或是C/Java Struct/Class）
這個pair 怎麼產生的呢？
上例來說
遇到x的話
0 14 887 3 x -> 0:3 14:3 887:3
pair的右邊永遠是x的最後一個數
pair的左邊是x 到數第二個數往前，所有的數
條件：pair 左邊不同於右邊 （不可有3:3 4:4)這種
同一個pair只能計入一次 （不可以有 1:3 1:3同時在output裡）
此外，以y為例
2 y -> (什麼都沒有，因為只有一個，不可能有pair, 2 之前是x, 所以不用考慮）
下面是一些例子
遇到a
4 4 3 a -> 4:3 (不需要重覆）
過到b
1 1 8 4 3 b -> 1:3 8:3 (沒有4:3，因為4:3已經出現過）
最後
1 2 3 1 2 3 c -> 2:3 (其它1 3 等等都出現過，3:3則因為3與３相同，不出現）
非數字的部份可以視作斷點，也就是
1 2 a 3 4 b的輸出不包含1:4 及2:4，因為2已經遇到斷點了，所以輸出是
1:2 and 3:4，而不是 1:2 1:4 2:4 3:4
可以假設 input array 的size 最多10,000 (可放入memory)
每個元素，數字範例在 0 - 999之間
也就是最多C(1000,2)種組合
輸出可以是任何資料type，轉成pair之後，順序就不重要
但每個pair，只能出現一次
如需要導入假設的話（時間／空間複雜度的需要取捨）
可以假設，平均input 的長度約200個元素
平均的輸出 pair 數是50 組
假設記憶體可用1GB，上面所有的input都是string (1->想成"1")
方便寫code，假設存在 bool isNumber(x)的方法
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 67.188.141.238
※ 編輯: chucheng 來自: 67.188.141.238 (08/08 16:05)
※ 編輯: chucheng 來自: 67.188.141.238 (08/08 16:10)
→
08/08 16:39, , 1F
08/08 16:39, 1F
→
08/08 17:08, , 2F
08/08 17:08, 2F
→
08/08 19:48, , 3F
08/08 19:48, 3F
→
08/08 19:57, , 4F
08/08 19:57, 4F
→
08/08 19:59, , 5F
08/08 19:59, 5F
→
08/08 20:16, , 6F
08/08 20:16, 6F
推
08/08 21:49, , 7F
08/08 21:49, 7F
→
08/09 14:32, , 8F
08/09 14:32, 8F
→
08/09 14:33, , 9F
08/09 14:33, 9F
→
08/09 14:34, , 10F
08/09 14:34, 10F
→
08/09 16:57, , 11F
08/09 16:57, 11F
→
08/10 01:21, , 12F
08/10 01:21, 12F
順序指的是輸出pair的順序不重要，不是input的順序不重要
input: 1 2 3 x
要 13 23 或是 先23 再13都可以
pcy用re解很漂亮，不過我直覺是如果對方要你假設有
isNumber(x)的方法，我直覺代表他不是要你用re這種library
他想要看你把pattern matching的部份也寫下來
(當然你可以假設有split/indexof一類)
另外因為這是interview遇到的問題，所以其實
也不可能跑回去問可不可以用re，所以很只是recap記得的部份
題意有不清楚請見諒囉，但pcy的答案確實就是要的output
※ 編輯: chucheng 來自: 216.113.168.141 (08/10 05:25)
→
08/12 00:37, , 13F
08/12 00:37, 13F
→
08/12 13:51, , 14F
08/12 13:51, 14F
→
08/14 16:52, , 15F
08/14 16:52, 15F
→
08/14 16:54, , 16F
08/14 16:54, 16F