7步解决算法问题

#计算机08:0692

众译鸣谢

原文字幕:原文字幕由译学馆搜集制作完成

译文字幕:[B]hugue于2017.07.28制作完成

审核过程:2

字幕详情

嗨 我是《程序员面试金典》的作者Gayle Laakmann McDowelll 今天我们要
讲述如何用7步解决算法问题 这不会减慢你(解决问题)的速度
相反 按照这个步骤还可以加快你的速度
所以我希望你能把它用在面试及面试的准备中
第一步是认真听问题 一般来说
在解决问题时每个细节都必不可少——无论你想找出所有解
还是想找出最优解 如果在你的算法中
有些细节没用到
一定要考虑一下可以把它用在哪 因为它可能对于
找到问题最优解是必须的 比如说 有两个
已排序且不同的数组 怎么才能找到它们的公共元素的数量呢?
许多人解决这个问题时会被难住一会儿
他们要做的是解决问题
他们知道数组已排序 但却没用到这个条件
已排序这个细节对于解决问题不是必须的
但它对于找到问题最优解是必须的 所以一定要记住问题的每一个细节
并且确保你用到了它们 第二步是有一个好的示例
对于上个问题:计算出两个已排序且不同的数组
的公共元素个数
多数人的例子就像这样 技术上来讲它也可以
但是没什么用 只要你看一下这个例子 就可以发现
它们只有一个公共元素 并且很明显就可以看出是哪一个
因为这个数组太小了 并且它有点特殊
更好的例子是这样的 数组更大且没有特殊值
提升你在算法问题上的表现的最好方法之一
是有更大的示例并且避免特殊情况
第三步是想出一个暴力算法
我并不是说要你费力去想出一个非常慢的算法
我的意思是 如果一开始你的算法
很慢 很糟糕
也没关系 刚开始有一个很慢的算法要比
什么也没有好多了
所以即使你的第一个算法很慢也没关系
非常非常重要的一点是
我不是要你去写出暴力算法的代码
而是去讲述你的暴力算法 说明它的运行时间
然后立即着手优化 算法问题的面试中
大多数时间应该花费在优化上 这就是第四步
一定要在它上面多花时间 一旦有了最优算法或者
准备写代码的时候 回想一下 确保你完全清楚
代码中要写什么 许多人在对要写什么还不完全清楚的情况下
就过早的开始写代码 最后以失败收场
对于你要写什么 理解80%是不够的
尤其是在白板上写时 所以花些时间从头到尾思考你的算法
确保你完全清楚自己要写什么
第六步是开始写代码 这个我要讲一些细节
有两件事需要记住 特别是在白板上写代码时
第一个技巧是在白板要尽量要把每一行写直
我并不是想评判你的手写笔迹或其他什么
但是人们开始写水平或者有些倾斜的一行时
他们就不知道if语句是写在for循环上面还是下面了
第二件事是明智地使用白板擦 如果白板上的东西你不需要了
就擦掉它
还有像从左上角开始写等 基本上尽可能的多留出空间
来写代码 如果确实没地方可以写了
用箭头也可以 我不会从这种事上来评判你
更重要的一点是 编程风格在白板上
和在电脑上一样重要 就是像大括号
命名习惯 即驼峰命名还是用下划线这种东西
这些风格上的东西绝对很重要
我不在乎你使用那种编程风格 我不在乎大括号
是否换行 我在乎的是你有自己的编程风格
并且风格统一 所以一定要坚持你的风格 涉及到变量名的时候
我知道在白板上写很长的变量名很令人恼火
但是对于一种好的编程风格来说 描述性的变量名很重要 有一种折衷的办法
第一次时写描述性的变量名 然后询问面试者
下次是否可以简写
这是一次很小的折衷——既说明了你重视好的变量名
又不会浪费大量时间 我想说的最后一件事是模块化
模块化你的代码 任何小的概念上的代码块都要模块化
把它们封装成函数 假设你的算法有三步
分别为:处理第一个字符串 处理第二个字符串以及比较它们的结果
不要一开始就写for循环遍历每个字符串
要先写一个包括这三步的总函数
包括第一步 第二步 第三步 然后再深入
处理所有的细节 记住所有概念上的代码块都要
封装到其他函数里 不要直接写在里面 一旦写完代码
你就要开始测试代码 许多人常犯的一个错误是
直接使用步骤二中的示例作为测试案例
问题是它太大了 会运行很长时间
而且你是参照这个例子写的代码 即使算法中有错误
在测试中也发现不了 问题仍会存在
更好的做法是
一行行的遍历你的代码 思考每一行代码
不用任何测试案例 只是思考代码是否做了正确的事
仔细检查任何看起来奇怪的地方 比如说for循环中是递减而不是递增
涉及到数学的地方也普遍会出错
思索 分析你的代码 考虑最容易出错的地方
并且仔细检查那里 你真正开始测试代码时
要用小的测试案例而不是大的 小的测试案例和
大的测试案例同样有效而且运行更快
实际上 因为运行地更快
人们还是十分倾向于使用小测试案例 小测试案例
发现错误的可能性要更大 所以刚开始使用小测试案例
再测试边缘情况 如果还有时间的话
就可以使用大的测试案例 最后有几个测试技巧
第一个是在你测试的时候 要想清楚自己在做什么
许多人在测试的时候 只是像机器人一样
运行他们的代码 他们只在输出后
看一下最后结果是否有意义
边测试边思考要好得多
这样你可以在错误发生时尽快发现它 而不是要到代码最后才发现
第二个技巧是测试时 确保你测试的是代码
而不是算法 许多人只是
使用示例一遍遍运行他们的算法
但他们甚至连代码也不看
他们不看代码具体会做哪些计算
所以要确保你是真正在测试代码 最后一件事是当你发现了
bug的时候
不要惊慌 只要认真思考是什么导致了这个bug 多数时候
人们会惊慌 并且第一次只会尝试修复输出的内容
但是却没认真思考过 然后他们就会
陷入更糟糕的处境 因为如果你错误的修改了代码
只修改了输出 却没修复真正的bug 那么你就不是在修复bug
而是把代码变得更复杂了 而且可能潜在地又导致了
一个新bug 你的处境就更糟糕了
如果你发现了bug
也没关系 有bug也不是什么大问题 这很正常
只是要想清楚bug是什么 来自哪里
现在你已经知道这7步了 我真心希望
在处理新问题时 你能使用它们 无论是在面试准备
还是在真正的面试中 祝你好运
以下内容有剧透 , 请注意打开姿势

精彩推荐

  • 数据结构:变位词问题的解法

    06:4133

  • 数据结构:堆

    10:3236

  • 公司如何评估技术面试者

    06:2811

  • 算法:记忆化和动态规划

    11:1641

  • 算法:位运算

    09:0516

  • 3个算法策略

    07:0033

  • 完全初学者编程入门指南

    09:13274

  • 【创始人世界2015】Daniel Katz: Artisan Ethos公司

    04:2787

更多视频, 请移步译学馆APP欣赏  GET APP