网易互娱游戏研发面试

#3.15网易互娱面试

##自我介绍

##游戏

1. 你觉得你参与游戏研发有什么优势?

基础知识

1. 讲一下C++的三大特性封装、继承和多态

封装可以使得代码模块化,继承可以扩展已存在的代码,他们的目的都是为了代码重用。而多态的目的则是为了接口重用

  • 封装:封装是在设计类的一个基本原理,是将抽象得到的数据和行为(或功能)相结合,形成一个有机的整体,也就是将数据与对数据进行的操作进行有机的结合,形成“类”,其中数据和函数都是类的成员。

  • 继承:如果一个类别B“继承自”另一个类别A,就把这个B称为“A的子类”,而把A称为“B的父类别”也可以称“A是B的超类”。继承可以使得子类具有父类别的各种属性和方法,而不需要再次编写相同的代码。在令子类别继承父类别的同时,可以重新定义某些属性,并重写某些方法,即覆盖父类别的原有属性和方法,使其获得与父类别不同的功能。

    1. 访问权限

      • public: 父类对象内部、父类对象外部、子类对象内部、子类对象外部都可以访问。
      • protected:父类对象内部、子类对象内部可以访问,父类对象外部、子类对象外部都不可访问。
      • private:父类对象内部可以访问,其他都不可以访问。

      |访问对象|public|protected|private|
      |-|-|-|-|
      |父类|可见|可见|可见|
      |子类|可见|可见|不可见|
      |父类外部|可见|不可见|不可见|
      |子类外部|可见|不可见|不可见|

    2. 继承方式
      ps.三种继承方式不影响子类对父类的访问权限,子类对父类只看父类的访问控制权。继承方式是为了控制子类(也称派生类)的调用方(也叫用户)对父类(也称基类)的访问权限。public、protected、private三种继承方式,相当于把父类的public访问权限在子类中变成了对应的权限。 如protected继承,把父类中的public成员在本类中变成了protected的访问控制权限;private继承,把父类的public成员和protected成员在本类中变成了private访问控制权。

      ps.友元是类级别的,不存在继承的问题。

  • 多态:多态性可以简单地概括为“一个接口,多种方法”,程序在运行时才决定调用的函数,它是面向对象编程领域的核心概念。多态(polymorphism),字面意思多种形状。

    1. 静态多态:静态多态也称为静态绑定或早绑定。编译器在编译期间完成的,编译器根据函数实参的类型(可能会进行隐式类型转换),可推断出要调用那个函数,如果有对应的函数就调用该函数,否则出现编译错误。

      • 函数重载

        编译器根据函数不同的参数表,对同名函数的名称做修饰,然后这些同名函数就成了不同的函数(至少对于编译器来说是这样的)。函数的调用,在编译器间就已经确定了,是静态的。也就是说,它们的地址在编译期就绑定了(早绑定)。

      • 泛型编程

        泛型编程就是指编写独立于特定类型的代码,泛型在C++中的主要实现为模板函数和模板类。
        泛型的特性:

          1. 函数模板并不是真正的函数,它只是C++编译生成具体函数的一个模子。
          1. 函数模板本身并不生成函数,实际生成的函数是替换函数模板的那个函数,比如上例中的add(sum1,sum2),这种替换是编译期就绑定的。
          3. 函数模板不是只编译一份满足多重需要,而是为每一种替换它的函数编译一份。
          4. 函数模板不允许自动类型转换。
          5. 函数模板不可以设置默认模板实参。比如template <typename T=0>不可以。
        
    2. 动态多态
      c++的动态多态是基于虚函数的。对于相关的对象类型,确定它们之间的一个共同功能集,然后在基类中,把这些共同的功能声明为多个公共的虚函数接口。各个子类重写这些虚函数,以完成具体的功能。客户端的代码(操作函数)通过指向基类的引用或指针来操作这些对象,对虚函数的调用会自动绑定到实际提供的子类对象上去。

    3. 宏多态(?)
      带变量的宏可以实现一种初级形式的静态多态:

      #include <iostream>
      #include <string>
      
      // 定义泛化记号:宏ADD
      #define ADD(A, B) (A) + (B);
      
      int main()
      {
          int i1(1), i2(2);
          std::string s1("Hello, "), s2("world!");
          int i = ADD(i1, i2);                        // 两个整数相加
          std::string s = ADD(s1, s2);                // 两个字符串“相加”
          std::cout << "i = " << i << "/n";
          std::cout << "s = " << s << "/n";
      }
      
    4. 动态多态和静态多态的比较

      1. 静态多态
        • 优点:
          1. 由于静多态是在编译期完成的,因此效率较高,编译器也可以进行优化;
          2. 有很强的适配性和松耦合性,比如可以通过偏特化、全特化来处理特殊类型;
          3. 最重要一点是静态多态通过模板编程为C++带来了泛型设计的概念,比如强大的STL库。
        • 缺点:
          1. 由于是模板来实现静态多态,因此模板的不足也就是静多态的劣势,比如调试困难、编译耗时、代码膨胀、编译器支持的兼容性不能够处理异质对象集合
      2. 动态多态
        • 优点:
          1. OO设计,对是客观世界的直觉认识;
          2. 实现与接口分离,可复用
          3. 处理同一继承体系下异质对象集合的强大威力
        • 缺点:
          1. 运行期绑定,导致一定程度的运行时开销;
          2. 编译器无法对虚函数进行优化
          3. 笨重的类继承体系,对接口的修改影响整个类层次;
      3. 不同点:
        • 本质不同,早晚绑定。静态多态在编译期决定,由模板具现完成,而动态多态在运行期决定,由继承、虚函数实现;
        • 动态多态中接口是显式的,以函数签名为中心,多态通过虚函数在运行期实现,静态多台中接口是隐式的,以有效表达式为中心,多态通过模板具现在编译期完成
      4. 相同点:
        • 都能够实现多态性,静态多态/编译期多态、动态多态/运行期多态;
        • 都能够使接口和实现相分离,一个是模板定义接口,类型参数定义实现,一个是基类虚函数定义接口,继承类负责实现;

