芦笋种植疑问 - 未名空间MITBBS历史存档

p*s2013-05-16 07:05

1 楼

windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
2 bool isBST(node *n);
3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
5 如何设计web browser的ui.瞎扯就好了.
面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

b*n2013-05-16 07:05

2 楼

主申請人，可否在485 180天后，從工業界的permanant position 變動到 university
post-doc 或者contractor之類的啊？？？? 還是一定要一個permanent position. 這
個是自己file AC21 要主動提到的麼？

m*o2013-05-16 07:05

3 楼

今年种了芦笋苗，长出细细的，真是细细的，芦笋。太细了，没法吃。，
几天后就来是开花了。
这个怎么护理，啥时候才能成为像店里那样的》
谢谢

j*l2013-05-16 07:05

4 楼

罗马数字不太好做，要很熟悉规则

b*12013-05-16 07:05

5 楼

种了几年了?

h*k2013-05-16 07:05

6 楼

恭喜，看来微软的offer拿定了。

l*n2013-05-16 07:05

7 楼

做好忍住两年嘴馋的准备吧。
看我的帖子
http://www.mitbbs.com/article_t0/gardening/31670525.html

【在 m**o 的大作中提到】

: 今年种了芦笋苗，长出细细的，真是细细的，芦笋。太细了，没法吃。，
: 几天后就来是开花了。
: 这个怎么护理，啥时候才能成为像店里那样的》
: 谢谢

d*e2013-05-16 07:05

8 楼

请问第三题是什么意思？

种解法,写了两种的code.

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

m*o2013-05-16 07:05

9 楼

看了有收获。
你说的很对，三年很快就过去，。
以前一直想种，一直没种，就是因为觉得三年太长。其实一晃都快8年了。

【在 l*n 的大作中提到】

: 做好忍住两年嘴馋的准备吧。
: 看我的帖子
: http://www.mitbbs.com/article_t0/gardening/31670525.html

y*o2013-05-16 07:05

10 楼

同问！！

l*n2013-05-16 07:05

11 楼

如果早些种的话，已经吃了五年的自产芦笋了，呵呵
不过永远不会太迟

【在 m**o 的大作中提到】

: 看了有收获。
: 你说的很对，三年很快就过去，。
: 以前一直想种，一直没种，就是因为觉得三年太长。其实一晃都快8年了。

m*62013-05-16 07:05

12 楼

congrats! tho i dont think the team is good...

m*o2013-05-16 07:05

13 楼

是呀总觉得也许不久就要搬家。结果就不敢下手，
不过也的确换了房子，。
这里也不知道能住多久。
不管他先种了再说。
今天订了巨峰葡萄。
早种早吃了。不能再拖了。

【在 l*n 的大作中提到】

: 如果早些种的话，已经吃了五年的自产芦笋了，呵呵
: 不过永远不会太迟

f*h2013-05-16 07:05

14 楼

不判断数字大小就是7行，加上判断1-3999要多两行
StringBuilder romanString=new StringBuilder();
for (int i=0;i
if (inputNumber<1)
break;
while (inputNumber>=ROMANNUMBERS[i]){

inputNumber-=ROMANNUMBERS[i];
romanString.append(ROMANSTRINGS[i]);
}

}
return romanString.toString();

l*n2013-05-16 07:05

15 楼

不要怕搬家。虽然不是很建议这样做，但是芦笋也是可以移植的。如果真的是下面两三
年就要搬家，那你就把芦笋种在raised bed里，这样挖的时候不会太损根

【在 m**o 的大作中提到】

: 是呀总觉得也许不久就要搬家。结果就不敢下手，
: 不过也的确换了房子，。
: 这里也不知道能住多久。
: 不管他先种了再说。
: 今天订了巨峰葡萄。
: 早种早吃了。不能再拖了。

f*h2013-05-16 07:05

16 楼

加上：
private static final int[] ROMANNUMBERS={1000,900,500,400,100,90,50,40
,10,9,5,4,1};
private static final String[] ROMANSTRINGS={"M","CM","D","CD","C","XC","
L"
,"XL","X","IX","V","IV","I"}
;

