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);
}
}
相关阅读
从红衣女再说说为什么害怕猪队友亲爱的你要幸福一个台湾企业都知道的事实，只有新雇员不知道因为老板和同事脾气不好就辞职，太幼稚问个狗家股票问题Re: 九章算法团购？能同时再做一份远程full time 工吗？累的时候该继续工作还是放松一下？G家做产品的组面试通过跟刷题无关，只看外表气质和谈吐诸君，赚到几个m的cash就退休？3.1 onsite，现在还没有消息职场最大的不公平就是薪酬倒挂，让人火大linkedin team match要多久收了offer 又不去怎样止损？小时候在《故事会》上看到一个故事，至今没想通 (转载)Google 的 HR 可以透露面试feedback的细节吗？现在公司女同事比赛看谁能钓到富二代男同事没人讨论uber退出东南亚？一年的哪个时候加入谷歌比较好？