记淘宝2011实习招聘笔试
2011年03月27日 星期日

选择题
第一题，两台电脑在局域网中，机器为千兆网卡，一台作服务器里面有一张网页为1K字节，问另一台下载这个网页的速度。
我答：我不知道1K是指1024还是1000…不过按我的算法没区别，1000 000000/8/1k
我选了10 000张/秒
第二题，单链表插入一个节点的问题。在p指向的节点后插入一个q指向的节点。
我答：q->next=p->next;p->next=q;
之后乱序，我记不清楚题号了。

有一题，地图染色问题，每个国家用矩形表示，让相邻国家颜色不同。离散里面有
有一题，问快速排序达到最坏情况时间复杂度n2的原数数组的具体情形。见数据结构
有一题，很扯的…指针取址符号混乱，选项却很白痴。
有一题，入栈序列1,2,3,4,5,..,n，第一个出栈的是n，问第i个出栈的是多少。
我答：n-i+1
最后一题，给中缀和后缀表达式，求前缀表达式。

填空题
第一题：数组(a1,a2,a3,a4..,an)，删除任意一个的概率相同，问平均删除一个要移动多少个。
我答：(n-1)/2
第二题：一个程序填空，程序大意是在数组里面找第二大的数。
注：不难

第三题：大致如下一个程序片段：
void xxx(x)
{
intcountx=0;
while(x)
{
countx++;
x=x&(x-1);
}
cout<<countx<<endl;
}
问xxx(9999)输出什么。
我答：8，记得做ACM的时候碰到过那个式子，貌似关于排列的，具体意思忘记了，搞一下可以明白是x变成二进制，里面有多少个1就是答案。

第四题：大致如下一个代码
inta[3][2]={1,2,3,4,5,6};
int*p[3];
p[0]=a[1];
问*(p[0]+1)是个什么东西
我答：4，蛮基础嗯。

