网易游戏2016校园招聘数据挖掘研究员在线笔试题和答案

      刚做完网易在线笔试题，感触最深的地方是，虽然题目形式和ACM题目相似，但是内容更偏向于实际应用。总共有四个题目，第一个题目属于字符串匹配类型，难度较低，第二个题目是模拟SQL语句的输出，第三个题目是KNN算法，第四个题目是贝叶斯算法。题目偏基础，算法思想很容易想到，但如果平常从来没写过这类算法，再加上代码能力不是很强的话，写起来还是有点吃力的。下面是第一题，第三题，第四题的答案。

题目1 : 虚拟游戏世界实体分析

描述

虚拟游戏世界里面有很多实体，实体可能由很多子实体或者子属性构成。由于实体之间可能有非常之多的嵌套，查询某个实体或者属性属于第几层嵌套，以便将来对虚拟世界的修改和展示是一项待解决的问题，作为未来的虚拟世界分析员，你能用程序解决这个问题吗？

输入

输入数据可能由多组数据构成，每组数据由两行构成：

第一行是对虚拟世界的描述,实体或者属性由英文字母或者数字构成，子实体和子属性紧接着父实体嵌套在{}中，兄弟实体或者属性用“,”分隔。

第二行是要查询的属性或者实体，有且仅有一个。

注意数据输入可能很大。

输出

输出为查询的实体或者属性的层数；如果属性不存在，输出-1；如果有多个结果满足查询，请从小到大输出所有去重之后的结果，用”,”分隔

样例输入

Fruit{apple{shape,color},orange{taste,price}}
Fruit
Fruit{apple{shape,color},orange{taste,price}}
orange
Fruit{apple{shape,color},orange{color,price},color}
color  

样例输出

1
2
2,3  

#include <string>
#include <vector>
#include <iostream>	
#include <algorithm> 
using namespace std;

int main()
{ 
    string s;
	string query;	
    while(cin >> s >> query) {
		int i = 0;
		int j = 0;
		int h = 1;
		int begin = 0;
		vector<int> ans;
        for( i = 0; i < s.size(); i++) {
			if(s[i] == '{' || s[i] == '}' || s[i] == ',') {
				if(i - begin == query.size()) {
					for(j = 0; j < query.size(); j++) {
						if(query[j] != s[begin + j]) {
							break;
						}
					}
					if(j == query.size()) {
						ans.push_back(h);
					}
				}
				begin = i + 1;
			}
			if(s[i] == '{') {
				h++;
				
			} else if(s[i] == '}') {
				h--;
			} 
		}
		sort(ans.begin(), ans.end());  
		if(ans.size() == 0)
			cout << -1 << endl;
		else {
			cout << ans[0];
			for(int k = 1; k < ans.size(); k++) {
				if(ans[k] != ans[k-1])
					cout << "," << ans[k];
			}
			cout << endl;
		}
    }
    return 0;
}

代码：

#include <string>
#include <vector>
#include <iostream>	
#include <algorithm> 
using namespace std;

typedef struct
{
	vector<double> f;
	char label;
}Elem;

typedef struct
{
	double cost;
	int idx;
}NN;

typedef struct
{
	int cnt;
	int idx;
}LabelCnt;

bool operator<(const NN &x, const NN &y)
{
    return x.cost < y.cost;
}

bool operator<(const LabelCnt &x, const LabelCnt &y)
{
    return x.cnt > y.cnt;
}