2. 虚函数、纯虚函数

- 概述

    它虚就虚在所谓“推迟联编”或者“动态联编”上,一个类函数的调用并不是在编译时刻被确定的,而是在运行时刻被确定的。由于编写代码的时候并不能确定被调用的是基类的函数还是哪个派生类的函数,所以被成为“虚”函数。

    虚函数只能借助于指针或者引用来达到多态的效果。常用的方式是父类指针指向子类对象。当有多个对于父类的继承时,可以统一用父类指针来表示各子类对象,但是事实上所指向的对象具体是哪一个,或者说所调用的函数是哪一个子类的对象的函数需要在运行时才知道。这就实现了多态。

    ```c
    class A
    {
        public:
            virtual void foo()
            {
                cout<<"A::foo() is called"<<endl;
            }
    };
    class B:public A
    {
        public:
            void foo()
            {
                cout<<"B::foo() is called"<<endl;
            }
    };
    int main(void)
    {
        A *a = new B();
        a->foo();   // 在这里,a虽然是指向A的指针,但是被调用的函数(foo)却是B的!
        return 0;
    }
    ```

- 语法

    ```c
    virtual void fun1()=0 //纯虚函数
    virtual void fun1()  // 虚函数
    ```

- 纯虚函数
    纯虚函数是在基类中声明的虚函数,它在基类中没有定义,但要求任何派生类都要定义自己的实现方法。含有虚函数的类成为抽象类,不能生成对象。
- 虚函数表
    虚表是属于类的,而不是属于某个具体的对象,`一个类只需要一个虚表即可` 。同一个类的所有对象都使用同一个虚表。为了指定对象的虚表,对象内部包含一个虚表的指针,来指向自己所使用的虚表。为了让每个包含虚表的类的对象都拥有一个虚表指针,编译器在类中添加了一个指针,*__vptr,用来指向虚表。这样,当类的对象在创建时便拥有了这个指针,且这个指针的值会自动被设置为指向类的虚表。
    C++的编译器应该是保证虚函数表的指针存在于对象实例中最前面的位置(这是为了保证取到虚函数表的有最高的性能——如果有多层继承或是多重继承的情况下)。

