二、數據結構和算法

1.使對象可以像數組一樣進行foreach循環,要求屬性必須是私有。(Iterator模式的PHP5實現,寫一類實現Iterator接口)(騰訊)
<?php
    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/>';
    }?>
2.用PHP實現一個雙向隊列(騰訊)
<?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。
<?php
    // 冒泡排序
    function bubble_sort(&$arr){        for ($i=0,$len=count($arr); $i < $len; $i++) {            for ($j=1; $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.寫出一種排序算法(要寫出代碼),并說出優化它的方法。(新浪)
<?php
    //快速排序
    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
    // 方案一,使用php來模擬這個過程
    function king($n,$m){
        $mokey = range(1, $n);
        $i = 0;        while (count($mokey) >1) {
            $i += 1;
            $head = array_shift($mokey);//一個個出列最前面的猴子
            if ($i % $m !=0) {                #如果不是m的倍數,則把猴子返回尾部,否則就拋掉,也就是出列
                array_push($mokey,$head);
            }            // 剩下的最后一個就是大王了
            return $mokey[0];
        }
    }    // 測試
    echo king(10,7);    // 方案二,使用數學方法解決
    function josephus($n,$m){
        $r = 0;        for ($i=2; $i <= $m ; $i++) {
            $r = ($r + $m) % $i;
        }        return $r+1;
    }    // 測試
    print_r(josephus(10,7));?>
6.寫一個二維數組排序算法函數,能夠具有通用性,可以調用php內置函數。
<?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.描述順序查找和二分查找(也叫做折半查找)算法,順序查找必須考慮效率,對象可以是一個有序數組(小米)
<?php
    /**
     * 順序查找
     * @param  array $arr 數組
     * @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;
        }
    }    /**
     * 二分查找,要求數組已經排好順序
     * @param  array $array 數組
     * @param  int $low   數組起始元素下標
     * @param  int $high  數組末尾元素下標
     * @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;
    }    // 測試:順序查找
    $arr1 = array(9,15,34,76,25,5,47,55);    echo seq_sch($arr1,47);//結果為6

    echo "<br />";    // 測試:二分查找
    $arr2 = array(5,9,15,25,34,47,55,76);    echo bin_sch($arr2,0,7,47);//結果為5?>
11.我們希望開發一款撲克游戲,請給出一套洗牌算法,公平的洗牌并將洗好的牌存儲在一個整形數組里。(鑫眾人云)
<?php
    $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.寫出你所知道的排序方法(億郵)

冒泡排序,快速排序,插入排序,選擇排序