面试回顾

最近面试中遇到的一些题目,其中一些答的不满意的和不会答的,在此记录下来,包含Unity3D的、C#和Lua的,以及一些算法题。

Unity3D

如何控制物体的渲染顺序(哪些因素影响到渲染顺序,影响的权重如何)?

影响因素如下:

  • 相机深度(Camera depth)
  • SortingLayer
  • OrderInLayer / SortingOrder
  • RenderQueue
  • 到相机的距离

如何影响:

  1. 相机深度影响权重最大,depth值小的会更早绘制;
  2. RenderQueue小于等于RenderQueue.GeometryLast的会比大于RenderQueue.GeometryLast的先绘制(RenderQueue.GeometryLast的值是2500);
  3. 若两个对象的RenderQueue同时小于等于GeometryLast或同时大于GeometryLast,则依次依据SortingLayer、OrderInLayer/SortingOrder和RenderQueue权重从大到小排序,即:
    • 如果SortingLayer不相等,SortingLayer小者更早绘制;
    • 如果SortingLayer相等,则OrderInLayer/SortingOrder小者更早绘制(OrderInLayer/SortingOrder取值范围-32768~32767);
    • 如果SortingLayer和OrderInLayer/SortingOrder均相等,则RenderQueue小者更早绘制;
  4. 若两个对象的RenderQueue同时小于等于GeometryLast或同时大于GeometryLast,且SortingLayer、OrderInLayer/SortingOrder和RenderQueue全都相等:
    • 若RenderQueue小于等于GeometryLast,则距离相机近者更早绘制;
    • 若RenderQueue大于GeometryLast,则距离相机远者更早绘制;

补充:
MeshRenderer使用的SortingOrder,对于UGUI中的Canvas而言叫做OrderInLayer;
对于Canvas而言,如果同一个Canvas中各个节点的z坐标不同,则会选择各元素的平均位置作为距离相机的位置来参与排序;

UGUI中,Anchors和Pivot的含义和区别?

Anchors:表示RectTransform的左下角和右上角在父节点中的位置,分别对应anchorMin和anchorMax。

Pivot:RectTransform自身旋转和缩放的中心。

RectTransform.anchoredPosition是Pivot相对于Anchor的位置,如果Anchors没有重合,则会根据Pivot的位置对Anchors插值得到anchoredPosition。

C#

List是链表还是数组?

本质是数组。

Dictionary是无序还是有序?

无序索引,其实现基于hash table,线程不安全。
如果有序索引可以使用SortedList,线程安全可以使用ConcurrentDictionary。

Lua

Lua中使用table做配表时的一些优化策略?

假如现在有这样的配表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
local hero_config = {
[1000] = {
name = 1008,
icon = "hero_365_01",
initStar = 0,
initQuality = 2,
initEquip = "1001",
initSkill = "1029"
},
[1001] = {
name = 1009,
icon = "hero_368_01",
initStar = 0,
initQuality = 3,
initEquip = "1001",
initSkill = "1029:1044"
},
[1002] = {
name = 1010,
icon = "hero_363_01",
initStar = 0,
initQuality = 2,
initEquip = "1002",
initSkill = "1029"
},
[1003] = {
name = 1018,
icon = "hero_369_01",
initStar = 0,
initQuality = 2,
initEquip = "1001",
initSkill = "1029"
},
[1004] = {
name = 1020,
icon = "hero_373_01",
initStar = 0,
initQuality = 1,
initEquip = "1002",
initSkill = "1029"
}
}
  • 使用字典形式的表保存配置信息时,如果有大量的字段保存的是相同的值,可以增加“默认值”这样一行,配置每行的字段时,如果该值等于默认值,则空缺,通过元表的形式使其从默认行去取值。按照这一思路优化后:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
local hero_config = {
[1000] = {
name = 1008,
icon = "hero_365_01",
},
[1001] = {
name = 1009,
icon = "hero_368_01",
initQuality = 3,
initSkill = "1029:1044"
},
[1002] = {
name = 1010,
icon = "hero_363_01",
initEquip = "1002",
},
[1003] = {
name = 1018,
icon = "hero_369_01",
},
[1004] = {
name = 1020,
icon = "hero_373_01",
initQuality = 1,
initEquip = "1002",
}
}

local mt_default = {
__index = {
initStar = 0,
initQuality = 2,
initEquip = "1001",
initSkill = "1029"
}
}

for k,v in pairs(hero_config) do
setmetatable(v,mt_default)
end
  • 使用整数做索引。各行的字段名称单独提出来,在保存字段值时直接使用数组形式的表。读表时根据字段获取到对应值在数组中的索引位置,然后再获取字段的值。按照这一思路优化后:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
