記淘寶2011實(shí)習(xí)招聘筆試
2011年03月27日 星期日

選擇題
第一題，兩臺電腦在局域網(wǎng)中，機(jī)器為千兆網(wǎng)卡，一臺作服務(wù)器里面有一張網(wǎng)頁為1K字節(jié)，問另一臺下載這個(gè)網(wǎng)頁的速度。
我答：我不知道1K是指1024還是1000…不過按我的算法沒區(qū)別，1000 000000/8/1k
我選了10 000張/秒
第二題，單鏈表插入一個(gè)節(jié)點(diǎn)的問題。在p指向的節(jié)點(diǎn)后插入一個(gè)q指向的節(jié)點(diǎn)。
我答：q->next=p->next;p->next=q;
之后亂序，我記不清楚題號了。

有一題，地圖染色問題，每個(gè)國家用矩形表示，讓相鄰國家顏色不同。離散里面有
有一題，問快速排序達(dá)到最壞情況時(shí)間復(fù)雜度n2的原數(shù)數(shù)組的具體情形。見數(shù)據(jù)結(jié)構(gòu)
有一題，很扯的…指針取址符號混亂，選項(xiàng)卻很白癡。
有一題，入棧序列1,2,3,4,5,..,n，第一個(gè)出棧的是n，問第i個(gè)出棧的是多少。
我答：n-i+1
最后一題，給中綴和后綴表達(dá)式，求前綴表達(dá)式。

填空題
第一題：數(shù)組(a1,a2,a3,a4..,an)，刪除任意一個(gè)的概率相同，問平均刪除一個(gè)要移動(dòng)多少個(gè)。
我答：(n-1)/2
第二題：一個(gè)程序填空，程序大意是在數(shù)組里面找第二大的數(shù)。
注：不難

第三題：大致如下一個(gè)程序片段：
void xxx(x)
{
intcountx=0;
while(x)
{
countx++;
x=x&(x-1);
}
cout<<countx<<endl;
}
問xxx(9999)輸出什么。
我答：8，記得做ACM的時(shí)候碰到過那個(gè)式子，貌似關(guān)于排列的，具體意思忘記了，搞一下可以明白是x變成二進(jìn)制，里面有多少個(gè)1就是答案。

第四題：大致如下一個(gè)代碼
inta[3][2]={1,2,3,4,5,6};
int*p[3];
p[0]=a[1];
問*(p[0]+1)是個(gè)什么東西
我答：4，蠻基礎(chǔ)嗯。

簡答題
第一題：7公斤米，50克砝碼，200克砝碼各一個(gè)，稱1350克米問最少要多少次，并編程回答。
我答，6次，可能一開始會想到 1350/250 + 2 = 7次，說明貪心無效。我不知道我的方法是不是很笨，用了遞推，或者你可以看成是動(dòng)態(tài)規(guī)劃。轉(zhuǎn)化一下題目的意思就是1克和4克砝碼，問多少次稱出27克大米，F(xiàn)[N]代表N克大米最少需要多少次。
則有：
F[N]=min{F[N-1],F[N-4],F[N-5]}+1
代碼如下：
intfindmin(int weight)
{
int v= weight/50;
int f[150];
f[0]=0;f[1]=1;f[2]=2;f[3]=3;f[4]=1;
if (v<5) return f[v];
int i;
for (i=5;i<=v;i++)
f[i]=min(f[i-1]+1,f[i-4]+1,f[i-5]+1);
return f[v];
}

注：我一開始愣了很久，我在想，稱好的大米可以作為砝碼來用嗎？？這樣就是另一種問題了吧。
附加：
如果天平能做為平衡工具的話，兩次平分到1750克，然后兩次量出200克，1750-400就是1350克了。。。四次。。。。

解答題第一題：
第一次：200+50，稱出250g 第二次：200+250，稱出450 第三次：200+450，稱出650共稱出1350g

