logo
Redian新闻
>未名空间
>pets - 心有所宠
>
猫咪可真记仇
avatar
猫咪可真记仇# pets - 心有所宠
f*m
1 楼
从版上大牛的面经中找到的：
---------------
1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
边）不是等假的吧？
-------------
2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
（这个在他提示下搞出的，code 用递归就几行而已）
考虑inorder 的succeesor。用inorder traverse，大家看对不对？
void inorder(node* n, node*& prev)
{
if (!n)
return;
inorder(n->left, prev);
if (!pre)
pre->succeesor = n;
pre = n;
inorder(n->right, pre);
}

------------
3） 给一个BST 和一个 int value， 找出和这个value 值最接近的node(老题分分钟搞
定）
-------
inorder traverse，对每个节点计算difference的绝对值，如果心的绝对值大于上一次
计算的，则输出inorder traverse的上一个节点值？
------------
4）二个人轮流打枪的问题算概率， 就是6发装弹夹里面有一颗子弹。然后轮流对照自
己头打，然后在shuffle 对方接着打。 这题没听清就开始做，导致浪费好些世间， 这
个教训大家千万记住了。
不了解这题啥意思？
------------
5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
int 然后turn on 里面3个bits
建立一个14*4的矩阵，把输入的排放在矩阵对应的位置，然后扫描每行、每列看能否组
成花顺， 顺子， 和同花。还有跟好的方法吗？
------------
6） 一个billion of urls, 然后让你输出最长的相同的prefix，包含这个prefix url
必须 占75% 以上。
把urls排序，然后放在，比如，100个盘上。既然必须占75%，中间的那个盘上的最长
prefix一定包括最后的那个最长的prefix。所以先算中间盘上的最长prefix，然后向两
边的盘搜索，同时根据情况缩小prfefix的长度，直到处理好75%的盘。对吗？
avatar
m*a
2 楼
谢谢谢谢
avatar
p*k
3 楼
昨天听我妈说我外婆在家住了俩月，D猫每天一见我外婆起床，就跳到沙发上有太阳晒
的地方把地儿占了，不给我外婆坐，前天我外婆一走，D猫就到我外婆床上便便宣布占
领。其实我外婆现在年纪大了，又无聊，对D猫还不错，经常还和颜悦色的和D猫说说话
，就是当年非典的时候，老是叫我妈把D猫送掉，从此和D猫结下梁子，如今都快十年了
，D猫还嫉恨着。
avatar
b*g
4 楼
第二题怎么用递归做？
BST tree 要求给每个node添加一个succeesor的指针。

了。

【在 f*********m 的大作中提到】
: 从版上大牛的面经中找到的：
: ---------------
: 1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
: 求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
: ，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
: 从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
: 边）不是等假的吧？
: -------------
: 2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
: （这个在他提示下搞出的，code 用递归就几行而已）
avatar
V*A
5 楼
可以
avatar
g*x
6 楼
赫赫，谁说猫记心不好，都记着呢。
avatar
r*h
7 楼
5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
int 然后turn on 里面3个bits建立一个14*4的矩阵，把输入的排放在矩阵对应的位置
，然后扫描每行、每列看能否组成花顺， 顺子， 和同花。还有跟好的方法吗？
刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了
avatar
p*k
8 楼
据说猫其实记忆力超好，只是会选择“重要的”东西才记下来

【在 g****x 的大作中提到】
: 赫赫，谁说猫记心不好，都记着呢。
avatar
b*7
9 楼
1)canJump
从右往左是经典dp，
f(i)表示第i+1个点跳到底n个点最小步骤
f(i) = min{1 + f(i+k)}, k = 1... A[i]
2）BST 加successor
void add_successor(TreeNode * root)
{
if(root == NULL) return NULL;
TreeNode * pre = NULL;
stack s;
for(TreeNode * p = root; p != NULL; p= p->left)
s.push(p);
while(!s.empty())
{
TreeNode * cur = s.top();
s.pop();
if(pre != NULL) pre->successor = cur;
pre = cur;
for(TreeNode * p = cur->right; p != NULL; p=p->left)
s.push(p);
}
pre->successor = NULL;
}
3）BST找最接近value的值
如果用inorder遍历，则是O（n）的时间复杂度
应该用两次binary search，分别找左边界（小于等于value，但最大的值）和右边界
（大于等于value但最小的值），比较这两个值的与value的差值取最小的
TreeNode * lower_bound(TreeNode * root, int value)
{
TreeNode * r = NULL;
while(root != NULL)
{
if(root->val <= value)
{
r = root;
root = root->right;
}
else
root = root->left;
}
return r;
}
TreeNode * upper_bound(TreeNode * root, int value)
{
TreeNode * r = NULL;
while(root != NULL)
{
if(root->val <= value)
root = root->right;
else
{
r = root;
root = root->left;
}
}
return r;
}
int nearestvalue(TreeNode * root, int value)
{
if(root == NULL) throw runtime_error("root is null");
TreeNode * left = lower_bound(root,value);
TreeNode * right = upper_bound(root,value);
if(left == NULL) return right->val;
if(right == NULL) return left->val;
return abs(left->val - value) < abs(right->val - value) ? left->val :
right->val;
}
avatar
b*s
10 楼
D猫能听懂你外婆说要送走他的话？！
我妈很久前也说过叫我把猫送走的话（现在不了），她来了得叫她别在猫跟前说嫌弃猫
的话，呵呵

