算法⼯程师笔试真题总结旷视科技2019
target =set()
data = data*2
for i in data:
if i in target:
print(i,sum-i)
else:
target.add(sum-i)
print("not find")
出⼀个数组中出现次数超过半数的元素(保证答案存在)
int moore_voting(vector<int>&num)
{
int curIdx =0, count =1;
for(int i =1; i < num.size();++i)
{
num[i]== num[curIdx]?++count :--count;
if(!count)
{
curIdx = i;
count =1;
}
}
return num[curIdx];
from collections import Counter
def Findelement(arr):
obj = collections.Counter(arr)
return[k for k,v in obj.items()if v >len(arr)/2]
iHandy2019校招
import sys
sys.setrecursionlimit(100000000)
global count
count =0
def fib(n):
global count
count = count +1
print(count)
if n==0:
return1
elif n==1:
return2
else:
return fib(n-1)+fib(n-2)
fib(9)
print(count)
或者观察规律：从n=3开开始，调⽤次数为前两次和加1
f(3) =f(2) +f(1) +1=5
f(4) =f(3) +f(4) +1=9
f(5) =f(4) +f(3) +1=15
f(6) =f(5) +f(4) +1=25
程序员接活的平台网站f(7) =f(6) +f(5) +1=41
f(8) =f(7) +f(6) +1=67
f(9) =f(8) +f(7) +1=109
PCA属于确定性算法，Kmeans属于不确定性算法
已知⼆叉树的前序序列是ABCDEFGH，中序序列是CBEDFAGH，其后序序列是?
CEFDBHGA
CPU利⽤率：运⾏的程序占⽤的CPU资源，表⽰机器在某个时间点的运⾏程序的情况。使⽤率越⾼，说明机器在这个时间上运⾏了很多程序，反之较少。
CPU是负责运算和处理的，内存是交换数据的。
1.可以看出CPU利⽤率低；3.I/O设备利⽤率低（减少多道程序的度数）
1.可以看出CPU利⽤率低；3.I/O设备利⽤率低（减少多道程序的度数）
CPU⼀次读取的太多的程序放⼊内存中，因此需要降低多道程序的度数
2.交换空间的磁盘利⽤率⾼（增⼤内存的容量）
交换空间利⽤率⾼，因此需要扩⼤数据交换空间（增⼤内存的容量）
A. AVL树是最先发明的⾃平衡⼆叉查树。在AVL树中任何节点的两个⼦树的⾼度最⼤差别为⼀，所以它也被称为⾼度平衡树。查、插⼊和删除在平均和最坏情况下都是O(log n)。
B.伸展树(Splay Tree)，也叫分裂树，是⼀种⼆叉排序树，它能在O(log n)内完成插⼊、查和删除操作。伸展树⽀持所有的⼆叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的。
C.红⿊树(Red Black Tree) 是⼀种⾃平衡⼆叉查树，它虽然是复杂的，但它的最坏情况运⾏时间也是⾮常良好的，并且在实践中是⾼效的: 它可以在O(log n)时间内做查，插⼊和删除，这⾥的n是树中元素的数⽬。
D.在⼆叉查树中查询元素的最优时间复杂度是O(logN)即在满⼆叉树的情况下，最坏时间复杂度是O(n)即除叶⼦节点外每个节点只有⼀个⼦节点。
爱奇艺2019秋招算法⽅向笔试题
6个圆盘的汉诺塔，总的移动次数
63，6^n-1
⼴义表K=(m,n,(p,(q,s)),(h,f))，则head[tail[head[tail[tail(K)]]]]的值
head() 返回列表的第⼀个元素；
tail() 返回列表的删去第⼀个元素之后的剩余列表；
K=(m,n,(p,(q,s)),(h,f)),
head[tail[head[tail[tail(K)]]]]
tail(K)-------(n,(p,(q,s)),(h,f))
tail[tail[K]]--------((p,(q,s)),(h,f))
head()-----((p,(q,s))
tail()-----(q,s)
head()-------q
UDP包含8个字节，包头结构：源端⼝ 16位；⽬的端⼝ 16位、；长度 16位；校验和 16位
TCP包含20个字节，包头结构：源端⼝号16位；⽬的端⼝号16位；序列号32位；确认号32位；HeaderLenAndFlag 前4位：TCP头长度、中6位：保留、后6位：标志位；窗⼝⼤⼩16位
；检验和16位；紧急数据偏移量16位。序列号是指客户端确认序列号以及以前的信息都收到了，窗⼝⼤⼩则是提⾼传输效率，保证信息按序到达。
程序员编写程序时使⽤⽂件系统提供的系统调⽤将内存中由address地址开始的n个字节或n个记录的信息写⼊指定⽂件中，但发现⽂件名不可⽤，可⾏的解决办法
1.使⽤⽂件描述符代替⽂件名
2.使⽤⽂件句柄代替⽂件名
京东2019算法⼯程师
分⽀限界法思想
1.以⼴度优先或以最⼩耗费（最⼤效益）优先的⽅式搜索问题的解空间树
2.分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展结点，活结点⼀旦成为扩展结点，就⼀次性产⽣其所有⼉⼦结点，其中导致不可⾏解或导致⾮最优解的⼉⼦结点被舍弃，其余⼉⼦结点被加⼊活结点表中
然后从活结点表中取下⼀结点成为当前扩展结点
3.重复上述结点扩展过程，直⾄到到所需的解或活结点表为空时为⽌
从中可以看出，⼴度优先且不满⾜的被舍弃，满⾜的其⼉⼦节点，所以其不可能再次成为活结点
回溯法：深度优先⾃然可以回到此节点。
在邻接表不确定或者没给出的情况下，深度优先和⼴度优先均有多种可能。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。