Aillieo Collection

SUBTITLE

0%

面试回顾

发表于 更新于 分类于

最近面试中遇到的一些题目，其中一些答的不满意的和不会答的，在此记录下来，包含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<T,U>是无序还是有序？

无序索引，其实现基于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设计与实现》