西西河

主题:【纪事】失败的苹果面试(上) -- landlord

共:💬133 🌺776
分页树展主题 · 全看首页 上页
/ 9
下页 末页
          • 家园 好代码自己会说话

            记得我们初学编程的时候,各位同学都在力求找到最优算法,写出最精简的代码,结果就导致有时候很难读懂。后来才渐渐意识到写代码还是简单质朴为好。所谓“重剑无锋,大巧不工”:-)

            上面这段代码,我大概会这样写:

            int fib(int n)

            {

            assert(n>0);

            int a1=1, a2=1, a3;

            if (n == 1) return a1;

            if (n == 2) return a2;

            for (int i = 3; i <= n; i++)

            {

            a3=a1+a2;

            a1=a2; a2=a3;

            }

            return a3;

            }

            编译出的机器代码应该是一样的,但是人读起来就更容易了。数列中相邻3个值的关系表达得很清楚。

          • 家园 兄台做得非常不错,赞一个

            细细一想,同事问这道题还是很有道理的。

            能用递归做出来的,起码说明思路清晰;能转换成循环的,说明有优化的意识,对于我们这种写企业级软件的,这两点都很重要。

            曾经有一位牛人(这人数学一定学得很不错)给出另类答案:

            double x = (1 + sqrt(5))/2;

            Fib(n) = (x^n - (1-x)^n)/sqrt(5);

            这是一个数学上简洁完美的答案,可是在计算机世界里,这是最优解吗?


            本帖一共被 1 帖 引用 (帖内工具实现)
            • 家园 这个是通项公式

              通常我遇到这种问题,都会首先想到通项公式,然后就是查表,最后才是常规方法。

            • 家园 对于公式求解

              有rounding的问题,所以最好是要舍入到最接近的那个整数才可以。要判断数学公式求解的优劣,就必须知道库函数x^n是如何实现的。因为库函数可以处理n非整数的情况,所以我估计是用数学里的一些逼近来求近似值,估摸着循环个几十次总是有必要的吧。但是可以用lgn算法,即按照n的二进制表示的位来迭代计算,所以我倾向于这个lgn的算法。如果实在不喜浮点表示的近似,可以用fibonacci迭代的矩阵表示。顺便问一下大牛,哪位知道那些数学函数在计算机里是怎么实现的?比如log,sin这些大概迭代多少次?

            • 家园 这题好像有点简单。

              要考递归和循环,可以让写1个比如n个数的全排列之类,让用递归和循环各实现一遍。

              这题80%的人做不出来,老外的平均水平也有点汗,不过人家牛的人也真牛,关键是有兴趣,人家的牛人是真热爱写程序,不像中国许多人做IT类工作只是为了工资相对还算比较高,当然中国的基础教育水平还是挺高的。

              还有人家的程序牛人四五十岁还在踏踏实实写程序,中国的程序牛人基本30岁就不怎么写程序了,一般都是挂着1个什么总的头衔,干起玩PPT,耍嘴皮子,坑蒙拐骗的勾当了。

              • 家园 循环稍有难度

                递归真的是基本人人会做了。不过要求非递归而且不用queue之类来展示存储的我还真没见人问过。可以用alphabetical order来生成下一个,或者用gray code。唉,俺压箱底准备impress下面试官的都毫无保留的告诉大家了。如果你有兴趣,请参看Knuth第四卷关于permutation的那一册。

            • 家园

              这哥们记得这个...汗啊...

        • 家园 是九连环那个数列么?

          那玩意儿有啥用啊?

        • 家园 80+15+10=

          105

    • 家园 那个苹果母牛怎么无缘无故就跳了出来?

      故事没开头???

    • 家园 花地主一个,呵呵。

      类似事情我也碰到过,有些面试官只会问自己懂的东西,不管你申请的是什么简历。

      当年有家公司,我去面试服务端开发,对方老问我mfc的问题,把我都问烦了。

    • 家园 也说说我某次失败的经历

      当地的龙头老大E公司招聘,去面试的时候怀里已揣了T公司的聘书,所以有些心不在焉.

      考管:你认为现场最需要注意的是什么?

      我:XX设备...

      之后的问题能听得出很俗套,一出门我就感到最关键的问题上犯了低级错误.对于工程技术人员来说,什么最重要:安全第一!

分页树展主题 · 全看首页 上页
/ 9
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河