3. 引用和指针的区别

指针-对于一个类型T,T* 就是指向T的指针类型,也即一个T*类型的变量能够保存一个T对象的地址,而类型T是可以加一些限定词的,如const、volatile等等。
引用-引用是一个对象的别名,主要用于函数参数和返回值类型,符号X&表示X类型的引用。

  • 不同点:

    本质: 指针指向一块内存,它的内容是所指内存的地址;而引用则是某块内存的别名,引用不改变指向。

    1. 引用不可以为空,但指针可以为空。定义一个引用的时候,必须初始化。因此使用指针之前必须做判空操作,而引用就不必。
    2. 引用不可以改变指向,对一个对象"至死不渝";但是指针可以改变指向,而指向其它对象。
    3. 引用的大小是所指向的变量的大小,因为引用只是一个别名而已;指针是指针本身的大小,4个字节(32位)。
    4. const int* p-> 指向常量的指针,int * const p->本身是常量的指针.后者需要在定义的时候初始化。对于引用来讲int const & p=i;和 const int &p=i;没什么区别,都是指指向的对象是常量。
    5. 引用和指针的++自增运算符意义不同,指针的++表示的地址的变化,一般是向下4个字节的大小(一个只针的大小),引用的++就是对应元素的++操作。
    6. 指针传递和引用传递
      • 指针传递参数本质上是值传递的方式,它所传递的是一个地址值。值传递过程中,被调函数的形式参数作为被调函数的局部变量处理,即在栈中开辟了内存空间以存放由主调函数放进来的实参的值,从而成为了实参的一个副本。值传递的特点是被调函数对形式参数的任何操作都是作为局部变量进行,不会影响主调函数的实参变量的值。
      • 引用传递过程中,被调函数的形式参数也作为局部变量在栈中开辟了内存空间,但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址,即通过栈中存放的地址访问主调函数中的实参变量。正因为如此,被调函数对形参做的任何操作都影响了主调函数中的实参变量。

4. 深拷贝和浅拷贝(值拷贝和位拷贝)

对于build-in类型来说,复制是简单的,都是开辟新的内存,将对应的值放入新开辟的位置即可,之后他们不再有关系(指针类型就是地址的复制,和指向的地方没关系)。
对于类而言,如果存在指针和引用类型,(const类型?),需要考虑自己来写拷贝构造函数和重载=操作符。

  • 浅拷贝(位拷贝)
    指将一个对象的内存映像按位原封不动的复制给另一个对象,所谓值拷贝就是指,将原对象的值复制一份给新对象。 在用"bitwise assignment"时会直接将对象的内存映像复制给另一个对象,这样两个对象会指向同一个内存区域,当一个对象被释放后,另一个对象的指针会成为野指针(悬垂指针)。这时,就应该编写operator=和copy constructor来实现值拷贝 。
    默认的拷贝构造函数”和“缺省的赋值函数”均采用“位拷贝”而非“值拷贝”的方式来实现,倘若类中含有指针变量,这两个函数注定将出错。

  • 深拷贝(值拷贝)
    在“深拷贝”的情况下,对于对象中动态成员,就不能仅仅简单地赋值了,而应该重新动态分配空间。

  • 产生复制的场景:

    1. 建立一个新对象,并用另一个同类的已有对象对新对象进行初始化
    2. 当函数的参数为类的对象时,这时调用此函数时使用的是值传递,也会产生对象的复制
    3. 函数的返回值是类的对象时,在函数调用结束时,需要将函数中的对象复制一个临时对象并传给改函数的调用处

    这里通过查资料存疑, 默认拷贝构造函数基本工作原理:对所有的非POD类型成员变量执行拷贝构造,POD类型成员变量则进行位拷贝,当成员变量都是POD类型的时候,编译器也许不会产生拷贝构造函数,只是对对象进行位拷贝。 默认operator=基本工资原理:对所有的非POD类型成员变量执行operator=操作,POD类型成员变量则进行位拷贝,当成员变量都是POD类型的时候,编译器也许不会产生operator=,只是对对象进行位拷贝。 从上面两个工作原理看到: 1.当class成员变量是有const修饰、引用类型、不能够提供operator=操作(例如boost::nocopyable)时候就不会产生operator=,我们对这个class对象进行赋值操作的时候就是编译出错。 2.当class成员变量是不能够提供拷贝构造操作(例如boost::nocopyable)时候就不会产生拷贝构造函数,我们对这个class对象进行拷贝构造操作的时候就是编译出错。 以前(2005年前?)c++各种参考文献对构造、析构和拷贝关注较多的是“深拷贝”和“浅拷贝”问题,现在的c++可能考虑更多的是如何保证不被拷贝^_^(个人见解)。

