一、簡答題

1. 動態鏈接庫和靜態鏈接庫的優缺點

2. 輪詢任務調度和可搶占式調度有什么區別?

3. 列出數據庫中常用的鎖及其應用場景

二、算法設計題

1. 給定N是一個正整數，求比N大的最小“不重復數”，這里的不重復是指沒有兩個相等的相鄰位，如1102中的11是相等的兩個相鄰位故不是不重復數，而12301是不重復數。

2. 設N是一個大整數，求長度為N的字符串的最長回文子串。

3. 坐標軸上從左到右依次的點為a[0]、a[1]、a[2]……a[n-1]，設一根木棒的長度為L，求L最多能覆蓋坐標軸的幾個點?

三、系統設計題

1. 在現代系統的設計過程中，為了減輕請求的壓力，通常采用緩存技術，為了進一步提升緩存的命中率，同常采用分布是緩存方案。調度模塊針對不同內容的用戶請求分配給不同的緩存服務器向用戶提供服務。請給出一個分布式緩存方案，滿足如下要求：

1) 單臺緩存服務器故障，整個分布式緩存集群，可以繼續提供服務。

2)通過一定得分配策略，可以保證充分利用每個緩存服務的存儲空間，及負載均衡。當部分服務器故障或系統擴容時，改分配策略可以保證較小的緩存文件重分配開銷。

3)當不同緩存服務器的存儲空間存在差異時，分配策略可以滿足比例分配。

下面給出我自己的一些解答，不保證100%正確，歡迎批評指正。

一、簡答題1. 動態鏈接庫和靜態鏈接庫的優缺點

解答：(1)動態鏈接庫(Dynamic Linked Library)：Windows為應用程序提供了豐富的函數調用，這些函數調用都包含在動態鏈接庫中。其中有3個最重要的DLL，Kernel32.dll、User32.dll和GDI32.dll。有兩種使用方式：一種是靜態加載，即在應用程序啟動時被加載;一種是動態加載，即是該動態鏈接庫在被使用時才被應用程序加載。優點如下：

a. 共享：多個應用程序可以使用同一個動態庫，啟動多個應用程序的時候，只需要將動態庫加載到內存一次即可;

b. 開發模塊好：要求設計者對功能劃分的比較好。

缺點是不能解決引用計數等問題。

(2)靜態庫(Static Library)：函數和數據被編譯進一個二進制文件(通常擴展名為.LIB)。在使用靜態庫的情況下，在編譯鏈接可執行文件時，鏈接器從庫中復制這些函數和數據并把它們和應用程序的其它模塊組合起來創建最終的可執行文件(.EXE文件)。靜態鏈接庫作為代碼的一部分，在編譯時被鏈接。優缺點如下：

代碼的裝載速度快，執行速度也比較快，因為編譯時它只會把你需要的那部分鏈接進去，應用程序相對比較大。但是如果多個應用程序使用的話，會被裝載多次，浪費內存。

2. 輪詢任務調度和可搶占式調度有什么區別?