第二題，有N個(gè)蛋和M個(gè)籃子，把蛋放到M個(gè)籃子里，每個(gè)籃子都不能為空。另外，需要滿足：任意一個(gè)小于N的正整數(shù)，都能由某幾個(gè)籃子內(nèi)蛋的數(shù)量相加的和得到。寫出程序，使得輸入一個(gè)(N,M)，輸出所有可能的分配情況。 我答：不能想出算出所有擺放方法的方法，期待ACM大牛路過。
（1. 先取M個(gè)蛋放入M個(gè)籃子（一個(gè)籃子一個(gè)蛋）
2.剩下的（N-M）個(gè)蛋按照1，2，4，。。方式依次維持各個(gè)籃子中蛋的數(shù)量（要有一個(gè)籃子保持只有一個(gè)蛋），若最后的蛋不是2的方次，有多少放入一個(gè)籃子
3.取L(L<=N)個(gè)蛋時(shí)，應(yīng)按二進(jìn)制編碼值考慮，如13個(gè)蛋：13的二進(jìn)制碼值是1101，則取有8個(gè)、4個(gè)和1個(gè)蛋的籃子即可。
另外：題目不完整，N與M應(yīng)該有數(shù)量關(guān)系：M<=N且N<2的M次方）
解答1
view plaincopy to clipboardprint?
/**
* 假設(shè) n>m 并且 n小于100
public class Test {
private int m;
private int n;
private int eggs[];
private int numAnswer;

Test(){
m=10;
n=20;
numAnswer=0;
eggs = new int[m];
for(int i=0;i<m;i++){
eggs[i]=0;
}
}
private void fill(boolean [] state, int step, int sum){
if(step>=m){
state[sum] = true;
return ;
}
fill(state,step+1,sum);
fill(state,step+1,sum+eggs[step]);
}

/**
* 判斷是否滿足：任意一個(gè)小于N的正整數(shù)，都能由某幾個(gè)籃子內(nèi)蛋的數(shù)量相加的和得到
* 算法：暴力枚舉所有籃子的組合
* @return
*/
private boolean judge(){
boolean [] state = new boolean [n+1];
for(int i=0;i<=n;i++){
state[i] = false;
}

fill(state,0,0);

for(int i=1;i<=n;i++){
if(!state[i]){
return false;
}
}
return true;
}

/**
* 給每個(gè)籃子分雞蛋，升序（后一個(gè)籃子的雞蛋必須不小于前一個(gè)籃子，避免重復(fù)計(jì)算）
* @param pre 前一個(gè)籃子雞蛋數(shù)
* @param already 前step個(gè)籃子 已使用的雞蛋數(shù)
* @param step 第step個(gè)籃子
*/
public void solve(int pre,int already, int step){
if(step==m-1){
//最后一個(gè)籃子
eggs[m-1]=n-already;
//不符合條件
if(eggs[m-1]<pre) return;

//判斷是否滿足：任意一個(gè)小于N的正整數(shù)，都能由某幾個(gè)籃子內(nèi)蛋的數(shù)量相加的和得到
if(judge()) {
for(int i=0;i<m;i++){
System.out.print(eggs[i]+" ");
}
System.out.println();
numAnswer++;
}
return ;
}

// 給第step個(gè)籃子裝雞蛋，pre 到 n-already 種可能
for(int i=pre; i<=n-already; i++){
eggs[step]=i;
//遞歸
solve(i,already+i,step+1);
}
}
public static void main(String arg [] ){
Test test = new Test();
test.solve(1,0,0);
System.out.println("可能情況的數(shù)量："+test.numAnswer);
}
}

 

