面试题总结
程序员文章站
2022-07-14 14:38:28
...
面试题:
如何查找一个未知长度的链表的中间节点。
解决办法:快慢指针
定义两个指针end,mid end每次走两步,mid每次走一步,当end走到链表的末尾时,mid所在的位置就是链表的中间元素的位置。
status getMidNode(LinkList L){
LinkList p = L, mid = L;
while(p){
if(p->next == NULL){
break;
}
p = p->next->next;
mid = mid->next;
}
printf("mid->data=%d\n",mid->data);
return OK;
}
快排与冒泡的区别:
快排的思想:分治策略。
快排时间复杂度平均情况是O(nlog2n)。
冒泡的时间复杂度平均情况是O(n^2)。
空间复杂度都为O(1)。
快排不稳定,冒泡是稳定的。
二分查找的实现方式:循环和递归
循环:
def binary_search(array,value):
low = 0
high = len(array)-1
while low <= high:
mid = (low + high)//2
if value == array[mid]
return mid
if value > mid:
low = mid + 1
else:
high = mid - 1
return 0
递归:
def binary_search(array,low,high,value):
if low <= high:
mid = (low + high)//2
if value == array[mid]:
return mid
if value > mid:
binary_search(array,mid+1,high,value)
else:
binary_search(array,low,mid-1,value)
return 0
如何快速判断一个数a是否为2^n
我的想法:将这个数对2取余;
面试官:可以进行进制转换,将a与a-1转换为二进制然后按位与,如果为0就是,否则不是。
tcp/ip协议的三次握手与四次挥手:
三次握手
四次挥手:
服务器的作用:存储与计算。
第一次面试,感觉问题回答的不是很好,准备的不是很充分,主要是以一个学习的心态来对待这次的面试。