r*******g
发帖数: 1335 | 1 直接从guangyi的总结里面的一个链接找的，但是链接没有答案，谢谢了
10. F(a, b) -> true or false means that person a knows person b. But it’
s not commutative, because person a can know person b, but b may not know a.
Say, you throw a party, you knows a number of people, invite them, then each
of them knows a bunch of people (those sets of people can intersect), so on
and so forth.
Now there is a celebrity comes in, everyone in the party knows him, but he
knows no one.
Write an algorithm effectively find out who the celebrity is.
这个题不是tree，不知道怎么找比较快。
13. Master mind guess.
Say a random 6-digit number is generated and hidden secretly.
Then there is a function: int Tell(int n); where the n is any 6-digit number
, and the function Tell returns how many of the digits are correct and in
the right position.
For example, if the secret is “123456”, and Tell(“523499”) -> 3
Now write an algorithm such that you can call Tell to figure out what is the
secret number efficiently.
这个题难道就是对每次变动每一位？这样岂不是开销比较大。
34. string/pattern matching. pattern can contain a-z and special chars
like "." and "*"
"." means matching any single char
"*" means matching zero or more chars of any kind.
string can contain a-z and "." "*". Note "." and "*" in string are just
regular chars, no special meanings.
这道题好像google出了很多次了，就是基于这样的字符怎么做匹配，谁能帮我考考古，
貌似这个版讨论过的。
谢谢了。 | l*****a
发帖数: 14598 | 2 pick up a,b, if a know b ,then a is not the celebrity
eachtime u can remove one from those people.
when there is only one,check whether he know no one and everyone know him
O(n)
a.
each
on
【在 r*******g 的大作中提到】
: 直接从guangyi的总结里面的一个链接找的，但是链接没有答案，谢谢了
: 10. F(a, b) -> true or false means that person a knows person b. But it’
: s not commutative, because person a can know person b, but b may not know a.
: Say, you throw a party, you knows a number of people, invite them, then each
: of them knows a bunch of people (those sets of people can intersect), so on
: and so forth.
: Now there is a celebrity comes in, everyone in the party knows him, but he
: knows no one.
: Write an algorithm effectively find out who the celebrity is.
: 这个题不是tree，不知道怎么找比较快。
| g*****i
发帖数: 2162 | 3 第一题是celebrity问题,面经了出现过几次了,楼上的就是标准解法.
第二题google下wiki有解释算法,当时我没仔细看.
第三题你google下wildcard match就可以了,递归写法很容易,网上有非递归写法,我没
记住. | l*****a
发帖数: 14598 | 4 我的做法是根据输入pattern生成一个状态转换表
比方说 a*b
initial state s[0],
f(s[0],a)=s[1]
f(s[1],a...)=s[1]
f(s[1],b)=s[2]
then just judge whether your input can go from s[0] to s[2]
use can use matrix or map to store the 状态转换表
a.
each
on
【在 r*******g 的大作中提到】
: 直接从guangyi的总结里面的一个链接找的，但是链接没有答案，谢谢了
: 10. F(a, b) -> true or false means that person a knows person b. But it’
: s not commutative, because person a can know person b, but b may not know a.
: Say, you throw a party, you knows a number of people, invite them, then each
: of them knows a bunch of people (those sets of people can intersect), so on
: and so forth.
: Now there is a celebrity comes in, everyone in the party knows him, but he
: knows no one.
: Write an algorithm effectively find out who the celebrity is.
: 这个题不是tree，不知道怎么找比较快。
| r*******g
发帖数: 1335 | 5 这个题确实和前面一道题思路一样，O(N)就行了，谢谢了
【在 l*****a 的大作中提到】
: pick up a,b, if a know b ,then a is not the celebrity
: eachtime u can remove one from those people.
: when there is only one,check whether he know no one and everyone know him
: O(n)
:
: a.
: each
: on
| r*******g
发帖数: 1335 | 6 找到第三题了，thanks
第二题貌似还要两个版本，一个版本是说位置不同就不count，一个版本说位置不同只
要重复出现了就count。
【在 g*****i 的大作中提到】
: 第一题是celebrity问题,面经了出现过几次了,楼上的就是标准解法.
: 第二题google下wiki有解释算法,当时我没仔细看.
: 第三题你google下wildcard match就可以了,递归写法很容易,网上有非递归写法,我没
: 记住.
| f*******t
发帖数: 7549 | 7 小时候都在文曲星上玩过猜数字游戏吧，就是给出一个随机的4位数，你输入一个数，
程序会告诉你哪些完全正确，哪些数字虽然出现了但位置不对。。。
虽然都会玩，但要给个算法还是一时想不出来
【在 r*******g 的大作中提到】
: 找到第三题了，thanks
: 第二题貌似还要两个版本，一个版本是说位置不同就不count，一个版本说位置不同只
: 要重复出现了就count。
| d*******u
发帖数: 186 | 8 Directed graph.
find a node without egress edge, but has all the ingress edge from
all the other nodes.
【在 l*****a 的大作中提到】
: pick up a,b, if a know b ,then a is not the celebrity
: eachtime u can remove one from those people.
: when there is only one,check whether he know no one and everyone know him
: O(n)
:
: a.
: each
: on
| d*******u
发帖数: 186 | 9 Directed graph.
find a node without egress edge, but has all the ingress edge from
all the other nodes.
【在 l*****a 的大作中提到】
: pick up a,b, if a know b ,then a is not the celebrity
: eachtime u can remove one from those people.
: when there is only one,check whether he know no one and everyone know him
: O(n)
:
: a.
: each
: on
| d*******u
发帖数: 186 | 10 Directed graph.
find a node without egress edge, but has all the ingress edge from
all the other nodes.
【在 l*****a 的大作中提到】
: pick up a,b, if a know b ,then a is not the celebrity
: eachtime u can remove one from those people.
: when there is only one,check whether he know no one and everyone know him
: O(n)
:
: a.
: each
: on
|
|
