|
锁定老帖子 主题：想起一道面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-07-28
我也说个面试题，上次去SAP面试的时候问我的。
写个程序，求以下表达式的值 1/1 + (1 + 2)/ (1 * 2) + (1 + 2 + 3) / (1 * 2 * 3) + ... + (1 + 2 + .. + n) / (1 * 2 * ..* n) 我当时看了，觉得这个怎么也是数学题，跟程序有什么关系。怎么说应该有个公式能把这个转换成一个很简单的表达式，然后可以得出精确的值。想了很久，因为数学很多都忘记了，就觉得很不爽，然后就说我不会。 面试官就说，那好，面试到此为止。 所以不会这个题目，说明我不是一个好软件工程师啊。。 然后说，我离开的时候，他对同事说，排列组合都不会。。。 后来回家之后，老婆给出了一个程序，当然运行是可以运行，我还是觉得是不够精确的，因为除法之后很多的精确度就消失了。应该是有数学的办法可以解决才对的。我死死的以为这个问题不应该用计算机解决。 大家有兴趣可以试试写个程序计算上面的数学表达式。 |
| 返回顶楼 | |
|
发表时间：2010-07-28
这个算典型的奇技淫巧了吧
|
| 返回顶楼 | |
|
发表时间：2010-07-28
显式地使用变量和隐式使用变量有区别吗？
就为了突显能力强？ |
| 返回顶楼 | |
|
发表时间：2010-07-28
congdepeng 写道 如果是你，怎么解答这道题目呢？ 不过给出的递归来计算单链表的方法还是很巧妙的。 值得记住这个方法。 |
| 返回顶楼 | |
|
发表时间：2010-07-28
linchao198401 写道 我也说个面试题，上次去SAP面试的时候问我的。
写个程序，求以下表达式的值 1/1 + (1 + 2)/ (1 * 2) + (1 + 2 + 3) / (1 * 2 * 3) + ... + (1 + 2 + .. + n) / (1 * 2 * ..* n) 我当时看了，觉得这个怎么也是数学题，跟程序有什么关系。怎么说应该有个公式能把这个转换成一个很简单的表达式，然后可以得出精确的值。想了很久，因为数学很多都忘记了，就觉得很不爽，然后就说我不会。 面试官就说，那好，面试到此为止。 所以不会这个题目，说明我不是一个好软件工程师啊。。 然后说，我离开的时候，他对同事说，排列组合都不会。。。 后来回家之后，老婆给出了一个程序，当然运行是可以运行，我还是觉得是不够精确的，因为除法之后很多的精确度就消失了。应该是有数学的办法可以解决才对的。我死死的以为这个问题不应该用计算机解决。 大家有兴趣可以试试写个程序计算上面的数学表达式。 这个题太直白了吧。
public static float t(int n){
if(n==1){
return 1;
}else{
float product = 1, sum = 0;
for(int i=0;i<n+1;i++){
product = product*n;
sum = sum+n;
}
return sum/product +t(n-1);
}
}
|
| 返回顶楼 | |
|
发表时间：2010-07-28
linchao198401 写道 congdepeng 写道 linchao198401 写道 evanmeng 写道
int lll(node* p) {
if (!p->next)
return 1;
return 1 + lll(p->next);
}
这算不用临时变量吗？ 我是感觉这种方式用的临时变量就更多了。 不是表面中没有int number就是没有使用临时变量的。 如果把题目改成，如果不声明int number的方式，如何得到单链表的长度。 如果在Java中，调用函数的时候，就会把this和函数的参数放入栈的变量列表中。这些也算是临时变量的一种的。 理论上来说，使用int number的速度(迭代)怎么也比递归快了。 只要判断p->next是不为空，就可以对number不断的加1，直到null为止。 一般都是要多想想能不能迭代，而不是想想能不能递归吧。递归写出来的程序都是比较接近数学的公式，更容易被人所理解的。 如果是你，怎么解答这道题目呢？ 我的概念里面就没有不需要临时变量就能得到链表长度的程序。 链表的长度难道不是临时变量？难道是链表自身就带有的变量？都是临时创建出来，然后赋值的。 当然你可以说面试官要的是代码里面没有临时变量。 那么如果用动态语言，直接提供返回单链表的长度，那还要什么临时变量，直接就是linkedList.length()就可以啦。 所以这个面试题。。。我不会。 然后面试官就会觉得，你连递归都不会啊。然后我就无语，说没有临时变量真的不会，然后我就离开面试现场。 同样是不会，但是要看思想的广度。 有的是真不会，有的是知道的太多了而不会。 |
| 返回顶楼 | |
|
发表时间：2010-07-28
linchao198401 写道 congdepeng 写道 linchao198401 写道 evanmeng 写道
int lll(node* p) {
if (!p->next)
return 1;
return 1 + lll(p->next);
}
这算不用临时变量吗？ 我是感觉这种方式用的临时变量就更多了。 不是表面中没有int number就是没有使用临时变量的。 如果把题目改成，如果不声明int number的方式，如何得到单链表的长度。 如果在Java中，调用函数的时候，就会把this和函数的参数放入栈的变量列表中。这些也算是临时变量的一种的。 理论上来说，使用int number的速度(迭代)怎么也比递归快了。 只要判断p->next是不为空，就可以对number不断的加1，直到null为止。 一般都是要多想想能不能迭代，而不是想想能不能递归吧。递归写出来的程序都是比较接近数学的公式，更容易被人所理解的。 如果是你，怎么解答这道题目呢？ 我的概念里面就没有不需要临时变量就能得到链表长度的程序。 链表的长度难道不是临时变量？难道是链表自身就带有的变量？都是临时创建出来，然后赋值的。 当然你可以说面试官要的是代码里面没有临时变量。 那么如果用动态语言，直接提供返回单链表的长度，那还要什么临时变量，直接就是linkedList.length()就可以啦。 所以这个面试题。。。我不会。 然后面试官就会觉得，你连递归都不会啊。然后我就无语，说没有临时变量真的不会，然后我就离开面试现场。 LinkedList.size()  前阵子一直在用
|
| 返回顶楼 | |
|
发表时间：2010-07-28
最后修改：2010-07-28
引用 [quote="linchao198401"]我也说个面试题，上次去SAP面试的时候问我的。
写个程序，求以下表达式的值 1/1 + (1 + 2)/ (1 * 2) + (1 + 2 + 3) / (1 * 2 * 3) + ... + (1 + 2 + .. + n) / (1 * 2 * ..* n) 我当时看了，觉得这个怎么也是数学题，跟程序有什么关系。怎么说应该有个公式能把这个转换成一个很简单的表达式，然后可以得出精确的值。想了很久，因为数学很多都忘记了，就觉得很不爽，然后就说我不会。 面试官就说，那好，面试到此为止。 所以不会这个题目，说明我不是一个好软件工程师啊。。 然后说，我离开的时候，他对同事说，排列组合都不会。。。 后来回家之后，老婆给出了一个程序，当然运行是可以运行，我还是觉得是不够精确的，因为除法之后很多的精确度就消失了。应该是有数学的办法可以解决才对的。我死死的以为这个问题不应该用计算机解决。 大家有兴趣可以试试写个程序计算上面的数学表达式。 这个好像没有什么简化的数学表达式，能简化成： 1 + 求和[i = 2 -> n ] {(i + 1) / (2 * (i - 1)!) } |
| 返回顶楼 | |
|
发表时间：2010-07-28
dongya1987 写道 linchao198401 写道 我也说个面试题，上次去SAP面试的时候问我的。
写个程序，求以下表达式的值 1/1 + (1 + 2)/ (1 * 2) + (1 + 2 + 3) / (1 * 2 * 3) + ... + (1 + 2 + .. + n) / (1 * 2 * ..* n) 我当时看了，觉得这个怎么也是数学题，跟程序有什么关系。怎么说应该有个公式能把这个转换成一个很简单的表达式，然后可以得出精确的值。想了很久，因为数学很多都忘记了，就觉得很不爽，然后就说我不会。 面试官就说，那好，面试到此为止。 所以不会这个题目，说明我不是一个好软件工程师啊。。 然后说，我离开的时候，他对同事说，排列组合都不会。。。 后来回家之后，老婆给出了一个程序，当然运行是可以运行，我还是觉得是不够精确的，因为除法之后很多的精确度就消失了。应该是有数学的办法可以解决才对的。我死死的以为这个问题不应该用计算机解决。 大家有兴趣可以试试写个程序计算上面的数学表达式。 这个题太直白了吧。
public static float t(int n){
if(n==1){
return 1;
}else{
float product = 1, sum = 0;
for(int i=0;i<n+1;i++){
product = product*n;
sum = sum+n;
}
return sum/product +t(n-1);
}
}
首先，sum/product肯定会导致最终的结果和实际应该的结果越来越偏离的。所以我当时想不出好办法，就觉得应该有个数学公式可以成立，然后使得那些损失的精度可以收集回来。 其次，你用的是递归，一般在用递归的时候就要想想是否可以用迭代替换，这个题目可以用迭代的。 for 1 .. n; select j; temp 1 = for (1 ..J) +; temp 2 = for (1 .. j) *; temp 3 = temp1 / temp2; temp3 +; end for 这个是最简单的，但是不够优化。 因为temp1从1 + 2, 到1 + 2 + 3等等中，重复计算了1 + 2，可以使用前一个temp1 + J应该就等于这次的temp1了。 当然temp3没有办法重复使用，因为每次都是临时结果，也是不精确的结果。在科学计算里面肯定不可以这样的。 如果修改成上面我说的办法，整个时间复杂度应该是O(N)就可以了。 |
| 返回顶楼 | |
|
发表时间：2010-07-28
linchao198401 写道 dongya1987 写道
public static float t(int n){
if(n==1){
return 1;
}else{
float product = 1, sum = 0;
for(int i=0;i<n+1;i++){
product = product*n;
sum = sum+n;
}
return sum/product +t(n-1);
}
}
首先，sum/product肯定会导致最终的结果和实际应该的结果越来越偏离的。所以我当时想不出好办法，就觉得应该有个数学公式可以成立，然后使得那些损失的精度可以收集回来。 其次，你用的是递归，一般在用递归的时候就要想想是否可以用迭代替换，这个题目可以用迭代的。 for 1 .. n; select j; temp 1 = for (1 ..J) +; temp 2 = for (1 .. j) *; temp 3 = temp1 / temp2; temp3 +; end for 这个是最简单的，但是不够优化。 因为temp1从1 + 2, 到1 + 2 + 3等等中，重复计算了1 + 2，可以使用前一个temp1 + J应该就等于这次的temp1了。 当然temp3没有办法重复使用，因为每次都是临时结果，也是不精确的结果。在科学计算里面肯定不可以这样的。 如果修改成上面我说的办法，整个时间复杂度应该是O(N)就可以了。 哦 我倒没想这么多 |
| 返回顶楼 | |
