Compile common PHP algorithm interview questions

This article introduces and organizes common PHP algorithm interview questions. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

1. Insertion sorting (one-dimensional array) The basic idea: Each time a data element to be sorted is inserted into the appropriate position in the previously sorted array, so that the array is still in order; until it is to be Sort until all data elements are inserted.

Example:

[Initial keyword] [49] 38 65 97 76 13 27 49

J=2(38) [38 49] 65 97 76 13 27 49

J=3(65) [38 49 65] 97 76 13 27 49

J=4(97) [38 49 65 97] 76 13 27 49

J=5(76) [38 49 65 76 97] 13 27 49

J=6(13) [13 38 49 65 76 97] 27 49

J=7(27 ) [13 27 38 49 65 76 97] 49

J=8(49) [13 27 38 49 49 65 76 97]

function insert_sort($arr){
    $count = count($arr);   
    for($i=1; $i<$count; $i++){      
        $tmp = $arr[$i];        
        $j = $i - 1;        
        while($arr[$j] > $tmp){          
            $arr[$j+1] = $arr[$j];          
            $arr[$j] = $tmp;            
            $j--;           
        }    
    }    
    return $arr; 
}

2. Selection sort (one-dimensional array) Basic Idea: In each pass, the smallest (or largest) element is selected from the data elements to be sorted, and the order is placed at the end of the sorted sequence until all the data elements to be sorted are arranged. Example:

[Initial keyword] [49 38 65 97 76 13 27 49]

13 after the first sorting [38 65 97 76 49 27 49]

After the second sorting 13 27 [65 97 76 49 38 49]

After the third sorting 13 27 38 [97 76 49 65 49]

After the fourth sorting 13 27 38 49 [49 97 65 76]

After the fifth sorting 13 27 38 49 49 [97 97 76]

After the sixth sorting 13 27 38 49 49 76 [76 97]

After the seventh sorting, 13 27 38 49 49 76 76 [97]

The final sorting result is 13 27 38 49 49 76 76 97

function select_sort($arr){     
    $count = count($arr);   
    for($i=0; $i<$count; $i++){      
        $k = $i;        
        for($j=$i+1; $j<$count; $j++){           
            if ($arr[$k] > $arr[$j]) $k = $j;        
        }       
        if($k != $i){           
            $tmp = $arr[$i];            
            $arr[$i] = $arr[$k];            
            $arr[$k] = $tmp;        
        }   
    }   
    return $arr; 
}

3. Bubble sort ( One-dimensional array) Basic idea: compare the sizes of the data elements to be sorted pairwise, and when it is found that the order of the two data elements is reversed, they are exchanged until there are no reversed data elements. Sorting process: Imagine that the sorted array R[1..N] is erected vertically, and each data element is regarded as a weighted bubble. According to the principle that light bubbles cannot be under heavy bubbles, the array R is scanned from bottom to top. Whenever a light bubble that violates this principle is scanned, it will be "floated" upward, and this process is repeated until the last two bubbles are the lighter one at the top and the heavier one at the bottom.

Example:

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

function bubble_sort($array){   
    $count = count($array);     
    if ($count <= 0) return false;   
    for($i=0; $i<$count; $i++){      
        for($j=$count-1; $j>$i; $j--){           
            if ($array[$j]<$array[$j-1]){                
                $tmp = $array[$j];              
                $array[$j] = $array[$j-1];              
                $array[$j-1] = $tmp;            
            }       
        }   
    }    
    return $array; 
}