解答2
using System;
using System.Collections.Generic;
using System.Text;
namespace CmpSplitEgg
{
class Program
{
static void Main(string[] args)
{
SplitEgg();
}

public static bool SplitEgg()
{
// 初始化變量，差額diffNum = 雞蛋數(shù)eggNum - 籃子數(shù)basketNum
int eggNum = 0, basketNum = 0, diffNum;
// 輸入雞蛋數(shù)、籃子數(shù)
Input(ref eggNum, ref basketNum);
// 排列結(jié)果，并初始化
int[] resultEggs = new int[basketNum];
for(int i=0;i<basketNum;i++)
{
resultEggs[i] = 1;
}

// 差額 = 雞蛋數(shù) - 籃子數(shù)
diffNum = eggNum - basketNum;
if (diffNum < 0)
{
Console.WriteLine("You can't make N < M");
return DoAgain() && SplitEgg();
}
else if (Math.Pow(2, basketNum) <= eggNum)
{
Console.WriteLine("You can't make N > 2^M");
return DoAgain() && SplitEgg();
}

// 對任意一個(gè)小于N的數(shù) 總能使幾個(gè)籃子里的雞蛋總數(shù)等于它，則需要編號n的籃子放的雞蛋數(shù)<=前面的雞蛋數(shù)總和+1
// 基于2進(jìn)制編碼是能表示所有數(shù)字且位數(shù)最小的編碼方式，上面條件由此推出
// 假設(shè)組合為升序排列，第一個(gè)籃子必然為1個(gè)雞蛋
RandomLay(resultEggs, 1, eggNum);

// 是否重新做一次
return DoAgain() && SplitEgg();
}

/// <summary>
/// 重新選擇
/// </summary>
public static bool DoAgain()
{
Console.WriteLine();
Console.WriteLine("if you want to enter the N and M again?Yes（Note: if not enter 'Y' or 'y', the application will quit...）");
string choice = Console.ReadLine();
return choice.ToLower() == "y";
}

/// <summary>
/// 輸入
/// </summary>
/// <param name="eggNum">雞蛋數(shù)量</param>
/// <param name="basketNum">籃子數(shù)量</param>
public static void Input(ref int eggNum, ref int basketNum)
{
while (true)
{
try
{
Console.WriteLine("Please enter the egg number N:");
eggNum = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Please enter the basket number M:");
basketNum = Convert.ToInt32(Console.ReadLine());
break;
}
catch (Exception)
{
Console.WriteLine("Enter error: please input integer!");
Console.WriteLine();
continue;
}
}
}

/// <summary>
/// 隨即放置雞蛋
/// </summary>
/// <param name="result">結(jié)果</param>
/// <param name="beginIndex">開始索引</param>
/// <param name="total">雞蛋數(shù)</param>
public static void RandomLay(int[] result, int index, int total)
{
// iMax為index對應(yīng)可取雞蛋數(shù)上限
int iMax = 1, basketNum = result.Length;
for (int j = 0; j < index; j++)
{
iMax += result[j];
}

// 復(fù)制
int[] copyResult = new int[basketNum];
for (int i = 0; i < basketNum; i++)
{
copyResult[i] = result[i];
}

// 結(jié)束條件1：已為最后一個(gè)籃子
if (index == basketNum - 1)
{
int mBasket = total - iMax + 1;
if (mBasket <= iMax)
{
copyResult[index] = mBasket;
Console.Write("Split solution: ");
foreach (int res in copyResult)
Console.Write(res + " ");
Console.WriteLine();
}
return;
}
for (int ii = copyResult[index - 1]; ii <= iMax; ii++)
{
// 結(jié)束條件2：當(dāng)前至少需要雞蛋數(shù)
int nowNum = ii * (basketNum - index) + iMax - 1;
// 表示無法再按升序放置雞蛋
if (nowNum > total)
break;
copyResult[index] = ii;
RandomLay(copyResult, index + 1, total);
}
}
}
}

解答3
[code=C/C++][/code]#include<iostream>
#include<math.h>
#include<malloc.h>
#include<fstream>
using namespace std;

struct solution
{
int *ptr;
struct solution *next;
};
typedef struct solution solu;

int* first(int n,int m); //計(jì)算出第一種組合
solu* others(int n,int m,solu *head,solu *prior); //計(jì)算出其他組合
int sum(int n,int *p); //計(jì)算前n-1個(gè)籃子里的蛋數(shù)和
bool only(solu *head,int *p,int m); //檢查組和是否滿足要求
int ways; //全局變量，保存組合的方法數(shù)

void main()
{
int n=0,m=0,i=0,k=0;
solu *head=NULL;
solu *temp=NULL;
LABLE: cout<<"輸入雞蛋數(shù)N=";
cin>>n;
cout<<"輸入籃子數(shù)M=";
cin>>m;
if(m<=0||n<=0||m>n||(double)n>=pow(2.0,m)) //對m,n的約束
{
cout<<"輸入不合法！"<<endl;
goto LABLE;
}
cout<<"正在計(jì)算..."<<endl;
head=others(n,m,head,NULL); //調(diào)用others開始計(jì)算
temp=head;
ofstream file("D:\\egg.txt"); //結(jié)果保存著這個(gè)目錄下
cout<<"共有"<<ways<<"種組合方式："<<endl;
file<<"共有"<<ways<<"種組合方式："<<endl;
k=ways;
while(temp!=NULL&&ways)
{
cout<<"方式"<<k-ways+1<<"："<<endl;
file<<"方式"<<k-ways+1<<"："<<endl;
for(i=0;i<m;i++)
{
cout<<*(temp->ptr+i)<<" ";
file<<*(temp->ptr+i)<<" ";
}
delete[] temp->ptr;
temp=temp->next;
cout<<endl;
file<<endl;
ways--;
}
file.close();
cout<<"操作結(jié)果保存在D://egg.txt，您可以查看或刪除之。";
cin>>i;
}

