金山WPS2016春季实习校园招聘笔试&面试问题回忆

恋喵大鲤鱼

发布于 2018-08-03 14:45:50

6870

发布于 2018-08-03 14:45:50

文章被收录于专栏：C/C++基础

下面将我在广州参加的2016年春季金山WPS实习招聘的整个过程中遇到的问题记录如下。不全，但是有些题目还是值得思考的。

1.笔试题

2016.4.11晚上在中山大学东校区（大学城校区）参加了金山WPS的笔试。记忆较为深刻的有如下几题。

题目一： 以下代码片段，输出的结果是什么？

    vector<int> vec(5);
    cout<<vec.size()<<endl;    //1
    vec.reserve(100);
    cout<<vec.size()<<endl;    //2
    vec.resize(50);
    cout<<vec.size()<<endl;    //3
    cout<<vec.capacity()<<endl;//4

本题考察的是vector向量容器的成员函数reserve()和resize()的作用和区别。reserve()用来改变vector向量容器的容量，即vec.capacity()的返回值。resize()用于改变vector的元素数量。所以代码中1,2,3,4的输出依次是：5，5，50，100。

题目二： 这是一道编程题，求三个矩形的交集矩形。给定矩形的定义如下：

struct Rect{
    int x; //表示矩形的左上水平坐标
    int y; //表示矩形的左上垂直坐标
    int w; //表示矩形宽度
    int h; //表示矩形高度
};

现在给三个矩形，求三个矩形的交集，如果没有交集，那么矩形的x，y，w和h均赋值为-1。例如下面示例图，求出三个矩形相交的粗线线框表示的矩形。

解题思路： 解题思路很重要，没有集体思路，题目肯定是做出不来的。下面给出本人的解题思路：（1）判断三个矩形有没有交集。这个是难点，该怎么做呢？可以在x轴方向将三个矩形按x的大小从左到右排列，判断两两矩形在x轴方向是否有交集，如果有任意一对没有相交那么三个矩形没有交集。判断方法是如果rectB.x>=rectA.x+rectA.w的话，那么说明rectA和rectB之间没有交集。

同理，在y轴方向做同样的判断；

（2）求出任意两个矩形的交集矩形，再将交集矩形与第三个矩形再求交集，可得最后的交集矩形。

有了正确和清晰的思路，就可以写代码了，下面给出本人的实现，可供网友参考。

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

struct Rect{
    int x; //表示矩形的左上水平坐标
    int y; //表示矩形的左上垂直坐标
    int w; //表示矩形宽度
    int h; //表示矩形高度
};

//按照x递增排序
bool compareX(const Rect& rectA,const Rect& rectB ){
    return rectA.x<rectB.x;
}

//按照y递增排序
bool compareY(const Rect& rectA,const Rect& rectB ){
    return rectA.y<rectB.y;
}

//判断三个矩形是否相交
bool isIntersect(const Rect& rectA,const Rect& rectB,const Rect& rectC){
    Rect rectLeft,rectXMid,rectRight; //从左向右的矩形
    Rect rectTop,rectYMid,rectBelow;  //从上到下的矩形

    //将矩形按照x由左向右排序
    vector<const Rect> vec;
    vec.push_back(rectA);
    vec.push_back(rectB);
    vec.push_back(rectC);
    sort(vec.begin(),vec.end(),compareX);
    rectLeft=vec[0],rectXMid=vec[1],rectRight=vec[2];

    //水平方向任意两个矩形没有交集
    if(rectXMid.x>=rectLeft.x+rectLeft.w||rectRight.x>=rectXMid.x+rectXMid.w||rectRight.x>=rectLeft.x+rectLeft.w)
        return false;

    //同理将矩形按照y由上往下排序
    sort(vec.begin(),vec.end(),compareY);
    rectTop=vec[0],rectYMid=vec[1],rectBelow=vec[2];

    //垂直方向任意两个矩形没有交集
    if(rectYMid.y>=rectTop.y+rectTop.h||rectBelow.y>=rectYMid.y+rectYMid.h||rectBelow.y>=rectTop.y+rectTop.h)
        return false;
    return true; //三个矩形有交集
}