4. Quick sort (one-dimensional array) Basic idea: In the current unordered area R [1..H ] Take any data element as the "baseline" for comparison (maybe recorded as R [I 1..H], and the data elements in the unordered sub-area on the left are all less than or equal to the reference element, the data elements in the unordered sub-area on the right are all greater than or equal to the reference element, and the reference X is located at the final sorting position , that is, R [1..I-1]≤X.Key≤RI 1..H, when both R [1..I-1] and R [I 1..H] are not empty, perform the The above division process is carried out until all data elements in the unordered sub-areas have been sorted. Example:

Initial keyword [49 38 65 97 76 13 27 49]

After the first exchange [27 38 65 97 76 13 49 49]

Second After the third exchange [27 38 49 97 76 13 65 49]

J scan to the left, the position remains unchanged. After the third exchange [27 38 13 97 76 49 65 49]

I Scan to the right, the position remains unchanged, after the fourth exchange [27 38 13 49 76 97 65 49]

J Scan to the left [27 38 13 49 76 97 65 49]

( One division process)

Initial keyword [49 38 65 97 76 13 27 49]

After one sorting [27 38 13] 49 [76 97 65 49]

After two sortings [13] 27 [38] 49 [49 65] 76 [97]

After three sortings 13 27 38 49 49 [65] 76 97

Final sorting Result 13 27 38 49 49 65 76 97

Status after each sorting

function quickSort(&$arr){    
    if(count($arr)>1){
        $k=$arr[0];
        $x=array();
        $y=array();
        $_size=count($arr);        
        for($i=1;$i<$_size;$i++){            
            if($arr[$i]<=$k){
                $x[]=$arr[$i];
            }elseif($arr[$i]>$k){
                $y[]=$arr[$i];
            }
        }
        $x=quickSort($x);
        $y=quickSort($y);        
        return array_merge($x,array($k),$y);
    }else{ 
        return$arr;
    }
}

5. Hill sort (shell sort) — O (n log n)

functionshell_sort(&$arr){    
    if(!is_array($arr))return;
    $n=count($arr);    
    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){
        for($i=$gap;$i<$n;++$i){
            for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){                
                $temp=$arr[$j];                
                $arr[$j]=$arr[$j+$gap];                
                $arr[$j+$gap]=$temp;
            }
        }
    }
}

6. Binary search

/** 
* 二分算法查找 
* @param array $array 要查找的数组 
* @param int $min_key 数组的最小下标 
* @param int $max_key 数组的最大下标 
* @param mixed $value 要查找的值 
* @return boolean 
*/ 
function bin_search($array,$min_key,$max_key,$value){             
    if($min_key <= $max_key){ 
        $key = intval(($min_key+$max_key)/2); 
        if($array[$key] == $value){ 
            return true; 
        }elseif($value < $array[$key]){ 
            return bin_search($array,$min_key,$key-1,$value);
        }else{ 
            return bin_search($array,$key+1,$max_key,$value);
        }   
    }else{      
        return false;   
    } 
}

7. Deletion of linear table (implemented in array)

function delete_array_element($array, $i)   {   
    $len = count($array);   
    for ($j=$i; $j<$len; $j++){      
        $array[$j] = $array[$j+1]   
    }   
    array_pop($array);  
    return $array; 
}

8. String length

function strlen($str)   { 
    if ($str == '') return 0; 
    $count = 0; 
    while (1){ 
        if ($str[$count] != NULL){ 
            $count++; 
            continue; 
        }else{ 
            break; 
        } 
    } 
    return $count; 
}

9. String flip

function strrev($str)   {   
    if ($str == '') return 0;   
    for ($i=(strlen($str)-1); $i>=0; $i--){   
        $rev_str .= $str[$i];   
    }   
    return $rev_str; 
}

10. String comparison

function strcmp($s1, $s2)   { 
    if (strlen($s1) < strlen($s2)) return -1; 
    if (strlen($s1) > strlen($s2)) return 1; 
    for ($i=0; $i<strlen($s1); $i++){ 
        if ($s1[$i] == $s2[$i]){ 
            continue; 
        }else{          
            return false; 
        }   
    }   
    return 0; 
}

11. Search string

function strstr($str, $substr)  { 
    $m = strlen($str); 
    $n = strlen($substr); 
    if ($m < $n) return false; 
    for ($i=0; $i<=($m-$n+1); $i++){ 
        $sub = substr($str, $i, $n); 
        if (strcmp($sub, $substr) == 0) return $i; 
    } 
    return false; 
}