简答题
第一题：7公斤米，50克砝码，200克砝码各一个，称1350克米问最少要多少次，并编程回答。
我答，6次，可能一开始会想到 1350/250 + 2 = 7次，说明贪心无效。我不知道我的方法是不是很笨，用了递推，或者你可以看成是动态规划。转化一下题目的意思就是1克和4克砝码，问多少次称出27克大米，F[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个蛋和M个篮子，把蛋放到M个篮子里，每个篮子都不能为空。另外，需要满足：任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到。写出程序，使得输入一个(N,M)，输出所有可能的分配情况。 我答：不能想出算出所有摆放方法的方法，期待ACM大牛路过。
（1. 先取M个蛋放入M个篮子（一个篮子一个蛋）
2.剩下的（N-M）个蛋按照1，2，4，。。方式依次维持各个篮子中蛋的数量（要有一个篮子保持只有一个蛋），若最后的蛋不是2的方次，有多少放入一个篮子
3.取L(L<=N)个蛋时，应按二进制编码值考虑，如13个蛋：13的二进制码值是1101，则取有8个、4个和1个蛋的篮子即可。
另外：题目不完整，N与M应该有数量关系：M<=N且N<2的M次方）
解答1
view plaincopy to clipboardprint?
/**
* 假设 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]);
}

/**
* 判断是否满足：任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到
* 算法：暴力枚举所有篮子的组合
* @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;
}

/**
* 给每个篮子分鸡蛋，升序（后一个篮子的鸡蛋必须不小于前一个篮子，避免重复计算）
* @param pre 前一个篮子鸡蛋数
* @param already 前step个篮子 已使用的鸡蛋数
* @param step 第step个篮子
*/
public void solve(int pre,int already, int step){
if(step==m-1){
//最后一个篮子
eggs[m-1]=n-already;
//不符合条件
if(eggs[m-1]<pre) return;

//判断是否满足：任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到
if(judge()) {
for(int i=0;i<m;i++){
System.out.print(eggs[i]+" ");
}
System.out.println();
numAnswer++;
}
return ;
}

// 给第step个篮子装鸡蛋，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("可能情况的数量："+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 = 鸡蛋数eggNum - 篮子数basketNum
int eggNum = 0, basketNum = 0, diffNum;
// 输入鸡蛋数、篮子数
Input(ref eggNum, ref basketNum);
// 排列结果，并初始化
int[] resultEggs = new int[basketNum];
for(int i=0;i<basketNum;i++)
{
resultEggs[i] = 1;
}

// 差额 = 鸡蛋数 - 篮子数
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();
}

// 对任意一个小于N的数 总能使几个篮子里的鸡蛋总数等于它，则需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
// 基于2进制编码是能表示所有数字且位数最小的编码方式，上面条件由此推出
// 假设组合为升序排列，第一个篮子必然为1个鸡蛋
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">鸡蛋数量</param>
/// <param name="basketNum">篮子数量</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">结果</param>
/// <param name="beginIndex">开始索引</param>
/// <param name="total">鸡蛋数</param>
public static void RandomLay(int[] result, int index, int total)
{
// iMax为index对应可取鸡蛋数上限
int iMax = 1, basketNum = result.Length;
for (int j = 0; j < index; j++)
{
iMax += result[j];
}

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

// 结束条件1：已为最后一个篮子
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++)
{
// 结束条件2：当前至少需要鸡蛋数
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); //计算出第一种组合
solu* others(int n,int m,solu *head,solu *prior); //计算出其他组合
int sum(int n,int *p); //计算前n-1个篮子里的蛋数和
bool only(solu *head,int *p,int m); //检查组和是否满足要求
int ways; //全局变量，保存组合的方法数

void main()
{
int n=0,m=0,i=0,k=0;
solu *head=NULL;
solu *temp=NULL;
LABLE: cout<<"输入鸡蛋数N=";
cin>>n;
cout<<"输入篮子数M=";
cin>>m;
if(m<=0||n<=0||m>n||(double)n>=pow(2.0,m)) //对m,n的约束
{
cout<<"输入不合法！"<<endl;
goto LABLE;
}
cout<<"正在计算..."<<endl;
head=others(n,m,head,NULL); //调用others开始计算
temp=head;
ofstream file("D:\\egg.txt"); //结果保存着这个目录下
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<<"操作结果保存在D://egg.txt，您可以查看或删除之。";
cin>>i;
}

int sum(int n,int *p) //计算前n-1个篮子里的总蛋数
{
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++) //每个篮子里放一个蛋
{
*(p+i)=1;
}
//下面的分配满足的条件：
//“总能找到几个篮子，使里面鸡蛋的和等于任意一个小于n的正整数”
//下面的if～else语句完成一种组合，升序排列，并使后面的篮里的蛋尽量多
if(n-m>m-1)
//剩下的蛋数大于前面m-1个篮子里的蛋数和，
{
*(p+m-1)+=m-1;
while(sum(m,p)<n) //还有蛋剩余
{
temp1=n-sum(m,p); //剩蛋数
for(i=m;i>0;)
{
temp2=sum(i-1,p); //第i个篮子前面的所有篮子里的蛋数的总和
if(*(p+i-1)<=temp2)
//第i个篮子里的蛋数小于等于前面篮子里蛋的总数，给这个篮里加蛋
//否则，见else
{
if(temp1<=temp2-*(p+i-1)+1) //剩下的蛋可以全部放到第i个篮里，完毕
{*(p+i-1)+=temp1;break;}
else {*(p+i-1)+=temp2-*(p+i-1)+1;break;} //在第i个篮子放可能达到的最多蛋数
}
else i--; //检测前面那个篮子
}
}

}
else *(p+m-1)+=n-m;
//剩下的蛋数小于等于前面m-1个篮子里的蛋数和，
//把所有的蛋都放到最后一个篮里，完成一种组合。
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); //调用first()生成满足后面的值最大的升序序列
head=s;
head->next=NULL;
prior=head;
ways=1;
}
for(j=m-1;j>0;j--) //两重循环，开始计算其他组合
//原理是从后面的篮子里取出鸡蛋放入前面的篮子中
{
if(*(prior->ptr+j)==1) //后面的篮子里蛋数为1，跳出循环
break;
for(i=j-1;i>0;i--) //一个个往前挨
{
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)) //检查是否满足条件，满足则将结果添加到链表中
{
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) //两个条件：1、升序，2、后面的数必须小于等于前面的篮子总数和加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, 假定鸡蛋已经全部按规定放好了，那么如果能取出X个鸡蛋（0<X< M）那么剩下的就是M-X个鸡蛋，也相当于取出了M-X个鸡蛋。所以只需要考虑能够取到1到M/2个鸡蛋即可。

