參加了2017年校招，面試了阿里、百度、騰訊、滴滴、美團(tuán)、網(wǎng)易、去哪兒等公司，個(gè)人是客戶端 Android 方向，總結(jié)了面試過程中頻率出現(xiàn)較高的題目，希望對(duì)大家有所幫助。
Java 一些知識(shí)點(diǎn)
Object 有哪些方法
public 方法：getClass、equals、hashCode、toString、wait、notify
protected 方法：clone、finalize
private 方法：registerNatives，該方法作用是將不同平臺(tái)C/C++實(shí)現(xiàn)的方法映射到Java中的native方法
1
2
3
4
5
6
7
public class Object {
? ?private static native void registerNatives();
? ?// 聲明后有緊接靜態(tài)代碼塊
? ?static {
? ? ? ?registerNatives();
? ?}
}
自動(dòng)裝箱
1
2
3
4
5
6
public static void main(String[] args) {
? ?int i = 0;
? ?Integer j = new Integer(0);
? ?System.out.println(j == i);
? ?System.out.println(j.equals(i));
}
上述代碼的輸出是
1
2
true
true
Java 虛擬機(jī) GC 根節(jié)點(diǎn)的選擇
Java通過可達(dá)性分析來(lái)判斷對(duì)象是否存活?；舅枷胧峭ㄟ^一系列稱為”GC roots”的對(duì)象作為起始點(diǎn)，可以作為根節(jié)點(diǎn)的是：
虛擬機(jī)棧（棧幀中的本地變量表）中引用的對(duì)象
本地方法棧中 JNI（即一般說的 Native 方法）引用的對(duì)象
方法區(qū)中類靜態(tài)屬性引用的對(duì)象
方法區(qū)中常量引用的對(duì)象
筆者這么理解，作為GC Roots的節(jié)點(diǎn)主要在全局性的引用（例如常量或類靜態(tài)屬性）與執(zhí)行上下文（例如棧幀中的本地變量表）中。
虛擬機(jī)棧、本地方法棧這都是局部變量，某個(gè)方法執(zhí)行完，某些局部使用的對(duì)象可以被回收。
類加載機(jī)制
啟動(dòng)類加載器( Bootstrap ClassLoader)
啟動(dòng)類加載器無(wú)法被 java 程序員直接引用, 這個(gè)類加載器負(fù)責(zé)把存放在\lib目錄中的, 或者被-Xbootclasspath參數(shù)指定路徑中的, 并且是被虛擬機(jī)識(shí)別的類庫(kù)加載到虛擬機(jī)內(nèi)存中.
擴(kuò)展類加載器(Extension ClassLoader)
負(fù)責(zé)加載在\lib\ext目錄中的, 或者被java.ext.dirs系統(tǒng)變量所指定的路徑中的所有類庫(kù)。
應(yīng)用程序類加載器( Application ClassLoader )
這個(gè)類加載器是ClassLoader 中的 getSystemClassLoader()方法的返回值, 一般稱其為系統(tǒng)類加載器, 它負(fù)責(zé)加載用戶類路徑( ClassPath )上所指定的類庫(kù)
從 java 虛擬機(jī)的角度而降, 只存在兩種不同的類加載器：
一個(gè)是啟動(dòng)類加載器( Bootstrap ClassLoader ), 這個(gè)類加載使用 C++ 語(yǔ)言實(shí)現(xiàn), 是虛擬機(jī)自身的一部分;
另一種是其他所有的類加載器, 他們由 java 語(yǔ)言實(shí)現(xiàn), 獨(dú)立于虛擬機(jī)之外, 并且全部繼承自java.lang.ClassLoader
加載類的尋找范圍就是 JVM 默認(rèn)路徑加上Classpath, 類具體是使用哪個(gè)類加載器不確定。
類加載主要步驟
加載 把 class 文件的二進(jìn)制字節(jié)流加載到 jvm 里面
驗(yàn)證 確保 class 文件的字節(jié)流包含的信息符合當(dāng)前 jvm 的要求 有文件格式驗(yàn)證, 元數(shù)據(jù)驗(yàn)證, 字節(jié)碼驗(yàn)證, 符號(hào)引用驗(yàn)證等
準(zhǔn)備 正式為類變量分配內(nèi)存并設(shè)置類變量初始值的階段, 初始化為各數(shù)據(jù)類型的零值
解析 把常量值內(nèi)的符號(hào)引用替換為直接引用的過程
初始化 執(zhí)行類構(gòu)造器()方法
使用 根據(jù)相應(yīng)的業(yè)務(wù)邏輯代碼使用該類
卸載 類從方法區(qū)移除
雙親委派模型
除了頂層的啟動(dòng)類加載器之外, 其余的類加載器都應(yīng)當(dāng)有自己的父類加載器, 父子關(guān)系這兒一般都是以組合來(lái)實(shí)現(xiàn)。
工作過程: 如果一個(gè)類加載器收到了類加載的請(qǐng)求, 它首先不會(huì)自己去嘗試加載這個(gè)類, 而是把這個(gè)請(qǐng)求委派給父類加載器去完成, 最終所有的加載請(qǐng)求都會(huì)傳送到頂層的啟動(dòng)類加載器中, 只有當(dāng)父類加載器反饋?zhàn)约簾o(wú)法完成這個(gè)請(qǐng)求時(shí)候, 才由子加載器來(lái)加載。
例如類Object，它放在rt.jar中，無(wú)論哪一個(gè)類加載器要加載這個(gè)類，最終都是委派給啟動(dòng)類加載器進(jìn)行加載，因此Object類在程序的各種類加載器環(huán)境中都是同一個(gè)類。
對(duì)于任何一個(gè)類, 都需要由加載它的類加載器和這個(gè)類本身一同確定其在 java 虛擬機(jī)中的唯一性。
ClassLoader.loadClass()的代碼如下，先檢查是否已經(jīng)被加載過，如果沒有則parent.loadClass()調(diào)用父加載器的loadClass()方法，如果父加載器為空則默認(rèn)使用啟動(dòng)類加載器作為父加載器。如果父類加載器加載失敗，拋出ClassNotFoundException，再調(diào)用自己的findClass()方法進(jìn)行加載。
另外，如果我們自己實(shí)現(xiàn)類加載器，一般是Override復(fù)寫 findClass方法，而不是loadClass方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
protected Class loadClass(String name, boolean resolve)
throws ClassNotFoundException {
? ?synchronized (getClassLoadingLock(name)) {
? ? ? ?// First, check if the class has already been loaded
? ? ? ?Class c = findLoadedClass(name);
? ? ? ?if (c == null) {
? ? ? ? ? ?long t0 = System.nanoTime();
? ? ? ? ? ?try {
? ? ? ? ? ? ? ?if (parent != null) {
? ? ? ? ? ? ? ? ? ?c = parent.loadClass(name, false);
? ? ? ? ? ? ? ?} else {
? ? ? ? ? ? ? ? ? ?c = findBootstrapClassOrNull(name);
? ? ? ? ? ? ? ?}
? ? ? ? ? ?} catch (ClassNotFoundException e) {
? ? ? ? ? ? ? ?// ClassNotFoundException thrown if class not found
? ? ? ? ? ? ? ?// from the non-null parent class loader
? ? ? ? ? ?}
? ? ? ? ? ?if (c == null) {
? ? ? ? ? ? ? ?// If still not found, then invoke findClass in order
? ? ? ? ? ? ? ?// to find the class.
? ? ? ? ? ? ? ?long t1 = System.nanoTime();
? ? ? ? ? ? ? ?c = findClass(name); //可以O(shè)verride該方法
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?if (resolve) {
? ? ? ? ? ?resolveClass(c);
? ? ? ?}
? ? ? ?return c;
? ?}
}
Java 后臺(tái)的一點(diǎn)知識(shí)
JSP 與 Servlet 的關(guān)系
Tomcat 等 Web 容器最終會(huì)把 JSP轉(zhuǎn)化為 Servlet
Jsp更擅長(zhǎng)表現(xiàn)于頁(yè)面顯示, Servlet更擅長(zhǎng)于邏輯控制
Servlet是利用 System.out.println()來(lái)輸出 html 代碼，由于包括大量的HTML標(biāo)簽、大量的靜態(tài)文本及格式等，導(dǎo)致Servlet的開發(fā)效率低下
JSP通過在標(biāo)準(zhǔn)的HTML頁(yè)面中嵌入Java代碼，其靜態(tài)的部分無(wú)須Java程序控制，Java 代碼只控制那些動(dòng)態(tài)生成的信息
最終 JSP 被容器解釋為 Servlet，其中Html 代碼也是用 System.out.println()等拼接輸出的
JSP 第一次訪問的時(shí)候，要轉(zhuǎn)化為 java 文件，然后編譯為 class 文件，所以第一次訪問 JSP 速度會(huì)比較慢，后面會(huì)快很多
Servlet 生命周期
主要是java.servlet.Servlet接口中的init() 、service() 、和destroy() 3個(gè)方法。
初始化階段，web容器通過調(diào)用init()方法來(lái)初始化Servlet實(shí)例，在Servlet的整個(gè)生命周期類，init()方法只被調(diào)用一次
客戶請(qǐng)求到來(lái)時(shí)，容器會(huì)開始一個(gè)新線程，并調(diào)用servlet的 service()方法，service() 方法根據(jù)請(qǐng)求的http方法來(lái)調(diào)用 doget() 或dopost()
終止階段調(diào)用destroy()方法，銷毀一些資源
GET 請(qǐng)求 vs POST 請(qǐng)求
GET用于信息獲取，是安全的和冪等的，GET一般是對(duì)后臺(tái)數(shù)據(jù)庫(kù)的信息進(jìn)行查詢
POST表示可能修改變服務(wù)器上的資源的請(qǐng)求，一般是對(duì)后臺(tái)數(shù)據(jù)庫(kù)進(jìn)行增、刪、改的操作
GET請(qǐng)求的參數(shù)會(huì)跟在URL后進(jìn)行傳遞，請(qǐng)求的數(shù)據(jù)會(huì)附在URL之后，以?分割URL和傳輸數(shù)據(jù)，參數(shù)之間以&相連，一般瀏覽器對(duì) URL 的長(zhǎng)度會(huì)有限制
POST請(qǐng)求，提交的數(shù)據(jù)則放置在是HTTP包的包體中，用類似Key-Value的格式發(fā)送一些數(shù)據(jù)，相對(duì)來(lái)說，GET請(qǐng)求會(huì)把請(qǐng)求的參數(shù)暴露在 URL 中，安全性比POST差一些
HTTP 請(qǐng)求的基本格式
請(qǐng)求行
請(qǐng)求頭（參數(shù)頭）
空白行
[] 請(qǐng)求實(shí)體（GET沒有， POST有）
數(shù)據(jù)庫(kù)
索引的分類
主要分為聚集索引和非聚集索引：
聚集索引存儲(chǔ)記錄物理上連續(xù)，而非聚集索引是邏輯上的連續(xù)，物理存儲(chǔ)并不連續(xù)
聚集索引一個(gè)表只能有一個(gè)，而非聚集索引一個(gè)表可以存在多個(gè)
ResultSet 統(tǒng)計(jì)記錄數(shù)目
Java 中使用JDBC連接數(shù)據(jù)庫(kù)，最后都會(huì)得到一個(gè) ResultSet，比如如下的代碼
1
2
3
4
Connection con = DriverManager.getConnection(url, username, password);
Statement sta = con.createStatement();
String sql = "select * from student";
ResultSet resultSet = sta.executeQuery(sql);
那么如何根據(jù)得到的ResultSet統(tǒng)計(jì)一共有多少條記錄呢？注意：ResultSet沒有提供類似size()、length的 API 來(lái)直接獲取總記錄數(shù)。
方法1：利用循環(huán)
1
2
3
4
int sum = 0;
while(resultSet.next()){
sum++;
}
方法2：利用ResultSet的getRow方法來(lái)獲得ResultSet的總行數(shù)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
resultSet.last(); //移到最后一行
int rowCount = resultSet.getRow(); //得到當(dāng)前行號(hào)，也就是記錄數(shù)
```
## 設(shè)計(jì)模式 ##
### 單例模式 ###
單例模式中必須保證只有一個(gè)實(shí)例存在。有時(shí)候單例是為了避免重復(fù)創(chuàng)建多個(gè)實(shí)例造成資源浪費(fèi)，有時(shí)候也是為了避免多個(gè)不同的實(shí)例導(dǎo)致系統(tǒng)不一致的行為。
Android 中，App啟動(dòng)時(shí)系統(tǒng)會(huì)創(chuàng)建一個(gè)`Application`對(duì)象，用來(lái)存儲(chǔ)系統(tǒng)的一些信息，這兒的`Application` 就是是單例模式的應(yīng)用?？梢酝ㄟ^`Context.getApplicationContext()`獲取唯一的`Application`實(shí)例。
```java
class Singleton {
private volatile static Singleton instance;
private Singleton() { }
public static Singleton getInstance() {
//第一重判斷
if (instance == null) {
//鎖定代碼塊
synchronized (Singleton.class) {
//第二重判斷
if (instance == null) {
instance = new Singleton(); //創(chuàng)建單例實(shí)例
}
}
}
return instance;
}
}
為什么synchronized里面需要加一次判斷if (instance == null)，是考慮這樣的特殊情形：比如線程A、B都到達(dá)第一個(gè)if (instance == null)，線程A進(jìn)入synchronized代碼中創(chuàng)建實(shí)例，線程B排隊(duì)等待。但當(dāng)A執(zhí)行完畢時(shí)，線程B進(jìn)入synchronized鎖定代碼，它并不知道實(shí)例已經(jīng)創(chuàng)建，將繼續(xù)創(chuàng)建新的實(shí)例，導(dǎo)致產(chǎn)生多個(gè)單例對(duì)象。
也可以用內(nèi)部類的方式創(chuàng)建，
1
2
3
4
5
6
7
8
9
10
public class Singleton(){
private static class Inner {
private static Singleton instance = new Singleton();
}
private Singleton() {
}
public static Singleton getInstance(){
return Inner.instance;
}
}
模板方法模式
在父類中實(shí)現(xiàn)一個(gè)算法不變的部分，并將可變的行為留給子類來(lái)實(shí)現(xiàn)。
比如AsyncTask 里面的四個(gè)方法onPreExecute、doInBackground、onProgressUpdate、onPostExecute
還有Activity也應(yīng)用了模板方法模式
onCreate、onStart、onResume、onPause、onStop、onDestroy、onRestart
適配器模式
分為兩種：類的適配器模式、對(duì)象的適配器模式
Android 里的 ListView 和 RecyclerView的setAdapter()方法就是使用了適配器模式。
觀察者模式
在 GUI 中，不管是 Windows 桌面應(yīng)用、或者 Android、IOS，都會(huì)給某個(gè)按鈕 Button 設(shè)置監(jiān)聽事件，這兒就是使用了觀察者模式。Android 中設(shè)置 Button 的監(jiān)聽事件代碼如下：
1
2
3
4
5
6
final Button button = (Button) findViewById(R.id.button_id);
button.setOnClickListener(new View.OnClickListener() {
? ?public void onClick(View v) {
? ? ? ?// Perform action on click
? ?}
});
筆試編程題
線程 VS 進(jìn)程
關(guān)于線程和進(jìn)程，不正確的描述是__。(選 D 棧是線程私有， 保存其運(yùn)行狀態(tài)和局部變量 )
A. 進(jìn)程的隔離性要好于線程
B. 線程在資源消耗上通常要比進(jìn)程輕量
C. 不同進(jìn)程間不會(huì)共享邏輯地址空間
D. 同一個(gè)進(jìn)程的線程之間共享內(nèi)存，包括堆和棧
E. 進(jìn)程間有途徑共享大量?jī)?nèi)存中的數(shù)據(jù)
F. 線程間通訊可以通過直接訪問全局變量，或者使用進(jìn)程間通訊的機(jī)制(IPC)
找出未打卡的員工
題目：輸入兩行數(shù)據(jù)，第一行為全部員工的 id，第二行為某一天打卡的員工 id，已知只有一個(gè)員工沒有打卡，求出未打卡員工的 id。（員工 id 不重復(fù)，每行輸入的 id 未排序）
輸入：
1001 1003 1002 1005 1004
1002 1003 1001 1004
輸出：
1005
分析：可以用兩個(gè) List，第一個(gè) List 保存所有員工的 id，第二個(gè) List 保存打卡員工的 id，從第一個(gè)List 中把第二個(gè) List 的數(shù)據(jù)都刪除，最終剩下的就是未打卡員工的 id。
更好的方法：異或，兩行數(shù)據(jù)中未打卡員工的 id 出現(xiàn)了一次，其余員工的 id 都出現(xiàn)了2次，兩個(gè)相同的數(shù)異或?yàn)?。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String[] ids = scan.nextLine().split(" ");
String[] marks = scan.nextLine().split(" ");
int result = 0;
for (int i = 0; i < ids.length; i++) {
result ^= Integer.parseInt(ids[i]);
}
for (int i = 0; i < marks.length; i++) {
result ^= Integer.parseInt(marks[i]);
}
System.out.println(result);
}
}
手寫代碼題
快速排序
排序是經(jīng)典面試題，公司也希望通過手寫快排來(lái)考察面試者的編程習(xí)慣和基本功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 排序范圍 [start, end], 包含 end
public void sort(int[] arr, int start, int end) {
if (start < end) {
int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
}
// 一次劃分代碼，返回被劃分后的基準(zhǔn)位置
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
if (left < right)
arr[left++] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot;
return left;
}
Note：快排是不穩(wěn)定的，常見的穩(wěn)定排序是：冒泡、插入、歸并
括號(hào)字符串是否合法
某個(gè)字符串只包括(和），判斷其中的括號(hào)是否匹配正確，比如(()())正確，((())()錯(cuò)誤，不允許使用棧。
這種類似題的常見思路是棧，對(duì)于左括號(hào)入棧，如果遇到右括號(hào)，判斷此時(shí)棧頂是不是左括號(hào)，是則將其出棧，不是則該括號(hào)序列不合法。
面試官要求不能使用棧，可以使用計(jì)數(shù)器，利用int count字段。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static boolean checkBrackets(String str) {
char[] cs = str.toCharArray();
int count = 0;
for (int i = 0; i < cs.length; i++) {
if (cs[i] == '(')
count++;
else {
count--;
if (count < 0) {
return false;
}
}
}
return count == 0;
}
撲克牌隨機(jī)發(fā)牌
對(duì)于52張牌，實(shí)現(xiàn)一個(gè)隨機(jī)打算撲克牌順序的程序。52張牌使用 int 數(shù)組模擬。
該算法的難點(diǎn)是如何保證隨機(jī)性？有個(gè)經(jīng)典算法shuffle，思路就是遍歷數(shù)組，在剩下的元素里再隨機(jī)取一個(gè)元素，然后再在剩下的元素里再隨機(jī)取一個(gè)元素。每次取完元素后，我們就不會(huì)讓這個(gè)元素參與下一次的選取。
1
2
3
4
To shuffle an array a of n elements (indices 0..n-1):
?for i from n ? 1 downto 1 do
? ? ? j ← random integer with 0 ≤ j ≤ i
? ? ? exchange a[j] and a[i]
注意這兒是0 ≤ j ≤ i，包括j=i的情況，因?yàn)榭赡芟磁坪竽硞€(gè)牌未發(fā)生交換，比如第51張牌還是原來(lái)的第51張牌。
1
2
3
4
5
6
7
8
9
10
11
public void randomCards() {
int[] data = new int[52];
Random random= new Random();
for (int i = 0; i < data.length; i++)
data[i] = i;
for (int i = data.length - 1; i > 0; i--) {
int temp = random.nextInt(i+1); //產(chǎn)生 [0,i] 之間的隨機(jī)數(shù)
swap(data,i,temp);
}
}
智力題
金條付費(fèi)
你讓工人為你工作7天，回報(bào)是一根金條，這個(gè)金條平分成相連的7段，你必須在每天結(jié)束的時(shí)候給他們一段金條，如果只允許你兩次把金條弄斷，你如何給你的工人付費(fèi)？
答案：切成一段,兩段,和四段.
第1天: 給出1.
第2天: 給出2,還回1.
第3天: 給出1.
第4天: 給出4,還回1+2.
第5天: 給出1.
第6天: 給出2,還回1.
第7天: 給出1.
賽馬
25匹馬，速度都不同，但每匹馬的速度都是定值。現(xiàn)在只有5條賽道，無(wú)法計(jì)時(shí)，即每賽一場(chǎng)最多只能知道5匹馬的相對(duì)快慢。問最少賽幾場(chǎng)可以找出25匹馬中速度最快的前3名？
答案：
25匹馬分成5組，先進(jìn)行5場(chǎng)比賽
再將剛才5場(chǎng)的冠軍進(jìn)行第6場(chǎng)比賽，得到第一名。按照第6場(chǎng)比賽的名詞把前面5場(chǎng)比賽所在的組命名為 A、B、C、D、E 組，即 A 組的冠軍是第6場(chǎng)第一名，B 組的冠軍是第二名 …
分析第2名和第3名的可能性，如果確定有多于3匹馬比某匹馬快，那它可以被淘汰了。因?yàn)?D 組是第6場(chǎng)的第四名，整個(gè)D 組被淘汰了，同意整個(gè) E 組被淘汰。剩下可能是整體的第2、3名的就是C組的第1名、B組的1、2名、A組的第2、3名。取這5匹馬進(jìn)行第7場(chǎng)比賽
-所以，一共需要7場(chǎng)比賽
? ?
? ? ?
?