local hero_config = {
[1000] = {
1008,
"hero_365_01",
0,
2,
"1001",
"1029"
},
[1001] = {
1009,
"hero_368_01",
0,
3,
"1001",
"1029:1044"
},
[1002] = {
1010,
"hero_363_01",
0,
2,
"1002",
"1029"
},
[1003] = {
1018,
"hero_369_01",
0,
2,
"1001",
"1029"
},
[1004] = {
1020,
"hero_373_01",
0,
1,
"1002",
"1029"
}
}

local key_index = {
name = 1,
icon = 2,
initStar = 3,
initQuality = 4,
initEquip = 5,
initSkill = 6

}

local mt = {
__index = function(t,k)
return t[key_index[k]]
end
}

for k,v in pairs(hero_config) do
setmetatable(v,mt)
end

Lua中table对象包含哪些内容(由什么组成)?

lua的table中包含内容参见lua源码中Table的定义:

1
2
3
4
5
6
7
8
9
10
11
typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* log2 of size of `node' array */
struct Table *metatable;
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
GCObject *gclist;
int sizearray; /* size of `array' array */
} Table;

主要包括:

  • GC相关的信息:CommonHeader、gclist
  • 数组部分的信息:array、sizearray
  • hash部分的信息:node、lastfree、lsizenode
  • 元表和元方法的信息:metatable、flags

Lua中如何实现面向对象?

项目中lua面向对象的实现很类似云风的方法,主要思路都是把基类设为子类的元表的__index,并且把类设置为类的实例的元表的__index

如果有两个脚本互相require,会出现什么结果?

如果直接两个脚本互相require,会出现下边的错误:

1
2
3
4
5
6
7
8
9
lua: ./a.lua:2: loop or previous error loading module 'b'
stack traceback:
[C]: in function 'require'
./a.lua:2: in main chunk
[C]: in function 'require'
./b.lua:2: in main chunk
[C]: in function 'require'
main.lua:1: in main chunk
[C]: ?

使用module的方式可以有效避免这样的问题,如分别定义三个lua脚本,并执行main.lua:

1
2
3
4
5
6
7
8
9
10
11
12
-- a.lua
module("a" , package.seeall)

print("will require b")
local b = require("b")
print("did require b")

local function func(arg)
print("a says {" .. tostring(arg) .. "}")
end

return {func = func}
1
2
3
4
5
6
7
8
9
10
11
12
-- b.lua
module("b" , package.seeall)

print("will require a")
local a = require "a"
print("did require a")

local function func(arg)
a.func("b says {" .. tostring(arg) .. "}")
end

return {func = func}
1
2
3
-- main.lua
local b = require "b"
b.func("this is main")

将会输出:

1
2
3
4
5
will require a
will require b
did require b
did require a
a says {b says {this is main}}

算法题

拷贝一个链表结构

题目:一个链表结构,链表中的各个Node中,所保存的数据data是对其它Node的引用,可以是引用上游、下游的Node也可能是引用的自己,现在要将整个链表结构拷贝一份,如何操作?

1
2
3
4
5
struct Node
{
Node* next;
Node* data;
}

当时的回答(其实后来也没有想出来更好的答案):

借助一个字典保存索引关系,需要对链状结构遍历两遍,时间复杂度O(n)。

  • 第一遍遍历时,一边创建新的链表一边向字典写入,key是被复制的原始的Node,value是复制之后新得到的Node;
  • 第二遍遍历时,在新的链表中填入data数据,读取对应的原来Node的data指向的Node,从字典中获取其对应的位于新链表中的Node,并在新的链表结构中将data指向该Node。

安卓解锁手势密码,列出所有的可能

题目:解锁手势密码,数字1-9一共9个按键,密码长度为4到9位,每个数字最多出现一次。其中数字2、4、6、8和5有点特殊,连接1-3时,如果之前2没有被选过,那么会在1-3之间插入2,即1-3-2;如果之前已经有过数字2,则直接1-3。数字4、6、8和5也同理。需要列出所有的可能的密码。

当时的解法:使用一个树来保存结果,逐层添加新的数字,每次在后边加入新的元素时,需要判断是否有经过的数字(比如在1的后边填3,如果前边没有出现过2的话,则无法添加3,只能添加2)。感觉思路没有什么问题,但是当时需要在墙上把解题过程用代码写出来,后来写着写着就跪了。

图形学

shader中制作描边特效的方法

对于模型的描边,通常是借助于模板缓冲区,在单独的pass中对顶点做出一些沿法线的偏移来绘制。对于sprite的描边则不得不在片段着色器中实现。各种方法整理了一下,放在这里了。

其它

还有一些问题,是难以回答出来或者完全不知道答案的,以后有时间再慢慢学习和研究:

  • 进程间通信的方法
  • 帧同步vs状态同步
  • 群体单位移动时的算法(避免拥塞)

REFERENCE

https://docs.unity3d.com/Manual/UIBasicLayout.html

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?view=netframework-4.7.2

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

《Lua设计与实现》