int sum(int n,int *p) //計(jì)算前n-1個(gè)籃子里的總蛋數(shù)
{
int total=0;
for(int i=0;i<n;i++)
{
total+=*(p+i);
}
return total;
}
int* first(int n,int m)
{
int *p,i=0,temp1=0,temp2=0;
p=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++) //每個(gè)籃子里放一個(gè)蛋
{
*(p+i)=1;
}
//下面的分配滿足的條件：
//“總能找到幾個(gè)籃子，使里面雞蛋的和等于任意一個(gè)小于n的正整數(shù)”
//下面的if～else語句完成一種組合，升序排列，并使后面的籃里的蛋盡量多
if(n-m>m-1)
//剩下的蛋數(shù)大于前面m-1個(gè)籃子里的蛋數(shù)和，
{
*(p+m-1)+=m-1;
while(sum(m,p)<n) //還有蛋剩余
{
temp1=n-sum(m,p); //剩蛋數(shù)
for(i=m;i>0;)
{
temp2=sum(i-1,p); //第i個(gè)籃子前面的所有籃子里的蛋數(shù)的總和
if(*(p+i-1)<=temp2)
//第i個(gè)籃子里的蛋數(shù)小于等于前面籃子里蛋的總數(shù)，給這個(gè)籃里加蛋
//否則，見else
{
if(temp1<=temp2-*(p+i-1)+1) //剩下的蛋可以全部放到第i個(gè)籃里，完畢
{*(p+i-1)+=temp1;break;}
else {*(p+i-1)+=temp2-*(p+i-1)+1;break;} //在第i個(gè)籃子放可能達(dá)到的最多蛋數(shù)
}
else i--; //檢測前面那個(gè)籃子
}
}

}
else *(p+m-1)+=n-m;
//剩下的蛋數(shù)小于等于前面m-1個(gè)籃子里的蛋數(shù)和，
//把所有的蛋都放到最后一個(gè)籃里，完成一種組合。
return p;

}

solu* others(int n,int m,solu* head,solu *prior)
{
int i=0,j=0,k=0;
if(head==NULL) //還沒有任何組合
{
solu *s=new(solu);
s->ptr=first(n,m); //調(diào)用first()生成滿足后面的值最大的升序序列
head=s;
head->next=NULL;
prior=head;
ways=1;
}
for(j=m-1;j>0;j--) //兩重循環(huán)，開始計(jì)算其他組合
//原理是從后面的籃子里取出雞蛋放入前面的籃子中
{
if(*(prior->ptr+j)==1) //后面的籃子里蛋數(shù)為1，跳出循環(huán)
break;
for(i=j-1;i>0;i--) //一個(gè)個(gè)往前挨
{
if(*(prior->ptr+j)-1>*(prior->ptr+i)) //后面的籃子減掉后不能比前面的少，保持升序排列
{
int *p=(int *)malloc(m*sizeof(int));
for(k=0;k<m;k++)
{
(*(p+k))=(*(prior->ptr+k));
}
(*(p+j))--;(*(p+i))++;
if(only(head,p,m)) //檢查是否滿足條件，滿足則將結(jié)果添加到鏈表中
{
solu *stemp=new(solu);
stemp->ptr=p;
stemp->next=head->next;head->next=stemp;
head=others(n,m,head,stemp);
ways++;
}
else delete[] p;

}
else if(*(prior->ptr+j)-1==*(prior->ptr+i))
continue;
else
break;
}
}
return head;
}
bool only(solu *head,int *p,int m) //判斷條件是否符合
{
solu *s=head;
int flag=0,i=0;
for(int k=0;k<m-1;k++)
{
if(*(p+k+1)<*(p+k)||*(p+k+1)>sum(k+1,p)+1) //兩個(gè)條件：1、升序，2、后面的數(shù)必須小于等于前面的籃子總數(shù)和加1
return false;
}
while(s!=NULL) //判斷是否有過相同的組合，有則返回false
{
flag=0;
for(i=0;i<m;i++)
{
if(*(s->ptr+i)!=*(p+i))
{
flag=1;
break;
}
}
if(!flag)
{
return false;
}
s=s->next;
}
return true; //檢查通過，返回true
}

