百度08-9-24成都電子科技大學筆試題(第一套)

　　百度08-9-24成都電子科技大學筆試題(第一套)   軟件測試

　　百度08-9-24成都電子科技大學筆試題(第一套)

　　008-9-24成都電子科技大學百度筆試題(第一套題)

　　一：編程題

　　現有一組共計N個固定的集合(N為萬量級)，每個集合有個從0開始遞增的集合ID，每個集

　　合包含1~M個TERM(M為0~100的量級)，希望設計一個程序能夠持續對外服務，輸入是一個

　　TERM數組，輸出其中任意一個集合ID(如果該TERM數組包含該集合的所有TERM)，如果找

　　不到輸出-1。要求：

　　1， 時間復雜度最優，能夠在短時間內對大量輸入逐個輸出

　　2， 實現具體的代碼(可以是偽代碼)，其中常用的數據結構可以采用標準庫。

　　3， 給出時間復雜度和空間復雜度。

　　TERM組合集合的文件格式舉例：

　　TERM_1 空格 TERM_2

　　TERM_1 空格 TERM_3

　　TERM_1 空格 TERM_3 TERM_4

　　輸入的為TERM數組(說明：TERM為一個詞，可能是中文，固定字符串表示)

　　二：算法題

　　你現在有一個文件，文件中順序存有N個記錄，R1,R2,...,RN,這些記錄不是有序的，但是

　　你知道一個整數M,這些記錄滿足R1

　　1,設計一個算法或編寫一個程序，將文件中的記錄排序為R1'取文件的次數為O(N),不限內存使用，

　　2,設計一個算法或編寫一個程序，將文件中的記錄排序為R1'寫文件的次數為O(N)，空間復雜度為O(1)，(亦即，你使用的內存大小和M,N均無關。)

　　三：系統設計題

原文轉自：http://www.anti-gravitydesign.com