程序面试题之我见

系统管理员 2023-08-17 17:16 82阅读 0赞

> 本文简述了自己对于程序面试题的一些看法

前些年程序面试题比较流行,自然也涌现了不少网红试题,这里简单讲解一下,也顺道说说自己的看法~

#### 链表 ####

> 简单起见,以下讨论的链表都是单链表

*  如何判断两条(不存在环)链表有交点 ? 如果有交点,如何找出交点 ?

存在交点的两条(不存在环)链表,其尾部节点一定是相同的(*这里有些朋友可能会有疑问,相交的链表不能是蝶形的吗(这样两条链表就可能存在不相同的尾部节点)?其实对于相交的链表来说,是不可能存在蝶形的相交方式的,因为对于相交的那个链表节点来说,其只有一个链接指针,不能形成蝶形链接*),所以我们直接遍历两条链表至尾部,然后比较各自的尾部节点是否相同就可以了~

至于如何找出链表相交的交点,我们要做的就是首先"对齐"两条链表,然后再同步遍历,遇到的第一个相等节点便是链表的交点.

那么怎么"对齐"两条链表呢?方法就是让长度较长的链表先遍历( l l − l s l\_l - l\_s ll−ls)个节点( l l l\_l ll 为较长链表的长度,  l s l\_s ls 为较短链表的长度),然后再开始遍历较短的链表.

(*至于如何获取链表的长度,我们可以通过遍历一遍链表的方式来获取*)

*  如何判断链表中存在环 ? 如果有环,如何找出入环点 ?

如果链表中存在环,那么链表就可以一直遍历下去而不会终止,有一个技巧性比较强的方法来判定链表是否存在环:

我们使用两个指针来遍历链表(慢指针和快指针),慢指针每次步进  1 1 1 个节点,快指针每次步进  2 2 2 个节点,如果两个指针中途相遇(指向相同的节点),则链表存在环,否则则没有环(两个指针中途没有相遇,意味着快指针首先达到了链表尾部,而既然链表存在尾部,自然也就没有环了)

至于为何慢指针和快指针(慢指针每次步进  1 1 1 个节点,快指针每次步进  2 2 2 个节点)在链表存在环的情况下一定会相遇,有兴趣的朋友可以自己证明一下.

这里可以引申一个更进一步的问题: 如果快慢指针采取另外的步进速度(譬如慢指针每次步进  1 1 1 个节点,快指针每次步进  3 3 3 个节点),那么在链表存在环的情况下快慢指针还一定会相遇吗?

(我简单分析了一下上述这个引申问题,如果慢指针每次步进  1 1 1 个节点,快指针每次步进  3 3 3 个节点的话,快慢指针是 **不保证** 一定会相遇的,至于更一般的情况,还需要进一步的论证)

那么如何找出链表的入环点呢?方法同样需要技巧性:

首先我们要计算出链表中环的元素个数,方法就是扩展使用上述判断链表有环的方法: 当慢指针和快指针相遇时(此时可以判断链表一定有环),那么相遇的那个链表节点就一定是环中的某一节点,我们从这个节点出发遍历链表,当再次回到这个节点的时候,即可得到链表中环的元素个数(设为  l c l\_c lc).

得到了链表中环的元素个数,我们便可以尝试找出入环点了:

我们创建两个指针,并让其中一个指针首先步进  l c l\_c lc 个节点,之后再让两个指针同步遍历,当两个指针相遇时,其共同指向的那个链表节点即为链表的入环点.

有兴趣的朋友可以证明一下上述方法的正确性.

> 进一步的问题 : 如何判断两条**存在环**的链表有交点 ? 如果有交点,如何找出交点 ? (有兴趣的朋友可以思考一下~)

关于链表的这几个题目,每一个题目的解法都需要一定的技巧,但朴素的来说,我们都可以通过建立节点缓存的方式来解决,虽然空间复杂度更高一些,但是通用性更高,也更容易理解.

#### 数组 ####

*  如何找出数组中的主元素 ?

