昨天google筆試的題目分析

發信人: elevation(elevation), 信區: CS
標 題: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日15:49:22 星期二)

選擇題+三道算法題

選擇題沒什麼難的 最後一道考的數據庫使用什麼存儲結構不會做。。

算法題
第一題沒什麼好說
第二題可破壞一個數組A[0..N-1]的條件下使用最少的內存判斷是否存在相同的元素
我的做法是堆排序 時間O(NlogN) 空間O(1) 複雜度上來看應該最優了
第三題已知每個點的父節點，求這棵樹的最大獨立集
用遞歸求解 類似動態規劃 但是不存在重疊子狀態 經典算法問題了
預處理每個節點的子節點存在一張表裏
時間O(N）空間O(N）

大家做的結果是這樣嗎？

--

※ 修改內容:?elevation 於 04月22日16:37:47 修改本文?[FROM: ]

※ 修改內容:?elevation 於 04月22日16:40:36 修改本文?[FROM: ]


[回覆本文] 發信人: phoenixCA(phoenix), 信區: CS
標 題: Re: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日15:59:30 星期二)

你接到面試通知了吧？我猜．．．

【 在 elevation 的大作中提到: 】
: 選擇題+三道算法題
: 選擇題沒什麼難的 最後一道考的數據庫使用什麼存儲結構不會做。。
: 算法題
: 第一題沒什麼好說
: 第二題可破壞一個數組A[0..N-1]的條件下使用最少的內存判斷是否存在相同的元素
: 我的做法是堆排序 時間O(NlogN) 空間O(1) 複雜度上來看應該最優了
: 第三題已知每個點的父節點，求這棵樹的最大獨立集
: 用遞歸求解 類似動態規劃 但是不存在重疊子狀態 經典算法問題了
: 預處理每個節點的子節點存在一張表裏
: 時間O(N）空間O(N）
: 大家做的結果是這樣嗎？

--
http://bbs.sjtu.edu.cn/file/WarCraft/111633283321730.jpg

http://bbs.sjtu.edu.cn/file/Inter/1150296246172540.jpg




※ 來源:?飲水思源 ?[FROM: ]


[回覆本文] 發信人: elevation(elevation), 信區: CS
標 題: Re: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日16:00:50 星期二)

有人接到了？我沒有
那些卷子不會這麼快就判好了吧
【 在 phoenixCA 的大作中提到: 】
: 你接到面試通知了吧？我猜．．．
: 【 在 elevation 的大作中提到: 】
: : 選擇題+三道算法題
: : 選擇題沒什麼難的 最後一道考的數據庫使用什麼存儲結構不會做。。
: : 算法題
: : 第一題沒什麼好說
: : 第二題可破壞一個數組A[0..N-1]的條件下使用最少的內存判斷是否存在相同的元素

: : 我的做法是堆排序 時間O(NlogN) 空間O(1) 複雜度上來看應該最優了
: : 第三題已知每個點的父節點，求這棵樹的最大獨立集
: : 用遞歸求解 類似動態規劃 但是不存在重疊子狀態 經典算法問題了
: : 預處理每個節點的子節點存在一張表裏
: : 時間O(N）空間O(N）
: : 大家做的結果是這樣嗎？

--

※ 來源:?飲水思源 ?[FROM: ]


[回覆本文] 發信人: phoenixCA(phoenix), 信區: CS
標 題: Re: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日16:01:41 星期二)

parttime版出消息了

【 在 elevation 的大作中提到: 】
: 有人接到了？我沒有
: 那些卷子不會這麼快就判好了吧
: 【 在 phoenixCA 的大作中提到: 】
: : 你接到面試通知了吧？我猜．．．

--
http://bbs.sjtu.edu.cn/file/WarCraft/111633283321730.jpg

http://bbs.sjtu.edu.cn/file/Inter/1150296246172540.jpg




※ 來源:?飲水思源 ?[FROM: ]


[回覆本文] 發信人: elevation(elevation), 信區: CS
標 題: Re: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日16:05:10 星期二)

莫非選擇題錯一道就掛？。。。
【 在 phoenixCA 的大作中提到: 】
: parttime版出消息了
: 【 在 elevation 的大作中提到: 】
: : 有人接到了？我沒有
: : 那些卷子不會這麼快就判好了吧

--

※ 來源:?飲水思源 ?[FROM: ]


[回覆本文] 發信人: phoenixCA(phoenix), 信區: CS
標 題: Re: 昨天google筆試的題目分析
發信站: 飲水思源 (2008年04月22日16:05:52 星期二)

bless
據說是，不清楚．．．