//两个矩形的交集，前提是两个矩形一定有交集
Rect intersection(const Rect& rectA,const Rect& rectB){
    Rect resRect;
    resRect.x=rectA.x>rectB.x?rectA.x:rectB.x; //选最右边的矩形的x作为交集的x
    resRect.y=rectA.y>rectB.y?rectA.y:rectB.y; //选最下面的矩形的y作为交集的y
    //选择左边矩形（x坐标较小者）的右边的作为交集矩形的右边，这样就可以求出交集矩形的宽度
    resRect.w=rectA.x+rectA.w<rectB.x+rectB.w?rectA.x+rectA.w-resRect.x:rectB.x+rectB.w-resRect.x;
    //同理，选择上面矩形（y坐标较小者）的下边的作为交集矩形的下边，这样就可以求出交集矩形的高度
    resRect.h=rectA.y+rectA.h<rectB.y+rectB.y?rectA.y+rectA.h-resRect.y:rectB.y+rectB.h-resRect.y;
    return resRect;
}


//求三个矩形的交集
Rect threeIntersection(const Rect& rectA,const Rect& rectB,const Rect& rectC){
    Rect res;
    bool isIntersectBool=isIntersect(rectA,rectB,rectC);
    if(isIntersectBool){ //有相交
        Rect rectAB=intersection(rectA,rectB);
        res=intersection(rectAB,rectC);
    }
    else
        res.x=res.y=res.w=res.h=-1;
    return res;
}

测试结果如下：

int main(){
    Rect rectA,rectB,rectC;
    //测试案例1
    //rectA.x=0,rectA.y=0,rectA.w=1,rectA.h=1;
    //rectB.x=1,rectB.y=1,rectB.w=1,rectB.h=1;
    //rectC.x=2,rectC.y=2,rectC.w=1,rectC.h=1;

    //测试案例2
    rectA.x=0,rectA.y=0,rectA.w=2,rectA.h=2;
    rectB.x=1,rectB.y=1,rectB.w=1,rectB.h=1;
    rectC.x=1,rectC.y=1,rectC.w=1,rectC.h=1;

    Rect resRect=threeIntersection(rectA,rectB,rectC);
    if(resRect.x!=-1){ //有相交
        cout<<"resRect.x:"<<resRect.x<<endl;
        cout<<"resRect.y:"<<resRect.x<<endl;
        cout<<"resRect.w:"<<resRect.x<<endl;
        cout<<"resRect.h:"<<resRect.x<<endl;
    }
    else
        cout<<"not intersect"<<endl;
    getchar();
}

测试案例1输出：not intersect；测试案例2输出： resRect.x:1 resRect.y:1 resRect.w:1 resRect.h:1

2.一面试题

2016.4.16日在大学城华工校内教学楼A5参加了XX的面试。有些题目记不太清了，简要记录我记得的题目。

一面大概经历30分钟的时间，问了C++基础知识和项目的一些问题，总体来说难度不大。

问题一： 请先自我介绍吧！答：介绍了我是在校学生，在校期间主要学习和研究的方面。

问题二： 你用过define吧，define的作用以及inline与其的区别。答： define用于宏定义，inline用于定义内联函数。二者的区别是inline定义的内联函数在使用时直接进行替换，（像宏一样展开），没有了调用的开销，效率也很高。但是内联函数也是一个真正的函数，编译器在调用一个内联函数时，会首先检查它的类型安全，避免了宏定义容易出错的缺点。

问题三： 申明一个返回值为void的函数原型，使得该函数能够接受函数体内申请的char*字符串。答：其实这一道题就是考察不通过返回值如何接受指针类型的变量。使用二重指针或者引用即可。函数原型可申明如下： void func(char*& str);

问题四： 使用过C++的操作符重载吧，你现在申明一个类的赋值操作符重载成员函数的原型。答：加入给定类为class A，那么赋值操作符重载成员函数的原型可申明如下： A& operator=(const A& a);

问题五： 请问平时用什么IDE进行开发，VS用过吧，你知道什么是内存断点吗？答：内存断点的介绍见：VS2012使用条件断点和内存断点。

