2017年高頻率的互聯網校園招聘面試題
前言
參加了2017年校招，面試了阿里、百度、騰訊、滴滴、美團、網易、去哪兒等公司，個人是客戶端 Android 方向，總結了面試過程中頻率出現較高的題目，希望對大家有所幫助。
Java 一些知識點
Object 有哪些方法
- public 方法： getClass 、 equals 、 hashCode 、 toString 、 wait 、 notify
- protected 方法： clone 、 finalize
- private 方法： registerNatives ，該方法作用是將不同平臺C/C++實現的方法映射到Java中的 native 方法
public class Object {
private static native void registerNatives();
// 聲明后有緊接靜態代碼塊
static {
registerNatives();
}
}
自動裝箱
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));
}
上述代碼的輸出是
true
true
Java 虛擬機 GC 根節點的選擇
Java通過可達性分析來判斷對象是否存活。基本思想是通過一系列稱為”GC roots”的對象作為起始點，可以作為根節點的是：
- 虛擬機棧（棧幀中的本地變量表）中引用的對象
- 本地方法棧中 JNI（即一般說的 Native 方法）引用的對象
- 方法區中類靜態屬性引用的對象
- 方法區中常量引用的對象
筆者這么理解，作為GC Roots的節點主要在全局性的引用（例如常量或類靜態屬性）與執行上下文（例如棧幀中的本地變量表）中。
虛擬機棧、本地方法棧這都是局部變量，某個方法執行完，某些局部使用的對象可以被回收。
類加載機制
- 啟動類加載器( Bootstrap ClassLoader)啟動類加載器無法被 java 程序員 直接引用, 這個類加載器負責把存放在 <JAVA_HOME>\lib 目錄中的, 或者被 -Xbootclasspath 參數指定路徑中的, 并且是被虛擬機識別的類庫加載到虛擬機內存中.
- 擴展類加載器(Extension ClassLoader)負責加載在 <JAVA_HOME>\lib\ext 目錄中的, 或者被 java.ext.dirs 系統變量所指定的路徑中的所有類庫。
- 應用程序類加載器( Application ClassLoader )這個類加載器是 ClassLoader 中的 getSystemClassLoader() 方法的返回值, 一般稱其為系統類加載器, 它負責加載用戶類路徑( ClassPath )上所指定的類庫
從 java 虛擬機的角度而降, 只存在兩種不同的類加載器：
- 一個是啟動類加載器( Bootstrap ClassLoader ), 這個類加載使用 C++ 語言實現, 是虛擬機自身的一部分;
- 另一種是其他所有的類加載器, 他們由 java 語言實現, 獨立于虛擬機之外, 并且全部繼承自 java.lang.ClassLoader
加載類的尋找范圍就是 JVM 默認路徑加上 Classpath , 類具體是使用哪個類加載器不確定。
類加載主要步驟
- 加載 把 class 文件的二進制字節流加載到 jvm 里面
- 驗證 確保 class 文件的字節流包含的信息符合當前 jvm 的要求 有文件格式驗證, 元數據驗證, 字節碼驗證, 符號引用驗證等
- 準備 正式為類變量分配內存并設置類變量初始值的階段, 初始化為各數據類型的零值
- 解析 把常量值內的符號引用替換為直接引用的過程
- 初始化 執行類構造器 <clinit>() 方法
- 使用 根據相應的業務邏輯代碼使用該類
- 卸載 類從方法區移除
雙親委派模型
除了頂層的啟動類加載器之外, 其余的類加載器都應當有自己的父類加載器, 父子關系這兒一般都是以組合來實現。
工作過程: 如果一個類加載器收到了類加載的請求, 它首先不會自己去嘗試加載這個類, 而是把這個請求委派給父類加載器去完成, 最終所有的加載請求都會傳送到頂層的啟動類加載器中, 只有當父類加載器反饋自己無法完成這個請求時候, 才由子加載器來加載。
例如類 Object ，它放在 rt.jar 中，無論哪一個類加載器要加載這個類，最終都是委派給啟動類加載器進行加載，因此 Object 類在程序的各種類加載器環境中都是同一個類。
對于任何一個類, 都需要由加載它的類加載器和這個類本身一同確定其在 java 虛擬機中的唯一性。
ClassLoader.loadClass() 的代碼如下，先檢查是否已經被加載過，如果沒有則 parent.loadClass() 調用父加載器的 loadClass() 方法，如果父加載器為空則默認使用啟動類加載器作為父加載器。如果父類加載器加載失敗，拋出 ClassNotFoundException ，再調用自己的 findClass() 方法進行加載。
另外，如果我們自己實現類加載器，一般是 Override 復寫 findClass 方法，而不是 loadClass 方法。
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); //可以Override該方法
}
}
if (resolve) {
resolveClass(c);
}
return c;
}
}</code></pre>
Java 后臺的一點知識
JSP 與 Servlet 的關系
- Tomcat 等 Web 容器最終會把 JSP轉化為 Servlet
- Jsp更擅長表現于頁面顯示, Servlet更擅長于邏輯控制
- Servlet是利用 System.out.println() 來輸出 html 代碼，由于包括大量的HTML標簽、大量的靜態文本及格式等，導致Servlet的開發效率低下
- JSP通過在標準的HTML頁面中嵌入Java代碼，其靜態的部分無須Java程序控制，Java 代碼只控制那些動態生成的信息
- 最終 JSP 被容器解釋為 Servlet，其中Html 代碼也是用 System.out.println() 等拼接輸出的
- JSP 第一次訪問的時候，要轉化為 java 文件，然后編譯為 class 文件，所以第一次訪問 JSP 速度會比較慢，后面會快很多
Servlet 生命周期
主要是 java.servlet.Servlet 接口中的 init() 、 service() 、和 destroy() 3個方法。
- 初始化階段，web容器通過調用 init() 方法來初始化 Servlet 實例，在Servlet的整個生命周期類， init() 方法只被調用一次
- 客戶請求到來時，容器會開始一個新線程，并調用servlet的 service() 方法， service() 方法根據請求的http方法來調用 doget() 或 dopost()
- 終止階段調用 destroy() 方法，銷毀一些資源
GET 請求 vs POST 請求
- GET 用于信息獲取，是安全的和冪等的， GET 一般是對后臺數據庫的信息進行查詢
- POST 表示可能修改變服務器上的資源的請求，一般是對后臺數據庫進行增、刪、改的操作
- GET 請求的參數會跟在URL后進行傳遞，請求的數據會附在URL之后，以 ? 分割URL和傳輸數據，參數之間以 & 相連，一般瀏覽器對 URL 的長度會有限制
- POST 請求，提交的數據則放置在是HTTP包的包體中，用類似 Key-Value 的格式發送一些數據，相對來說， GET 請求會把請求的參數暴露在 URL 中，安全性比 POST 差一些
HTTP 請求的基本格式
- < request line> 請求行
- <headers> 請求頭（參數頭）
- <blank line> 空白行
- [<request-body>] 請求實體（ GET沒有， POST有 ）
數據庫
索引的分類
主要分為聚集索引和非聚集索引：
- 聚集索引存儲記錄物理上連續，而非聚集索引是邏輯上的連續，物理存儲并不連續
- 聚集索引一個表只能有一個，而非聚集索引一個表可以存在多個
ResultSet 統計記錄數目
Java 中使用 JDBC 連接數據庫，最后都會得到一個 ResultSet，比如如下的代碼
Connection con = DriverManager.getConnection(url, username, password);
Statement sta = con.createStatement();
String sql = "select * from student";
ResultSet resultSet = sta.executeQuery(sql);
那么如何根據得到的 ResultSet 統計一共有多少條記錄呢？注意： ResultSet 沒有提供類似 size() 、 length 的 API 來直接獲取總記錄數。
方法1：利用循環
int sum = 0;
while(resultSet.next()){
sum++;
}
方法2：利用ResultSet的getRow方法來獲得ResultSet的總行數
resultSet.last(); //移到最后一行
int rowCount = resultSet.getRow(); //得到當前行號，也就是記錄數
設計模式
單例模式
單例模式中必須保證只有一個實例存在。有時候單例是為了避免重復創建多個實例造成資源浪費，有時候也是為了避免多個不同的實例導致系統不一致的行為。
Android 中，App啟動時系統會創建一個 Application 對象，用來存儲系統的一些信息，這兒的 Application 就是是單例模式的應用。可以通過 Context.getApplicationContext() 獲取唯一的 Application 實例。
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(); //創建單例實例
}
}
}
return instance;
}
}</code></pre>
為什么 synchronized 里面需要加一次判斷 if (instance == null) ，是考慮這樣的特殊情形：比如線程A、B都到達第一個 if (instance == null) ，線程A進入 synchronized 代碼中創建實例，線程B排隊等待。但當A執行完畢時，線程B進入 synchronized 鎖定代碼，它并不知道實例已經創建，將繼續創建新的實例，導致產生多個單例對象。
也可以用內部類的方式創建，
public class Singleton(){
private static class Inner {
private static Singleton instance = new Singleton();
}
private Singleton() {
}
public static Singleton getInstance(){
return Inner.instance;
}
}
模板方法模式
在父類中實現一個算法不變的部分，并將可變的行為留給子類來實現。
比如 AsyncTask 里面的四個方法 onPreExecute 、 doInBackground 、 onProgressUpdate 、 onPostExecute
還有 Activity 也應用了模板方法模式
onCreate 、 onStart 、 onResume 、 onPause 、 onStop 、 onDestroy 、 onRestart
適配器模式
分為兩種：類的適配器模式、對象的適配器模式
Android 里的 ListView 和 RecyclerView 的 setAdapter() 方法就是使用了適配器模式。
觀察者模式
在 GUI 中，不管是 Windows 桌面應用、或者 Android、IOS，都會給某個按鈕 Button 設置監聽事件，這兒就是使用了觀察者模式。Android 中設置 Button 的監聽事件代碼如下：
final Button button = (Button) findViewById(R.id.button_id);
button.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
// Perform action on click
}
});
筆試編程題
線程 VS 進程
關于線程和進程，不正確的描述是 __ 。(選 D 棧是線程私有， 保存其運行狀態和局部變量 )
A. 進程的隔離性要好于線程
B. 線程在資源消耗上通常要比進程輕量
C. 不同進程間不會共享邏輯地址空間
D. 同一個進程的線程之間共享內存，包括堆和棧
E. 進程間有途徑共享大量內存中的數據
F. 線程間通訊可以通過直接訪問全局變量，或者使用進程間通訊的機制(IPC)
找出未打卡的員工
題目：輸入兩行數據，第一行為全部員工的 id，第二行為某一天打卡的員工 id，已知只有一個員工沒有打卡，求出未打卡員工的 id。（員工 id 不重復，每行輸入的 id 未排序）
輸入：
1001 1003 1002 1005 1004
1002 1003 1001 1004
輸出：
1005
分析：可以用兩個 List，第一個 List 保存所有員工的 id，第二個 List 保存打卡員工的 id，從第一個List 中把第二個 List 的數據都刪除，最終剩下的就是未打卡員工的 id。
更好的方法：異或，兩行數據中未打卡員工的 id 出現了一次，其余員工的 id 都出現了2次，兩個相同的數異或為0。
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);
}
}</code></pre>
手寫代碼題
快速排序
排序是經典面試題，公司也希望通過手寫快排來考察面試者的編程習慣和基本功。
// 排序范圍 [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);
}
}
// 一次劃分代碼，返回被劃分后的基準位置
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：快排是不穩定的，常見的穩定排序是：冒泡、插入、歸并
括號字符串是否合法
某個字符串只包括 ( 和 ） ，判斷其中的括號是否匹配正確，比如 (()()) 正確， ((())() 錯誤， 不允許使用棧 。
這種類似題的常見思路是棧，對于左括號入棧，如果遇到右括號，判斷此時棧頂是不是左括號，是則將其出棧，不是則該括號序列不合法。
面試官要求不能使用棧，可以使用計數器，利用 int count 字段。
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;
}</code></pre>
撲克牌隨機發牌
對于52張牌，實現一個隨機打算撲克牌順序的程序。52張牌使用 int 數組模擬。
該算法的難點是如何保證隨機性？有個經典算法 shuffle ，思路就是遍歷數組，在剩下的元素里再隨機取一個元素，然后再在剩下的元素里再隨機取一個元素。每次取完元素后，我們就不會讓這個元素參與下一次的選取。
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 的情況，因為可能洗牌后某個牌未發生交換，比如第51張牌還是原來的第51張牌。
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); //產生 [0,i] 之間的隨機數
swap(data,i,temp);
}
}</code></pre>
智力題
金條付費
你讓工人為你工作7天，回報是一根金條，這個金條平分成相連的7段，你必須在每天結束的時候給他們一段金條，如果只允許你兩次把金條弄斷，你如何給你的工人付費？
答案：切成一段,兩段,和四段.
第1天: 給出1.
第2天: 給出2,還回1.
第3天: 給出1.
第4天: 給出4,還回1+2.
第5天: 給出1.
第6天: 給出2,還回1.
第7天: 給出1.
賽馬
25匹馬，速度都不同，但每匹馬的速度都是定值。現在只有5條賽道，無法計時，即每賽一場最多只能知道5匹馬的相對快慢。問最少賽幾場可以找出25匹馬中速度最快的前3名？
答案：
- 25匹馬分成5組，先進行5場比賽
- 再將剛才5場的冠軍進行第6場比賽，得到第一名。按照第6場比賽的名詞把前面5場比賽所在的組命名為 A、B、C、D、E 組，即 A 組的冠軍是第6場第一名，B 組的冠軍是第二名 …
- 分析第2名和第3名的可能性，如果確定有多于3匹馬比某匹馬快，那它可以被淘汰了。因為 D 組是第6場的第四名，整個D 組被淘汰了，同意整個 E 組被淘汰。剩下可能是整體的第2、3名的就是C組的第1名、B組的1、2名、A組的第2、3名。取這5匹馬進行第7場比賽
-所以，一共需要7場比賽
來自：http://www.codeceo.com/article/it-interview-question-2017.html