作者chucheng (時間太少事情太多)
看板Soft_Job
標題[請益] Interview問題
時間Thu Aug 8 15:57:21 2013
遇到一個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)
→ pcyu16:暴力無難度 空間複雜度你有寫memory, 時間複雜度限制是? 08/08 16:39
→ blackwindy:這算簡單的問題吧... 08/08 17:08
→ pcyu16:還要減複雜度就input逐字讀, 然後answer可以一開始就用set 08/08 19:57
→ pcyu16:output 沒有講很清楚, 所以我就大概意思一下orz 08/08 19:59
→ qmomo:宣告pLeft[]; pRight[]; 對binary tree做insertion NlogN ? 08/08 20:16
推 smartclever:搞個balance tree O(n)就做出來惹 08/08 21:49
→ yzugsr:題目有一處不明：順序不重要是指tuple 3:4及4:3不能重複嗎? 08/09 14:32
→ yzugsr:文字敘述不清楚，原以為是視為不同tuple，可以重複 08/09 14:33
→ yzugsr:但不能重複的組合數才會是C(1000,2),可重複為1000*999 08/09 14:34
→ pcyu16:完全沒有回應阿 放個題意不完整的問題人就跑了是怎樣 08/09 16:57
→ haloarch:對啊 看無啦 不是問題的問題 你很奇怪耶你 08/10 01:21
順序指的是輸出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)
→ pcyu16:當時就是覺得處理 input 很麻煩才用 python + re.. XD 08/12 13:51
→ liangjr:講究的話可以把string轉成int再塞進tuple 08/14 16:54