當前位置:文思屋>學習教育>考研>

阿里巴巴2013筆試題

文思屋 人氣:2.98W

共兩題:

阿里巴巴2013筆試題

1. 關於圖片檔案儲存的一個開放性的題目,沒什麼好說的。

2. 有一顆樹,每一個樹節點儲存著一個數字,現在想要找到兩個相同的'節點(這兩個節點儲存的數字及其所有子樹均相等)。

以下是我答題時候的思路,歡迎大家討論。

思路1:

1) 首先通過一個遍歷(如前序遍歷)得到一個數字序列,並對樹中的葉子節點在這個序列中做標記(現在問題退化為在一個數字串中找出重複的字串,且這些字串應該是以標記的葉子節點結尾的)

2) 採用字尾樹可以很方便的求得相同的數字串序列

3) 驗證2)中得到的結果(應該是一個小結果集) 是否滿足要求,驗證的時間複雜度應該是比較小的

思路2:

1) 對樹中的每一個節點設定一個權值,這個權值為其所有子節點的權值及其自身數字值之間的乘積(可能需要bignumber,或者考慮將這些數字進行移位異或)

2) 採用後序遍歷,計算每一個節點的權值,並順帶記錄其樹深度。統計權值和深度均相同的節點

​3) 驗證2)中得到的結果是否滿足要求,驗證的時間複雜度應該是比較小的