【在 p******k 的大作中提到】
: 昨天听我妈说我外婆在家住了俩月，D猫每天一见我外婆起床，就跳到沙发上有太阳晒
: 的地方把地儿占了，不给我外婆坐，前天我外婆一走，D猫就到我外婆床上便便宣布占
: 领。其实我外婆现在年纪大了，又无聊，对D猫还不错，经常还和颜悦色的和D猫说说话
: ，就是当年非典的时候，老是叫我妈把D猫送掉，从此和D猫结下梁子，如今都快十年了
: ，D猫还嫉恨着。
avatar
b*7
11 楼
4）
设两人概率分别为p1,1-p1
则p1 = 1/6 + 5/6 * (1-p1) ==> p1 = 6/11, 1-p1 = 5/11
5)
判断顺子：将7张牌按数字排序，然后遍历找是否有连续的5个数字
判断同花：将7张牌按花色排序，然后找是否有连续的5个花色
判断同花顺：将同花中的最多连续的花色按数字排序，找连续5个数字
6)
构建trie，trie节点中加一个计数变量，统计多少个url包含该trie节点，然后按层遍
历+减枝找到最长的prefix
struct TrieNode{
char c;
vector childs;
int count;
};
avatar
p*k
12 楼
我觉猫能听懂的话比狗多

【在 b******s 的大作中提到】
: D猫能听懂你外婆说要送走他的话？！
: 我妈很久前也说过叫我把猫送走的话（现在不了），她来了得叫她别在猫跟前说嫌弃猫
: 的话，呵呵
avatar
q*s
13 楼
题目说有1billion个url。这个trie得多大啊，memory 能放下么？

【在 b******7 的大作中提到】
: 4）
: 设两人概率分别为p1,1-p1
: 则p1 = 1/6 + 5/6 * (1-p1) ==> p1 = 6/11, 1-p1 = 5/11
: 5)
: 判断顺子：将7张牌按数字排序，然后遍历找是否有连续的5个数字
: 判断同花：将7张牌按花色排序，然后找是否有连续的5个花色
: 判断同花顺：将同花中的最多连续的花色按数字排序，找连续5个数字
: 6)
: 构建trie，trie节点中加一个计数变量，统计多少个url包含该trie节点，然后按层遍
: 历+减枝找到最长的prefix
avatar
b*s
14 楼
猫也分不同性格，有些猫不记仇，被教训完后很快就和你亲亲热热

【在 p******k 的大作中提到】
: 我觉猫能听懂的话比狗多
avatar
q*s
15 楼

这题能解释一下么？

【在 b******7 的大作中提到】
: 4）
: 设两人概率分别为p1,1-p1
: 则p1 = 1/6 + 5/6 * (1-p1) ==> p1 = 6/11, 1-p1 = 5/11
: 5)
: 判断顺子：将7张牌按数字排序，然后遍历找是否有连续的5个数字
: 判断同花：将7张牌按花色排序，然后找是否有连续的5个花色
: 判断同花顺：将同花中的最多连续的花色按数字排序，找连续5个数字
: 6)
: 构建trie，trie节点中加一个计数变量，统计多少个url包含该trie节点，然后按层遍
: 历+减枝找到最长的prefix
avatar
H*g
16 楼
个性不同啊～～～～
avatar
b*7
17 楼
多个字符串求comon prefix时trie是常规思路。
trie假设只考虑a~z，则是26叉树，大部分叶子节点为空，树最大高度为url的最大长度
。trie树节点的个数远小于url的个数，
就算超内存了，也可以按照B+树思想，将超出部分放外存
如果有更好的思路，不烦说出来参考下

【在 q***s 的大作中提到】
: 题目说有1billion个url。这个trie得多大啊，memory 能放下么？
avatar
b*a
18 楼
我家那个就是。每次尿在counter上我都按着拍脑门，隔一会一样屁颠屁颠跑过来求挠
挠。

