开发岗 挂经

发表于
字数统计: 953 words | 阅读时长 ≈ 4 mins

今天面的岗位是软件开发岗位, 从网上看到的信息这个主要是用C#和.Net开发，平没有提前做准备就直接去面了…

进了大楼先是有门禁，然后电梯需要刷卡才会告知你是在第几台电梯，真是服了，面试之前居然还要填写各种表格，简直无语了，而且之前的简历也是需要你提交各种相关的资料，比如成绩单，学历证明，内心对这家公司有些失望。话不多说简单介绍以后直接进入主题。

  1. 从N的列表里面均匀分布选择M个元素，并且要求不能有重复
    思路：假设给定区间[b,e)需要从中选取m个互不重复的随机数，如果持续查找，如果已经存在则丢弃，这种效率很低。
    可以采用“筛选法”，[b,e)区间的数放到数组N，生成[0, N.size）内的一个随机数r作为A的索引，然后将A[r]剔除，重复直到找到所需数量的随机数。
1
2
3
4
5
6
7
8
9
10
11
12
13
void random_sequence(int b, int e, int n, vector<int> &ret){
	vector<int> tmp;
	for(int i = b; i < e; i++)
	{
		tmp.push_back(i);
	}
	while (ret.size() < n)
	{
		int r = rand() % tmp.size();
		ret.push_back(tmp[r]);
		tmp.erase(tmp.begin() + r);
	}
}

update: 另一种方法相当于洗牌，对当前的数组进行交换(每一个随机数的索引指向的元素和数组循环依次交换依次。最后取前面k个)

扩展：
生成随机数的方法有两种，伪随机数和真实随机。
伪随机数一般用线性同余的方法 

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
而真书随机会加入一些噪声扰动，比如：用户按键盘的位置与速度、用户运动鼠标的路径坐标。 

2. hashmap 

既然提到了这个话题，那么hashmap为什么会比list的查找效率更快？

dict 采用的是hash_map 存储形式，查找效率很高，但是不稳定，时间复杂度在O(1) ~ O(N)
而基于树结构的map时间负责度O(logN)

扩展:

python中的key的hash默认是id
```py
class A:
	def __hash__(self):
		print(id:, id(self))
		return id(self)

	def __repr__(self):
		return 'class:' + str(self.__class__)+ ',id:' + str(id(self))

a = A() 
d = {}
d[a] = 1
## id : 43887112

通过__hash__修改hash值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class B:
	def __init__(self, name):
		self.name = name 

	def __hash__(self):
		return hash(self.name)

	## update 
	def __eq__(self, r):
		if self.name == r.name:
			return True 
		else:
			return False

d  = {}
b1 = B('unlucky')
b2 = B('unlucky1')
d[b1] = 1
d[b2] = 2
b2.name = 'unlucky'
d[b2] = 3
print(d)

## 这个时候会出现三个name，因为更新字典会寻找合适的hashtable位置，key相等才会返回已有的位置
  1. multiprocessing里面异步如何进行交流的
    引入Pool 提供并行化操作，支持Queue队列和Pipes管道进行交流，同步意味着有序。
    异步：不同程序但愿之间在过程中无需通信。
    并发描述的是程序的组织结构，利用有限的计算机资源使得多个任务可以实时或近似实时处理。
    并行描述的是程序的执行状态，多个任务同时执行，利用富余资源加速完成多个任务。

总结：
并行是利用多核加速多任务完成进屋，并发是为了让独立的子任务尽快被执行，但是不一定加快整体速度。
异步是高校组织非阻塞任务的方式，

或许应了那句“面试造坦克，工作拧螺丝”这句话，但一问三不知，内功还是需要加强。