百度2012校园招聘机器学习/数据挖掘工程师(北京)笔试题目 2011.10.16

一.简单题
1. C++中STL vector 相关
(1).push_back函数的内存分配是怎样的？
(2).clear函数的内存分配是如何实现的？

2.给出了一个C语言的代码，找出foo函数中的错误或者不合理的地方

void foo(char a[100], cnt[256])
{
memset(cnt, 0, sizeof(cnt));

while(*a != ‘\0′)
{
++cnt[*a];
++a;
}
for(char c=’a'; c<=’z'; ++c)
{
printf(“%c, d”, c, cnt[c]);
}
}

int main()
{
char a[100] = “百度abc”;
char cnt[256];

foo(char a[100], cnt[256]);
}

二.算法设计

1.已知函数rand(s,t)可以给出[s,t]的小数，用该函数给出半径为R的园内的n个随机点，并分析时间复杂度。

2.已知服务器只能存贮m个请求query, 请给出一个设计，从用户的请求中随机取出m个，并尽量保证每一个query取出的概率相同，不到最后时间没人知道用户的请求量是多少。

三.
分类聚类算法相关（K-NN,linear SVM etc ）
1.给出下面的样本（方块）在1-邻近，3-邻近，5-邻近 下的标签。
+

— + —
方块位置
— —

2.说明K的取值大小对算法的影响（复杂度，训练精度，测试精度等等）

3.一个厂商准备上线一个在线图片分类算法，数据量大，服务器资源有限，查询时间需要快一些，请在linear SVM, logistic regression,discriminate regression等算法中选择一个实现，并说明理由和分析，并与k-NN进行优势与劣势比较。