double distance(vector<double> &f1, vector<double> &f2) {
	double sum = 0.0;
	for(int i = 0; i < f1.size(); i++) {
		sum += (f1[i] - f2[i]) * (f1[i] - f2[i]);
	}
	return sum;
}
int main()
{ 
    int k,L,M,N;
    while(cin >> k >> L >> M >> N) {
		int i = 0;
		int j = 0;
		vector<Elem> trainData;
		trainData.resize(M);
		for( i = 0; i < M; i++) {
			trainData[i].f.resize(L);
			for( j = 0; j < L; j++) {
				cin >> trainData[i].f[j];
			}
			cin >> trainData[i].label;
		}
		vector<Elem> testData;
		testData.resize(N);
		for( i = 0; i < N; i++) {
			testData[i].f.resize(L);
			for( j = 0; j < L; j++) {
				cin >> testData[i].f[j];
			}
			vector<NN> nnCost;
			nnCost.resize(M);
			int t = 0;
			for( t = 0; t < M; t++) {
				nnCost[t].idx = t;
				nnCost[t].cost = distance(trainData[t].f, testData[i].f);
			}
			sort(nnCost.begin(), nnCost.end());  
			vector<LabelCnt> labels;
			labels.resize(4);
			for( t = 0; t < labels.size(); t++) {
				labels[t].cnt = 0;
				labels[t].idx = t;
			}
			for( t = 0; t < k; t++) {
				int idx = nnCost[t].idx;
				int label = trainData[idx].label - 'A';
				labels[label].cnt++;
			}
			sort(labels.begin(), labels.end()); 
			vector<int> ans;
			ans.push_back(labels[0].idx);
			for( t = 1; t < labels.size(); t++) {
				if(labels[t].cnt == labels[t-1].cnt)
					ans.push_back(labels[t].idx);
				else
					break;
			}
			for( t = 0; t < ans.size(); t++) {
				cout << (char)(ans[t]+'A');
			}
			cout << endl;
		}
    }
    return 0;
}

代码：

#include <string>
#include <vector>
#include <iostream>	
#include <algorithm> 
using namespace std;

typedef struct
{
	vector<int> f;
}Elem;

void split(string s, vector<int> &values) {
	char sep = '\t';
	int begin = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == sep) {
			int num = 0;
			for(int j = begin; j < i; j++) {
				num = num * 10 + s[j] - '0';
			}
			if(num > 0)
				values.push_back(num);		
			begin = i + 1;
		}
	}
	int num = 0;
	for(int j = begin; j < s.size(); j++) {
		num = num * 10 + s[j] - '0';
	}
	if(num > 0)
		values.push_back(num);
}

double getPrior(vector<Elem> &data, int label) {
	int good = 0;
	for(int i = 0; i < data.size(); i++) {
		if(data[i].f[2] == label)
			good++;
	}
	if(good == 0)
		return 0.0;
	return 1.0*good/data.size();
}

double getPosterior(vector<Elem> &data, int idx, int k, int label) {
	int cnt = 0;
	int sum = 0;
	for(int i = 0; i < data.size(); i++) {
		if(data[i].f[2] == label) {
			sum++;
			if(data[i].f[idx] == k)
				cnt++;
		}
		
	}
	if(cnt == 0)
		return 0.0;
	return 1.0*cnt/sum;
}

int main()
{ 
	char s[100];
	vector<int> titles;
	gets(s);
	string strLine(s);
	split(strLine, titles);
	gets(s);
    vector<Elem> data;
	Elem item;
	item.f.resize(3);
    while(cin >> item.f[0] >> item.f[1] >> item.f[2]) {
		data.push_back(item);
    }
	int i = 0;
	double prior1 = getPrior(data, 1);
	double prior2 = getPrior(data, 2);
	vector<double> posterior1_0(11,0.0);
	vector<double> posterior1_1(11,0.0);
	vector<double> posterior2_0(11,0.0);
	vector<double> posterior2_1(11,0.0);
	int k;
	for(k = 1; k <= 10; k++) {
		posterior1_0[k] = getPosterior(data, 0, k, 1);
		posterior1_1[k] = getPosterior(data, 1, k, 1);
		posterior2_0[k] = getPosterior(data, 0, k, 2);
		posterior2_1[k] = getPosterior(data, 1, k, 2);
	}
	for( i = 0; i < titles.size(); i++) {
		if(titles[i] == 1) {
			printf("%.3f\n",prior2);
		} else if(titles[i] == 2) {
			for(int j = 1; j <= 9; j++) {
				printf("%.3lf,",posterior2_0[j]);
			}
			double ans = 0.0;
			ans = posterior2_0[10];
			printf("%.3lf\n",ans);
		} else if(titles[i] == 3) {
			double ans = 0.0;
			ans = prior2 * posterior2_0[9] * posterior2_1[9];
			ans /= (prior1 * posterior1_0[9] * posterior1_1[9] + prior2 * posterior2_0[9] * posterior2_1[9]);
			printf("%.3lf\n",ans);
		}
	}
    return 0;
}