228
技術社區[雲棲]
我的麵試庫
算法題
公司現在的麵試對算法要求很高，不妨開個貼，整理一下，弄出幾個自己很熟悉又很有代表性的算法題，免得每次都要重新準備。
參考： https://blog.csdn.net/v_july_v/article/details/6543438
1. 有1000萬條查詢字符串記錄，找出top 10 出現次數最多查詢串。
用Hash Table 統計查詢字符串出現次數，時間複雜度是O(N)，詳細：https://blog.csdn.net/v_july_v/article/details/6256463
用size為10的最大堆排序，找出Top 10，時間複雜度為N*logK,。
關於堆排序：
https://www.benfrederickson.com/2013/10/10/heap-visualization.html
https://en.wikipedia.org/wiki/Binary_heap
2. 對N個整數，尋找最小的K個整數 （例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。）
用部分排序+堆排序，https://blog.csdn.net/v_JULY_v/article/details/6370650
3. 設計一個算法，把一個含有N個元素的數組循環右移K位，要求時間複雜度為O（N）
常規做法，時間複雜度是O(N*K), 用逆排序可以做到O(N) https://blog.csdn.net/v_JULY_v/article/details/6322882
對N個元素，用N/2的時間就可以逆排序，空間上隻需要一個額外存儲。思路是不需要一個一個元素向右移動，隻需要將數組的一半和另一半交換即可！
Reverse(int* arr, int b, int e)
{
for(; b < e; b++, e--)
{
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
}
}
或者
for(int i=0;i<=N/2;i++)
{ int t;
t=a[N-i];
a[N-i]=a[i];
a[i]=t;
}
設計題
1. 如果讓你設計一個數據庫連接池，你將如何設計？
數據庫SQL
有兩張表，學生表 和 學生選課表， 寫一條SQL統計所有學生的選課數，注意可能存在一門課程都沒有選的情況。
考察點，left join 和 group by
完整SQL
select s.id, sum(case when c.name is not null then 1 else 0 end) from student as s left join course as c on s.id = c.studentId group by s.id
left join、right join、inner join的區別
left join(左聯接) 返回包括左表中的所有記錄和右表中聯結字段相等的記錄right join(右聯接) 返回包括右表中的所有記錄和左表中聯結字段相等的記錄
inner join(等值連接) 隻返回兩個表中聯結字段相等的行
Java題
1. HashSet HashTable 和 HashMap 的區別
HashSet實現了Set接口，它不允許集合中有重複的值，要先確保對象重寫equals()和hashCode()方法
HashMap中怎樣處理hash衝突的？ HashTable 是線程安全的，HashTable不接受null的key和value
2. web container中加載執行servlet的過程？ web.xml中配置，然後init() --> get() / post() --> destroy()，其是不是線程安全的？ volatile 這個關鍵字的作用（對變量進行同步操作）
3. String和StringBuffer的區別，衍生到immutable class，immutable的好處（線程安全，安全的參數傳入，減少內存消耗），如何實現immutable class.
4. JVM的類加載機製是怎樣的？
bootstrap
classloader load 核心庫
|
extension classloader load jre/lib/ext
|
system classloader load -classpath 指定的jar包或類路徑
https://www.blogjava.net/lhulcn618/archive/2006/05/25/48230.html
5. Java的內存模型？ 你碰過幾種outOfMemory的錯誤，都是由什麼原因造成的？ permgen, heap space, thread stack
參考 https://www.cnblogs.com/windlaughing/archive/2013/05/27/3101650.html
設計題
什麼是觀察者模式
架構題
1. 什麼是RESTFul架構
2. 談談你理解的分布式係統架構
最後更新：2017-04-03 16:49:02