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