5. python用过吗?

6. TCP和UDP的区别及应用场景

  • 区别

    1. 面向连接VS无连接
      TCP建立一个连接需要3次握手IP数据包,断开连接需要4次握手。另外断开连接时发起方可能进入TIME_WAIT状态长达数分钟(视系统设置,windows一般为120秒),在此状态下连接(端口)无法被释放。
      UDP不需要建立连接,可以直接发起。
    2. 可靠VS不可靠
      TCP利用握手、ACK和重传机制,udp没有。
      1,校验和(校验数据是否损坏);
      2,定时器(分组丢失则重传);
      3,序列号(用于检测丢失的分组和重复的分组);
      4,确认应答ACK(接收方告知发送方正确接收分组以及期望的下一个分组);
      5,否定确认(接收方通知发送方未被正确接收的分组);
      6,窗口和流水线(用于增加信道的吞吐量)。(窗口大小:无需等待确认应答而可以继续发送数据的最大值)
    3. 有序性
      TCP利用seq序列号对包进行排序,udp没有。
    4. 面向字节流vs面向报文
      • 面向报文
        面向报文的传输方式是应用层交给UDP多长的报文,UDP就照样发送,即一次发送一个报文。因此,应用程序必须选择合适大小的报文。若报文太长,则IP层需要分片。UDP对应用层交下来的报文,既不合并,也不拆分,而是保留这些报文的边界。这也就是说,应用层交给UDP多长的报文,UDP就照样发送,即一次发送一个报文。(一个upd的最大报文长度2^16-1-20-8,20是ip报文头,8是udp报文头)
      • 面向字节流
        面向字节流的话,虽然应用程序和TCP的交互是一次一个数据块(大小不等),但TCP把应用程序看成是一连串的无结构的字节流。TCP有一个缓冲,当应用程序传送的数据块太长,TCP就可以把它划分短一些再传送。如果应用程序一次只发送一个字节,TCP也可以等待积累有足够多的字节后再构成报文段发送出去。
    5. tcp有流量控制,udp没有
    6. tcp的头部比20bytes,udp8byres
  • TCP应用场景:
    效率要求相对低,但对准确性要求相对高的场景。因为传输中需要对数据确认、重发、排序等操作,相比之下效率没有UDP高。举几个例子:文件传输(准确高要求高、但是速度可以相对慢)、接受邮件、远程登录。

  • UDP应用场景:
    效率要求相对高,对准确性要求相对低的场景。举几个例子:QQ聊天、在线视频、网络语音电话(即时通讯,速度要求高,但是出现偶尔断续不是太大问题,并且此处完全不可以使用重发机制)、广播通信(广播、多播)。

7. TCP连接的建立和断开