l*d2013-05-16 07:05

17 楼

我是无知者无畏；开好菜地，看到芦笋根就买了几十棵，种完了才知道要过两年才能迟
到；不过我第二年就开吃了，反正种得多。

【在 l*n 的大作中提到】

: 不要怕搬家。虽然不是很建议这样做，但是芦笋也是可以移植的。如果真的是下面两三
: 年就要搬家，那你就把芦笋种在raised bed里，这样挖的时候不会太损根

h*k2013-05-16 07:05

18 楼

罗马数字如何表示大于3999的数目？

【在 f*******h 的大作中提到】

: 不判断数字大小就是7行，加上判断1-3999要多两行
: StringBuilder romanString=new StringBuilder();
: for (int i=0;i:
: if (inputNumber<1)
: break;
: while (inputNumber>=ROMANNUMBERS[i]){
:
: inputNumber-=ROMANNUMBERS[i];
: romanString.append(ROMANSTRINGS[i]);

h*k2013-05-16 07:05

19 楼

其实你这程序可以再减掉两行，见下

上面这两行可以并入for循环的终止条件里
for( int i = 0; i < ROMANLENGTH && inputNumber > 0; ++i )

【在 f*******h 的大作中提到】

: 不判断数字大小就是7行，加上判断1-3999要多两行
: StringBuilder romanString=new StringBuilder();
: for (int i=0;i:
: if (inputNumber<1)
: break;
: while (inputNumber>=ROMANNUMBERS[i]){
:
: inputNumber-=ROMANNUMBERS[i];
: romanString.append(ROMANSTRINGS[i]);

p*72013-05-16 07:05

20 楼

你google offer有了？

【在 h**k 的大作中提到】

: 恭喜，看来微软的offer拿定了。

p*72013-05-16 07:05

21 楼

面霸啊，你好多面试啊

目不难~
种解法,写了两种的code.
据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
写只要7行，很牛~
时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点
喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

K*g2013-05-16 07:05

22 楼

我写的isBST()代码，请大家指出错误，或者可以优化的地方
typedef struct T_NODE
{
struct T_NODE *left, *right;
int v;
} NODE;
int isBST(NODE* root)
{
if(root==NULL) return 1;
if(root->left!=NULL)
{
if(root->left->v>root->v) return 0;
if(findLeftBiggest(root->left) > root->v) return 0;
}
if(root->right!=NULL)
{
if(root->right->vv) return 0;
if(findRightSmallest(root->right) < root->v) return 0;
}

return isBST(root->left) && isBST(root->right

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

f*h2013-05-16 07:05

23 楼

罗马字母上面加上横杠，那个没法输入，所以面试那个就没意义了

【在 h**k 的大作中提到】

: 罗马数字如何表示大于3999的数目？

f*h2013-05-16 07:05

24 楼

递归里面可以保存当前最大值，就不用反复调用寻找左边最大和右边最小了。

【在 K******g 的大作中提到】

: 我写的isBST()代码，请大家指出错误，或者可以优化的地方
: typedef struct T_NODE
: {
: struct T_NODE *left, *right;
: int v;
: } NODE;
: int isBST(NODE* root)
: {
: if(root==NULL) return 1;
: if(root->left!=NULL)

K*g2013-05-16 07:05

25 楼

保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。

【在 f*******h 的大作中提到】

: 递归里面可以保存当前最大值，就不用反复调用寻找左边最大和右边最小了。

f*52013-05-16 07:05

26 楼

带简历干什么？

目不难
~
种解法,写了两种的code.
据是否有
效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
写只要
7行，很牛~
时候带给我。另
外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建
议大家以后要沙
拉就好了，情愿饿一点，不要太狼狈。。。

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

f*h2013-05-16 07:05

27 楼

你可以想象一下从root做起，那么root.value对于左边的树来说就是最大值，对右边的
树来说就是最小值，这样可以省时间

【在 K******g 的大作中提到】

: 保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。

s*t2013-05-16 07:05

28 楼

http://cslibrary.stanford.edu/110/BinaryTrees.html
上面对这个题讲得挺明白的。

【在 K******g 的大作中提到】

: 保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。

s*t2013-05-16 07:05

29 楼

第一题，
我能想到的是，先测试是否是circle，如果是的话，再break circle，然后再找
intersection，不知道还有没有更好的方法。

目不难~
种解法,写了两种的code.
据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
写只要7行，很牛~
时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点
喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

p*s2013-05-16 07:05

30 楼

最简单的方法是用hash~

【在 s*******t 的大作中提到】

: 第一题，
: 我能想到的是，先测试是否是circle，如果是的话，再break circle，然后再找
: intersection，不知道还有没有更好的方法。
:
: 目不难~
: 种解法,写了两种的code.
: 据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 写只要7行，很牛~
: 时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点
: 喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

K*g2013-05-16 07:05

31 楼

但是你要不停的在左子树找最大的，当前节点左孩子的值与该节点左子树的最大值是不
同的，所以保不保存意义不大，因为每次搜索的时候，走的路径不同

【在 f*******h 的大作中提到】

: 你可以想象一下从root做起，那么root.value对于左边的树来说就是最大值，对右边的
: 树来说就是最小值，这样可以省时间

K*g2013-05-16 07:05

32 楼

还有一个更好的办法：
1）先求出List-1的长度L1，求出List-2的长度L2
2) 定 D = abs(L1-L2)
3) 让长的那个List先走D步,然后两个List同时走
最后相遇的那个节点就是重合的那个点
如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
找到重合的点了。

【在 p**********s 的大作中提到】

: 最简单的方法是用hash~

f*h2013-05-16 07:05

33 楼

isBst(Node node, int maxValue, int minValue)
用这个做递归，刚开始maxValue=Integer.MAX_VALUE minValue=Integer.MIN_VALUE
从root做起：
isBst(root.left,root.value,Integer.MIN_VALUE) && isBst(root.right,Integer.
MAX_VALUE, root.value)
明白了么？

【在 K******g 的大作中提到】

: 但是你要不停的在左子树找最大的，当前节点左孩子的值与该节点左子树的最大值是不
: 同的，所以保不保存意义不大，因为每次搜索的时候，走的路径不同

K*g2013-05-16 07:05

34 楼

不明白
你把这个值传下去干吗呢？每次搜索左子树最大值的时候，走的都是不同路径（从左子
树一直向右，找到最右的一个leaf就返回），你保存这个值有什么意义呢
如果不保存，需要把每个节点遍历一边， O(n),对每个节点，需要搜索左右子树的最值，O（nlogn)。
所以最终的复杂度是O(n+nlogn)
你保存的话，复杂度又是多少？

【在 f*******h 的大作中提到】

: isBst(Node node, int maxValue, int minValue)
: 用这个做递归，刚开始maxValue=Integer.MAX_VALUE minValue=Integer.MIN_VALUE
: 从root做起：
: isBst(root.left,root.value,Integer.MIN_VALUE) && isBst(root.right,Integer.
: MAX_VALUE, root.value)
: 明白了么？

f*h2013-05-16 07:05

35 楼

再仔细想想，认真想想。
源程序：
boolean isBst( Node root )
{
return isBst( root, Integer.MAX_VALUE, Integer.MIN_VALUE );
}
int isBst( Node root, int max, int min)
{
if (root==null) return true;
if (root.value >=min && root.value <= max)
{
return isBst( root.left, root.value, min) && isBst( root.right, max,
root.value);
}
else
{
return false;
}
}

f*h2013-05-16 07:05

36 楼

O(N)+O(N) call stack

p*s2013-05-16 07:05

37 楼

正解~

【在 f*******h 的大作中提到】

: 再仔细想想，认真想想。
: 源程序：
: boolean isBst( Node root )
: {
: return isBst( root, Integer.MAX_VALUE, Integer.MIN_VALUE );
: }
: int isBst( Node root, int max, int min)
: {
: if (root==null) return true;
: if (root.value >=min && root.value <= max)

p*s2013-05-16 07:05

38 楼

hash对有环的情况好处理~
你说的方法对有环的情况其实不用断开,相交点肯定在每个环之前,所以只要记下两个
list在环之前的长度就行了.

【在 K******g 的大作中提到】

: 还有一个更好的办法：
: 1）先求出List-1的长度L1，求出List-2的长度L2
: 2) 定 D = abs(L1-L2)
: 3) 让长的那个List先走D步,然后两个List同时走
: 最后相遇的那个节点就是重合的那个点
: 如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
: 找到重合的点了。

p*s2013-05-16 07:05

39 楼

方法二用inorder，传递上一个访问值。如果当前值大于上个值就继续，否则return
false.

【在 f*******h 的大作中提到】

: 再仔细想想，认真想想。
: 源程序：
: boolean isBst( Node root )
: {
: return isBst( root, Integer.MAX_VALUE, Integer.MIN_VALUE );
: }
: int isBst( Node root, int max, int min)
: {
: if (root==null) return true;
: if (root.value >=min && root.value <= max)

r*92013-05-16 07:05

40 楼

如何找到环开始的节点？ efficiently...

【在 K******g 的大作中提到】

: 还有一个更好的办法：
: 1）先求出List-1的长度L1，求出List-2的长度L2
: 2) 定 D = abs(L1-L2)
: 3) 让长的那个List先走D步,然后两个List同时走
: 最后相遇的那个节点就是重合的那个点
: 如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
: 找到重合的点了。

m*g2013-05-16 07:05

41 楼

有环的话，应该看两个list入环的入口是否相同。
如果相同，那么才往前面推。如果入口不相同，那么相交就是环长。

【在 p**********s 的大作中提到】

: hash对有环的情况好处理~
: 你说的方法对有环的情况其实不用断开,相交点肯定在每个环之前,所以只要记下两个
: list在环之前的长度就行了.

K*g2013-05-16 07:05

42 楼

怎么传递上一个访问值？从上往下可以传递，如果inorder从leaf返回的时候，你怎么
把左边被访问的leaf传到上一层去？除非你additional storage存起来，就可以了

【在 p**********s 的大作中提到】

: 方法二用inorder，传递上一个访问值。如果当前值大于上个值就继续，否则return
: false.

A*H2013-05-16 07:05

43 楼

any details of problem 3?

i*e2013-05-16 07:05

44 楼

第二题 isBST(node*) 我把我的思路和解法都写下来了。让大家参考参考下。
http://www.ihas1337code.com/2010/09/determine-if-binary-tree-is-binary.html

目不难~
种解法,写了两种的code.
据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
写只要7行，很牛~
时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点
喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。

y*e2013-05-16 07:05

45 楼

目不难~
种解法,写了两种的code.
据是否有效),用stack做.题目挺
复杂的,但想到DFS这步就豁然开朗了.
写只要7行，很牛~
时候带给我。另外中午吃饭错点
了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙
拉就好了，情愿饿一点，不要太
狼狈。。。
尝试用C#写Roman number。没有检测输入的值。
1 private char[] romans = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
2 private int[] values = {1000, 500, 100, 50, 10, 5, 1 };
3
4 public string string2Roam(int num) {
5 StringBuilder sb = new StringBuilder();
6 for (int i = 0; i < values.Length; i++) {
7 sb.append(new String(romans[i], num / va

【在 p**********s 的大作中提到】

: windows live team, 面了5个,很奇怪只有第一个是principle,其他都是manager. 题目不难~
: 1 find intersection of two link list(each one may have a circle).我给了四种解法,写了两种的code.
: 2 bool isBST(node *n);
: 3 DFS在uml里的变种(大概是说有个database,里面存了结构化的网页数据，要判断数据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 4 string2Roam.把1-1000里的数字string变成罗马数字string. 貌似他手下的人用C#写只要7行，很牛~
: 5 如何设计web browser的ui.瞎扯就好了.
: 面试前一天晚上12点才发现没带简历，赶紧发信给hr让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。