【在 b******s 的大作中提到】
: 猫也分不同性格，有些猫不记仇，被教训完后很快就和你亲亲热热
avatar
b*7
19 楼
设A、B两人概率为Pa,Pb
则A获胜有两种可能：
1.A第一次就kill了B，概率为1/6
2.A第一次没有kill掉B（5/6的概率），但接下来的轮到B先开始的回合里，B没有获胜(
1-Pa的概率)，总概率为5/6*(1-Pa)
Pa = 1/6 + 5/6 * (1- Pa)

【在 q***s 的大作中提到】
:
: 这题能解释一下么？
avatar
p*k
20 楼
被教训和被逐出家门还是不一样的

【在 b******s 的大作中提到】
: 猫也分不同性格，有些猫不记仇，被教训完后很快就和你亲亲热热
avatar
c*7
21 楼
有parent指针

【在 b****g 的大作中提到】
: 第二题怎么用递归做？
: BST tree 要求给每个node添加一个succeesor的指针。
:
: 了。
avatar
b*s
22 楼
D猫是怎么领会到外婆说的话的严重性呢？动物真的很牛

【在 p******k 的大作中提到】
: 被教训和被逐出家门还是不一样的
avatar
g*o
23 楼
我对这题目理解不一样
手枪一共六发子弹，开枪时要是没子弹，弹匣走一格，并不是再次随机分布
也就是打完5枪要是都没子弹，子弹必然在第六格里了
这样第一枪死人的概率p1=1/6
第二枪死人的概率p2=5/6*1/5=1/6
p3=(1-1/6-1/6)*1/4
p4=(1-p1-p2-p3)/3
p5=p6=(1-p1-p2-p3-p4)/2
Pa=p2+p4+p6;
pb=p1+p3+p5
这样解对吗？

胜(

【在 b******7 的大作中提到】
: 设A、B两人概率为Pa,Pb
: 则A获胜有两种可能：
: 1.A第一次就kill了B，概率为1/6
: 2.A第一次没有kill掉B（5/6的概率），但接下来的轮到B先开始的回合里，B没有获胜(
: 1-Pa的概率)，总概率为5/6*(1-Pa)
: Pa = 1/6 + 5/6 * (1- Pa)
avatar
h*n
24 楼
原来真的能听懂啊～
avatar
r*n
25 楼
about 6): Trie approach will definitely work. But using random sampling can
be simpler.
call a url a target iff it is of the format: prefix (as desired) + junk. By
a random drawing, we have 0.75 odd to get a target.
1. randomly choose n url from the 1 billion urls. The prob. that the chosen
ones are all targets is 1-(1-0.75)^n = 1-2^{-2n}
2. looks like n=10 is enough to grantee that all we drew are targets
3. use one index, call idx, pointing at the beginning of these urls, compare
url[0][idx],...url[9][idx]. If all of them agrees, ++idx; otherwise, return
idx since we already found the prefix
4. some one may question this method: will we also (falsely) accept chars in
the junk as parts of the prefix? Unlikely! By assuming each of the 26 chars
happens independently and uniformly in junk of each urls, the false
positive is 26^{-10} (all url[0][idx],...url[9][idx] equals) that is almost
impossible...
avatar
p*k
26 楼
不知道，我内心里觉得跟我老跟他们说话有关系，小咪也能听懂好多话，没那么贼就是了
另外也可能只是觉得我外婆当年不太喜欢他，但是我外婆不太住我家的，能一直记着也
不容易

【在 b******s 的大作中提到】
: D猫是怎么领会到外婆说的话的严重性呢？动物真的很牛
avatar
q*c
27 楼
A 开枪不死， A/B 地位就对换了。

【在 g****o 的大作中提到】
: 我对这题目理解不一样
: 手枪一共六发子弹，开枪时要是没子弹，弹匣走一格，并不是再次随机分布
: 也就是打完5枪要是都没子弹，子弹必然在第六格里了
: 这样第一枪死人的概率p1=1/6
: 第二枪死人的概率p2=5/6*1/5=1/6
: p3=(1-1/6-1/6)*1/4
: p4=(1-p1-p2-p3)/3
: p5=p6=(1-p1-p2-p3-p4)/2
: Pa=p2+p4+p6;
: pb=p1+p3+p5
avatar
q*c
28 楼
...what happened to the keyword *shuffle*?

【在 g****o 的大作中提到】
: 我对这题目理解不一样
: 手枪一共六发子弹，开枪时要是没子弹，弹匣走一格，并不是再次随机分布
: 也就是打完5枪要是都没子弹，子弹必然在第六格里了
: 这样第一枪死人的概率p1=1/6
: 第二枪死人的概率p2=5/6*1/5=1/6
: p3=(1-1/6-1/6)*1/4
: p4=(1-p1-p2-p3)/3
: p5=p6=(1-p1-p2-p3-p4)/2
: Pa=p2+p4+p6;
: pb=p1+p3+p5
avatar
F*n
29 楼
题目说了每打一枪都shuffle

