a******u
发帖数: 69 | 1 三轮
1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
b) 给你n个用户和k,找出发帖数最多的k个用户。
2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
大的那条是什么。
b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
a2*...*an-1.
3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
Characters Given Read4”类似。
前两轮基本bug free.第三轮被抓出些bug。
第二天得知面挂，觉得有点不可思议。 |
l*********8
发帖数: 4642 | 2 不是应该四轮吗？
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
a******u
发帖数: 69 | 3 那天面的new grad都只有3轮哎，两轮ninja，一轮jedi
【在 l*********8 的大作中提到】
: 不是应该四轮吗？
|
l*********8
发帖数: 4642 | 4 2.b你怎么做的？
【在 a******u 的大作中提到】
: 那天面的new grad都只有3轮哎，两轮ninja，一轮jedi
|
p*u
发帖数: 2454 | 5 http://www.mitbbs.com/article/Dreamer/34377763_3.html
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
l*********8
发帖数: 4642 | |
a******u
发帖数: 69 | 7 他说不能用除法
所以
我建了两个数组:b, c
b1 = a1*a2*...*an
b2 = a2*a3*...*an
...
bn = an
c1 = a1
c2 = a1*a2
...
cn = a1*a2*...*an
output:
b2
c1 * b3
c2 * b4
...
cn-1
【在 l*********8 的大作中提到】
: 2.b你怎么做的？
|
a******u
发帖数: 69 | 8 我不是老印面的。
是个白人mm
【在 l*********8 的大作中提到】
: read4k那个面试官的问题？
|
m****n
发帖数: 142 | 9 FB 是一票否决 完全取决于最jerk的面试官
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
x**********a
发帖数: 1372 | 10 哪个office？多谢。
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
|
|
a******u
发帖数: 69 | 11 我之前看过一下这道题。大概知道tricky的地方在哪，但没自己写过。面的时候，我还
没说我写完，她就抓出来一些bug。。。
【在 p*u 的大作中提到】
: http://www.mitbbs.com/article/Dreamer/34377763_3.html
|
a******u
发帖数: 69 | 12 menlo park
【在 x**********a 的大作中提到】
: 哪个office？多谢。
|
a******u
发帖数: 69 | 13 人生好艰难
【在 m****n 的大作中提到】
: FB 是一票否决 完全取决于最jerk的面试官
|
l*********8
发帖数: 4642 | 14 这个方法可以啊
【在 a******u 的大作中提到】
: 他说不能用除法
: 所以
: 我建了两个数组:b, c
: b1 = a1*a2*...*an
: b2 = a2*a3*...*an
: ...
: bn = an
: c1 = a1
: c2 = a1*a2
: ...
|
q********c
发帖数: 1774 | 15 你的FB加面没？
【在 l*********8 的大作中提到】
: 这个方法可以啊
|
s******7
发帖数: 1758 | 16 这几道都是常见题，估计大家都做出来了，选谁只能靠长相和聊天吹牛拍马功夫了 |
a******u
发帖数: 69 | 17 可以发邮件问recruiter三个面试官的feedback吗？
【在 m****n 的大作中提到】
: FB 是一票否决 完全取决于最jerk的面试官
|
l*****a
发帖数: 14598 | 18 可以只用一个数组
【在 l*********8 的大作中提到】
: 这个方法可以啊
|
l*********8
发帖数: 4642 | 19 re and zan.
可能楼主大体思路上都对了, 但细节上不够优化。
【在 l*****a 的大作中提到】
: 可以只用一个数组
|
a******u
发帖数: 69 | 20 好吧。看来我的确多用了数组。但以我回来过往的经历，面试官会让我改进方法。所以
我习惯一开始给出最好解释的方法，然后等他让我改进。
re and zan.可能楼主大体思路上都对了, 但细节上不够优化。
【在 l*********8 的大作中提到】
: re and zan.
: 可能楼主大体思路上都对了, 但细节上不够优化。
|
|
|
n*******e
发帖数: 37 | |
n*******e
发帖数: 37 | 22 请问2a是给定两个leaf nodes吗? 还是找任意两个leaf nodes?
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
l*****a
发帖数: 14598 | 23 这个不见得是真正原因
不过以后尽可能写最优的好了，知道最优还不写最后莫名悲剧的例子太多了
【在 a******u 的大作中提到】
: 好吧。看来我的确多用了数组。但以我回来过往的经历，面试官会让我改进方法。所以
: 我习惯一开始给出最好解释的方法，然后等他让我改进。
:
: re and zan.可能楼主大体思路上都对了, 但细节上不够优化。
|
l*****a
发帖数: 14598 | 24 result[0]=1;
result[i]=result[i-1]*arr[i-1];
int c=1;
for(int i=arr.length-2;i>=0;i--) {
c*=arr[i+1];
result[i]*=c;
}
【在 n*******e 的大作中提到】
: 想请问只用一个数组的方法
: 可以说说吗
|
a******u
发帖数: 69 | 25 任意啊。给定的话就只有一个path的
请问2a是给定两个leaf nodes吗? 还是找任意两个leaf nodes?
【在 n*******e 的大作中提到】
: 请问2a是给定两个leaf nodes吗? 还是找任意两个leaf nodes?
|
h***k
发帖数: 161 | 26 跑了一下这个方法结果不对
【在 l*****a 的大作中提到】
: result[0]=1;
: result[i]=result[i-1]*arr[i-1];
: int c=1;
: for(int i=arr.length-2;i>=0;i--) {
: c*=arr[i+1];
: result[i]*=c;
: }
|
l*****a
发帖数: 14598 | 27 上面那个放在循环里面了吗
那你认为什么地方有问题呢
【在 h***k 的大作中提到】
: 跑了一下这个方法结果不对
|
h***k
发帖数: 161 | 28 上面那一段感觉你是写的通项公式嘛？放到循环里index溢出，能展开讲讲么?
【在 l*****a 的大作中提到】
: 上面那个放在循环里面了吗
: 那你认为什么地方有问题呢
|
l*****a
发帖数: 14598 | 29 for(int i=1;i<=arr.length-1;i++)
你是这么写的吗？
【在 h***k 的大作中提到】
: 上面那一段感觉你是写的通项公式嘛？放到循环里index溢出，能展开讲讲么?
|
h***k
发帖数: 161 | 30 for(int i=arr.length-2;i>=0;i--) {
【在 l*****a 的大作中提到】
: for(int i=1;i<=arr.length-1;i++)
: 你是这么写的吗？
|
|
|
l*****a
发帖数: 14598 | 31 这个什么结果？你输入数组几个item
result[0]=1;
for(int i=1;i<=arr.length-1;i++) {
result[i]=result[i-1]*arr[i-1];
}
int c=1;
for(int i=arr.length-2;i>=0;i--) {
c*=arr[i+1];
result[i]*=c;
}
【在 h***k 的大作中提到】
: for(int i=arr.length-2;i>=0;i--) {
|
w*****t
发帖数: 485 | 32 有更简洁的做法，one pass with O(1) spaces:
vector Multiplication(vector &arr)
{
if (arr.empty()) return vector();
const int N = arr.size();
vector result(N, 1);
int left = 1, right = 1;
for (int i = 0; i < N; ++i) {
result[i] *= left;
result[N-1-i] *= right;
left *= arr[i];
right *= arr[N-1-i];
}
return result;
} |
h***k
发帖数: 161 | 33 原来这里有循环，这个对的！
【在 l*****a 的大作中提到】
: 这个什么结果？你输入数组几个item
: result[0]=1;
: for(int i=1;i<=arr.length-1;i++) {
: result[i]=result[i-1]*arr[i-1];
: }
: int c=1;
: for(int i=arr.length-2;i>=0;i--) {
: c*=arr[i+1];
: result[i]*=c;
: }
|
h***k
发帖数: 161 | 34 算法是对的，但明显是O(n)time O(n) space啊
【在 w*****t 的大作中提到】
: 有更简洁的做法，one pass with O(1) spaces:
: vector Multiplication(vector &arr)
: {
: if (arr.empty()) return vector();
: const int N = arr.size();
: vector result(N, 1);
: int left = 1, right = 1;
: for (int i = 0; i < N; ++i) {
: result[i] *= left;
: result[N-1-i] *= right;
|
M********t
发帖数: 5032 | 35 你做地太好了，他们认为你预先知道答案。
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
z***b
发帖数: 127 | 36 楼主你那个树的题怎么答的？这题要想写好挺不容易啊。 |
h*********o
发帖数: 230 | 37 二叉树这个题怎么做啊？
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
h*********o
发帖数: 230 | 38 二叉树这个题怎么做啊？
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
w*****t
发帖数: 485 | 39 如果要算存放结果的空间那就是O(n)， 我指的是额外空间占用.
简洁的地方就是one pass， 一般解法都是two pass.
【在 h***k 的大作中提到】
: 算法是对的，但明显是O(n)time O(n) space啊
|
w*****t
发帖数: 485 | 40 share 一个：
int maxLeafPath(TreeNode *root, int &maxPath)
{
if (!root) return INT_MIN;
if (!root->left && !root->right) return root->val;
int leftPath = maxLeafPath(root->left, maxPath);
int rightPath = maxLeafPath(root->right, maxPath);
if (root->left && root->right)
maxPath = max(maxPath, root->val + leftPath + rightPath);
return root->val + max(leftPath, rightPath);
}
int maxLeafPath(TreeNode *root)
{
int maxPath = INT_MIN;
maxLeafPath(root, maxPath);
return maxPath;
}
【在 h*********o 的大作中提到】
: 二叉树这个题怎么做啊？
|
|
|
L***s
发帖数: 1148 | 41
jerk不是形容词，谢谢
【在 m****n 的大作中提到】
: FB 是一票否决 完全取决于最jerk的面试官
|
r****7
发帖数: 2282 | 42 比如一个只有左节点的树，最后返回的还是INT_MIN
【在 w*****t 的大作中提到】
: share 一个：
: int maxLeafPath(TreeNode *root, int &maxPath)
: {
: if (!root) return INT_MIN;
: if (!root->left && !root->right) return root->val;
: int leftPath = maxLeafPath(root->left, maxPath);
: int rightPath = maxLeafPath(root->right, maxPath);
: if (root->left && root->right)
: maxPath = max(maxPath, root->val + leftPath + rightPath);
: return root->val + max(leftPath, rightPath);
|
a******u
发帖数: 69 | 43 我的想法跟你一样。实现有些不同。但思路也是递归的过程中同时更新该节点到叶子的
最大权值路，和以它为中介点的叶到叶最大路。
share 一个：int maxLeafPath(TreeNode *root, int
【在 w*****t 的大作中提到】
: share 一个：
: int maxLeafPath(TreeNode *root, int &maxPath)
: {
: if (!root) return INT_MIN;
: if (!root->left && !root->right) return root->val;
: int leftPath = maxLeafPath(root->left, maxPath);
: int rightPath = maxLeafPath(root->right, maxPath);
: if (root->left && root->right)
: maxPath = max(maxPath, root->val + leftPath + rightPath);
: return root->val + max(leftPath, rightPath);
|
a******u
发帖数: 69 | 44 我当时没有考虑到这种不存在叶到叶的path的情况
比如一个只有左节点的树，最后返回的还是INT_MIN
【在 r****7 的大作中提到】
: 比如一个只有左节点的树，最后返回的还是INT_MIN
|
a******u
发帖数: 69 | 45 那我也没办法啊，问我leetcode的题。
你做地太好了，他们认为你预先知道答案。
【在 M********t 的大作中提到】
: 你做地太好了，他们认为你预先知道答案。
|
z***b
发帖数: 127 | 46 我觉得这些都应该和面试官qualify吧？这也是我觉得这题不好写对的原因。
【在 a******u 的大作中提到】
: 我当时没有考虑到这种不存在叶到叶的path的情况
:
: 比如一个只有左节点的树，最后返回的还是INT_MIN
|
a******u
发帖数: 69 | 47 也是的。但他看完我的code说，I think it is correct. 然后就问下一题了。
我觉得这些都应该和面试官qualify吧？这也是我觉得这题不好写对的原因。
【在 z***b 的大作中提到】
: 我觉得这些都应该和面试官qualify吧？这也是我觉得这题不好写对的原因。
|
z***b
发帖数: 127 | 48 b) 给你n个用户和k,找出发帖数最多的k个用户。
这题你咋答的？ 说的是quick select那个，让你写代码没？
【在 a******u 的大作中提到】
: 也是的。但他看完我的code说，I think it is correct. 然后就问下一题了。
:
: 我觉得这些都应该和面试官qualify吧？这也是我觉得这题不好写对的原因。
|
c*****m
发帖数: 271 | 49 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai;
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
c*****m
发帖数: 271 | 50 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai; |
|
|
c*****m
发帖数: 271 | 51 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai; |
c*****m
发帖数: 271 | 52 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai; |
a******u
发帖数: 69 | 53 我跟他说了个Nlogk的用heap的方法，他就让我写了。写完也没让我improve。这道题一
定要用quick select吗?
我本身不是很喜欢quick select这种worst case会到n^2的方法。。。但expect time是
n的方法。
b) 给你n个用户和k,找出发帖数最多的k个用户。这题你咋答的？ 说的是quick select
那个，让你写代码没？
【在 z***b 的大作中提到】
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 这题你咋答的？ 说的是quick select那个，让你写代码没？
|
a******u
发帖数: 69 | 54 1.a就是
11可以解码为k，也可以解码为aa
1.a看不明白到底要干啥1.b是用小顶堆么？2.a二叉树从一个叶子到另外一个叶子不是
只有一条路么？2.b不能用除法的还用一个数组的话是否可以这样：b[0] = 1b[1] = ..
......
【在 c*****m 的大作中提到】
: 1.a看不明白到底要干啥
: 1.b是用小顶堆么？
: 2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
: 2.b不能用除法的还用一个数组的话是否可以这样：
: b[0] = 1
: b[1] = an
: b[2] = an-1*an
: ...
: b[n-2] = a3*a4*...*an
: front = 1
|
e*******o
发帖数: 23 | 55 看到大牛说的select top K有三种方法
Nlogk，这是用堆
klogN，这是用什么方法？
N，这是quick select对吗？
请大牛们指教，实在感谢 |
z***b
发帖数: 127 | 56 quick select按 median of median的最优解法worst case 是 O(N),你该提下的。如果
让你写就写那个选一个pivot的就行了
我觉得你已经答得挺好了，多面几家，肯定有好offer.
select
【在 a******u 的大作中提到】
: 我跟他说了个Nlogk的用heap的方法，他就让我写了。写完也没让我improve。这道题一
: 定要用quick select吗?
: 我本身不是很喜欢quick select这种worst case会到n^2的方法。。。但expect time是
: n的方法。
:
: b) 给你n个用户和k,找出发帖数最多的k个用户。这题你咋答的？ 说的是quick select
: 那个，让你写代码没？
|
a******u
发帖数: 69 | 57 堆的方法就是维护一个小根堆。每次进来一个数就push进堆里。当堆的size大于K的时
候，就pop出来最小的那个。
Quick select期望复杂度是n
运用快排的思路。但每次递归进去下层都是上一层的size的1/2。所以时间复杂度就是
一个power serie的和，which is O(n).
看到大牛说的select top K有三种方法Nlogk，这是用堆klogN，这是用什么方法？N，
这是quick select对吗？请大牛们指教，实在感谢
【在 e*******o 的大作中提到】
: 看到大牛说的select top K有三种方法
: Nlogk，这是用堆
: klogN，这是用什么方法？
: N，这是quick select对吗？
: 请大牛们指教，实在感谢
|
a******u
发帖数: 69 | 58 Median of median那个方法我没有仔细研究过，面试的时候也没想起来。写随机pivot
的quick select应该也没有太大问题。但他也没让我写哎。anyway，谢谢鼓励
quick select按 median of median的最优解法worst case 是 O(N),你该提下的。如果
让你写就写那个选一个pivot的就行了我觉得你已经答得........
【在 z***b 的大作中提到】
: quick select按 median of median的最优解法worst case 是 O(N),你该提下的。如果
: 让你写就写那个选一个pivot的就行了
: 我觉得你已经答得挺好了，多面几家，肯定有好offer.
:
: select
|
c*****m
发帖数: 271 | 59 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai; |
c*****m
发帖数: 271 | 60 1.a看不明白到底要干啥
1.b是用小顶堆么？
2.a二叉树从一个叶子到另外一个叶子不是只有一条路么？
2.b不能用除法的还用一个数组的话是否可以这样：
b[0] = 1
b[1] = an
b[2] = an-1*an
...
b[n-2] = a3*a4*...*an
front = 1
i in [2,n]:
print front*b[n-i]; front*=ai; |
|
|
c*****m
发帖数: 271 | 61
【在 a******u 的大作中提到】
: 好吧。看来我的确多用了数组。但以我回来过往的经历，面试官会让我改进方法。所以
: 我习惯一开始给出最好解释的方法，然后等他让我改进。
:
: re and zan.可能楼主大体思路上都对了, 但细节上不够优化。
|
h*********o
发帖数: 230 | 62 二叉树这个题怎么做啊？
【在 a******u 的大作中提到】
: 三轮
: 1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
: b) 给你n个用户和k,找出发帖数最多的k个用户。
: 2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
: 大的那条是什么。
: b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*
: a2*...*an-1.
: 3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
: Characters Given Read4”类似。
: 前两轮基本bug free.第三轮被抓出些bug。
|
a******u
发帖数: 69 | 63 weibest在前面给出了做法。
二叉树这个题怎么做啊？
【在 h*********o 的大作中提到】
: 二叉树这个题怎么做啊？
|
w*****t
发帖数: 485 | 64 用三数取中法简单些，最坏有O(N^2)的可能性，但非常低:
int SelectPivot(vector &a, int low, int high)
{
// 三数取中法
assert(low >= 0);
if (low >= high) return low;
int mid = low + (high - low) / 2;
if (a[low] < a[mid]) swap(a[low], a[mid]);
if (a[mid] < a[high]) swap(a[mid], a[high]);
if (a[low] < a[mid]) swap(a[low], a[mid]);
// hide pivot
// |--low--| ... |--pivot--|--high--|
swap(a[mid], a[high-1]);
return high - 1;
}
pivot
【在 a******u 的大作中提到】
: Median of median那个方法我没有仔细研究过，面试的时候也没想起来。写随机pivot
: 的quick select应该也没有太大问题。但他也没让我写哎。anyway，谢谢鼓励
:
: quick select按 median of median的最优解法worst case 是 O(N),你该提下的。如果
: 让你写就写那个选一个pivot的就行了我觉得你已经答得........
|
