g**********y
发帖数: 14569 | 1 As a newbie on a particular internet discussion board, you notice a distinct
trend among its veteran members; everyone seems to be either unfailingly
honest or compulsively deceptive. You decide to try to identify the members
of the two groups, starting with the assumption that every senior member
either never lies or never tells the truth. You compile as much data as
possible, asking each person for a list of which people are liars. Since the
people you are asking have been around on the board for a long time, you
may assume that they have perfect knowledge of who is trustworthy and who is
not. Each person will respond with a list of people that they accuse of
being liars. Everyone on the board can see that you are a tremendous n00b,
so they will grudgingly give you only partial lists of who the liars are. Of
course these lists are not to be taken at face value because of all the
lying going on.
You must write a program to determine, given all the information you've
collected from the discussion board members, which members have the same
attitude toward telling the truth. It's a pretty popular discussion board,
so your program will need to be able to process a large amount of data
quickly and efficiently.
Input Specifications
Your program must take a single command line argument; the name of a file.
It must then open the file and read out the input data. The data begins with
the number of veteran members n followed by a newline. It continues with n
chunks of information, each defining the accusations made by a single member
. Each chunk is formatted as follows:
followed by m lines each containing the name of one member that the accuser
says is a liar. accuser name and m are separated by some number of tabs and
spaces. m will always be in [0, n]. All member names contain only alphabetic
characters and are unique and case-sensitive.
Example input file:
5
Stephen 1
Tommaso
Tommaso 1
Galileo
Isaac 1
Tommaso
Galileo 1
Tommaso
George 2
Isaac
Stephen
Output Specifications
Your output must consist of two numbers separated by a single space and
followed by a newline, printed to standard out. The first number is the size
of the larger group between the liars and the non-liars. The second number
is the size of the smaller group. You are guaranteed that exactly one
correct solution exists for all test data.
Example output:
3 2
解法很简单，就是画出有向图，用两种颜色标记。合并所有有向图，最后可以归并为两
个子集。返还两个子集大小就行。
问题是用什么数据结构来描述这个有向图，可以很方便地合并。
我用的是一个name->set的map, 另一个set->set的一一映射。结果code起来很messy。
有什么好想法？ | s*****y
发帖数: 897 | | a********m
发帖数: 15480 | 3 直接暴力应该code比较简单吧。就是太慢。o(2^n) | g**********y
发帖数: 14569 | 4 换了种结构，ListArray + HashMap, code还是ugly, 稍
好点。
public class LiarLiar {
public int[] divide(String[] line) {
ArrayList list = new ArrayList();
HashMap pairs = new HashMap();
int N = Integer.parseInt(line[0].trim());
for (int i=0, j=1; i
String[] s = line[j].split(" ");
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
merge(list, pairs, name, line[j].trim());
}
}
int i = 0;
while (list.get(i).size() == 0) i++;
int j = i+1;
while (list.get(j).size() == 0) j++;
int a = list.get(i).size();
int b = list.get(j).size();
return a>b? new int[]{a, b} : new int[]{b, a};
}
private void merge(ArrayList list, HashMap
pairs,
String name, String accused) {
int i = find(list, name);
if (i < 0) {
i = createSet(list, name);
}
int j = find(list, accused);
if (j < 0) {
j = createSet(list, accused);
}
int i2 = -1;
int j2 = -1;
if (pairs.containsKey(i)) {
j2 = pairs.get(i);
if (j2 != j) {
list.get(j).addAll(list.get(j2));
list.get(j2).clear();
}
}
if (pairs.containsKey(j)) {
i2 = pairs.get(j);
if (i2 != i) {
list.get(i).addAll(list.get(i2));
list.get(i2).clear();
}
}
pairs.put(i, j);
pairs.put(j, i);
}
private int createSet(ArrayList list, String name) {
HashSet set = new HashSet();
set.add(name);
list.add(set);
return list.size() - 1;
}
private int find(ArrayList list, String name) {
for (int i=0; i
if (list.get(i).contains(name)) return i;
}
return -1;
}
} | a**********2
发帖数: 340 | 5 你有提交成功吗？是不是server down掉了？ | d*******d
发帖数: 2050 | 6 这不就是facebook的puzzle么
distinct
members
the
is
【在 g**********y 的大作中提到】
: As a newbie on a particular internet discussion board, you notice a distinct
: trend among its veteran members; everyone seems to be either unfailingly
: honest or compulsively deceptive. You decide to try to identify the members
: of the two groups, starting with the assumption that every senior member
: either never lies or never tells the truth. You compile as much data as
: possible, asking each person for a list of which people are liars. Since the
: people you are asking have been around on the board for a long time, you
: may assume that they have perfect knowledge of who is trustworthy and who is
: not. Each person will respond with a list of people that they accuse of
: being liars. Everyone on the board can see that you are a tremendous n00b,
| v***n
发帖数: 5085 | 7 re
【在 d*******d 的大作中提到】
: 这不就是facebook的puzzle么
:
: distinct
: members
: the
: is
| i**********e
发帖数: 1145 | 8 你提交上facebook puzzle了吗？
直觉是有可能过不了 bot 的 time limit...
随便乱猜的，很有可能我猜错 :)
如果用 bfs 应该效率会更好吧
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**********y 的大作中提到】
: 换了种结构，ListArray + HashMap, code还是ugly, 稍
: 好点。
: public class LiarLiar {
: public int[] divide(String[] line) {
: ArrayList list = new ArrayList();
: HashMap pairs = new HashMap();
:
: int N = Integer.parseInt(line[0].trim());
: for (int i=0, j=1; i: String[] s = line[j].split(" ");
| d*******d
发帖数: 2050 | 9 对，bfs
bot down 了个把月了。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | | g**********y
发帖数: 14569 | 11 我不知道这是facebook的puzzle, 在careercup看见了，就想写个简单易懂的版本，为
准备interview写，完全没考虑运行速度。
回头考虑一下速度。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| g**********y
发帖数: 14569 | 12 再换了种结构，这个快一些，100000人，每个人accuse 1~3个，1.3秒左右算出来。
public class LiarLiar {
public int[] divide(String[] line) {
int N = Integer.parseInt(line[0].trim());
HashMap map = new HashMap();
for (int i=0, j=1; i
String[] s = line[j].split(" ");
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
add(map, name, line[j].trim());
add(map, line[j].trim(), name);
}
}
HashSet a = new HashSet();
HashSet b = new HashSet();
ArrayList q1 = new ArrayList();
q1.add(map.keySet().iterator().next());
ArrayList q2 = new ArrayList();
while (!q1.isEmpty()) {
for (String s : q1) {
if (!a.contains(s)) {
a.add(s);
q2.addAll(map.get(s));
}
}
q1.clear();
for (String s : q2) {
if (!b.contains(s)) {
b.add(s);
q1.addAll(map.get(s));
}
}
q2.clear();
}
return a.size()>b.size()? new int[]{a.size(), b.size()} : new int[]{b.size(), a.size()};
}
private void add(HashMap map, String s1, String s2) {
if (!map.containsKey(s1)) {
map.put(s1, new HashSet());
}
map.get(s1).add(s2);
}
} |
|
