R***i
发帖数: 78 | 1 说他们问题变态不是盖的，第一轮就两道
1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
in[i]，不能用除号, O(n) time required
虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
虾米就算能过这轮后面肯定也要挂。 |
r*******e
发帖数: 7583 | 2 P？猜不出来
except
我这种小
【在 R***i 的大作中提到】
: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。
|
i**9
发帖数: 351 | |
g**e
发帖数: 6127 | 4 1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
第二题也用dp就行了保存P[0, i]和P[i, n]的值
out[i] = P[0, i-1] x P[i+1, n]
没见过这两题，不知道对不对
except
我这种小
【在 R***i 的大作中提到】
: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。
|
r*******e
发帖数: 7583 | 5 第二题就是pre-processing生成两个partial product array
不符合最优子结构的性质，应该不能叫DP
【在 g**e 的大作中提到】
: 1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
: 第二题也用dp就行了保存P[0, i]和P[i, n]的值
: out[i] = P[0, i-1] x P[i+1, n]
: 没见过这两题，不知道对不对
:
: except
: 我这种小
|
k*****7
发帖数: 72 | |
t****n
发帖数: 324 | 7 Paypal?
【在 k*****7 的大作中提到】
: 同问哪里是P？
|
t*********e
发帖数: 1136 | |
c********0
发帖数: 112 | 9 第一个题貌似是那个Catalan number
第二题两个指针扫一遍就行了
具体参考1337code |
r***u
发帖数: 241 | 10 Palantir很富啊
【在 t*********e 的大作中提到】
: This one?
: http://www.palantir.com/
|
|
|
s*i
发帖数: 388 | 11 五角大楼都用他家软件，牛x了
【在 r***u 的大作中提到】
: Palantir很富啊
|
g*****i
发帖数: 19 | 12 第1题： N！种不同Trees, 因为从第一个其添加节点时，可选的位子数分别1， 2， 。
。。N。
except
我这种小
【在 R***i 的大作中提到】
: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。
|
f*****w
发帖数: 2602 | |
R***i
发帖数: 78 | 14 不是n!, 我开始以为也是，被面试的人指出错了。还是要用DP做。
【在 g*****i 的大作中提到】
: 第1题： N！种不同Trees, 因为从第一个其添加节点时，可选的位子数分别1， 2， 。
: 。。N。
:
: except
: 我这种小
|
R***i
发帖数: 78 | 15 1. close, but not quite
2. wrong
【在 g**e 的大作中提到】
: 1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
: 第二题也用dp就行了保存P[0, i]和P[i, n]的值
: out[i] = P[0, i-1] x P[i+1, n]
: 没见过这两题，不知道对不对
:
: except
: 我这种小
|
g*********s
发帖数: 1782 | 16 不能用除号，自己实现个除法行不？
【在 R***i 的大作中提到】
: 1. close, but not quite
: 2. wrong
|
g**e
发帖数: 6127 | 17 指点一下哪错了，至少我运行了几个例子倒没错
/**
* c[i] = A[0]*A[1]*..*A[i]
* d[i] = A[n]*A[n-1]*..*A[i]
*
* and c[0] = a[0], d[n]=a[n];
*
* then B[i] = c[i-1] * d[i+1]
*
* @return b
*/
public static final int[] multiply(int[] a) {
if (a.length==1)
return a;
int n = a.length-1;
int[] b = new int[n+1];
int[] c = new int[n+1];
int[] d = new int[n+1];
c[0] = a[0];
d[n] = a[n];
for (int i=1;i<=n;i++) {
c[i] = c[i-1] * a[i];
d[n-i] = d[n-i+1] * a[n-i];
}
b[0] = d[1];
b[n] = c[n-1];
for (int i=1; i<=n-1; i++) {
b[i] = c[i-1] * d[i+1];
}
return b;
}
【在 R***i 的大作中提到】
: 1. close, but not quite
: 2. wrong
|
g***s
发帖数: 3811 | 18 没错。 直方图也可以用类似的方法来做，比用栈要清楚一些。
指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite
【在 g**e 的大作中提到】
: 指点一下哪错了，至少我运行了几个例子倒没错
: /**
: * c[i] = A[0]*A[1]*..*A[i]
: * d[i] = A[n]*A[n-1]*..*A[i]
: *
: * and c[0] = a[0], d[n]=a[n];
: *
: * then B[i] = c[i-1] * d[i+1]
: *
: * @return b
|
g**e
发帖数: 6127 | 19 1题typo，应该是
f(n) = sum( f(i) * f(n-1-i) ) i=0..n-1
结果跟catalam number一样
public static final int binaryTreeNum (int n) {
if (n<0) return 0;
if (n==0 || n==1) return 1;
int[] f = new int[n+1];
f[0] = 1;
f[1] = 1;
for (int i=2; i<=n; i++) {
for (int j=0; j
f[i] += f[j] * f[i-j-1];
}
}
return f[n];
}
【在 R***i 的大作中提到】
: 1. close, but not quite
: 2. wrong
|
g**e
发帖数: 6127 | 20 用栈的方法我看了很久以后才自己写对了一个，太绕了
【在 g***s 的大作中提到】
: 没错。 直方图也可以用类似的方法来做，比用栈要清楚一些。
:
: 指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
: ★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite
|
|
|
g*********s
发帖数: 1782 | 21 那个怎么做？
【在 g***s 的大作中提到】
: 没错。 直方图也可以用类似的方法来做，比用栈要清楚一些。
:
: 指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
: ★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite
|
R***i
发帖数: 78 | 22 这个是对的
【在 g**e 的大作中提到】
: 1题typo，应该是
: f(n) = sum( f(i) * f(n-1-i) ) i=0..n-1
: 结果跟catalam number一样
: public static final int binaryTreeNum (int n) {
: if (n<0) return 0;
: if (n==0 || n==1) return 1;
:
: int[] f = new int[n+1];
: f[0] = 1;
: f[1] = 1;
|
g***s
发帖数: 3811 | |
g**e
发帖数: 6127 | |
B*M
发帖数: 1340 | 25 你们咋都这么聪明呢！
我老嫉妒死了都，
你们都看了什么书才看到这样的？
【在 g**e 的大作中提到】
: 指点一下哪错了，至少我运行了几个例子倒没错
: /**
: * c[i] = A[0]*A[1]*..*A[i]
: * d[i] = A[n]*A[n-1]*..*A[i]
: *
: * and c[0] = a[0], d[n]=a[n];
: *
: * then B[i] = c[i-1] * d[i+1]
: *
: * @return b
|
g***s
发帖数: 3811 | 26 原来你以前也没仔细看啊。 ：）
【在 g**e 的大作中提到】
: 这个比用stack简洁多了，学习了
|
g*****i
发帖数: 19 | 27 problem 1 should be changed to that how many tree stuctures of full binary
tree with N node. is correct?
except
我这种小
【在 R***i 的大作中提到】
: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。
|
k*****7
发帖数: 72 | 28 我面过这家，两轮挂掉。。。
第二题pre-processing，用空间换时间。
第一题f(n) = sum( f(i) * f(n-1-i) )怎么构造的？试了试确实正确。求大虾解释下
吧 |
g*****i
发帖数: 19 | 29 比较好的第推公式是：f(n) =(2*(2n-1)/(n+1))*f(n-1)
f(0) = 1;
【在 g**e 的大作中提到】
: 1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
: 第二题也用dp就行了保存P[0, i]和P[i, n]的值
: out[i] = P[0, i-1] x P[i+1, n]
: 没见过这两题，不知道对不对
:
: except
: 我这种小
|
g**e
发帖数: 6127 | 30 选一个当root，剩下n-1个点组成左子树或者右子树，或者两边都有，如果左子树有i个
节点，那么右子树就剩n-1-i个，所以结果应该是
f(n) = sum( f(i) * f(n-i-1) ) for i=0..n-1
另外有人也提到了，n个点的binary tree的个数是 catalan number
http://en.wikipedia.org/wiki/Catalan_number
【在 k*****7 的大作中提到】
: 我面过这家，两轮挂掉。。。
: 第二题pre-processing，用空间换时间。
: 第一题f(n) = sum( f(i) * f(n-1-i) )怎么构造的？试了试确实正确。求大虾解释下
: 吧
|
|
|
i***e
发帖数: 452 | 31 1 求all b(x), b(x)=在x右边第一比ax小的位置 [b(x)=n+1 if all are larger than
ax] O(n) using DP.
这个如何写递归保证O（n) ？
【在 g***s 的大作中提到】
: http://www.mitbbs.com/article_t1/JobHunting/31816659_0_2.html
: 32楼
|
i***e
发帖数: 452 | 32
这个不对吧。 a[i] < a[i+1] 同时 a[i] 可能小于b[i+1]了 。
【在 g**e 的大作中提到】
: 选一个当root，剩下n-1个点组成左子树或者右子树，或者两边都有，如果左子树有i个
: 节点，那么右子树就剩n-1-i个，所以结果应该是
: f(n) = sum( f(i) * f(n-i-1) ) for i=0..n-1
: 另外有人也提到了，n个点的binary tree的个数是 catalan number
: http://en.wikipedia.org/wiki/Catalan_number
|
i***e
发帖数: 452 | 33 而且那个帖子说的是应该存位置， 存值没有什么用了.. |
i***e
发帖数: 452 | 34 我知道你的意思， 你的算法是先算b[i+1] 然后算b[i] 对吧？ 如果a[i] > a[i+1],
那么b[i] = i+1, 这个没错了， 但是如果a[i] < a[i+1]的话， 我们不能直接得出b[i
] = b[i+1]; 因为b[i+1]那个位置的数只是比a[i+1]小， 而这个数可能比a[i]要大，
这样的话我们算b[i]的时候就跟b[i+1]的值没有任何很直接的关系了 , 不知道你的算
法是不是这样的？ 请指出如果我错了的话 |
g**e
发帖数: 6127 | 35 你说的对，我开始想的太简单了，脑袋不清楚。
不过DP还是可以做的。 下面虽然有两重循环，但是数组a最多只会被访问两次，所以依
然是O(n)。
等grass和其它大牛来指正
int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
//int[] a = {1, 3, 5, 4, 1};
int n = a.length;
int[] b = new int[n];
b[n-1] = n;
for (int i=n-2; i>=0; i--) {
if (a[i]>a[i+1])
b[i] = i+1;
else {
int tmp = i+1;
while (b[tmp]= a[i])
tmp = b[tmp];
if(tmp==n)
b[i] = n;
else
b[i] = b[tmp];
}
}
[i
，
【在 i***e 的大作中提到】
: 我知道你的意思， 你的算法是先算b[i+1] 然后算b[i] 对吧？ 如果a[i] > a[i+1],
: 那么b[i] = i+1, 这个没错了， 但是如果a[i] < a[i+1]的话， 我们不能直接得出b[i
: ] = b[i+1]; 因为b[i+1]那个位置的数只是比a[i+1]小， 而这个数可能比a[i]要大，
: 这样的话我们算b[i]的时候就跟b[i+1]的值没有任何很直接的关系了 , 不知道你的算
: 法是不是这样的？ 请指出如果我错了的话
|
o****d
发帖数: 2835 | 36 哈哈 前几天刚写过第2题
先从左到右一遍 再从右到左一遍
大致就是
out[0]=1;
out[1]=in[0]；
out[2]=out[1]*in[1]=in[0]*in[1];
out[3]=out[2]*in[2]=in[0]*in[1]*in[2];
...
out[n-1]=out[n-2]*in[n-2]=in[0]*in[1]*in[2]*...*in[n-2];
然后反过来把后半段再乘上就是 (后半段可以用一个temp变量来存,所以也只是O(1)空间)
out[n-1]=out[n-1]*1;
out[n-2]=out[n-1]*(in[n-1]);
out[n-3]=out[n-2]*(in[n-1]*in[n-2]);
out[n-4]=out[n-3]*(in[n-1]*in[n-2]*in[n-3]);
...
except
我这种小
【在 R***i 的大作中提到】
: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。
|
i***e
发帖数: 452 | 37
感觉你这个是O(n2)的了， 一个简单的例子就是从中位数的之后的元素都是降序的，
这样你的那个while loop 只能每次走一步了， 所以每次循环就是linear time 了，
前面的元素如何有n/4个元素进入你这个loop 的话就是O(n2)的time了
【在 g**e 的大作中提到】
: 你说的对，我开始想的太简单了，脑袋不清楚。
: 不过DP还是可以做的。 下面虽然有两重循环，但是数组a最多只会被访问两次，所以依
: 然是O(n)。
: 等grass和其它大牛来指正
: int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
: //int[] a = {1, 3, 5, 4, 1};
: int n = a.length;
: int[] b = new int[n];
: b[n-1] = n;
: for (int i=n-2; i>=0; i--) {
|
g**e
发帖数: 6127 | 38 我已经给了个例子了，while loop最坏的情况只有第一次进入的时候每次走一步，以后
再进
while的时候，就不可能每次走一步了，因为上一个数对应的index已经跳跃了
以依
【在 i***e 的大作中提到】
:
: 感觉你这个是O(n2)的了， 一个简单的例子就是从中位数的之后的元素都是降序的，
: 这样你的那个while loop 只能每次走一步了， 所以每次循环就是linear time 了，
: 前面的元素如何有n/4个元素进入你这个loop 的话就是O(n2)的time了
|
g***s
发帖数: 3811 | 39 这是对的。很经典的一个DP问题。
很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。
【在 g**e 的大作中提到】
: 你说的对，我开始想的太简单了，脑袋不清楚。
: 不过DP还是可以做的。 下面虽然有两重循环，但是数组a最多只会被访问两次，所以依
: 然是O(n)。
: 等grass和其它大牛来指正
: int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
: //int[] a = {1, 3, 5, 4, 1};
: int n = a.length;
: int[] b = new int[n];
: b[n-1] = n;
: for (int i=n-2; i>=0; i--) {
|
g**e
发帖数: 6127 | 40 激动啊，得到大牛肯定
不过你前面提到的"c(x)=在x左边最后一个比ax小的位置 c(x)=0 if all are larger
than ax"，我觉得这种情况c(x)=-1
这样后面算最大面积的时候 (b(x)-c(x)-1)*a(x)才正确
比如a={2,3}, b={2,2}, c={-1,0} 最大面积4
贴个完整的代码
public class LargestHistogramRectangleDP {
public static int largestHistogram(int[] a) {
int maxArea = 0;
int n = a.length;
int[] b = new int[n];
int[] c = new int[n];
b[n-1] = n;
for (int i=n-2; i>=0; i--) {
if (a[i]>a[i+1])
b[i] = i+1;
else {
int tmp = i+1;
//keep checking b[i] until find some t such
that a[t]
//although there are two loops, each element
in array a will
//be accessed at most two times.
while (b[tmp]= a[i]) {
tmp = b[tmp];
}
b[i] = tmp==n ? n : b[tmp];
}
}
for (int i : b) {
System.out.print(i+" ");
}
System.out.println();
c[0] = -1;
for (int i=1; i
if (a[i]>a[i-1])
c[i] = i-1;
else {
int tmp = i-1;
//keep checking c[i] until find some t such
that a[t]
while (c[tmp]>=0 && a[c[tmp]]>=a[i])
tmp = c[tmp];
c[i] = tmp==-1 ? -1 : c[tmp];
}
}
for (int i : c) {
System.out.print(i+" ");
}
System.out.println();
int s = 0, e = 0;
for (int i=0; i
int tmp = (b[i] - c[i] -1) * a[i];
if (tmp>maxArea) {
maxArea = tmp;
s = c[i] + 1;
e = b[i] - 1;
}
}
System.out.println("max histogram rectangle area is " +
maxArea + ", index starts at " + s + " and ends at " +e);
return maxArea;
}
public static void main(String[] args) {
//int[] a = {1, 3, 5, 4, 1};
int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
//int[] a = {4, 4, 10, 5, 7, 8, -1};
//int [] a = {7, 11, 10, 5, 5,1};
largestHistogram(a);
}
}
【在 g***s 的大作中提到】
: 这是对的。很经典的一个DP问题。
: 很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。
|
|
|
g***s
发帖数: 3811 | 41 我那给点是基于下标1..n
所以才有
[b(x)=n+1 if all are larger than ax]
和
[c(x)=0 if all are larger than ax]
具体实现要用下标0..n-1的话，要做改动。
最近你练得很勤快啊。祝好运！
【在 g**e 的大作中提到】
: 激动啊，得到大牛肯定
: 不过你前面提到的"c(x)=在x左边最后一个比ax小的位置 c(x)=0 if all are larger
: than ax"，我觉得这种情况c(x)=-1
: 这样后面算最大面积的时候 (b(x)-c(x)-1)*a(x)才正确
: 比如a={2,3}, b={2,2}, c={-1,0} 最大面积4
: 贴个完整的代码
: public class LargestHistogramRectangleDP {
: public static int largestHistogram(int[] a) {
: int maxArea = 0;
:
|
k*****7
发帖数: 72 | 42 明白了！多谢前辈！
【在 g**e 的大作中提到】
: 选一个当root，剩下n-1个点组成左子树或者右子树，或者两边都有，如果左子树有i个
: 节点，那么右子树就剩n-1-i个，所以结果应该是
: f(n) = sum( f(i) * f(n-i-1) ) for i=0..n-1
: 另外有人也提到了，n个点的binary tree的个数是 catalan number
: http://en.wikipedia.org/wiki/Catalan_number
|
m**q
发帖数: 189 | 43 刚刚看了1337code上的解答，挺精巧的，没看之前
只想到了从头和尾各扫描一遍。
1337code上的链接
http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
【在 c********0 的大作中提到】
: 第一个题貌似是那个Catalan number
: 第二题两个指针扫一遍就行了
: 具体参考1337code
|
p*****u
发帖数: 310 | 44 请问这个2N怎么来的？如 2 3 4 1 0，至少a[3]这个元素就被access了3次。
【在 g***s 的大作中提到】
: 这是对的。很经典的一个DP问题。
: 很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。
|
b*******8
发帖数: 37364 | 45 第一个Catalan树，手头推导结果有两种方法。一种先搞递归式，再用组合数学的生成函数，很难记住临时写出。第二种是转换为等价的（）配对计数问题，所有组合数减去不合法的配对，数据结构书上有，也很复杂，但是可以记住。
如果是写程序算，用第一种递归比较好。 |
