先總體說下題型，共有20道選擇題，4道簡答題，3道編程題和1道擴展題，題目都比較簡單，限時一小時完成。
一、選擇題
選擇題非常簡單，都是基礎題，什麼死鎖發生的條件、HashMap和HashSet查找插入刪除的時間復雜度、Thread類和Runnable接口、排序復雜度比較、建堆調整堆等等，具體的也記不得了。
二、簡答題
1. 簡述Servlet的生命周期
2. 寫出至少8個Java常用的包名稱
3. Overload和Override的區別，Overloaded方法能不能修改返回值類型？
4. 不用中間變量交換a和b的值
三、編程題
1. 有N個人圍一圈依次報數，數到3的人出列，問當只剩一個人時他原來的位子在哪裡？
2. 有兩個已遞增有序的單鏈表pLinkList和qLinkList，將這兩個鏈表合並成一個遞增有序的鏈表，請自己定義單鏈表的結構。
3. 具體題目不記得，大概意思就是：從N個數中隨機抽取出M個數（M < N），為了使抽取比較均勻，請自己定義抽取函數使得抽取的數既均勻又盡量隨機。
四、擴展題
具體題目也記不清了，一大堆，大概意思是：有一個海量日志庫，裡面的每條日志記錄都有相應的關鍵詞和訪問次數，但記錄是無序的，為了挖掘客戶偏好，需要找出前N個最高訪問次數的日志記錄，請設計算法盡量使時間復雜度和空間復雜度最低。
下面是我自己寫的答案，不一定正確，歡迎大家批評指定和提出自己更好的想法和意見：
1. 簡述Servlet的生命周期
答：Web容器加載servlet，生命周期開始，通過調用servlet的的init()方法進行servlet的初始化，通過調用service()方法實現，根據請求的不同調用不同的doGet()和doPost()方法，結束服務，web容器調用servlet的destroy()方法。
一個servlet的生命周期由部署servlet的容器控制，當一個請求映射到一個servlet時，容器執行下步驟：
1.加載servlet類
2.創建一個servlet類的實例
3.調用init初始化servlet實例，
4.調用service方法，傳遞一個請求和響應對象
5.容器要移除一個servlet，調用servlet的destroy方法結束該servlet
2. 寫出至少8個Java常用的包名稱
答：答出以下的任意8個就行了
1. java.lang Java 編程語言的基本類庫
2. java.applet 創建 applet 需要的所有類
3. java.awt 創建用戶界面以及繪制和管理圖形、圖像的類
4. java.io 通過數據流、對象序列以及文件系統實現的系統輸入、輸出
5. java.net 用於實現網絡通訊應用的所有類
6. java.util 集合類、時間處理模式、日期時間工具等各類常用工具包
7. java.sql 訪問和處理來自於 Java 標准數據源數據的類
8. java.test 以一種獨立於自然語言的方式處理文本、日期、數字和消息的類和接口
9. java.security 設計網絡安全方案需要的一些類
10. java.beans 開發 Java Beans 需要的所有類
11. java.math 簡明的整數算術以及十進制算術的基本函數
12. java.rmi 與遠程方法調用相關的所有類
3. Overload和Override的區別，Overloaded方法是否可以改變返回值類型？
答：Overload是重載的意思，Override是覆蓋的意思，也就是重寫。
（1）重載Overload表示同一個類中可以有多個名稱相同的方法，但這些方法的參數列表各不相同（即參數個數或類型不同），重載發生在同一個類中。
（2）重寫Override表示子類中的方法可以與父類中的某個方法的名稱和參數完全相同，通過子類創建的實例對象調用這個方法時，將調用子類中的定義方法，這相當於把父類中定義的那個完全相同的方法給覆蓋了，這也是面向對象編程的多態性的一種表現。子類覆蓋父類的方法時，只能比父類拋出更少的異常，或者是拋出父類拋出的異常的子異常，因為子類可以解決父類的一些問題，不能比父類有更多的問題。子類方法的訪問權限只能比父類的更大，不能更小。如果父類的方法是private類型，那麼，子類則不存在覆蓋的限制，相當於子類中增加了一個全新的方法。重寫發生在不同的類（父類和子類）中。
（3）至於Overloaded的方法是否可以改變返回值的類型這個問題，要看你倒底想問什麼呢？這個題目很模糊。如果幾個Overloaded的方法的參數列表不一樣，它們的返回者類型當然也可以不一樣。但我估計你想問的問題是：如果兩個方法的參數列表完全一樣，是否可以讓它們的返回值不同來實現重載Overload。這是不行的，我們可以用反證法來說明這個問題，因為我們有時候調用一個方法時也可以不定義返回結果變量，即不要關心其返回結果，例如，我們調用map.remove(key)方法時，雖然remove方法有返回值，但是我們通常都不會定義接收返回結果的變量，這時候假設該類中有兩個名稱和參數列表完全相同的方法，僅僅是返回類型不同，java就無法確定編程者倒底是想調用哪個方法了，因為它無法通過返回結果類型來判斷。
4. 不用中間變量交換a和b的值
答：很多種方法，我這裡給出最簡單的：
a = a + b;
b = a - b;
a = a - b;
1. 有N個人圍一圈依次報數，數到3的倍數的人出列，問當只剩一個人時他原來的位子在哪裡？
解答：經典的轉圈踢人問題，好吧專業一點，約瑟夫環問題，相信大家都會，下面給我的code：
int main()
{
int N, i, j;
printf("Please enter the number of people(N): ");
scanf("%d", &N);
int *pArray = (int *)malloc(sizeof(int) * N);
int count = 0;
// 這裡編號為0 ~ N - 1
for(i = 0; i < N; i++)
{
pArray[i] = i;
}
for(i = 0, j = 0; i < N; i = (i + 1) % N)
{
if(pArray[i] != -1)
{
j++;
if(j % 3 == 0)
{
pArray[i] = -1;
count++;
if(count == N)
{
printf("The last people is %d\n", i);
break;
}
}
}
}
return 0;
}
好吧，我承認我的算法很臃腫，完全是模擬了整個游戲過程，時間復雜度為O(mn)，這裡m=3，網上有個大牛給出了歸納數學的方法，具體方法如下：
為了討論方便，先把問題稍微改變一下，並不影響原意：
問題描述：n個人（編號0~(n-1))，從0開始報數，報到(m-1)（這裡m=3）的退出，剩下的人繼續從0開始報數，求最後剩下一個人的編號。
我們知道第一個人(編號一定是m%n-1) 出列之後，剩下的n-1個人組成了一個新的約瑟夫環（以編號為k=m%n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2並且從k開始報0。
現在我們把他們的編號做一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換後就完完全全成為了(n-1)個人報數的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那麼根據上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k)%n
如何知道(n-1)個人報數的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f[i]表示i個人玩游戲報m退出最後勝利者的編號，最後的結果自然是f[n]
遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了這個公式，我們要做的就是從1-n順序算出f[i]的數值，最後結果是f[n]。因為實際生活中編號總是從1開始，我們輸出f[n]+1
由於是逐級遞推，不需要保存每個f[i]，程序也是異常簡單：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int N, i, s = 0;
printf("Please enter the number of people(N): ");
scanf("%d", &N);
for (i = 2; i <= N; i++)
{
s = (s + 3) % i;
}
printf ("The last people is %d\n", s);
return 0;
}
這個算法的時間復雜度為O(n)，相對於模擬算法已經有了很大的提高。算n，m等於一百萬，一千萬的情況不是問題了。可見，適當地運用數學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執行效率。數學確實很重要啊！！！
2. 有兩個已遞增有序的單鏈表pLinkList和qLinkList，將這兩個鏈表合並成一個遞增有序的鏈表，請自己定義單鏈表的結構。
解答：同樣很經典，不用多說，直接上我自己的code（不是最好的）：
#include <iostream>
using namespace std;
struct LinkList {
int data;
LinkList *next;
};
LinkList* createList() {
LinkList *head = NULL, *p, *q;
int data;
cin >> data;
while(data) {
p = new LinkList;
p->data = data;
p->next = NULL;
if(head == NULL) {
head = p;
q = head;
}
else {
q->next = p;
q = p;
}
cin >> data;
}
return head;
}
// 合並後的鏈表放在pLinkList中
void merge(LinkList *&pLinkList, LinkList *qLinkList) {
LinkList *pre, *p, *q;
pre = NULL;
p = pLinkList;
q = qLinkList;
while(p != NULL && q != NULL) {
if(p->data < q->data)
{
pre = p;
p = p->next;
}
else
{
// 如果p第一個結點大於q，則改變合並後頭結點為q
if(pre == NULL)
{
pLinkList = q;
}
else
{
pre->next = q;
}
pre = q;
q=q->next;
pre->next = p;
}
}
// 最後不要忘了qLinkList剩余的大結點
if(q != NULL)
{
pre->next = q;
}
}
void print(LinkList *l) {
LinkList *p = l;
while(p != NULL) {
if(p->next == NULL) {
cout << p->data;
break;
}
cout << p->data << " -> ";
p = p->next;
}
cout << endl;
}
int main() {
cout << "Please enter pLinkList: ";
LinkList *pLinkList = createList();
print(pLinkList);
cout << "\nPlease enter pLinkList: ";
LinkList *qLinkList = createList();
print(qLinkList);
merge(pLinkList, qLinkList);
cout << "\nThe merge LinkList is: \n";
print(pLinkList);
return 0;
}
3. 具體題目不記得，大概意思就是：從N個數中隨機抽取出M個數（M < N），為了使抽取比較均勻，請自己定義抽取函數使得抽取的數既均勻又盡量隨機。
解答：當時時間太急了，沒來得及多想，做法很傻：從1 ~ M*N中隨機抽取一個數字，然後mod (N + 1)，求得的值為N個數中的下標，再根據此下標去N個數中取，重復M次即可。假如這N個數存在數組nArray[]中，抽取的M個數存在數組mArray[]中，偽代碼描述如下：
for(int i = 0; i < M; i++)
{
int index = Random(M * N) % N;
mArray[i] = nArray[index];
}
由於覺得這個算法實在是不好，就懶得測試了，大家有好想法的趕緊提出來吧。
具體題目也記不清了，一大堆描述，大概意思是：有一個海量日志庫，裡面的每條日志記錄都有相應的關鍵詞和訪問次數，但記錄是無序的，為了挖掘客戶偏好，需要找出前N個最高訪問次數的日志記錄，請設計算法盡量使時間復雜度和空間復雜度最低。
解答：典型的Top K問題，我用的算法也是大家都知道的，大致描述下思路：假如關鍵詞和訪問次數成一個記錄結構體，維護一個有N個該結構體的小根堆，初始化為N個日志記錄的關鍵詞和訪問次數（建堆算法），每次有新的記錄時，將該記錄的訪問次數與小根堆的堆頂元素進行比較，如果大於堆頂元素則與堆頂元素交換記錄，然後調整堆結構使其重新為一個小根堆，否則置之不理。當所有記錄遍歷完後，所有的堆元素就是所要求的前N個最高訪問次數的日志記錄。時間復雜度為O(MlgN)，不知道自己分析的對不對，完全是自以為是的想法，如果大家有更好的算法歡迎提出！