12. String replacement

function str_replace($substr, $newsubstr, $str) { 
    $m = strlen($str); 
    $n = strlen($substr); 
    $x = strlen($newsubstr); 
    if (strchr($str, $substr) == false) return false; 
    for ($i=0; $i<=($m-$n+1); $i++){ 
        $i = strchr($str, $substr); 
        $str = str_delete($str, $i, $n); 
        $str = str_insert($str, $i, $newstr); 
    } 
    return $str; 
}

13. Insert a string

function str_insert($str, $i, $substr)  { 
    for($j=0; $j<$i; $j++){ 
        $startstr .= $str[$j]; 
    } 
    for ($j=$i; $j<strlen($str); $j++){ 
        $laststr .= $str[$j]; 
    } 
    $str = ($startstr . $substr . $laststr); 
    return $str; 
}

14. Delete a string

function str_delete($str, $i, $j){  
    for ($c=0; $c<$i; $c++){ 
        $startstr .= $str[$c]; 
    } 
    for ($c=($i+$j); $c<strlen($str); $c++){ 
        $laststr .= $str[$c]; 
    } 
    $str = ($startstr . $laststr); 
    return $str; 
}

15. Copy a string

function strcpy($s1, $s2){ 
    if (strlen($s1)==NULL || !isset($s2)) return; 
    for ($i=0; $i<strlen($s1); $i++){ 
        $s2[] = $s1[$i]; 
    } 
    return $s2; 
}
16、连接字符串
function strcat($s1, $s2){ 
    if (!isset($s1) || !isset($s2)) return; 
    $newstr = $s1; 
    for($i=0; $i<count($s); $i++){ 
        $newstr .= $st[$i]; 
    } 
    return $newsstr; 
}

17. Simple encoding function (corresponding to the php_decode function)

function php_encode($str)    { 
    if ($str=='' && strlen($str)>128) 
        return false;
    for($i=0; $i<strlen($str); $i++){ 
        $c = ord($str[$i]); 
        if ($c>31 && $c<107) 
            $c += 20; 
            if ($c>106 && $c<127) 
                $c -= 75; 
                $word = chr($c); 
                $s .= $word; 
            } 
            return $s; 
        }
    }
}

18. Simple decoding Function (corresponding to the php_encode function)

function php_decode($str)   { 
    if ($str=='' && strlen($str)>128) return false; 
    for($i=0; $i<strlen($str); $i++){ 
        $c = ord($word); 
        if ($c>106 && $c<127) $c = $c-20; 
        if ($c>31 && $c<107) $c = $c+75; 
        $word = chr($c); 
        $s .= $word; 
    } 
    return $s; 
}

19. Simple encryption function (corresponding to the php_decrypt function)

function php_encrypt($str)  {   
    $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
    $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
    if (strlen($str) == 0) return false;     
    for ($i=0; $i<strlen($str); $i++){    
        for ($j=0; $j<strlen($encrypt_key); $j++){    
            if ($str[$i] == $encrypt_key[$j]){   
                $enstr .= $decrypt_key[$j];      
                break;   
            }    
        }    
    }   
    return $enstr; 
}

20. Simple decryption function (corresponding to the php_encrypt function)

function php_decrypt($str)  { 
    $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
    $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; 
    if (strlen($str) == 0) return false; 
    for ($i=0; $i<strlen($str); $i++){ 
        for ($j=0; $j<strlen($decrypt_key); $j++){ 
            if ($str[$i] == $decrypt_key[$j]){ 
                $enstr .= $encrypt_key[$j]; 
                break; 
            } 
        } 
    } 
    return $enstr; 
}

Recommended learning: "PHP Video Tutorial"

The above is the detailed content of Compile common PHP algorithm interview questions. For more information, please follow other related articles on the PHP Chinese website!