一、近期面试笔试题
- 冒泡算法 --》请手写一个冒泡算法?
- 二分查找算法 --》请用C/C++、Java、Python其中一个编程语言实现二分查找算法;给定一个有序(升序)整型数组A,可含有重复元素,找出最小的下标L,使得A[i]等于整数target,下标不存在则返回-1。
- 冒泡算法和二分查找算法在广州的笔试中经常出现,需要重点熟悉一下。
二、解析
1.请手写一个冒泡算法
这道题是我在面试广州迪奥信息科技的第一道关卡,也就是面试前的笔试题,因为没有了解过就中招了,而且在后面的面试中也被问到了,“请简单的说说冒泡算法原理”,很无奈,我只能告诉他冒泡我没有了解过,又失去了一次面试的机会。
2.冒泡算法介绍
- 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
- 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
- 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
3.算法的原理
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
4.使用Python3实现
以下为Python3代码实现冒泡算法,其他语言可自行baidu:
l=[5,3,6,2,1,4,8,7,9]
for i in range(len(l)-1):
for j in range(len(l)-1-i):
if l[j] > l[j+1]:
l[j],l[j+1] = l[j+1],l[j]
print(l)
三、二分查找算法
1.请用C/C++、Java、Python其中一个编程语言实现二分查找算法;给定一个有序(升序)整型数组A,可含有重复元素,找出最小的下标L,使得A[i]等于整数target,下标不存在则返回-1。
二分查找算法是探迹面试的第一道关卡,也是笔试题第二题,共八道题就有三道算法题,可见算法的重要性。
2.二分查找算法介绍
- 二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])。
- 简单说:一维数组,折半查找。
- 确定该区间的中间位置K。
- 将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]<T 类似上面查找区间为array[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间将缩小一半,递归查找即可。时间复杂度为:O(log2n)。
3.二分查找算法的原理
- 假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.
- 开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为a[mid]>x,故应在前半段中查找。
- 令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>a[mid],故确定应在后半段中查找。
- 令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。
- 如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。
4.使用Python3实现
mylist = [20,50,22,-22,0,15,222,28,29,99,1999,100823,55,35,5,1,2,3,8,9,55,10239,234234]
def lgfind(arr,v):
arr = sorted(arr)
print(arr)
start = 0
arrLen = len(arr)-1
while( start <= arrLen ):
mid = (start + arrLen) // 2
print('mid',mid)
if arr[mid] == v:
return v
if arr[mid] > v:
arrLen= mid - 1
else:
start= mid + 1
return false
have = lgfind(mylist,28)
print(have)
四、总结
在目前这个时间,IT的找工作一般分为三部曲:
- 投简历;
- 线下笔试/线上测试;
- 面试(n+1面)
而算法在笔试中常出现,在面试前可以多多熟悉,没面上也不用灰心,总结再战。
用谁说过的话:在哪跌倒就在哪里躺下。
以上理论来自百度百科。
版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/zhouxbr/article/details/103188827
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。