Line实习面

发表于 更新于 分类于

1. 笔试

问题1：平衡二叉树的性质（笔者菜，画蛇添足了…）

正确解答：平衡二叉树或者是棵空树，或者是具有下列性质的二叉树：

  • 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
  • 若将二叉树节点的平衡因子（Balance Factor）定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1，0，1。
  • 只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去平衡了

问题2：在浏览器中输入 www.xxxx.com 后执行的全部过程。

正确解答：

  1. 客户端浏览器通过DNS解析到 www.xxxx.com 的IP地址，然后通过TCP进行封装数据包，输入到网络层。
  2. 在客户端的传输层，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
  3. 客户端的网络层不必关心应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，就是通过查找路由表决定通过哪个路径到达服务器。
  4. 客户端的链路层，包通过链路层发送到路由器，通过邻居协议查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换IP数据包。现在就可以传输了，然后发送IP数据包到达服务器的地址。

问题3： 设计实现HashTable类。(这题博主见过两次了，都没答对，是真的菜…)

HashTable有两个问题需要解决，首先是key值哈希化，我们可以借助Python自带的hash函数解决key的哈希编码问题。其次是Hash 冲突的解决机制，在这里只考虑最简单的一种，即将同一个 hash 值下的不同的 key 存放在数组的同一个位置，以链表形式保存。

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
class MyDict(object):
	def __init__(self,size = 10000):
		self.hash_list = [list() for _ in range(size)]
		self.size = size
	def __setitem__(self,key,value):
		# 利用python自带的hash函数，对key哈希并对size取模
		# hashed_key位置没有值就追加，否则覆盖
		hashed_key = hash(key)%self.size
		for item in self.hash_list[hashed_key]:
			if item[0] == key:
				item[1] = value
				break
			else:
				self.hash_list[hashed_key].append([key,value])
	def __getitem__(self,key):
		# return: key所对应的value
		# 没有key，就抛出keyError
		for item in self.hash_list[hash(key)%self.size]:
			if item[0] == key:
				return item[1]
			raise keyError(key)
	def __repr__(self):
		# hashtable打印
		result = []
		for sub_list in self.hash_list:
			if not sub_list:
				continue
			for item in sub_list:
				result.append(str(item[0])+":"+str(item[1]))
		return "{"+",".join(result)+"}"

参考答案：不用 Python 自带的 Dict 实现自己的 HashTable

2. 面试

主要问博主与简历相关的工作与能力，后续博主会陆续更新自己的研究内容。（博主过了，但不能实习可惜…）