PHP interview questions algorithm questions

小云云
Release: 2023-03-20 15:10:01
Original
17745 people have browsed it

Algorithm questions often appear in PHP interview questions. This article mainly shares with you the algorithm questions of PHP interview questions, hoping to help everyone.

Related recommendations: "2019 PHP Interview Questions Summary (Collection)"

Interview Questions - Algorithm Questions:

1. Insertion sort (one-dimensional array) 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 all the data elements to be sorted are until the insertion is complete. 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; 
}
Copy after login

2. Selection sort (one-dimensional array) Basic idea: Each pass selects the smallest (or largest) element from the data elements to be sorted, in order Place it at the end of the sorted array until all data elements to be sorted are exhausted. Example:

[Initial keyword] [49 38 65 97 76 13 27 49]
13 after the first sort [38 65 97 76 49 27 49]
13 after the second sort 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]
Fifth After the sixth sorting pass 13 27 38 49 49 [97 97 76]
After the sixth sorting pass 13 27 38 49 49 76 [76 97]
After the seventh sorting pass 13 27 38 49 49 76 76 [ 97]
Final sorting result 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; 
}
Copy after login

3. Bubble sorting (one-dimensional array) Basic idea: compare the sizes of the data elements to be sorted pairwise and find two data When the order of elements is reversed, swapping is performed until there are no more data elements in reverse order. 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 light bubbles that violate this principle are scanned, they are made to "float" 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; 
}
Copy after login

4. Quick sort (one-dimensional array) Basic idea: Take any data element in the current unordered area R[1..H] as the "baseline" for comparison (it may be recorded as The current disordered area is divided into two smaller disordered areas on the left and right: R[1..I-1] and R[I 1..H], and the data elements in the left disordered subarea are less than or equal to the reference elements. , 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 R When both [1..I-1] and R[I 1..H] are non-empty, perform the above division process on them respectively until all data elements in the unordered sub-area 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]
After the second 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, the fourth exchange After [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 After that 13 27 38 49 49 [65] 76 97
The final sorting result 13 27 38 49 49 65 76 97
The 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;
    }
}
Copy after login

5. Hill sorting (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;
            }
        }
    }
}
Copy after login

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; 	
    } 
}
Copy after login

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; 
}
Copy after login

8, String length

function strlen($str)	{ 
    if ($str == &#39;&#39;) return 0; 
    $count = 0; 
    while (1){ 
        if ($str[$count] != NULL){ 
            $count++; 
            continue; 
        }else{ 
            break; 
        } 
    } 
    return $count; 
}
Copy after login

9, String flip

function strrev($str)	{ 	
    if ($str == &#39;&#39;) return 0; 	
    for ($i=(strlen($str)-1); $i>=0; $i--){ 	 
        $rev_str .= $str[$i]; 	
    } 	
    return $rev_str; 
}
Copy after login

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; 
}
Copy after login

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; 
}
Copy after login

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; 
}
Copy after login

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; 
}
Copy after login

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; 
}
Copy after login

15, copy string

function strcpy($s1, $s2){ 
    if (strlen($s1)==NULL || !isset($s2)) return; 
    for ($i=0; $i<strlen($s1); $i++){ 
        $s2[] = $s1[$i]; 
    } 
    return $s2; 
}
Copy after login

16, connect string

function strcat($s1, $s2){ 
    if (!isset($s1) || !isset($s2)) return; 
    $newstr = $s1; 
    for($i=0; $i<count($s); $i++){ 
        $newstr .= $st[$i]; 
    } 
    return $newsstr; 
}
Copy after login

17, simple encoding function (corresponding to php_decode function)

function php_encode($str) { if ($str=='' && strlen($str)>128) return false; for($i=0; $i31 && $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==&#39;&#39; && 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; 
}
Copy after login

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; 
}
Copy after login

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; 
}
Copy after login

Related recommendations:

php’s classic algorithm questions Apple

A classic algorithm question caused by a commonly used Linux command in a project

A brief discussion on some basic algorithm questions on characters and arrays in js

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

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!