问题六： 你用过只能指针吧，写一个简单的使用示例。答：

class A;
scopted_ptr<A> spA(new A());

其他问题是在是记不起来，不过都是一些基本的C++的基础知识点而已。

3.二面试题

二面的整个过程是由一个问题展开的，主要是一些算法和数据结构的描述。最开始的问题描述如下：

颜色可由RGB来表示，R，G，B对应的取值是0-255，那么RGB色彩模式可以表示256∗256∗256=224=16M(1M=1024)256*256*256=2^{24}=16M(1M=1024)中颜色，大概1600万多种颜色。现在给一个文本文件，里面记录的是RGB颜色信息，记录的格式大概如下:

255,0,0;255,0,0;0,255,0;0,0,255;...

现在要求你统计出文件中颜色出现次数前十的颜色是什么？

答：（1）使用map容器，存储颜色和颜色出现的次数。颜色的ID使用RGB三原色对应的数值拼接在一起构成一个字符串。比如颜色255,0,0，那么该颜色可以表示成：”255000000”。（2）现在要做的就是对map中的键值对pair<colorID,count>按照count进行递减排序，取出前十个count对应的颜色即可。但是由于map是按照键值的大小来排序的，所以要按照值来排序的话，需要进行拷贝至vector向量容器中再排序。

其实可以直接将键值对存储在vector中，但是这样每次查找颜色的时候会时间复杂度会比较答，所以还是采取上面的策略。

问题二： 除了上面的这个办法，还有什么更好办法呢？比如不适用STL的话。答：不使用STL中的容器的话，我们可以将颜色值作为数组的下标，来统计每一个颜色出现的次数。具体做法是RGB对应的值作为一个int的低位的三个字节，那么数组长度就是256∗256∗256=224=16M256*256*256=2^{24}=16M。如果使用int数组来存储颜色出现的次数，那么这个数组的空间大小就是16M*sizeof(int)=64M，这个空间对于堆来说完全没有问题，最后再对数组进行遍历取出前十个次数最多的颜色即可。

注意，这里是不能对数组进行排序的，因为颜色使用数组的下标进行表示的，如果排序那么颜色出现的次数与颜色就不能相互对应了。

问题三： 既然你这么喜欢map，那你写一段map容器的删除代码吧，用来删除出现指定次数的颜色。答：平时没怎么使用map来删除容器中的元素，根据记忆，不假思索的就写出了如下的代码：

//假设删除出现次数为2的颜色
map<string,int > countMap;//存放颜色与出现次数的map容器
for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it){
        if(it->second==2){
            countMap.erase(it);
        }
}

问题四： （面试官看了一下）你觉的你写的代码有问题吗？答：面试官出这道背后肯定隐藏着坑，等着我去跳，主要考察我对STL容器的使用的熟练程度。当时没有想出来，就说没问题。回来一查，果然有个巨坑，STL容器的删除和插入操作隐藏的陷阱主要有如下两条。

（1）对于节点式容器(map, list, set)元素的删除，插入操作会导致指向该元素的迭代器失效，其他元素迭代器不受影响；（2）对于顺序式容器(vector，string，deque)元素的删除、插入操作会导致指向该元素以及后面的元素的迭代器失效。

所以，在删除一个元素的时候，是没有什么问题的。即：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it){
        if(it->second==2){
            countMap.erase(it);
            break;
        }
}

但是，当删除多个出现相同次数的颜色时，程序会出现崩溃。原因是通过迭代器删除指定的元素时，指向那个元素的迭代器将失效，如果再次对失效的迭代器进行++操作，则会带来未定义行为，程序崩溃。解决方法有二，还是以上面的map容器为例，示例删除操作的正确实现：

方法一： 当删除特定值的元素时，删除元素前保存当前被删除元素的下一个元素的迭代器。

map<string,int >::iterator nextIt=countMap.begin();
for(map<string,int>::iterator it=countMap.begin();;){
        if(nextIt!=countMap.end())
            ++nextIt;
        else break;
        if(it->second==2){
            countMap.erase(it);
        }
        it=nextIt;
    }

