g*y
2 楼
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。
有什么好想法？
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。
有什么好想法？
A*0
3 楼
no-cost extension
【在 b********n 的大作中提到】
: 新手AP准备跳槽，现在有几个基金。有可能这个FY的钱不一定能在现在的学校用完，这
: 个需要怎么操作？谢谢！
【在 b********n 的大作中提到】
: 新手AP准备跳槽，现在有几个基金。有可能这个FY的钱不一定能在现在的学校用完，这
: 个需要怎么操作？谢谢！
s*y
4 楼
这是facebook的面试题吧。
https://www.facebook.com/careers/puzzles.php?puzzle_id=20
https://www.facebook.com/careers/puzzles.php?puzzle_id=20
x*1
5 楼
File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年半载应
该没问题。
BTW,你是已经有下一家了，还是正在找马阶段？
【在 b********n 的大作中提到】
: 新手AP准备跳槽，现在有几个基金。有可能这个FY的钱不一定能在现在的学校用完，这
: 个需要怎么操作？谢谢！
该没问题。
BTW,你是已经有下一家了，还是正在找马阶段？
【在 b********n 的大作中提到】
: 新手AP准备跳槽，现在有几个基金。有可能这个FY的钱不一定能在现在的学校用完，这
: 个需要怎么操作？谢谢！
a*m
6 楼
直接暴力应该code比较简单吧。就是太慢。o(2^n)
b*n
7 楼
已经有下家，NCE不是必须要在本学校把这个FY的钱用掉的吗？时间上看我估计没法用
完，可以转到新学校吗？
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年
半载应
: 该没问题。
: BTW,你是已经有下一家了，还是正在找马阶段？
【在 x**1 的大作中提到】
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年半载应
: 该没问题。
: BTW,你是已经有下一家了，还是正在找马阶段？
完，可以转到新学校吗？
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年
半载应
: 该没问题。
: BTW,你是已经有下一家了，还是正在找马阶段？
【在 x**1 的大作中提到】
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年半载应
: 该没问题。
: BTW,你是已经有下一家了，还是正在找马阶段？
g*y
8 楼
换了种结构，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 name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
}
}
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
}
return -1;
}
}
好点。
public class LiarLiar {
public int[] divide(String[] line) {
ArrayList
HashMap
int N = Integer.parseInt(line[0].trim());
for (int i=0, j=1; i
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
}
}
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
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
HashSet
set.add(name);
list.add(set);
return list.size() - 1;
}
private int find(ArrayList
for (int i=0; i
}
return -1;
}
}
A*0
9 楼
已经给的钱不容易转走，你可以搞个adjunct,在原来的学校用完。
【在 b********n 的大作中提到】
: 已经有下家，NCE不是必须要在本学校把这个FY的钱用掉的吗？时间上看我估计没法用
: 完，可以转到新学校吗？
:
:
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年
: 半载应
:
: 该没问题。
:
: BTW,你是已经有下一家了，还是正在找马阶段？
:
【在 b********n 的大作中提到】
: 已经有下家，NCE不是必须要在本学校把这个FY的钱用掉的吗？时间上看我估计没法用
: 完，可以转到新学校吗？
:
:
: File个no-cost extension，自己和领导签个字，sponsor一般会同意，延长一年
: 半载应
:
: 该没问题。
:
: BTW,你是已经有下一家了，还是正在找马阶段？
:
a*2
10 楼
你有提交成功吗？是不是server down掉了？
d*d
11 楼
这不就是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,
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
12 楼
re
【在 d*******d 的大作中提到】
: 这不就是facebook的puzzle么
:
: distinct
: members
: the
: is
【在 d*******d 的大作中提到】
: 这不就是facebook的puzzle么
:
: distinct
: members
: the
: is
i*e
13 楼
你提交上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
直觉是有可能过不了 bot 的 time limit...
随便乱猜的，很有可能我猜错 :)
如果用 bfs 应该效率会更好吧
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**********y 的大作中提到】
: 换了种结构，ListArray
: 好点。
: public class LiarLiar {
: public int[] divide(String[] line) {
: ArrayList
: HashMap
:
: int N = Integer.parseInt(line[0].trim());
: for (int i=0, j=1; i
d*d
14 楼
对，bfs
bot down 了个把月了。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
bot down 了个把月了。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
i*e
15 楼
你可以利用这个人写的 test case generator 来测试算法速度：
http://www.facebook.com/topic.php?uid=15325934266&topic=9670
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
http://www.facebook.com/topic.php?uid=15325934266&topic=9670
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
g*y
16 楼
我不知道这是facebook的puzzle, 在careercup看见了，就想写个简单易懂的版本，为
准备interview写，完全没考虑运行速度。
回头考虑一下速度。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
准备interview写，完全没考虑运行速度。
回头考虑一下速度。
【在 i**********e 的大作中提到】
: 你提交上facebook puzzle了吗？
: 直觉是有可能过不了 bot 的 time limit...
: 随便乱猜的，很有可能我猜错 :)
: 如果用 bfs 应该效率会更好吧
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
g*y
17 楼
再换了种结构，这个快一些，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 name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
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);
}
}
public class LiarLiar {
public int[] divide(String[] line) {
int N = Integer.parseInt(line[0].trim());
HashMap
for (int i=0, j=1; i
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
add(map, line[j].trim(), name);
}
}
HashSet
HashSet
ArrayList
q1.add(map.keySet().iterator().next());
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
if (!map.containsKey(s1)) {
map.put(s1, new HashSet
}
map.get(s1).add(s2);
}
}
相关阅读
工作机会拒绝offer， 需要赔偿吗？内部refer问题求Zynga refer给字符串，里边是几个单词中间没空格，输出所有可能的句子。收到F的口头offer, 【包子已发】 谢谢大家！今天可以follow up了吗？请教skype做teaching demo有人知道mulesoft company吗？刚才想了想大牛们选择加入三星很make senseT家电面一般有几轮？ [UPDATE面经]有谁了解LAB126公司搬家了，i797上的和DS160的不一致怎么办？？再回首，还是对linkedlist找cycle那题很疑惑fresh grad 去不是e-verify的公司是不是不靠谱？请问salesforce onsite总是过不了2小时内的码工onsite大家觉得明年H1B什么时候会用完呢贴个朋友的amazon面经看来在大公司工作一段时间还是很有必要的。。。