有幸參加了2013年5月5日阿里巴巴的實習(xí)生招聘筆試，這次筆試的難度對我而言，前半部分不涉及算法的內(nèi)容，都比較容易。而后面3道關(guān)于算法的習(xí)題都解答得很不好，暴露出來自己的一些問題。本人馬上也要畢業(yè)了，想通過這個博客記錄下自己在準(zhǔn)備應(yīng)聘過程中所遇到的各種問題、難題，記錄下來以供查閱，同時與諸君分享，歡迎積極交流。
一、單項選擇題
1.下列說法不正確的是：
A.SATA硬盤的速度速度大約為500Mbps/s B.讀取18XDVD光盤數(shù)據(jù)的速度為1Gbps C.千兆以太網(wǎng)的數(shù)據(jù)讀取速度為1Gpbs D.讀取DDR3內(nèi)存數(shù)據(jù)的速度為100Gbps
我自己做題時候的思路是：本人有08年的Y430一臺，當(dāng)時給硬盤測速時，記得是60MB/s，也即480Mbps/s，選項A大差不差；印象中，光盤的速度再快，也只有幾十M/s，硬盤尚不能達到1Gbps，更何況光盤呢？基本上可以確定B是錯誤的；所謂的千兆，即1000M=1G，C是對的；而對于DDR3的內(nèi)存速度，有次為了創(chuàng)建ramdisk，使用工具對內(nèi)存進行了鑒別，隱約記得速度是GB/s級別的，D選項中，100Gbps換算過來也就是12.5GB/s，有理由相信它是正確的。綜上，可以判斷出B是錯誤的。
2.（）不能用于Linux中的進程通信 A.共享內(nèi)存 B.命名管道 C.信號量 D.臨界區(qū)
所謂的臨界區(qū)（critical section），實際上指的是一段代碼。選D；在《Windows核心編程第五版》中，對臨界區(qū)的解釋是：它是一小段代碼，它在執(zhí)行之前需要獨占對一些共享資源的訪問權(quán)。這種方式可以讓多行代碼以“原子方式”來對資源進行操控。這里的原子方式，指的是代碼知道除了當(dāng)前線程之外，沒有其他任何線程會同時訪問該資源。當(dāng)然，系統(tǒng)仍然可以暫停當(dāng)前線程去調(diào)度其他線程。但是，在當(dāng)前線程離開臨界區(qū)之前，系統(tǒng)是不會去調(diào)度任何想要訪問同一資源的其他線程。
至于A、B、C，都是進程通信的手段。
Linux中，進程通信的手段有：待補充。
3.設(shè)在內(nèi)存中有P1,P2,P3三道程序，并按照P1,P2,P3的優(yōu)先級次序運行，其中內(nèi)部計算和IO操作時間由下表給出（CPU計算和IO資源都只能同時由一個程序占用）： P1:計算60ms --> IO 80ms --> 計算20ms P2:計算120ms --> IO 40ms --> 計算40ms P3:計算40ms --> IO 80ms --> 計算40ms 完成三道程序比單道運行節(jié)省的時間是（） A.80ms B.120ms C.160ms D.200ms
這道題考察操作系統(tǒng)中有關(guān)進程調(diào)度，作業(yè)調(diào)度的有關(guān)內(nèi)容。做題時，畫圖解比較清晰易懂。由于每個進程都有三個階段：計算、IO、計算，我們將這三次計算命名為A、B、C。同時需要注意，題目中沒有明說，我們假設(shè)P1、P2、P3是不可搶占的。
60ms 80ms 40ms 20ms 20ms 20ms 40ms 40ms 40ms
P1(A)--> P1(B) --> P1(C)
P2(A) P2(A) --> P2(B) P2(B) --> P2(C)
P3(A) P3(A) --> P3(B) P3(B) --> P3(C)
最終耗時：60+80+40+20+20+20+40+40+40=360ms；
全串行執(zhí)行耗時：160+200+160=520ms；
節(jié)約了520ms-360ms=160ms。
4.兩個等價線程并發(fā)的執(zhí)行下列程序，a為全局變量，初始為0，假設(shè)printf、++、--操作都是原子性的，則輸出不可能是哪個（）
void foo() {
if(a <= 0) {
a++;
}
else {
a--;
}
printf("%d", a);
}
A.01
B.10
C.12
D.22當(dāng)時我寫的答案是D，而網(wǎng)上其他版本，好多都講的是C。后來自己思考了一下，覺得A可能是正確的，下面將一下我的思路。
對于B答案，P1執(zhí)行程序，輸出1，P2執(zhí)行程序，輸出0；
對于C答案，初始為0，P1執(zhí)行完判斷語句，決定要執(zhí)行a++，中斷，P2進行判斷，此時a仍然等于0，執(zhí)行判斷語句，并執(zhí)行輸出，得到1，P1然后繼續(xù)執(zhí)行，此時它該執(zhí)行a++，這時a=1，執(zhí)行并輸出，結(jié)果為2；
對于D答案，初始為0，P1執(zhí)行完判斷語句，決定要執(zhí)行a++，中斷，P2進行判斷，此時a仍然等于0，執(zhí)行a++，得到a=1，中斷，P1繼續(xù)執(zhí)行a++，a=2，P1輸出，得到2，P1結(jié)束，P2繼續(xù)執(zhí)行輸出語句，得到2；
對于A答案，我現(xiàn)在再三思考，絞盡腦汁也想不起來當(dāng)初為什么會判斷它不是答案。o(╯□╰)o。
5.給定fun函數(shù)如下，那么fun(10)的輸出結(jié)果是（）
int fun(int x) {
return (x==1) ? 1 : (x + fun(x-1));
}
A.0
B.10
C.55
D.3628800遞歸展開，f(10)=10+f(9)=10+9+f(8)+……+1=55。
6.在c++程序中，如果一個整型變量頻繁使用，最好將他定義為（） A.auto B.extern C.static D.register
C語言中提供了存儲四種修飾符：auto，register，extern，static的：
auto修飾符僅在語句塊內(nèi)部使用，初始化可為任何表達式，其特點是當(dāng)執(zhí)行流程進入該語句塊的時候執(zhí)行初始化操作，沒有默認(rèn)值。
使用register修飾符修飾變量，將暗示編譯程序相應(yīng)的變量將被頻繁地使用，如果可能的話，應(yīng)將其保存在CPU的寄存器中，以加快其存儲速度。
static靜態(tài)變量聲明符。在聲明它的程序塊，子程序塊或函數(shù)內(nèi)部有效，值保持，在整個程序期間分配存儲器空間，編譯器默認(rèn)值0。是C/C++中很常用的修飾符，它被用來控制變量的存儲方式和可見性。static被引入以告知編譯器，將變量存儲在程序的靜態(tài)存儲區(qū)而非棧上空間。
extern可以置于變量或者函數(shù)前，以表示變量或者函數(shù)的定義在別的文件中，提示編譯器遇到此變量和函數(shù)時在其他模塊中尋找其定義。另外，extern也可用來進行鏈接指定。
7.長為n的字符串中匹配長度為m的子串的復(fù)雜度為（） A.O(n) B.O(m+n) C.O(n+logm) D.O(m+logn)
筆試的時候，KMP算法還復(fù)習(xí)，現(xiàn)在都已經(jīng)忘得差不多了，當(dāng)時答案是蒙的。字符串匹配算法在最近也必須得重新復(fù)習(xí)。m=1時，匹配需要O(n)，m增大，也需要有相應(yīng)的開銷；C最像，所以選C。（注：此部分以后再補充）。
8.判斷一包含n個整數(shù)a[]中是否存在i、j、k滿足a[i] + a[j] = a[k]的時間復(fù)雜度為（） A.O(n) B.O(n^2) C.O(nlog(n)) D.O(n^2log(n))
待補充。
9.下列排序算法中最壞復(fù)雜度不是n(n-1)/2的是 A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序
顯而易見。排序算法的比較待補充。
10.三次射擊能中至少一次的概率是0.95，請問一次射擊能中的概率是多少？ A.0.32 B.0.5 C.0.63 D.0.85
公式很簡單，1-(1-p)^3=0.95。接下來需要有一定的估算技巧。A選項可以看作是1/3，C選項可看作是2/3，D選項可看作4/5。
二、不定項選擇題
1.以下哪些進程狀態(tài)轉(zhuǎn)換是正確的() A.就緒到運行 B.運行到就緒 C.運行到阻塞 D.阻塞到運行 E.阻塞到就緒
這題考察linux系統(tǒng)的進程調(diào)度問題，A、B、C、E都是可以的。D中，阻塞到運行，中間需要經(jīng)歷就緒狀態(tài)。
進程切換圖，待補充。
2.一個棧的入棧數(shù)列為：1、2、3、4、5、6；下列哪個是可能的出棧順序。（選項不記得）
這種題是�？嫉�，要熟悉stack的后進先出規(guī)則。
3.下列哪些代碼可以使得a和b交換數(shù)值。（選項不記得）
用兩個數(shù)代入看每一個選項的代碼能否交換其數(shù)值，選出答案。如果不放心，可再選一組進行驗證。
4.A和B晚上無聊就開始數(shù)星星。每次只能數(shù)K個（20<=k<=30）A和B輪流數(shù)。最后誰把星星數(shù)完誰就獲勝，那么當(dāng)星星數(shù)量為多少時候A必勝？（選項不記得） A、2013 B、2888 C、4062 D、*** E、***
對于上述答案，A有必勝的策略，A、B、C、D、E都應(yīng)該選擇。首先，A先取，使剩余的星星為50的倍數(shù)。然后數(shù)星星的順序為B、A、B、A……。B數(shù)k個星星，則A就數(shù)50-k個，使剩余星星始終為50的倍數(shù)，最后，一定是A數(shù)最后的星星。A必勝。
三、填空問答題
1.給你一個整型數(shù)組A[N]，完成一個小程序代碼（20行之內(nèi)），使得A[N]逆向，即原數(shù)組為1，2，3，4，逆向之后為4，3，2，1
void revense(int * a,int n) {
}待補充。
2.自選調(diào)度方面的問題，題目很長，就是給你三個線程，分別采用先來先分配的策略和最短執(zhí)行之間的調(diào)度策略，然后計算每個線程從提交到執(zhí)行完成的時間。 題目實在太長，還有幾個表格�？疾斓氖遣僮飨到y(tǒng)里面作業(yè)調(diào)度算法先進先出和最短作業(yè)優(yōu)先。
待補充。
3.有個苦逼的上班族，他每天忘記定鬧鐘的概率為0.2，上班堵車的概率為0.5， 如果他既沒定鬧鐘上班又堵車那他遲到的概率為1.0，如果他定了鬧鐘但是上班堵車那他遲到的概率為0.9， 如果他沒定鬧鐘但是上班不堵車他遲到的概率為0.8，如果他既定了鬧鐘上班又不堵車那他遲到的概率為0.0， 那么求出他在60天里上班遲到的期望。
待補充。
4.戰(zhàn)報交流：戰(zhàn)場上不同的位置有N個戰(zhàn)士（n>4），每個戰(zhàn)士知道當(dāng)前的一些戰(zhàn)況，現(xiàn)在需要這n個戰(zhàn)士通過通話交流，互相傳達自己知道的戰(zhàn)況信息。 每次通話，可以讓通話的雙方知道對方的所有情報，設(shè)計算法，使用最少的通話次數(shù)，是的戰(zhàn)場上的n個士兵知道所有的戰(zhàn)況信息，不需要寫程序代碼，得出最少的通話次數(shù)。
待補充。
5.有N個人，其中一個明星和n-1個群眾，群眾都認(rèn)識明星，明星不認(rèn)識任何群眾，群眾和群眾之間的認(rèn)識關(guān)系不知道。 現(xiàn)在如果你是機器人R2T2，你每次問一個人是否認(rèn)識另外一個人的代價為O(1)，試設(shè)計一種算法找出明星，并給出時間復(fù)雜度（沒有復(fù)雜度不得分）。
解答：這個問題等價于找未知序列數(shù)中的最小數(shù)，我們將reg這個函數(shù)等價為以下過程：，如果i認(rèn)識j，記作i大于等于j,同樣j不一定大于等于i,滿足要求，i不認(rèn)識j記作i<j，對明星k,他不認(rèn)識所有人，則k是其中最小的數(shù)，且滿足其余的人都認(rèn)識他，也就是其余的人都大于等于k.這樣問題就被轉(zhuǎn)換了。就拿N=5來說，首先有數(shù)組S[5]={A,B,C,D,E}這5個變量，里邊存放著隨機數(shù)，求是否存在唯一最小數(shù)，如果存在位置在S中的哪里。（樓主這里是這個意思，按我的理解題中這個最小數(shù)一定是存在且唯一的）
int finds(S,N)
{
int flag=0;//用于判定是否有明星，即當(dāng)前最小數(shù)另外出現(xiàn)幾次
int temp=0;//存放最小數(shù)在S中的位置
for(i=1;i<N;i++)
｛
if(!reg(S[i],S[temp])//如果temp標(biāo)號的數(shù)小于i標(biāo)號的數(shù)
｛
temp=i;
flag=0;//更換懷疑對象（最小數(shù)）時，標(biāo)記清零
｝
elseif(reg(S[temp]，S[i])//如果temp里存放的確實是唯一最小數(shù)是不會跑進這里來的
{
flag++;
` }
｝
if(flag>0) return -1;//表示沒有明星,例如所有的數(shù)都相等
return temp;//返回明星在S中的位置
}
四、綜合題
有一個淘寶商戶，在某城市有n個倉庫，每個倉庫的儲貨量不同，現(xiàn)在要通過貨物運輸，將每次倉庫的儲貨量變成一致的，n個倉庫之間的運輸線路圍城一個圈，即1->2->3->4->...->n->1->...，貨物只能通過連接的倉庫運輸，設(shè)計最小的運送成本（運貨量*路程）達到淘寶商戶的要求，并寫出代碼。
解答：
有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為1，求使所有人獲得均等糖果的最小代價。
分析：
假設(shè)a1分給an的糖果數(shù)為k，則可以得到以下的信息：
a1 a2 a3 an-1 an
當(dāng)前數(shù)目：a1-k a2 a3 an-1 an+k
所需代價：|a1-k-ave| |a1+a2-k-2*ave| |a1+a2+a3-k-3*ave||a1+..+a(n-1)-k-(n-1)*ave| |k|
以sum[i]表示從a1加到ai減掉i*ave的和值，這以上可以化簡為
總代價 = |s1-k|+|s2-k|+...+|s(n-1)-k|+|k|
不難看出：當(dāng)k為s1...s(n-1)中的中位數(shù)的時候，所需的代價最小
代碼：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int X = 1000005;
typedef long long ll;
ll sum[X],a[X];
ll n;
ll Abs(ll x){
return max(x,-x);
}
int main(){
//freopen("sum.in","r",stdin);
while(cin>>n){
ll x;
ll tot = 0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
tot += a[i];
}
ll ave = tot/n;
for(int i=1;i<n;i++)
sum[i] = a[i]+sum[i-1]-ave;
sort(sum+1,sum+n);
ll mid = sum[n/2];
ll ans = Abs(mid);
for(int i=1;i<n;i++)
ans += Abs(sum[i]-mid);
cout<<ans<<endl;
}
return 0;
}
喜歡 
頂
難過
囧
圍觀
無聊