如何更加简洁的实现该方法呢？下面给出该方法的《Effective STL》一书的具体实现：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();){
        if(it->second==2){
            countMap.erase(it++);
        }else
            ++it;
    }

该实现方式利用了后置++操作符的特性，在erase操作之前，迭代器已经指向了下一个元素。

再者我查了map.erase()返回指向紧接着被删除元素的下一个元素的迭代器，所以可以实现如下：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();){
        if(it->second==2){
            it=countMap.erase(it);
        }else
            ++it;
}

方法二： 当删除满足某些条件的元素，可以使用remove_copy_if & swap方法。当然，方法一的满足特性值是满足某些条件的特例，因此，也可以应用此方法。

那么如何通过remove_copy_if 删除 map< string,int>中的元素呢？网上很少有给出map的实现，一般都是以vector为例。所以这里给出我的实现。

在通过remove_copy_if 按照条件拷贝了需要的元素之后，如何实现两个map的交换，可以直接调用map的成员函数swap。参考代码：

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <iterator>  

using namespace std;

map<string,int> mapCount;

//不拷贝的条件
bool notCopy(pair<string,int> key_value){
    return key_value.second==1;
}

int main(){
    mapCount.insert(make_pair("000",0));
    mapCount.insert(make_pair("001",1));
    mapCount.insert(make_pair("002",2));
    mapCount.insert(make_pair("003",1));

    map<string,int> mapCountTemp;//临时map容器
    //之所以要用inserter()函数是因为通过调用insert()成员函数来插入元素，并由用户指定插入位置
    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notCopy);

    mapCount.swap(mapCountTemp);//实现两个容器的交换

    cout<<mapCount.size()<<endl;     //输出2
    cout<<mapCountTemp.size()<<endl; //输出4

    //验证
    //正确输出:
    //000 0
    //002 2
    for(map<string,int>::iterator it=mapCount.begin();it!=mapCount.end();++it){
        cout<<it->first<<" "<<it->second<<endl;
    }

    getchar();
}

这种方法的缺点：虽然实现两个map的交换的时间复杂度是常量级，一般情况下，拷贝带来的时间开销会大于删除指定元素的时间开销，并且临时map容器也增加了空间的开销。

总结： 关于容器的删除，有篇blog总结的很好，现在转贴如下：

删除容器中具有特定值的元素： （1）如果容器是vector、string或者deque，使用erase-remove的惯用法。如果容器是list，使用list::remove。如果容器是标准关联容器，使用它的erase成员函数。

删除容器中满足某些条件的元素： （2）如果容器是vector、string或者deque，使用erase-remove_if的惯用法。如果容器是list，使用list::remove_if。如果容器是标准关联容器，使用remove_copy_if & swap 组合算法，或者自己协议个遍历删除算法。参考资料：李健《编写高质量C++代码》第七章，用好STL这个大轮子。

问题五： 你知道STL中容器的迭代器的底层实现机制吗？答：平时只是少量的用过一些容器，还真没有深入的去了解过，所以没答出来。

提到STL，必须要马上想到其主要的6个组成部件，分别是：容器、算法、迭代器、仿函数、适配器和空间分配器，本文主要介绍迭代器。迭代器是连接容器和算法的一种重要桥梁。

STL中容器迭代器的本质是类对象，其作用类似于数据库中的游标（cursor），除此之外迭代器也是一种设计模式。我们可以对它进行递增（或选择下一个）来访问容器中的元素，而无需知道它内部是如何实现的。其行为很像指针，都可以用来访问指定的元素。但是二者是完全不同的东西，指针代表元素的内存地址，即对象在内存中的存储位置；而迭代器则代表元素在容器中的相对位置。

C++的迭代器简单实现示例： 要自定义一个迭代器，就要重载迭代器一些基本操作符：*（解引用）、++（自增）、==（等于）、!=（不等于）、=（赋值）。以便它在range for语句中使用。range for 是C++11中新增的语句，如我们对一个集合使用语句for （auto i : collection ）时，它的含义其实为：