8. 死锁的条件及解决的办法

  • 死锁的条件
    必须同时存在以下的四个条件才能发生死锁。

    1. 互斥条件
      即某个资源在一段时间内只能由一个进程占有,不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器,打印机等等,必须在占有该资源的进程主动释放它之后,其它进程才能占有该资源。这是由资源本身的属性所决定的。
    2. 不可抢占条件。
      进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放。
    3. 占有且申请条件。
      进程至少已经占有一个资源,但又申请新的资源;由于该资源已被另外进程占有,此时该进程阻塞;但是,它在等待新资源之时,仍继续占用已占有的资源。
    4. 循环等待条件
      存在一个进程等待序列{P1,P2,...,Pn},其中P1等待P2所占有的某一资源,P2等待P3所占有的某一源,......,而Pn等待P1所占有的的某一资源,形成一个进程循环等待环。
  • 死锁的预防
    死锁的预防是保证系统不进入死锁状态的一种策略。

  1. 破坏互斥条件
    有些资源不能被共享。--没用
    2. 破坏不可抢占条件。
    可抢占式,即要求申请失败的进程释放自己占有的资源给别人用,降低系统性能。
    3. 破坏占有且申请条件。
    直接申请自己所需要的所有资源。--1.不可预知自己需要什么资源 2.资源利用率低,长期占有自己可能不用的资源。
    4. 破坏循环等待条件
    资源分类、编号,按序申请。 --·1.编号可能是困难的,维护相应的序列是困难的
  • 死锁的避免
    死锁的避免指的是不限制进程有关申请资源的命令,而是对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配。
    银行家算法。当一个进程申请使用资源的时候,银行家算法通过先 试探 分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若不安全则试探分配作废,让该进程继续等待。

判定安全状态需要已分配资源、还需要的资源、可用资源、finish判定符

9. 复杂度为O(nlogn)的排序算法有哪些?是否稳定?选一个讲一下

  1. 快速排序
  2. 归并排序
  3. 堆排序

10. 介绍一下哈希表?哈希函数中如果碰到冲突如何解决?

哈希表(Hash Table,也叫散列表),是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。哈希表的实现主要需要解决两个问题,哈希函数和冲突解决。

  • 哈希函数
    哈希函数也叫散列函数,它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构,同时散列结果应当具有同一性(输出值尽量均匀)和雪崩效应(微小的输入值变化使得输出值发生巨大的变化)。

  • 冲突解决
    链地址法的基本思想是,为每个 Hash 值建立一个单链表,当发生冲突时,将记录插入到链表中。

11. 设计模式了解吗?

SOLID
S(单一功能原则Single responsibility principle)规定每个类都应该有一个单一的功能,并且该功能应该由这个类完全封装起来。所有它的(这个类的)服务都应该严密的和该功能平行(功能平行,意味着没有依赖)。
O(开闭原则)软件中的对象(类,模块,函数等等)应该对于扩展是开放的,但是对于修改是封闭的。
L(里氏替换原则Liskov Substitution principle)派生类必须能完全取代其基类
I(接口隔离原则interface-segregation principle) 客户不依赖于他不使用的方法。
D(控制反转原则Inversion of Control)高层级的模块不应该依赖于低层级的模块,他们应该都依赖于抽象。细节依赖于抽象,而不是抽象依赖于细节。
依赖注入:Class A中用到了Class B的对象b,一般情况下,需要在A的代码中显式的new一个B的对象。
采用依赖注入技术之后,A的代码只需要定义一个私有的B对象,不需要直接new来获得这个对象,而是通过相关的容器控制程序来将B对象在外部new出来并注入到A类里的引用中。而具体获取的方法、对象被获取时的状态由配置文件(如XML)来指定。

二叉树的先序遍历、中序遍历、后续遍历

1. 如何判断链表是否有环

快慢指针:定义两个指针,同时从链表的头节点出发,一个指针一次走一步,另一个指针一次走两步。如果走得快的指针追上了走得慢的指针,那么链表就是环形链表;如果走得快的指针走到了链表的末尾(next指向 NULL)都没有追上第一个指针,那么链表就不是环形链表。
map:如果不考虑空间复杂度,可以使用一个map记录走过的节点,当遇到第一个在map中存在的节点时,就说明回到了出发点,即链表有环,同时也找到了环的入口。