【在 g****o 的大作中提到】
: 我对这题目理解不一样
: 手枪一共六发子弹，开枪时要是没子弹，弹匣走一格，并不是再次随机分布
: 也就是打完5枪要是都没子弹，子弹必然在第六格里了
: 这样第一枪死人的概率p1=1/6
: 第二枪死人的概率p2=5/6*1/5=1/6
: p3=(1-1/6-1/6)*1/4
: p4=(1-p1-p2-p3)/3
: p5=p6=(1-p1-p2-p3-p4)/2
: Pa=p2+p4+p6;
: pb=p1+p3+p5
avatar
b*7
30 楼
看得不是非常明白，但感觉是不是和题意有点不一样。
题目要求找prefix满足75%的url，而不是说找一个prefix有75%的概率是这n个url的
prefix。所以这是一个确定的算法，肯定得遍历所有字符串一遍

can
By
chosen
compare
return

【在 r*****n 的大作中提到】
: about 6): Trie approach will definitely work. But using random sampling can
: be simpler.
: call a url a target iff it is of the format: prefix (as desired) + junk. By
: a random drawing, we have 0.75 odd to get a target.
: 1. randomly choose n url from the 1 billion urls. The prob. that the chosen
: ones are all targets is 1-(1-0.75)^n = 1-2^{-2n}
: 2. looks like n=10 is enough to grantee that all we drew are targets
: 3. use one index, call idx, pointing at the beginning of these urls, compare
: url[0][idx],...url[9][idx]. If all of them agrees, ++idx; otherwise, return
: idx since we already found the prefix
avatar
f*m
31 楼
"刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了"
这也是根据“每种颜色的牌总数和每种号码的牌总数“建立一个表，然后把输入的牌放
到相应的表位置，比如，将对应位置置1，然后看1的排列是否满足题目要求，对吧？

【在 r**h 的大作中提到】
: 5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
: int 然后turn on 里面3个bits建立一个14*4的矩阵，把输入的排放在矩阵对应的位置
: ，然后扫描每行、每列看能否组成花顺， 顺子， 和同花。还有跟好的方法吗？
: 刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了
avatar
f*m
32 楼
怎么理解B没有获胜的概率是 1-Pa的概率？

胜(

【在 b******7 的大作中提到】
: 设A、B两人概率为Pa,Pb
: 则A获胜有两种可能：
: 1.A第一次就kill了B，概率为1/6
: 2.A第一次没有kill掉B（5/6的概率），但接下来的轮到B先开始的回合里，B没有获胜(
: 1-Pa的概率)，总概率为5/6*(1-Pa)
: Pa = 1/6 + 5/6 * (1- Pa)
avatar
b*7
33 楼
此时B先开枪，由于子弹shuffle了，故相当于最初的A。所以没有获胜的概率为1-Pa

【在 f*********m 的大作中提到】
: 怎么理解B没有获胜的概率是 1-Pa的概率？
:
: 胜(
avatar
f*m
34 楼
有道理，多谢。

【在 b******7 的大作中提到】
: 此时B先开枪，由于子弹shuffle了，故相当于最初的A。所以没有获胜的概率为1-Pa
avatar
r*n
35 楼
嗯 但是反过来想 如果真有这个URL, sampler一定能找到 如果sampler找不到 那遍历
一遍也找不到.

【在 b******7 的大作中提到】
: 看得不是非常明白，但感觉是不是和题意有点不一样。
: 题目要求找prefix满足75%的url，而不是说找一个prefix有75%的概率是这n个url的
: prefix。所以这是一个确定的算法，肯定得遍历所有字符串一遍
:
: can
: By
: chosen
: compare
: return
相关阅读
update！！！！紧急求助！！！！！！门口有一只猫一直叫，叫了好久好久好久，但不吃不喝的感谢大家bless 家咪基本已经适应来还愿了猫！ 你的事发了！ (转载)为什么我们家的两条母狗会互相操对方？黑妞这点是不是也像猫？我家猫为啥会跟人一样打呼噜打算退led灯留包装，猥琐不？Harvard Taro养猫养狗的下一只会养什么样的？那种忽悠喵星人吃药的药囊叫什么呢？紧急求问！！！！有一只猫在我家门口呆了一整晚！！！送几个wellness罐头狗和猫的不同 (转载)过年了，6只猫一起出场给大家拜个年！想请问猫奴们:这个猫喝toilet里的水是否正常？母老虎的眼神[紧急求助] 怎么能让猫不‘嗷嗷’叫家猫的饭盆里惊现一只死老鼠！和爸爸看电视出现少儿不宜镜头时 (转载)去饭馆吃饭看到的野猫
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。