阿里巴巴校园招聘——灵犀互娱、游戏研发工程师、一面面经

╰半夏微凉° 2022-09-04 06:41 682阅读 0赞

今天下午，参加了阿里巴巴、灵犀互娱、游戏研发工程师的一面，感觉提问的问题不是很难，但是可能基础不是很好，并且游戏这方面接触的也比较少，所以面试的表现不是很好。

面试集中在以下几个方面：

# 1. C++基础知识 #

### 构造函数是否可以作为虚函数？ ###

答案：构造函数是不可以作为虚函数的。  
为什么呢？

1.  因为构造函数是，需要确定对象的类型，而虚函数是在运行期间确定类型的，因此编译器无法知道是要构造基类对象，还是构造派生类的对象，因此构造函数不可以是虚函数。
2.  虚函数的执行依赖于虚函数表，而虚函数表是在构造函数中进行初始化工作的，即初始化vptr，指向正确的虚函数表。在构造期间，虚函数表还没有生成，因此不能将构造函数设为虚函数。

### 多态的原理 ###

通过基类引用或指针调用一个虚函数时，根据对象是基类对象还是派生类对象，调用相应的基类或派生类的函数。

通过虚函数表来实现。

# 2. 如何实现一个游戏中任务？ #

怎么存储数据的？  
如何实现交互？

# 3. 如何实现一个游戏中的排行榜？ #

这个当时面试的考虑了一个很憨的数据结构，想通过 一层中转，引入一倍的空间，实现根号n级别的复杂度，但是想了想，通用性很不方便。

## （1）假设战力上限最高千万级别，而且玩家数量比较多 ##

后来想想，引入一层中转不够用，也不够灵活，那么引入多层中转呢，这不就是 一个二叉排序树了吗，从最大的区间一层层的往下划分，直到将所有战力值区间都给划分了。

假设战力值最高为百万、千万级别，这种方法引入的空间开销为节点数的两倍，大概几百兆级别，差不多够用了。

**更新排行榜：**  
二叉排序树，插入和删除的复杂度都是O（log(n)）级别的从对应的战力值区间进行向上更新，也算是比较快速了。

**查询个人排名：**  
这个计算一个树上前面的区间的数量即可，复杂度O(log(n))。

**退化问题：**  
可以考虑使用红黑树来进行优化，防止退化。

**数组模拟实现简单的二叉排序树：**

class Node {
          //树节点
    	constructor(value) {
        
    	    this.value = value
    		this.left = null
    		this.right = null
    	}
    }
     
    class NodeSearch {
          //搜索树
    	constructor() {
        
    	    this.root = null
    		this.len = 0
    	}
    	
    	add(key) {
         //生成节点
    		let node = new Node(key)
    		if(this.root) {
        
    			this.insertNode(this.root,node)
    		}else{
        
    			this.root = node
    		}
    		this.len++
    		return this
    	}
    	
    	insertNode(root, node) {
         //插入节点
    		if(root.value > node.value) {
        
    			root.left ? this.insertNode(root.left,node) : root.left = node 
    		}else{
        
    			root.right ? this.insertNode(root.right, node) : root.right = node;
    		}
    	}
    	
    	toTree(arr) {
         //生成树
    		if(toString.call(arr) !== "[object Array]") return false
    		for(let i=0;i<arr.length;i++) {
        
    			this.add(arr[i])
    		}
    	}
    	
    	toArray() {
        
    		let result = []
    		if(this.len > 0) {
        
    			const middleOrder = (root) => {
        
    			    root.left && middleOrder(root.left);
    			    result.push(root.value);
    			    root.right && middleOrder(root.right);
    			    return result;
    			};
    			return middleOrder(this.root);
    		}
    	}
    }
    let arr = [23,3,12,45,3]
     
    let ns = new NodeSearch()
     
    ns.toTree(arr)
    console.log(ns.toArray())

但是如果玩的人很少的话，而战力值对应的区间又很大（一刀999，战力百十亿），这种方法就比较困难了。

## （2）假设玩家比较少，而且战力百千亿 ##

一个简单的实现方法：

1.  先用快速排序等算法进行初始化，复杂度O(n\*log(n))。
2.  每次调整，直接使用冒泡排序的思路（排行榜变化感觉大多数情况下都是逐渐变化，因此利用冒泡排序的特性，这种较好情况的复杂度可以接受，毕竟人不多）

## （3）如果玩家百亿，而且战力百万亿（想法很好） ##

怎么搞呢，我没有想出一种能很好解决的方法，大佬们提示一下。

# 4. 其他 #

除了这些问题以外，剩下的就是问了问大学期间有哪些具有挑战性的事件等等 。  
基本的开场自我介绍。  
结束的有哪些想要继续了解的。

## 总体感受 ##

自己表现的并不是很好。

首先，C++的基础不够牢固，很多C++的知识点没有答上来，面试官和我都表示很尴尬  
\{  
面试官：怎么回事，小老弟？我这个热场问题你都不行？  
我：菜鸡瑟瑟发抖，不敢说话。  
// 回去后一定要奋发图强，恶补基础。  
\}

其次，除了游戏开发这方面不是很了解以外，基础的算法和应变能力也不是很强，希望能继续努力。