首先要说明下什么是数组的主元素,所谓**数组的主元素**,是指出现次数大于  n / 2 n / 2 n/2 ( n n n 为数组的元素个数)的数组元素,例如数组  \[ 2 , 1 , 1 , 1 \] \[2, 1, 1, 1\] \[2,1,1,1\], 其中  1 1 1 出现了  3 3 3 次, 大于  n / 2 = > 4 / 2 = > 2 n / 2 => 4 / 2 => 2 n/2=>4/2=>2 次,所以  1 1 1 就是这个数组的主元素;而对于数组  \[ 2 , 1 , 1 , 3 \] \[2, 1, 1, 3\] \[2,1,1,3\], 其中  1 1 1 只出现了  2 2 2 次(不大于  n / 2 = > 4 / 2 = > 2 n / 2 => 4 / 2 => 2 n/2=>4/2=>2 次),所以  1 1 1 不是这个数组的主元素.

现在我们**已知一个数组中存在主元素**,问题是如何找出这个主元素?

朴素的方法是将数组排序,然后取中间位置的元素即可(不要忘了前提,我们知道数组一定存在主元素)~

代码大概是这个样子(Lua):

function major_element(t)
        -- sort first
        table.sort(t)
        -- return center
        return t[math.ceil(#t / 2)]
    end

上述代码的时间复杂度一般是  O ( n l g n ) O(nlgn) O(nlgn),即等于排序的时间复杂度~

进一步的,既然我们排序的目的是获取中间位置的元素,那么有没有可能在不排序数组的情况下获取中间位置的元素呢?

我们可以使用 [BFPRT 算法][BFPRT],算法的细节不少,有兴趣的朋友可以深入了解下,这里我们只要知道该算法可以获取指定位置大小(第  k k k 小)的数组元素,并且时间复杂度为  O ( n ) O(n) O(n).

function major_element(t)
        return BFPRT(t, math.ceil(#t / 2))
    end

现在我们代码的时间复杂度变为了  O ( n ) O(n) O(n) ~

下面讲一下这个问题的"标准答案",技巧性比较强,问题的关键是你要注意到以下等式:

> 假设数组  A A A 存在主元素,并且其包含的元素分别为  a 0 , a 1 , . . . a n a\_0, a\_1, ... a\_n a0,a1,...an,假设  a i ≠ a j a\_i \\neq a\_j ai=aj,将  a i a\_i ai 和  a j a\_j aj 从数组  A A A 中去除后得到数组  A ′ A' A′,我们有:  
>  **A A A 的主元素 =  A ′ A' A′ 的主元素**

编码实现上也有一定的技巧性,我们采用计数方式来实现上面的等式,方法是遍历数组,对于相等的元素我们增加计数,对于不相等的元素则减少计数,代码如下(Lua):

function major_element(t)
        local element = t[1]
        local count = 1
        
    	for i = 2, #t do
            if t[i] == element then
                count = count + 1
    		else
                count = count - 1
                if count == 0 then
                    count = 1
                    element = t[i]
                end
            end
        end
       
        return element
    end

*  如何判断数组中存在主元素 ?

注意这个问题与上面问题的区别,上面的问题有一个已知条件,即数组存在主元素,而这个问题则没有这个前提,即数组可能存在主元素也可能不存在主元素.

上述基于 排序 或者 BFPRT 的方法可以直接沿用,多出的步骤就是需要判断一下获取到的元素是否确实是主元素,示例代码如下(Lua):

function major_element(t)
        -- sort first
        table.sort(t)
        -- check then
        local pending = t[math.ceil(#t / 2)]
        local check_count = math.floor(#t / 2) + 1
        local count = 0
        for i = 1, #t do
            if t[i] == pending then
                count = count + 1
                if count >= check_count then
                    return pending
                end
            end
        end
    end

至于上述那种技巧性很强的实现方式,这里就不再适用了…

#### 后记 ####

网上看到的不少面试题,很多都是偏于技巧性质的(譬如上面讲述的几道题目),但个人觉得,这些题目除了测试智力之外,其他的作用就比较有限了,甚至从工程角度考虑,偏于技巧性的方法一般都意味着复杂性和不可扩展性,朴素方法虽然在时间或者空间复杂度上更高一些,但是往往比较简单,容易理解,通用性和扩展性也更好,很多时候其实是工程实现中更优的选择~

[BFPRT]: https://en.wikipedia.org/wiki/Median_of_medians