异度部落格

学习是一种生活态度。

0%

Posted on In

OS: Ubuntu 12.04   Hadoop: Hadoop 1.0.4

1.安装集群所需软件

1
2
sudo apt-get install install ssh
sudo apt-get install rsync

配置ssh免密码登录

1
2
ssh-keygen -t dsa -P '' -f ~/.ssh/id_dsa
cat ~/.ssh/id_dsa.pub >>~/.ssh/authorized_keys

验证是否成功

1
ssh localhost

2.安装JDK

安装部分就不重复了，主要说明下环境变量的添加

1
sudo vi /etc/profile

将下面三句话添加到最后

1
2
3
export JAVA_HOME=/usr/lib/jvm/java-6-openjdk
export PATH=$JAVA_HOME/bin:$PATH
export CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar

3.安装Hadoop

下载地址：http://apache.etoak.com/hadoop/common/ 建议选择：1.0.x版本的tar文件，不建议使用deb或者rpm的包，因为后面回带来很复杂的程序权限问题。 修改配置文件，指定JDk安装路径

1
vi conf/hadoop-env.sh
1
export JAVA_HOME=/usr/lib/jvm/java-6-openjdk

修改Hadoop核心配置文件core-site.xml，这里配置的是HDFS的地址和端口号

1
vi conf/core-site.xml
1
2
3
4
5
6
7
8
9
10
<pre class="brush: xml; gutter: true; first-line: 1"><configuration>
     <property>
         <name>fs.default.name</name>
         <value>hdfs://localhost:9000</value>
     </property>
<property>
    <name>hadoop.tmp.dir</name>
    <value>/home/killua/Application/tmp/hadoop-${user.name}</value>
  </property>
</configuration>

修改Hadoop中HDFS的配置，配置的备份方式默认为3，因为安装的是单机版，所以需要改为1 vi conf/hdfs-site.xml

1
2
3
4
5
6
<configuration>
     <property>
         <name>dfs.replication</name>
         <value>1</value>
     </property>
</configuration>

修改Hadoop中MapReduce的配置文件，配置的是JobTracker的地址和端口

1
vi conf/mapred-site.xml
1
2
3
4
5
6
<configuration>
	<property>
		<name>mapred.job.tracker</name>
		<value>localhost:9001</value>
	</property>
  </configuration>

启动Hadoop，在启动之前，需要格式化Hadoop的文件系统HDFS

1
2
bin/hadoop namenode -format
然后启动Hadoop所有服务，输入命令

bin/start-all.sh

1
2
3
4
**4.验证是否安装成功**
打开浏览器，分别输入一下网址：
http://localhost:50030 (MapReduce的Web页面)
http://localhost:50070 (HDfS的web页面)

Posted on In

ICTCLAS（Institute of Computing Technology,Chinese Lexical Analysis System），由中国科学院计算技术研究开发，功能包括中文分词；词性标注；命名实体识别；新词识别；同时支持用户词典；支持繁体中文；支持 gb2312、GBK、UTF8 等多种编码格式，是世界上最好的汉语词法分析器之一。 下载地址：http://ictclas.org/ictclas_download.aspx

原系统只提供了 C++和 Java 版本，为了方便广大 Pythoner，决定用 python 对其进行重新封装。目前仅支持 Linux，Windows 版本开发中。 pyictclas 模块中包含三个类：一个 PyICTCLAS 类，用于分词工具的调用;一个是 CodeType?类，用于存放各种编码的枚举类型;一个是 POSMap 类用于存放标注集枚举类型。

项目主页：http://code.google.com/p/python-ictclas/

该项目废除，新项目参考：http://www.yidooo.net/archives/nlpir-python-version.html

Posted on In

【试题描述】写一个函数，求两个整数的和，要求在函数体内不得使用加减乘除四则运算符合。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int add(int num1, int num2) {

	int sum;
	int carry;
	do {
		sum = num1 ^ num2;
		carry = (num1 & num2) << 1;

		num1 = sum;
		num2 = carry;
	} while(num2 != 0);

	return num1;
}

Posted on In

【试题描述】我们把只包含因子2、3和5的数称作丑数。求按从到大的顺序的第1500个丑数。例如6,8是丑数，而14不是，因为它包含因子7.习惯上把1当作第一个丑数。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int Min(int a, int b, int c) {

	return (a < b ? a : b) < c ? (a < b ? a : b) : c;
}

int uglyNumber(int n) {

	if(n <= 0) {
		throw ("Invalid Input.");
	}

	long* uglyNum = new long[n];
	uglyNum[0] = 1;

	int index2 = 0;
	int index3 = 0;
	int index5 = 0;
	int indexLast = 0;

	while(indexLast < n) {
		int min = Min(uglyNum[index2] * 2, uglyNum[index3] * 3, uglyNum[index5] * 5);
		uglyNum[++indexLast] = min;

		while(uglyNum[index2] * 2 <= uglyNum[indexLast]) {
			index2++;
		}

		while(uglyNum[index3] * 3 <= uglyNum[indexLast]) {
			index3++;
		}

		while(uglyNum[index5] * 5 <= uglyNum[indexLast]) {
			index5++;
		}
	}

	return uglyNum[n - 1];

}

Posted on In

