2018-10-04 · Tools

每个程序员1小时内必须解决的5个编程问题

每个程序员1小时内必须解决的5个编程问题

这篇文章很久以前就看过了,也做过里面的题目,并不是认同里面的观念,只是单纯的想做下里面的题目。

下面是文章原文:

每次我发布软件工程师的岗位工作要求,各种求职申请就会纷至沓来,接踵而至。但每每让我困惑的是,似乎总有那么几位应聘者完全不明白所谓“编程”的意思。
5-problems-programmer-1-hour

当然,他们另有想法。

而我认为,如果你应聘的是“Web前端开发”岗位,那么你只懂jQuery也可以胜任,那么,“软件工程师”是不是就意味着会HTML、JavaScript和CSS这些必备技能就行了呢?

(我觉得那些聊起XML、JSON、XSLT、SOAP、HTTP、REST、SSL和200多个首字母缩写词来头头是道,但却不会区分整型和浮点型数据类型的家伙很有意思。呵呵)

你真的会写代码吗?

对于应聘程序员的求职人员,我,作为用人单位,首先希望的是你会写代码。我指的是真正的代码:我给你一个问题,你使用任何你觉得舒适的编程语言给出它的解决方案。

你真的能做到这一点吗?

策略:如果你不能在1小时以内解决以下5个问题,那么你首先要做的是重新审视自己。的确,或许你各方面的工作都干的不错,但是我依然觉得你现在还不配“软件工程师(或程序员,计算机科学专家,甚至是“开发人员”)”这个头衔。不要自欺欺人,先花点时间来调整你的重点吧。

5个问题

问题1

使用for循环、while循环和递归写出3个函数来计算给定数列的总和。

问题2

编写一个交错合并列表元素的函数。例如:给定的两个列表为[a,B,C]和[1,2,3],函数返回[a,1,B,2,C,3]。

问题3

编写一个计算前100位斐波那契数的函数。根据定义,斐波那契序列的前两位数字是0和1,随后的每个数字是前两个数字的和。例如,前10位斐波那契数为:0,1,1,2,3,5,8,13,21,34。

问题4

编写一个能将给定非负整数列表中的数字排列成最大数字的函数。例如,给定[50,2,1,9],最大数字为95021。

问题5

编写一个在1,2,…,9(顺序不能变)数字之间插入+或-或什么都不插入,使得计算结果总是100的程序,并输出所有的可能性。例如:1 + 2 + 34 – 5 + 67 – 8 + 9 = 100。
如果你能力超群,上面这些问题对你而言只是小菜一碟,1小时之内解决完全绰绰有余的话,请将我的慷慨陈词当作是在放屁。

不过,如果你觉得本文对你很有帮助的话,欢迎分享,并留下您宝贵的见解。Thank for reading。

我的思路

问题1

略。。。

问题2

问题2使用数组解决,直接上代码

    static String[] question2(String[] o1, String[] o2) {
        String[] result = new String[o1.length + o2.length];
        for (int i = 0; i < o1.length; i++) {
            result[i * 2] = o1[i];
        }
        for (int i = 0; i < o2.length; i++) {
            result[i * 2 + 1] = o2[i];
        }
        return result;
    }

问题3

问题3的解法是很多的, 百度 或者 Google 都能找到很多的答题方式,这里主要记录下数组的方式。

寻找编程环境的边界

int 型:

    /**
     * 用迭代法寻找编程环境支持的最大整数(int型)的斐波那契数是第几个斐波那契数
     * @return
     */
    public int max_int_iteration() {
        int a = 1, b = 1, c = 2;
        int count = 3;
        // 一旦c达到编程环境最大斐波那契数,便会产生内存溢出,从而变成一个负数,到此循环结束
        while (b < c){
            a = b;
            b = c;
            c = a + b;
            count++;
        }
        return count;
    }
    // 最大是第 47 个数

long 型:

    /**
     * 用迭代法寻找编程环境支持的最大整数(long型)的斐波那契数是第几个斐波那契数
     * @return
     */
    public long max_int_iteration() {
        long a = 1, b = 1, c = 2;
        long count = 3;
        // 一旦c达到编程环境最大斐波那契数,便会产生内存溢出,从而变成一个负数,到此循环结束
        while (b < c){
            a = b;
            b = c;
            c = a + b;
            count++;
        }
        return count;
    }
    // 最大是第 93 个数    

考虑性能,首先数学公式

公式的推导请自行搜索,下图为公式的具体实现:

fibonacci-formula

    static String question3(int n) {
        double temp = Math.sqrt(5.0);
        double result = (1 / temp) * (Math.pow((1 + temp) / 2, n) - Math.pow((1 - temp) / 2, n));
        DecimalFormat format = new DecimalFormat("#");
        return format.format(result);
    }

使用数组解决公式的误差计算

        BigInteger[] arr = new BigInteger[100];
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                arr[0] = BigInteger.ZERO;
            }
            if (i == 1) {
                arr[i] = BigInteger.ONE;
            }
            if (i > 1) {
                arr[i] = arr[i - 1].add(arr[i - 2]);
            }
        }
        System.out.println(Arrays.toString(arr));

问题4

这道题主要是重写数组的排序规则

        Integer[] arr = {50, 2, 1, 9};
        Arrays.sort(arr, (o1, o2) -> ("" + o2 + o1).compareTo("" + o1 + o2));
        System.out.println(Arrays.toString(arr));

问题5

首先列出所有的排列组合

    static Set<String> add(Set<String> set, String op) {
        Set<String> result = new HashSet<>();
        for (String line : set) {
            result.add(line + op);
        }
        return result;
    }

    static void question5() throws ScriptException {
        String[] arr = {"1", "2", "3", "4", "5", "6", "7", "8", "9"};
        String[] ops = {"+", "-", ""};
        Set<String> set = new HashSet<>();
        // 穷举所有排列组合
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                set.add(arr[i]);
                continue;
            }
            Set<String> newSet = new HashSet<>();
            for (String o : ops) {
                newSet.addAll(add(set, o));
            }
            set = newSet;
            set = add(set, arr[i]);
        }
        // 循环计算组合的结果,脚本引擎
        for (String line : set) {
            if (100 == eval(line)) {
                System.out.println(line + " = 100");
            }
        }
    }

然后使用脚本引擎去计算结果

    static ScriptEngineManager scriptEngineManager = new ScriptEngineManager();

    static ScriptEngine scriptEngine = scriptEngineManager.getEngineByName("JavaScript");

    static int eval(String script) throws ScriptException {
        return Double.valueOf(scriptEngine.eval(script).toString()).intValue();
    }

总结

从题目来看第一题就没啥说的了,第二、三、四题都是对数组的灵活运用。其中并没用到多么高深的数据结构或者是算法等。其实我们自己所学的已经能解决实际场景中的大部分需求,重要的是如何去简化需求和考虑边界问题,将问题考虑全面。