p**********s
发帖数: 115 | 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让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。 | j**l
发帖数: 2911 | | h**k
发帖数: 3368 | | d********e
发帖数: 132 | 4 请问第三题是什么意思？
种解法,写了两种的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让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。
| y*****o
发帖数: 36 | | m******6
发帖数: 599 | 6 congrats! tho i dont think the team is good... | f*******h
发帖数: 53 | 7 不判断数字大小就是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(); | f*******h
发帖数: 53 | 8 加上：
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"}
; | h**k
发帖数: 3368 | 9 罗马数字如何表示大于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**k
发帖数: 3368 | 10 其实你这程序可以再减掉两行，见下
上面这两行可以并入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********7
发帖数: 549 | 11 你google offer有了？
【在 h**k 的大作中提到】
: 恭喜，看来微软的offer拿定了。
| p********7
发帖数: 549 | 12 面霸啊，你好多面试啊
目不难~
种解法,写了两种的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******g
发帖数: 1870 | 13 我写的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*******h
发帖数: 53 | 14 罗马字母上面加上横杠，那个没法输入，所以面试那个就没意义了
【在 h**k 的大作中提到】
: 罗马数字如何表示大于3999的数目？
| f*******h
发帖数: 53 | 15 递归里面可以保存当前最大值，就不用反复调用寻找左边最大和右边最小了。
【在 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******g
发帖数: 1870 | 16 保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。
【在 f*******h 的大作中提到】
: 递归里面可以保存当前最大值，就不用反复调用寻找左边最大和右边最小了。
| f*********5
发帖数: 576 | 17 带简历干什么？
目不难
~
种解法,写了两种的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*******h
发帖数: 53 | 18 你可以想象一下从root做起，那么root.value对于左边的树来说就是最大值，对右边的
树来说就是最小值，这样可以省时间
【在 K******g 的大作中提到】
: 保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。
| s*******t
发帖数: 248 | 19 http://cslibrary.stanford.edu/110/BinaryTrees.html
上面对这个题讲得挺明白的。
【在 K******g 的大作中提到】
: 保存的用处应该不是很大吧？因为每个节点的左边最大和右边最小都是不同的。
| s*******t
发帖数: 248 | 20 第一题，
我能想到的是，先测试是否是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**********s
发帖数: 115 | 21 最简单的方法是用hash~
【在 s*******t 的大作中提到】
: 第一题，
: 我能想到的是，先测试是否是circle，如果是的话，再break circle，然后再找
: intersection，不知道还有没有更好的方法。
:
: 目不难~
: 种解法,写了两种的code.
: 据是否有效),用stack做.题目挺复杂的,但想到DFS这步就豁然开朗了.
: 写只要7行，很牛~
: 时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点
: 喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。
| K******g
发帖数: 1870 | 22 但是你要不停的在左子树找最大的，当前节点左孩子的值与该节点左子树的最大值是不
同的，所以保不保存意义不大，因为每次搜索的时候，走的路径不同
【在 f*******h 的大作中提到】
: 你可以想象一下从root做起，那么root.value对于左边的树来说就是最大值，对右边的
: 树来说就是最小值，这样可以省时间
| K******g
发帖数: 1870 | 23 还有一个更好的办法：
1）先求出List-1的长度L1，求出List-2的长度L2
2) 定 D = abs(L1-L2)
3) 让长的那个List先走D步,然后两个List同时走
最后相遇的那个节点就是重合的那个点
如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
找到重合的点了。
【在 p**********s 的大作中提到】
: 最简单的方法是用hash~
| f*******h
发帖数: 53 | 24 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******g
发帖数: 1870 | 25 不明白
你把这个值传下去干吗呢？每次搜索左子树最大值的时候，走的都是不同路径（从左子
树一直向右，找到最右的一个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*******h
发帖数: 53 | 26 再仔细想想，认真想想。
源程序：
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*******h
发帖数: 53 | | p**********s
发帖数: 115 | 28 正解~
【在 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**********s
发帖数: 115 | 29 hash对有环的情况好处理~
你说的方法对有环的情况其实不用断开,相交点肯定在每个环之前,所以只要记下两个
list在环之前的长度就行了.
【在 K******g 的大作中提到】
: 还有一个更好的办法：
: 1）先求出List-1的长度L1，求出List-2的长度L2
: 2) 定 D = abs(L1-L2)
: 3) 让长的那个List先走D步,然后两个List同时走
: 最后相遇的那个节点就是重合的那个点
: 如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
: 找到重合的点了。
| p**********s
发帖数: 115 | 30 方法二用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********9
发帖数: 1116 | 31 如何找到环开始的节点？ efficiently...
【在 K******g 的大作中提到】
: 还有一个更好的办法：
: 1）先求出List-1的长度L1，求出List-2的长度L2
: 2) 定 D = abs(L1-L2)
: 3) 让长的那个List先走D步,然后两个List同时走
: 最后相遇的那个节点就是重合的那个点
: 如果某个List有环，我们先找到环开始的节点，并且断开，然后用上述的方法，就可以
: 找到重合的点了。
| m*****g
发帖数: 226 | 32 有环的话，应该看两个list入环的入口是否相同。
如果相同，那么才往前面推。如果入口不相同，那么相交就是环长。
【在 p**********s 的大作中提到】
: hash对有环的情况好处理~
: 你说的方法对有环的情况其实不用断开,相交点肯定在每个环之前,所以只要记下两个
: list在环之前的长度就行了.
| K******g
发帖数: 1870 | 33 怎么传递上一个访问值？从上往下可以传递，如果inorder从leaf返回的时候，你怎么
把左边被访问的leaf传到上一层去？除非你additional storage存起来，就可以了
【在 p**********s 的大作中提到】
: 方法二用inorder，传递上一个访问值。如果当前值大于上个值就继续，否则return
: false.
| A*H
发帖数: 127 | 34 any details of problem 3? | i**********e
发帖数: 1145 | 35 第二题 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*********e
发帖数: 518 | 36
目不难~
种解法,写了两种的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让帮忙打印几份，第二天见面的时候带给我。另外中午吃饭错点了中餐，结果聊天的时候最上全是面条，很多次都差点喷出来了^-^ 建议大家以后要沙拉就好了，情愿饿一点，不要太狼狈。。。
|
|
