MapReduce--8--求互为好友的好友对
MapReduce面试题2--求互为好友的好友对1、数据格式A:B,C,D,F,E,OB:A,C,E,KC:F,A,D,ID:A,E,F,LE:B,C,D,M,LF:A,B,C,D,E,O,MG:A,C,D,E,FH:A,C,D,E,OI:A,OJ:B,OK:A,C,DL:D,E,FM:E,F,GO:A,H,I,J,K数据的格式以“:”分割成两部分,前面是用户,后
·
MapReduce面试题2--求互为好友的好友对
1、数据格式
现在有一份如下这种格式的数据:
A:B,C,D,F,E,O
B:A,C,E,K
C:F,A,D,I
D:A,E,F,L
E:B,C,D,M,L
F:A,B,C,D,E,O,M
G:A,C,D,E,F
H:A,C,D,E,O
I:A,O
J:B,O
K:A,C,D
L:D,E,F
M:E,F,G
O:A,H,I,J,K
数据的格式以“:”分割成两部分,前面是用户,后面是该用户的好友,以
A:B,C,D,F,E,O
为例:B,C,D,E,F,O是用户A的好友
2、题目:求互为好友的好友对
以以下数据为例:
A:B,C,D,F,E,O
B:A,C,E,K
从以上数据可以得出:第一行中,B用户是A用户的好友, 第二行中,A用户是B用户的好友。所以A用户和B用户是互为好友的好友对
请求出以上数据中的所有互为好友的好友对
3、解题思路
根据题目的要求,最后得出的结果一定是类似于以下格式的数据:
A-B
A-C
...
观察结果数据,能够得出一个清晰的结论:
如果答案中,出现
A-B
这种结果,那么一定表示:
A是B的好友,同时, B也是A的好友。 这样才能得出A-B这样的结果。
如果结果中没有A-E这样的结果,那必定表示,要么只存在两种情况之一:要么E不是A的好友,要么A不是E的好友
所以如果把类似的这种
A-B
B-A
数据给整理下,比如调整这两个用户ID的顺序,就能得出来
A-B
A-B
这样的数据,这样就会导致有2个
A-B
如果结果中没有
A-E
则证明:不可能同时存在
A-E
和
E-A
要不然,经过用户ID的倒转,就会出现2个
A-E
所以,题目的解题思路就出来了。在mapper阶段写出key-value的时候以“用户-好友”为key,不过输出的时候,都要把key中的连个用户ID按照字典顺序排序,始终把字母小的用户ID放置在前面即可。最后根据每次reduce方法中的values集合的大小是否是2就可以输出结果了。
4、具体代码实现
package com.ghgj.mazh.mapreduce.exercise.fans;
import java.io.IOException;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.NullWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
/**
* 作者: 马中华:http://blog.csdn.net/zhongqi2513
* 日期: 2017年8月6日下午3:42:57
*
* 描述:求互为好友的好友对
*/
public class FansMR {
public static void main(String[] args) throws Exception {
// 指定hdfs相关的参数
Configuration conf = new Configuration();
// conf.set("fs.defaultFS", "hdfs://hadoop02:9000");
// System.setProperty("HADOOP_USER_NAME", "hadoop");
Job job = Job.getInstance(conf);
// 设置jar包所在路径
job.setJarByClass(FansMR.class);
// 指定mapper类和reducer类
job.setMapperClass(FansMRMapper.class);
job.setReducerClass(FansMRReducer.class);
// 指定maptask的输出类型
job.setMapOutputKeyClass(Text.class);
job.setMapOutputValueClass(Text.class);
// 指定reducetask的输出类型
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(NullWritable.class);
// 指定该mapreduce程序数据的输入和输出路径
Path inputPath = new Path("D:\\bigdata\\commonfriends\\input");
Path outputPath = new Path("D:\\bigdata\\commonfriends\\hufen_output");
FileSystem fs = FileSystem.get(conf);
if (fs.exists(outputPath)) {
fs.delete(outputPath, true);
}
FileInputFormat.setInputPaths(job, inputPath);
FileOutputFormat.setOutputPath(job, outputPath);
// 最后提交任务
boolean waitForCompletion = job.waitForCompletion(true);
System.exit(waitForCompletion ? 0 : 1);
}
private static class FansMRMapper extends Mapper<LongWritable, Text, Text, Text> {
@Override
protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
String line = value.toString();
String[] tokens = line.split(":");
String person = tokens[0];
String[] fens = tokens[1].split(",");
/**
* 写出的数据格式:
* AB ---> A
* AB ---> B
* 如果AB是互粉对,那么必然 AB 所对应的的 values组合会有两个值,也就是必定会有 A 和 B
*/
for (String fen : fens) {
context.write(new Text(combineStr(person, fen)), new Text(person));
}
}
/**
* 此方法的作用就是把 AB 和 BA 的组合 都编程 AB
*/
private String combineStr(String a, String b) {
if (a.compareTo(b) > 0) {
return b +"-"+ a;
} else {
return a +"-"+ b;
}
}
}
private static class FansMRReducer extends Reducer<Text, Text, Text, NullWritable> {
@Override
protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
int sum = 0;
for (Text t : values) {
sum++;
}
if (sum == 2) {
context.write(key, NullWritable.get());
}
}
}
}
5、结果
最后请看结果数据:
A-B
A-C
A-D
A-F
A-O
B-E
C-F
D-E
D-F
D-L
E-L
E-M
F-M
H-O
I-O
J-O
至此,大功告成。。。 ヾ(◍°∇°◍)ノ゙
更多推荐
已为社区贡献7条内容
所有评论(0)