f*********m
发帖数: 726 | 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%的盘。对吗？ |
b****g
发帖数: 192 | 2 第二题怎么用递归做？
BST tree 要求给每个node添加一个succeesor的指针。
了。
【在 f*********m 的大作中提到】
: 从版上大牛的面经中找到的：
: ---------------
: 1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
: 求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
: ，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
: 从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
: 边）不是等假的吧？
: -------------
: 2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
: （这个在他提示下搞出的，code 用递归就几行而已）
|
r**h
发帖数: 1288 | 3 5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
int 然后turn on 里面3个bits建立一个14*4的矩阵，把输入的排放在矩阵对应的位置
，然后扫描每行、每列看能否组成花顺， 顺子， 和同花。还有跟好的方法吗？
刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了 |
b******7
发帖数: 92 | 4 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;
} |
b******7
发帖数: 92 | 5 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;
}; |
q***s
发帖数: 487 | 6 题目说有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
|
q***s
发帖数: 487 | 7
这题能解释一下么？
【在 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
|
b******7
发帖数: 92 | 8 多个字符串求comon prefix时trie是常规思路。
trie假设只考虑a~z，则是26叉树，大部分叶子节点为空，树最大高度为url的最大长度
。trie树节点的个数远小于url的个数，
就算超内存了，也可以按照B+树思想，将超出部分放外存
如果有更好的思路，不烦说出来参考下
【在 q***s 的大作中提到】
: 题目说有1billion个url。这个trie得多大啊，memory 能放下么？
|
b******7
发帖数: 92 | 9 设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 的大作中提到】
:
: 这题能解释一下么？
|
c****7
发帖数: 4192 | 10 有parent指针
【在 b****g 的大作中提到】
: 第二题怎么用递归做？
: BST tree 要求给每个node添加一个succeesor的指针。
:
: 了。
|
|
|
g****o
发帖数: 547 | 11 我对这题目理解不一样
手枪一共六发子弹，开枪时要是没子弹，弹匣走一格，并不是再次随机分布
也就是打完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)
|
r*****n
发帖数: 20 | 12 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... |
q*c
发帖数: 9453 | 13 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
|
q*c
发帖数: 9453 | 14 ...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
|
F*****n
发帖数: 1552 | 15 题目说了每打一枪都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
|
b******7
发帖数: 92 | 16 看得不是非常明白，但感觉是不是和题意有点不一样。
题目要求找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
|
f*********m
发帖数: 726 | 17 "刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了"
这也是根据“每种颜色的牌总数和每种号码的牌总数“建立一个表，然后把输入的牌放
到相应的表位置，比如，将对应位置置1，然后看1的排列是否满足题目要求，对吧？
【在 r**h 的大作中提到】
: 5） 写个函数 输入7张牌， 然后输出是否有同花顺， 顺子， 和同花。 return 一个
: int 然后turn on 里面3个bits建立一个14*4的矩阵，把输入的排放在矩阵对应的位置
: ，然后扫描每行、每列看能否组成花顺， 顺子， 和同花。还有跟好的方法吗？
: 刚写了一个判断梭哈的，发现只要记录每种颜色的牌总数和每种号码的牌总数就行了
|
f*********m
发帖数: 726 | 18 怎么理解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)
|
b******7
发帖数: 92 | 19 此时B先开枪，由于子弹shuffle了，故相当于最初的A。所以没有获胜的概率为1-Pa
【在 f*********m 的大作中提到】
: 怎么理解B没有获胜的概率是 1-Pa的概率？
:
: 胜(
|
f*********m
发帖数: 726 | 20 有道理，多谢。
【在 b******7 的大作中提到】
: 此时B先开枪，由于子弹shuffle了，故相当于最初的A。所以没有获胜的概率为1-Pa
|
r*****n
发帖数: 20 | 21 嗯 但是反过来想 如果真有这个URL, sampler一定能找到 如果sampler找不到 那遍历
一遍也找不到.
【在 b******7 的大作中提到】
: 看得不是非常明白，但感觉是不是和题意有点不一样。
: 题目要求找prefix满足75%的url，而不是说找一个prefix有75%的概率是这n个url的
: prefix。所以这是一个确定的算法，肯定得遍历所有字符串一遍
:
: can
: By
: chosen
: compare
: return
|
