1. 使对象可以像数组一样进行foreach循环，要求属性必须是私有。(Iterator模式的PHP5实现，写一类实现Iterator接口)（腾讯）
class Test implements Iterator { private $item = array( 'id' => 1, 'name' => 'php' ); public function rewind() { reset($this->item); } public function current() { return current($this->item); } public function key() { return key($this->item); } public function next() { return next($this->item); } public function valid() { return($this->current()!==false); } } // 测试 $t = new Test; foreach($t as $k => $v){ echo$k,'--->',$v,'<br/>'; } /*输出结果 id--->1 name--->php*/
2. 用PHP实现一个双向队列（腾讯）
class Deque { private $queue = array(); public function addFirst($item) { return array_unshift($this->queue,$item); } public function addLast($item) { return array_push($this->queue,$item); } public function removeFirst() { return array_shift($this->queue); } public function removeLast() { return array_pop($this->queue); } }
3. 请使用冒泡排序法对以下一组数据进行排序 10 2 36 14 10 25 23 85 99 45。
// 冒泡排序 function bubble_sort(&$arr) { for ($len = count($arr), $i = 0; $i < $len; $i++) { for ($j=0; $j < $len - $i; $j++) { if ($arr[$j - 1] > $arr[$j]) { $temp = $arr[$j - 1]; $arr[$j - 1] = $arr[$j]; $arr[$j] = $temp; } } } } $arr = array(10, 2, 36, 14, 10, 25, 23, 85, 99, 45); bubble_sort($arr); print_r($arr);
4. 写出一种排序算法（要写出代码），并说出优化它的方法。（新浪）
// 快速排序 function partition(&$arr,$low,$high) { $pivotkey = $arr[$low]; while ($low < $high) { while ($low < $high && $arr[$high] >= $pivotkey) { $high--; } $temp = $arr[$low]; $arr[$low] = $arr[$high]; $arr[$high] = $temp; while ($low < $high && $arr[$low] <= $pivotkey) { $low++; } $temp = $arr[$low]; $arr[$low] = $arr[$high]; $arr[$high]=$temp; } return $low; } function quick_sort(&$arr,$low,$high) { if ($low < $high) { $pivot = partition($arr,$low,$high); quick_sort($arr,$low,$pivot-1); quick_sort($arr,$pivot+1,$high); } }
该算法是通过分治递归来实现的，其效率很大程度上取决于参考元素的选择，可以选择数组的中间元素，也可以随机得到三个元素，然后选择中间的那个元素（三数中值法）。
另外还有一点，就是当我们在分割时，如果分割出来的子序列的长度很小的话（小于5到20），通常递归的排序的效率就没有诸如插入排序或希尔排序那么快了。因此可以会去判断数组的长度，如果小于10的话，直接用插入排序，而不再递归调用这个快速排序。
5. 一群猴子排成一圈，按1，2，...，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去...，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n,输出最后那个大王的编号。（新浪）（小米）
这是著名的约瑟夫环问题
方案一，使用php来模拟这个过程
function king($n,$m) { $monkey = range(1, $n); $i = 0; while (count($monkey) > 1) { $i += 1; $head = array_shift($monkey); // 一个个出列最前面的猴子 if ($i % $m != 0) { // 如果不是m的倍数，则把该猴子返回尾部，否则就抛掉，也就是出列了 array_push($monkey, $head); } } // 剩下的最后一个就是大王了 return $monkey[0]; } // 测试 echo king(10,7); // 9
方案二，使用数学方法解决
function josephus($n,$m) { $r = 0; for ($i = 2; $i < $n; $i++) { $r = ($r + $m) % $i; } return $r + 1; } print_r(josephus(10,7)); // 2
6. 写一个二维数组排序算法函数，能够具有通用性，可以调用php内置函数。
// 二维数组排序，$arr是数据，$keys是排序的健值，$order是排序规则，1是降序，0是升序 function array_sort($arr,$keys,$order=0) { if(!is_array($arr)){ return false; } $keysvalue = array(); foreach ($arr as $key => $val) { $keysvalue[$key] = $val[$keys]; } if ($order == 0) { asort($keysvalue); } else { arsort($keysvalue); } reset($keysvalue); foreach ($keysvalue as $key => $vals) { $keysort[$key] = $key; } $new_array=array(); foreach($keysort as $key => $val){ $new_array[$key] = $arr[$val]; } return $new_array; } //测试 $person=array( array('id'=>2,'name'=>'zhangsan','age'=>23), array('id'=>5,'name'=>'lisi','age'=>28), array('id'=>3,'name'=>'apple','age'=>17) ); $result = array_sort($person,'name',1); print_r($result);
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. 描述顺序查找和二分查找（也叫做折半查找）算法，顺序查找必须考虑效率，对象可以是一个有序数组（小米）
/** * 顺序查找 * @param $arr array 数组 * @param $k 要查找的元素 * @return mixed 成功返回数组下标，失败则返回-1 */ function seq_sch($arr, $k) { for ($i = 0, $n = count($arr); $i < $n; $i++) { if ($arr[$i] == $k) { break; } } if ($i < $n) { return $i; } else { return -1; } } // 测试 $arr = array(9,15,34,76,25,5,47,55); echo seq_sch($arr,47); // 6
/** * 二分查找，要求数组已经排好序 * @param $arr array 数组 * @param $low int 数组起始元素下标 * @param $high int 数组末尾元素下标 * @param $k 要查找的元素 * @return mixed 成功返回数组下标，失败则返回-1 */ function bin_sch($array, $low, $high, $k) { if ($low <= $high) { $mid = intval(($low + $high) / 2); if ($array[$mid] == $k) { return $mid; } elseif ($k < $array[$mid]) { return bin_sch($array, $low, $mid - 1, $k); } else { return bin_sch($array, $mid + 1, $high, $k); } } return -1; } // 测试 $arr = array(5,9,15,25,34,47,55,76); echo bin_sch($arr,0,7,47); // 5
11. 我们希望开发一款扑克游戏，请给出一套洗牌算法，公平的洗牌并将洗好的牌存储在一个整形数组里。（鑫众人云）
没有固定答案，简单洗牌算法参考
$card_num = 54; // 牌数 function wash_card($card_num) { $cards = $tmp = array(); for ($i = 0; $i < $card_num; $i++) { $tmp[$i]=$i; } for ($i = 0; $i < $card_num; $i++) { $index = rand(0, $card_num-$i-1); $cards[$i] = $tmp[$index]; unset($tmp[$index]); $tmp = array_values($tmp); } return$cards; } // 测试 print_r(wash_card($card_num));
12. 写出你所知道的排序方法（亿邮）
冒泡排序，快速排序，插入排序，选择排序