又如有的哥们讲的1,2,4,8.。。2^(k-1)这样数列比较特殊，有k位这样的数列,可从中取出若干个数相加得到任意小于2^k-1的数（因为K位这样的数列相加的和为2^k - 1）,那么依照题意我们应该从这样的数列开始考虑。

现在有N个篮子，先拿掉一个篮子。那么这N-1个篮子按上面的方法放鸡蛋的话可表示出所有小于2^(N-1)-1的数，如果2^(N-1)-1 > M/2那么该题有解，否则无解。

情况一 M > 2^(N-1)-1 > M/2
给N-1个篮子中分别放1,2,4,8....2^(N-2)个鸡蛋，剩下的鸡蛋全部放最后一个篮子里。
由于前N-1个篮子可表示任意小于M/2的数，所以这N个篮子可表示所有小于M的数。如果不考虑篮子的编号和顺序，此情况只有一种放法。
情况二 2^(N-1)-1 > M
按上面的方法还没放到第N-1个篮子鸡蛋就没了，那么这时的做法是，先按上面的方法放好所有鸡蛋。假设放到第x个篮子鸡蛋就没了，那么从x+1个篮子开始回头从x篮子里拿一个鸡蛋放入其中，然后是x+2篮子同样的处理，依次类推。如果x篮子中只剩一个鸡蛋了还有篮子是空的，那么从x-1篮子中取鸡蛋。依次类推放满所有篮子。按这种方法如果N=M，则每个篮子放一个鸡蛋。如果不考虑篮子的编号和顺序则方法是很有限的，也就是将鸡蛋在几个篮子里倒来倒去。

可以看出此算法的复杂度只有N，根本不需要递归什么的。老太太按这种方法操作也能很快得出一个解。

也可以看出给定若干个鸡蛋，至少需要多少个篮子才能满足题目要求，比如100个鸡蛋就最少需要7个篮子 500个鸡蛋最少需要9个篮子，1000个鸡蛋最少需要10个篮子

第三题，大意淘宝网的评论系统，原先只有一个评论表，对于现在大用户，大数据量，大访问量，请设计一个合理可行的架构来优化关于评论的数据库。
我答：哥蒙了，哥胡言乱语的。

附加题：前端设计师必答
第一题：图片默认为半透明，鼠标移上去变成不透明。
我注：img标签onfocus和onblur的应用，注意这个透明的属性在IE和FireFox下是不同的。而且用js控制的时候，属性名也要注意…

第二题：一个输入框，和一个列表框，列表框里面有很多字符串，在输入框里面输入字符串时，列表框中字符串前缀是该字符串的做高亮或者其他显著表示。最后回车选择或者鼠标双击列表框选择。
我注：看上去要写不少东西啊……实在懒了。

总结：
基础偏多，大题很算法，很偏实际应用，前面不会不应该了，后面看造化，毕竟时间也不多。
最后：如果有错，请指正，仅给路人或未来想进淘宝的孩子或八卦的朋友做些参考。