• 欢迎来到本博客,希望可以y一起学习与分享

php面试题之二——数据结构和算法(高级部分)

PHP benz 来源:php面试题之二——数据结构和算法(高级部分) 4年前 (2018-04-05) 126次浏览 0个评论 扫描二维码

目录

文章目录[隐藏]

二、数据结构和算法

1.使对象可以像数组一样进行foreach循环,要求属性必须是私有。(Iterator模式的PHP5实现,写一类实现Iterator接口)(腾讯)

2.用PHP实现一个双向队列(腾讯)

3.请使用冒泡排序法对以下一组数据进行排序10 2 36 14 10 25 23 85 99 45。

4.写出一种排序算法(要写出代码),并说出优化它的方法。(新浪)

该算法是通过分治递归来实现的,其效率很大程度上取决于参考元素的选择,可以选择数组的中间元素,也可以随机得到三个元素,然后选择中间的那个元素(三数中值法)。
另外还有一点,就是当我们在分割时,如果分割出来的子序列的长度很小的话(小于5到20),通常递归的排序的效率就没有诸如插入排序或希尔排序那么快了。因此可以会去判断数组的长度,如果小于10的话,直接用插入排序,而不再递归调用这个快速排序。

5.一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n,输出最后那个大王的编号。(新浪)(小米)

这是著名的约瑟夫环问题

6.写一个二维数组排序算法函数,能够具有通用性,可以调用php内置函数。

7.用二分法查找一个长度为10的排好序的线性表,查找不成功时最多需要比较次数是(小米)

4

8.从0,1,2,3,4,5,6,7,8,9,这十个数字中任意选出三个不同的数字,“三个数字中不含0和5”的概率是(小米)

7/15

9.一个三角形三个顶点有3只老鼠,一声枪响,3只老鼠开始沿三角形的边匀速运动,请问他们相遇的概率是(小米)

75%,每只老鼠都有顺时针、逆时钟两种运动方向,3只老鼠共有8种运动情况,只有当3只老鼠都为顺时针或者逆时钟,它们才不会相遇,剩余的6中情况都会相遇,故相遇的概率为6/8=75%。

10.描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组(小米)

11.我们希望开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里。(鑫众人云)

12.写出你所知道的排序方法(亿邮)

冒泡排序,快速排序,插入排序,选择排序


文章 php面试题之二——数据结构和算法(高级部分) 转载需要注明出处
喜欢 (0)

您必须 登录 才能发表评论!