任意給定的M 和N, 假定雞蛋已經(jīng)全部按規(guī)定放好了，那么如果能取出X個(gè)雞蛋（0<X< M）那么剩下的就是M-X個(gè)雞蛋，也相當(dāng)于取出了M-X個(gè)雞蛋。所以只需要考慮能夠取到1到M/2個(gè)雞蛋即可。

又如有的哥們講的1,2,4,8.。。2^(k-1)這樣數(shù)列比較特殊，有k位這樣的數(shù)列,可從中取出若干個(gè)數(shù)相加得到任意小于2^k-1的數(shù)（因?yàn)镵位這樣的數(shù)列相加的和為2^k - 1）,那么依照題意我們應(yīng)該從這樣的數(shù)列開始考慮。

現(xiàn)在有N個(gè)籃子，先拿掉一個(gè)籃子。那么這N-1個(gè)籃子按上面的方法放雞蛋的話可表示出所有小于2^(N-1)-1的數(shù)，如果2^(N-1)-1 > M/2那么該題有解，否則無解。

情況一 M > 2^(N-1)-1 > M/2
給N-1個(gè)籃子中分別放1,2,4,8....2^(N-2)個(gè)雞蛋，剩下的雞蛋全部放最后一個(gè)籃子里。
由于前N-1個(gè)籃子可表示任意小于M/2的數(shù)，所以這N個(gè)籃子可表示所有小于M的數(shù)。如果不考慮籃子的編號和順序，此情況只有一種放法。
情況二 2^(N-1)-1 > M
按上面的方法還沒放到第N-1個(gè)籃子雞蛋就沒了，那么這時(shí)的做法是，先按上面的方法放好所有雞蛋。假設(shè)放到第x個(gè)籃子雞蛋就沒了，那么從x+1個(gè)籃子開始回頭從x籃子里拿一個(gè)雞蛋放入其中，然后是x+2籃子同樣的處理，依次類推。如果x籃子中只剩一個(gè)雞蛋了還有籃子是空的，那么從x-1籃子中取雞蛋。依次類推放滿所有籃子。按這種方法如果N=M，則每個(gè)籃子放一個(gè)雞蛋。如果不考慮籃子的編號和順序則方法是很有限的，也就是將雞蛋在幾個(gè)籃子里倒來倒去。

可以看出此算法的復(fù)雜度只有N，根本不需要遞歸什么的。老太太按這種方法操作也能很快得出一個(gè)解。

也可以看出給定若干個(gè)雞蛋，至少需要多少個(gè)籃子才能滿足題目要求，比如100個(gè)雞蛋就最少需要7個(gè)籃子 500個(gè)雞蛋最少需要9個(gè)籃子，1000個(gè)雞蛋最少需要10個(gè)籃子

第三題，大意淘寶網(wǎng)的評論系統(tǒng)，原先只有一個(gè)評論表，對于現(xiàn)在大用戶，大數(shù)據(jù)量，大訪問量，請?jiān)O(shè)計(jì)一個(gè)合理可行的架構(gòu)來優(yōu)化關(guān)于評論的數(shù)據(jù)庫。
我答：哥蒙了，哥胡言亂語的。

附加題：前端設(shè)計(jì)師必答
第一題：圖片默認(rèn)為半透明，鼠標(biāo)移上去變成不透明。
我注：img標(biāo)簽onfocus和onblur的應(yīng)用，注意這個(gè)透明的屬性在IE和FireFox下是不同的。而且用js控制的時(shí)候，屬性名也要注意…

第二題：一個(gè)輸入框，和一個(gè)列表框，列表框里面有很多字符串，在輸入框里面輸入字符串時(shí)，列表框中字符串前綴是該字符串的做高亮或者其他顯著表示。最后回車選擇或者鼠標(biāo)雙擊列表框選擇。
我注：看上去要寫不少東西啊……實(shí)在懶了。

總結(jié)：
基礎(chǔ)偏多，大題很算法，很偏實(shí)際應(yīng)用，前面不會不應(yīng)該了，后面看造化，畢竟時(shí)間也不多。
最后：如果有錯(cuò)，請指正，僅給路人或未來想進(jìn)淘寶的孩子或八卦的朋友做些參考。