山石网科面试

code4lala发布于2019/03/15 14:17

原创文章

上午面试山石网科。

面试前先给了一套卷子做,先问我更熟悉C++还是Java呀,当然是C++。

本来看这公司名字,来之前把计算机网络给复习了一下,结果那卷子上的题好多操作系统的,计算机网络的也有,少。可惜操作系统没复习。(以后应该先认真仔细看看公司简介的

印象比较深的一题是C++的,给定i为6,求代码的输出结果,大概长这样:

void f(int i){
    if(++i<=6||i++<7||i++<8||++i<9){
        //...
    }
    i++;
    cout<<i;
}

当然是11了。

如果长这样呢:

void f(int i){
    if(++i<=6||i++<7||i++<=8||++i<9){
        //...
    }
    i++;
    cout<<i;
}

那就变成10了,因为到i++<=8时候判断为真后边就不判断了,因为逻辑运算是或,一个为真就可以了。

卷子上还有两道写代码的,第一题是给定编码方式让写一个解码功能,题目大概是这样:

'1'=>'3'
'2'=>'5'
...

我就写了个这样的。

string decode(const string & s) {
    string ans = "";
    for (char x : s) {
        switch (x)
        {
        case '3':ans += '1'; break;
        case '5':ans += '2'; break;
        // ...
        default:
            ans += x;
            break;
        }
    }
    return ans;
}

感觉没啥问题。

第二个写代码的题目是判断一个链表存储的字符串是不是回文序列,要求时间复杂度为O(n),空间复杂度为O(1)。

不知道怎么将时间复杂度控制到O(n),就按照常规思路一个一个判断了,时间复杂度为O(n^2),就不上代码了。

比较诧异的是最后一题竟然是初等数论的题,之前校招题里边还没见过有这种题呢。不过考虑到这是个安全公司应该挺合理的。

题目说一个监狱管理员管理监狱里的囚犯,给他们吃饭时一个桌子坐三个人会多两个,坐5个人多4个,坐7个人多6个,坐9个人多8个,坐11个人正好,求囚犯最少多少人。

题目抽象成数学公式就是这样子的:

其中a、b、c、d、e、n均为正整数,求最小的n

先简化条件了当然:

那么进一步有:

即有:

很显然了,用欧拉定理:

然后倒着推:

那么答案就是

然后面试,先自我介绍,讲了一下大学几年自己都干了啥,做了啥,学了啥。

完事问了我做的校园网客户端的一些东西,都是自己一行一行敲出来的当然问啥答啥。

接着考了一道题:

求一个集合的所有子集,比如说{1,2}有四个子集:空集、{1}、{2}、{1,2}。

先画了一个树,表示遍历过程:

AVGr4I.png

然后写代码:

void loop(int* array, int index, const set<int> &s) {
    set<int> s1 = s;
    set<int> s2 = s;
    s2.insert(array[index]);
    loop(array, index + 1, s1);
    loop(array, index + 1, s2);
}

然后面试官问:递归出口呢?

(尴尬。太紧张给忘了。

然后加上递归出口:

void loop(int* array, int index, const set<int> &s) {
    if(index >= n) return;
    set<int> s1 = s;
    set<int> s2 = s;
    s2.insert(array[index]);
    loop(array, index + 1, s1);
    loop(array, index + 1, s2);
}

面试官:我要的结果呢?你怎么不输出啊?

void loop(int* array, int index, const set<int> &s) {
    if (index >= n) {
        // cout<< ...... 
        return;
    }
    set<int> s1 = s;
    set<int> s2 = s;
    s2.insert(array[index]);
    loop(array, index + 1, s1);
    loop(array, index + 1, s2);
}

然后就完事了,面试官说我思路很清晰。

其实还能改,当时紧张没想起来。

空间复杂度降低:(不过这样时间复杂度就提升了耶,好像没什么实质性改进

void loop(int* array, int index, bool *b) {
    if (index >= n) {
        cout << "result: ";
        for (int i = 0; i < n; i++) {
            if (b[index])cout << array[index];
        }
        cout << endl;
    }
    b[index] = false;
    loop(array, index + 1, b);
    b[index] = true;
    loop(array, index + 1, b);
}