【试题描述】输入一个二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成的一条路径。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void findPath(BinaryTreeNode* rootNode, int expectSum,
		vector<int>& path, int curSum) {

	if(rootNode == NULL) {
		return ;
	}

	path.push_back(rootNode->value);
	curSum += rootNode->value;

	if(rootNode->left == NULL && rootNode->right == NULL
			&& curSum == expectSum) {
		cout << "Find a path: ";
		for(vector<int>::iterator iter = path.begin(); iter != path.end(); iter++) {
			cout << *iter << " ";
		}
		cout << endl;
	}

	if(rootNode->left != NULL) {
		findPath(rootNode->left, expectSum, path, curSum);
	}

	if(rootNode->right != NULL) {
		findPath(rootNode->right, expectSum, path, curSum);
	}

	path.pop_back();
	curSum -= rootNode->value;
}

void findPaths(BinaryTreeNode* rootNode, int expectSum) {

	vector<int> path;
	findPath(rootNode, expectSum, path, 0);
}

Posted on In

【试题描述】输入一棵二叉树的根结点，求该树的深度。从根结点到叶子结点依次经过的结点（含根、叶子节点）形成树的一条路径，最长路径的长度为树的深度。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
int treeDepth(BinaryTreeNode* rootNode) {

	if(rootNode == NULL) {
		return 0;
	}

	int leftSubTreeDepth = treeDepth(rootNode->left);
	int rightSubTreeDepth = treeDepth(rootNode->right);

	return leftSubTreeDepth > rightSubTreeDepth ? (leftSubTreeDepth + 1) : (rightSubTreeDepth + 1);
}

Posted on In

【试题描述】输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出a，b，c所能排列出来的所有字符串abc，acb，bac，bca，cab，cba。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

void permutation(char* str, int begin) {

	if(begin == strlen(str)) {
		cout << str << endl;
	} else {
		for(int i = begin; i < strlen(str); ++i) {
			char tmp = str[i];
			str[i] = str[begin];
			str[begin] = tmp;

			permutation(str, begin + 1);

			tmp = str[i];
			str[i] = str[begin];
			str[begin] = tmp;
		}
	}
}

void permutation(char* str) {
	if(str == NULL) {
		return ;
	}

	permutation(str, 0);
}

int main() {
	char str[] = "abc";
	//char* str = "abc"; //Runtime Error
	permutation(const_cast<char*>(str));
	return 0;
}

Posted on In

【试题描述】统计一个数字在排序数组中出现的次数。例如输入的排序数组{1, 2, 3, 3, 3, 3, 4, 5}

和数字3,由于3在这个数组中出现了4次，因此输出4。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int GetFirstK(int array[], int length, int start, int end, int k) {

	if(start > end) {
		return -1;   //No Found
	}

	int middle = (start + end) / 2;
	if(array[middle] == k) {

		if((middle > 0 && array[middle - 1] != k)
				|| middle == 0) {
			return middle;
		} else {
			end = middle - 1;
		}
	} else if(array[middle] < k) {
		start = middle + 1;
	} else {
		end = middle - 1;
	}

	return GetFirstK(array, length, start, end, k);
}

int GetLastK(int array[], int length, int start, int end, int k) {

	if(start > end) {
		return -1;   //No Found
	}

	int middle = (start + end) / 2;
	if(array[middle] == k) {

		if((middle < length - 1 && array[middle + 1] != k)
				|| middle == length - 1) {
			return middle;
		} else {
			start = middle + 1;
		}
	} else if(array[middle] < k) {
		start = middle + 1;
	} else {
		end = middle - 1;
	}

	return GetLastK(array, length, start, end, k);
}

int GetNumOfK(int array[], int length, int k) {

	if(array == NULL || length <= 0) {
		throw ("Invalid input.");
	}

	int first = GetFirstK(array, length, 0 , length - 1, k);
	int last = GetLastK(array, length, 0 , length - 1, k);

	if(first > -1 && last > -1) {
		return last - first + 1;
	}

	return -1;
}

Posted on In

【试题描述】数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

【试题来源】未知

【试题分析】时间复杂度O(n),空间复杂度O(1)

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findMoreThanHalf(int array[], int n) {

	if(array == NULL || n <= 0) {
		throw ("Invalid input.");
	}

	int num = array[0];
	int times = 1;

	for(int i = 1; i < n; i++) {
		if(array[i] == num) {
			++times;
		} else {
			--times;
			if(times == 0) {
				num = array[i];
				times = 1;
			}
		}
	}

	return num;
}

Posted on In

【试题描述】输入n个整数，找出其中最小的k个数。

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void leastKNum(int array[], int n, int k) {

	if(array == NULL || n < k || n <= 0) {
		throw ("Invalid input.");
	}

	priority_queue<int> heap;  //大顶堆

	for(int i = 0; i < n; i++) {

		if(i < k) {
			heap.push(array[i]);
		} else {
			if(array[i] < heap.top()) {
				heap.pop();
				heap.push(array[i]);
			}
		}
	}

	//Print the reslut
	while(!heap.empty()) {
		cout << heap.top() << " ";
		heap.pop();
	}
	cout << endl;
}

最大K个数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void topKNum(int array[], int n, int k) {

	if(array == NULL || n < k || n <= 0) {
		throw ("Invalid input.");
	}

	priority_queue< int, vector<int>, greater<int> > heap;  //小顶堆

	for(int i = 0; i < n; i++) {

		if(i < k) {
			heap.push(array[i]);
		} else {
			if(array[i] > heap.top()) {
				heap.pop();
				heap.push(array[i]);
			}
		}
	}

	//Print the reslut
	while(!heap.empty()) {
		cout << heap.top() << " ";
		heap.pop();
	}
	cout << endl;
}