近期面试遇到的算法题分享

近期面试遇到的算法题分享

最近在看一些外部机会,上海这边的互联网公司聊了一圈,还有一些海外公司,像新加坡的shopee这种,发现不管是Leader岗还是架构岗,算法面这关是怎么也逃不了的。一开始以为,可能处于对我这种老年人的照顾,其实也并没有考得特别深,决定把近期遇到的一些算法题总结一下解题思路,一来如果有准备去头条抖音拼多多等公司的小伙伴可以作为参考,毕竟重复出题的概率不低,二来也是给自己攒攒RP,下周就要面对Facebook和Google的面试,内心还是很惊恐的,疯狂学英语刷算法中。

本篇文章适合像我一样没有提前刷过算法的同学,leetcode上百题的算法大佬们轻拍。

题1:给定一个巨大的数组,找出其中的中值

这个题我遇到了两个不同前置条件的问题:

  1. 数组已排序,但有重复值。
  2. 数组未排序,每个数字都是唯一的。

问题1比较简单,我当时的解法是采用了快慢指针的方式,

  • 首先我们设置两个指针slow和fast,slow指针每次移动一步,fast指针每次移动两步;
  • 遇到相同的数字都不记步数;
  • 记录快指针移动次数,当快指针无法继续移动时,如果计数为偶数,慢指针刚好指向中点;反之,当快指针走完,慢指针指向中点前一个节点。

问题2就想对复杂一些,一般解法可能会先对数组进行排序,然后直接取int((len(arrays) + 1)/2),但也可以参考快排的思想。

  1. 随机选择一个数字,让它和数组中每一个数字去比大小,如果比它小就放在左边,如果比它大就放在右边。2. 第一次划分的结果可能是一边多一边少,中值只可能在多的一边,而不可能在少的一边。因此,第二次只需要在大的一边随机选择一个数字,再进行一次划分,看是否平衡。
  2. 以此类推。
题2:求子数组的最大和

输入一个整型数组,数组里面有正数也有负数,数组中的连续一个或者多个整数组成一个子数组,每一个子数组都有一个和,求所有子数组和的最大值。

例如:输入数组为{1,-2,3,10,-4,7,2,-5},和的最大子数组为{3,10,-4,7,2},因此输出为子数组的和18。

可能看到标题很多大佬们都要笑了——这不是考烂了嘛?然而这么多年了,还是一直在考,这道题是我在面试Shopee的时候遇到的,顺便说一下第一次参与机考,感觉给个页面,没有任何快捷键硬写代码,比在白纸上手写要费劲多了……

解题思路第一反应可能是枚举,求出所有子数组的和,然后比较求出最大的值,即可。然而对于长度为n的数组,它的子数组共有n(n-1)/2个,O(n^2),然后再对于每一个数组求和,时间复杂度为O(n)。这个效率一看就太低了,而这就是这道题最容易坑爹的地方。解法1太过于差,以至于第一时间就会被否定,然后将思路放在优化解法1上,而显分治法则是个很容易落入圈套的方向——将数组从中间分为两个子数组,则最大子数组必然出现在以下三种情况之一:

  1. 完全位于左边的数组中。
  2. 完全位于右边的数组中。
  3. 跨越中点,包含左右数组中靠近中点的部分。

递归将左右子数组再分别分成两个数组,直到子数组中只含有一个元素,退出每层递归前,返回上面三种情况中的最大值。但这种情况下,算法的时间复杂度应该是O(nlogn)。

从快速否定解法1,到显而易见的优化方向解法2,这个过程太过自然了,以至于很容易忽略实际上有线性时间的解法:

对于某个子数组,如果它的下一个数为正数,加上该正数和会增加;而加上一个负数,和会减少;如果当前子数组的话为负数,下一个数不论是正数还是负数,都会使得子数组的和进一步减少,因而这时候应该将子数组和重置为0。基于这种思路我们可以写出如下的代码:

int MaxSub(int *arr,int len)
{
    int i;
    int MaxSum = 0;
    int CurSum = 0;
    for(i=0;i<len;i++)
    {
        CurSum += arr[i];
        if(CurSum > MaxSum)
            MaxSum = CurSum;
        if(CurSum < 0) //重点!
            CurSum = 0;
    }
    return MaxSum;
}

另外,这道题还有一个求二叉树最大和路径的变式题
这个变式是在拼多多二面的时候遇到的,但要求用非递归的实现,这里就当做思考题。提示:可以考虑后序遍历。

题3:给定一个二维数组board其中每个元素是字符(char),找出一个字符串word是否在数组中。字符串由二维数组中横、纵相邻的字符构成,则为true;数组中每个元素最多使用一次。

例子:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "ABCB", 返回 false.

这道题记得是在头条面试时候遇到的,卡了我很久,面完做面试回顾的时候,发现自己应该是没有做到bug free的。搜了一下发现有点像传统的“n皇后问题”,利用回溯递归就比较容易解决,其中几个需要注意的地方,也是我当时写出bug的地方,我写在代码注释里了,大家需要注意。

```
//从给定一个点起开始回溯遍历
bool backtrace(vector>& board, const string& word, int idx, int row, int col) {
if (idx == word.size()) return true;//word到底了,只能返回true,否则就无论如何都false了
if (row<0 || col < 0 || row == board.size() || col == board[0].size() || board[row][col] != word[idx]) return false; //矩阵到底了或者不匹配返回false
//进到这里,说明已经匹配到word[idx] == board[row][col]了,继续向上下左右找word[idx+1]
board[row][col] = 0;//标记当前节点为0,防止重复取该节点,无限循环,重点!
bool ret = backtrace(board, word, idx+1, row+1, col) ||
backtrace(board, word, idx+1, row-1, col) ||
backtrace(board, word, idx+1, row, col+1) ||
backtrace(board, word, idx+1, row, col-1);
board[row][col] = word[idx]; //查完了,把上面标记为0的再改回来,重点!
return ret;
}

//输入函数
bool Exist(vector>& board, string word) {
//遍历所有起点
for (int i = 0; i < board.size(); i++)
for (int j = 0; j < board[0].size(); j++)
if(backtrace(board, word, 0, i, j)) return true;

top Created with Sketch.