所以寻找环入口的方法就是采用两个指针,一个从表头出发,一个从相遇点出发,一次都只移动一步,当二者相等时便是环入口的位置

2. 如何判断链表是否相交

我们可以从头遍历两个链表。创建两个栈,第一个栈存储第一个链表的节点,第二个栈存储第二个链表的节点。每遍历到一个节点时,就将该节点入栈。两个链表都入栈结束后。则通过top判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道,若两个链表相交,则从第一个相交节点开始,后面的节点都相交。
若两链表相交,则循环出栈,直到遇到两个出栈的节点不相同,则这个节点的后一个节点就是第一个相交的节点。

  • 遍历链表记录长度。
    同时遍历两个链表到尾部,同时记录两个链表的长度。若两个链表最后的一个节点相同,则两个链表相交。
    有两个链表的长度后,我们就可以知道哪个链表长,设较长的链表长度为len1,短的链表长度为len2。
    则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表,当遍历到的链表的节点相同时,则这个节点就是第一个相交的节点。

如何用两个栈实现一个队列

二叉树的广度优先搜索

二叉树的深度优先搜索

一个整数数组,一个整数n,如何判断数组中是否存在两个数的和等于n

3. 有m个玩家,取游戏排行榜中排名前k的玩家进行决斗,如何选取

快排:只排
容量为k最大堆

  1. 游戏的帧率为60帧,每秒更新六十次,每次都要上传玩家数据,假设上传一次需要100ms,但是一次上传最多16ms,如何解决
  2. 开服创建账号时,需要对玩家在数据库中的ID进行分配(数据库只有一个,但玩家会被分配到多个物理机中进行处理),每个新玩家创建都需要去数据库中查找,如何减少查找数据库的次数(提示,一台物理机向数据库请求一千条ID,下一台请求下一千条ID,当一千条分配完后再向数据库请求)
  3. 玩家战斗结束后根据积分更新排行榜,在排行榜太大更新速度慢的情况下如何实时更新玩家排名(提示:可以区分粒度)
  4. 阴阳师的进度条如何实现?当一个式神的回合结束后进度条如何变化?有没有影响进度条的情况?

有什么想问的

  1. 实习进去之后会接触到什么技术?
    主要是使用python语言,引擎可能会使用C++,没有python基础不影响,但是最好先自学
  2. 如何知道自己是否通过面试?
    等待通知,五到十个工作日之内,目前只面了几个,还不能确定

我的凉了的和没凉的面试记录地址(持续更新),https://github.com/darkmoon233/GreenPills-CSNotes

#实习##面经##网易互娱##C++工程师##游戏研发工程师#
全部评论
我上午刚面完基础架构部。。。也被问到了哈希表与top k问题
点赞 回复
分享
发布于 2019-03-25 15:59
厉害
点赞 回复
分享
发布于 2019-03-25 16:00
乐元素
校招火热招聘中
官网直投
大佬牛逼
点赞 回复
分享
发布于 2019-03-25 16:18
这个帖子是真的棒
点赞 回复
分享
发布于 2019-03-25 16:21
设计模式不是问 单例模式、观察者模式那些的吗
点赞 回复
分享
发布于 2019-03-25 16:24
不错的,讲得比较细
点赞 回复
分享
发布于 2019-04-02 11:59
最后几题是怎么做的呢?就是关于游戏的,我自己的想法是这样的
点赞 回复
分享
发布于 2019-04-02 12:20
这问的题和我面的重复率好高啊
点赞 回复
分享
发布于 2019-04-08 15:07
点赞 回复
分享
发布于 2019-04-11 12:07
请问第三部分的第一题和第三题大佬怎么解决的啊?
点赞 回复
分享
发布于 2019-04-14 11:54
很详细
点赞 回复
分享
发布于 2019-08-16 23:22
好贴!
点赞 回复
分享
发布于 2019-08-21 09:30
这面经也太良心了8
点赞 回复
分享
发布于 2019-09-18 10:56

相关推荐

41 308 评论
分享
牛客网
牛客企业服务