您还未登录! 登录 | 注册 | 帮助  

您的位置: 首页 > 业务知识 > 正文

当一个程序员真正掌握算法之后,会变得有多强?

发表于:2020-02-13 作者:佚名 来源:民工哥技术之路

2020 = 1024 + 996... 对于程序员来说,2020 年看起来可不怎么“友好”啊。

但是不管外部环境如何,提升自身内功都是每个职场人所必需的。在如今的环境下,想要换一份理想的工作更是需要“找准时机,抓住机会”,当然在面试前的准备是必不可少的。极客大学邀请了算法训练营的助教,请他们分享一下作为面试官喜欢考察候选人哪些能力、他们有哪些“ 精选算法面试题 ”。我们的助教们来自美团、百度或海外的一线互联网公司,希望他们分享的经验可以帮助到你。

前美团资深工程师 Windy

作为面试官,我比较看中候选人的行业背景、专业技能还有一些软素质。具体来说:

  • 行业背景就是上一份工作所在的领域比如电商、社交等;
  • 专业技能的话主要是语言基础,高并发、分布式、中间件等知识,以及排查问题、运维、设计的能力。这里面最重要的是编程能力,针对高级岗位还要考察架构能力。
  • 软素质包括候选人的沟通能力、项目管理能力和领导力等。

作为面试官,在面试过程我会用笔试题的形式考察候选人的思维逻辑能力,通常考察的具体知识点包括链表、树、排序、二分查找等,需要候选人能够分析出不同算法的时间复杂度和空间复杂度。题目我会选择 LeetCode 上简单到中等难度的题目,常考的有:

  • 单链表翻转(递归或者循环)
  • 树的前中后序遍历
  • 动态规划(爬楼梯以及变形问题、斐波那契数列、股票问题)
  • 二分查找(以及变形)
  • 排序(快排)

通过算法面试题的考察,我希望候选人不光可以展示编程能力,还可以通过详细了解题目,展示自己的沟通能力和推演能力(如何构建题目的思路)。最关键的编程能力,候选人可以展示自己对于问题边界的思考,比较不同方法的性能和效率,给出解决问题的多种方法。

我的精选算法面试题是:搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例 1:


  1. 输入: 
  2. matrix = [ 
  3.   [1, 3, 5, 7], 
  4.   [10, 11, 16, 20], 
  5.   [23, 30, 34, 50] 
  6. target = 3 
  7. 输出: true 


示例 2:


  1. 输入: 
  2. matrix = [ 
  3.   [1, 3, 5, 7], 
  4.   [10, 11, 16, 20], 
  5.   [23, 30, 34, 50] 
  6. target = 13 
  7. 输出: false 


百度高级研发工程师 Kimze

针对不同层次的候选,作为面试官肯定有所侧重。在算法训练营中有不少是在校的学生,针对应届毕业生的话,我主要是考察态度、编程基础,以及数据结构和算法的基本功。对于有经验的同学来说,我会结合简历技能,围绕项目经验,考察领域能力的广度和深度,探知到候选人的上限,也可以互相交流学习。

高可用、高性能、高扩展性作为后端通用的技术,针对不同技术栈,我会考察:

  • 分布式分层架构设计理解
  • LB 负载均衡、前端压缩 /CDN 缓存 /DNS 相关知识
  • 多级缓存、MQ 异步解耦
  • 无状态化设计 -> 快速扩缩容
  • DB Sharding 、读写分离、分库分表、SQL 和慢查询优化、JVM 优化等措施
  • ES 检索、数据异构、大数据处理
  • 一致性设计:批量异步、串行改并行、同步改异步
  • 数据协议、通信协议
  • 容量预估规划、全链路压测、灰度发布设计、降级 / 熔断 / 限流的设计、RPC 服务治理
  • 分布式配置、注册、监控
  • CI/CD:“Docker + Kubernetes”架构

对于数据结构和算法的考察,比较基础的如快排、归并、二分查找的题目,候选人要能分析出时间和空间复杂度,并展示出相关推演的过程。对于高级一些的内容,我最低的要求是有思路,知道什么情况下用什么样的数据结构和算法,并写出模板即可。比如我会问:

Redis 底层数据结构设计,引申出跳表的原理,再扩展到 Hash 的实现及扩容实现,希望考察候选人是否了解跳表优缺点, 以及 Redis 为什么这么设计。

MySQL B+ 树索引结构的时间复杂度以及选型原因,希望考察为什么使用 B+ 树而不是红黑树或 Hash、跳表。

我考察的具体题目并不多,我认为非常好的一道题目是:零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:


  1. 输入: coins = [1, 2, 5], amount = 11 
  2. 输出: 3 

解释:11 = 5 + 5 + 1

示例 2:


  1. 输入: coins = [2], amount = 3 
  2. 输出: -1 

说明:

你可以认为每种硬币的数量是无限的。

Serko 高级软件工程师 Xu;

不同公司、不同职位、不同级别所要求能力、范围和深度不一样,海外公司和国内互联网公司的业务需求也有很大不同,但我认为作为程序员一般需要具备下面能力:

  • 编程能力(编码、数据结构和算法、数学)
  • 简洁代码(Clean code)
  • 好的编程实践(Good programming practices)
  • 软件设计
  • 系统设计
  • 软件架构
  • 系统架构
  • 分析和解决问题能力
  • 领导力
  • 沟通表达能力
  • 合作能力
  • 分享能力
  • 持续学习能力

对于大多数需要面试的初级和中级程序员来说,作为技术面第一轮的白板算法题,我一般会出 LeetCode 上 easy 到 meduim 的题目,这类题目一般可以暴力求解、能够优化,有多种解法和思路,同时候选人最好能够展示一些软件工程方面的实力。

在做题过程中,有几点需要注意:

  • 理解题目,在这个过程中要和面试官沟通,澄清题目的要求和相关疑问,而不是一上来就开始写程序。
  • 设计算法,在这个过程中和面试官不断互动,一步一步探寻最优解,而不是一声不吭,一个人”埋头苦干“。
  • 实现算法,在这个过程中可以展示你对软件开发和测试的理解。
  • 代码完成后,酌情可以和面试官讨论一些相关东西,比如 TDD、BDD、CI/CD 等。

我的精选算法面试题是:验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:


  1. 输入: 
  2.  
  3.     2 
  4.    / \ 
  5.   1   3 
  6.  
  7. 输出: true 

示例 2:


  1. 输入: 
  2.     5 
  3.    / \ 
  4.   1   4 
  5.      / \ 
  6.     3   6 
  7. 输出: false 
  8. 解释: 输入为: [5,1,4,null,null,3,6]。 
  9.      根节点的值为 5 ,但是其右子节点值为 4 。 


以上这些题目你都会做了吗?

什么?你不会?那也不用捉急,同其他编程技能一样,高效掌握常见的算法与数据结构知识,并学会用相应的算法来解决实际工作和面试中的算法问题,都是 可以通过学习和训练不断提高的。