for(auto __begin = collection.begin(),auto __end = collection.end();__begin!=__end;++__begin)
{ 
    i = *__begin;
    ...//循环体
}

begin和end是集合的成员函数，它返回一个迭代器。如果让一个类可以有range for的操作，它必须满足以下几条：（1）拥有begin和end函数，它们均返回迭代器，其中end函数返回一个指向集合末尾，但是不包含末尾元素的值，即用集合范围来表示，一个迭代器的范围是 [ begin, end ）一个左闭右开区间。

（2）必须重载++、！=和解引用（*）运算符。迭代器看起来会像一个指针，但是不是指针。迭代器必须可以通过++最后满足！=条件，这样才能够终止循环。

下面给出最简单的实现代码。我们定义一个CPPCollection类，里面有个字符串数组，我们让它能够通过range for将每个字符串输出来。

　　class CPPCollection {
public:
//迭代器类
    class Iterator{
    public:
        int index;//元素下标
        CPPCollection& outer;
        Iterator(CPPCollection &o, int i):outer(o), index(i){}

        void operator++(){
            index++;
        }
        std::string operator*() const{
            return outer.str[index];
        }
        bool operator!=(Iterator i){
            return i.index!=index;
        }
    };

public:
    CPPCollection(){
        string strTemp[10]={"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};
        int i=0;
        for(auto strIt:strTemp)
            str[i++]=strIt;
    }

    Iterator begin(){
        return Iterator(*this,0);
    }
    Iterator end(){
        return Iterator(*this, 10);
    }

private:
    std::string str[10];
};

我们定义了个内部的嵌套类Iterator,并为它重载了++、*、！=运算符。由于C++中的内部嵌套类与外围的类没有联系，为了访问外部类对象的值，我们必须要传入一个引用（或指针，本例中传入引用）。Iterator的自增方法其实就是增加内部的一个索引值。判断！=的方法是和另外一个迭代器做比较，这个迭代器一般是集合的末尾，当我们的索引值等于末尾的索引值end时，认为迭代器已经达到了末尾。在CPPCollection类中，定义了begin（）、end（）分别返回开头、结束迭代器，调用如下代码：

　　CPPCollection cpc;
　　for (auto i : cpc){
    　　std::cout <<i<<std::endl;
　　}
　　//或者
　　CPPCollection cpc;
　　for(CPPCollection::Iterator i= cpc.begin();i!=cpc.end();++i){
        std::cout<<*i<<std::endl;
   }

即可遍历集合中的所有元素了。

在泛型算法中，为了对集合中的每一个元素进行操作，我们通常要传入集合的迭代器头、迭代器尾，以及谓词，例如std::find_if（vec.begin（）， vec.end（）， …），这种泛型算法其实就是在迭代器的首位反复迭代，然后运行相应的行为。

4.小结

金山WPS的面试让我发现了自己的很多知识盲点，给我本人也敲响了警钟。好好学习，好好总结吧。断断续续历时一个星期才完成了本blog。有点痛苦，靡不有初鲜克有终，凡是贵在坚持，最终还是坚持了下来。

面对求职应聘，丰富的项目经验和专业性质的比赛获奖会给简历锦上添花（简历筛选）；扎实的算法与数据结构基础和过硬的编程能力是通过在线编程（笔试环节）的不二法门；全面而深入的编程语言知识点是通过面试的可靠保障（面试环节）。

静心复习，努力备战！

参考文献

[1]如何删除C++容器中的值. [2]STL容器删除元素的陷阱. [3]STL中各种容器的删除操作. [4]std::map::erase. [5]inserter.cplusplus reference. [6]插入型迭代器(Insert Iterator)或插入器(inserter). [7] inserter、back_inserter、front_inserter. [8]http://www.cplusplus.com/reference/map/map/swap/. [9]http://www.cppblog.com/haosola/archive/2014/08/25/208128.aspx. [10]百度百科.迭代器. [11]编写高质量代码：改善C++程序的150个建议.李健.机械工业出版社.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016年04月17日，如有侵权请联系 cloudcommunity@tencent.com 删除

容器

ios

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

容器

ios

登录后参与评论

0 条评论

热度