最新评论 (0)


7 Steps to Solve Algorithm Problems

嗨 我是《程序员面试金典》的作者Gayle Laakmann McDowelll 今天我们要
Hi, I’m Gayle Laakmann McDowelll, author of Cracking the Coding Interview. Today we’re going to
讲述如何用7步解决算法问题 这不会减慢你(解决问题)的速度
cover seven steps to solve algorithm problems. These will not slow you down. On the
相反 按照这个步骤还可以加快你的速度
contrary it will actually speed you up if you follow this process. So I really
encourage you to do that both in your preparation and in the real interview. The
第一步是认真听问题 一般来说
first step is to listen carefully to the problem. So, generally speaking every
single detail in a question is necessary to solve that problem – either to solve it
还是想找出最优解 如果在你的算法中
all or to solve it optimally. So if there’s some detail you haven’t used in
the question in your algorithm so far
一定要考虑一下可以把它用在哪 因为它可能对于
think about how you can put that to use because it might be necessary to solve
找到问题最优解是必须的 比如说 有两个
the problem optimally. Let me give you an example. You have two arrays, sorted and
已排序且不同的数组 怎么才能找到它们的公共元素的数量呢?
distinct – how did you find the number of elements in common between the two
arrays? A lot of people solve this problem and they’ll get kind of stuck for awhile
and what they’ll do is they’ll be solving the problem and they’ll know the
他们知道数组已排序 但却没用到这个条件
arrays are sorted but they haven’t actually used the fact that it’s sorted. This
sorting detail – it’s not necessary just to find an algorithm but it is necessary to
但它对于找到问题最优解是必须的 所以一定要记住问题的每一个细节
solve the problem optimally. So remember every single detail in the problem and
并且确保你用到了它们 第二步是有一个好的示例
make sure you use it. The second piece is to come up with a good example, so the
last problem that I gave two arrays sorted and distinct compute the number of
elements in common,
多数人的例子就像这样 技术上来讲它也可以
most people’s examples look like this. Yes technically if it’s a problem but
但是没什么用 只要你看一下这个例子 就可以发现
it’s not very useful. As soon as you glance at this example you notice that
它们只有一个公共元素 并且很明显就可以看出是哪一个
there’s only one element common and you know exactly what it is and it’s obvious
因为这个数组太小了 并且它有点特殊
because this example is so small and it’s actually kind of a special case. A better
更好的例子是这样的 数组更大且没有特殊值
example is something like this – much larger and you’ve avoided some special
cases. One of the easiest ways of improving your performance on algorithm questions
is just make your examples larger and really avoid special cases.
The third step is to come up with a brute force algorithm.
Now I’m not saying you need to go out of your way to come up with something slow,
我的意思是 如果一开始你的算法
I’m really just saying, hey if the first thing you have is only something really
很慢 很糟糕
really slow and terrible
也没关系 刚开始有一个很慢的算法要比
that’s okay. It is so much better to start off with something slow then to
start off with nothing at all.
So it’s fine if your first algorithm is slow and terrible whatever. However, and this is
very very very important,
I’m not saying to code the brute force.
而是去讲述你的暴力算法 说明它的运行时间
I’m saying just state your brute force algorithm, state its runtime, and then
然后立即着手优化 算法问题的面试中
immediately go to optimizing. A good chunk of the time on algorithm interview
大多数时间应该花费在优化上 这就是第四步
question will often be spent on optimizations. So that’s step 4 and spend
一定要在它上面多花时间 一旦有了最优算法或者
some good time on it. Then once you have an optimal algorithm or you’re ready to
准备写代码的时候 回想一下 确保你完全清楚
start coding take a step back and just make sure you know exactly what you’re
代码中要写什么 许多人在对要写什么还不完全清楚的情况下
going to do in your code. So many people code prematurely when they aren’t really
就过早的开始写代码 最后以失败收场
really comfortable with what they’re about to do and it ends in disaster. An eighty percent
对于你要写什么 理解80%是不够的
understanding of what you’re about to write is really not enough for a
尤其是在白板上写时 所以花些时间从头到尾思考你的算法
whiteboard especially. So take a moment and walk through your algorithm and make
sure you know exactly what you’re about to do.
第六步是开始写代码 这个我要讲一些细节
Step 6 is to start coding and I’m gonna go into this in a bit of detail. So
有两件事需要记住 特别是在白板上写代码时
a couple things to keep in mind particularly when you’re coding on a whiteboard. The
first couple tips are kind of whiteboard specific but try to write your lines
straight. I’m not gonna be judging you on your handwriting and things like that but
when people start writing their lines and sharp angles they start to lose
track over whether this if statement under this for loop or not. The second
第二件事是明智地使用白板擦 如果白板上的东西你不需要了
thing is use your board space wisely. If you don’t need stuff up on the board
anymore just erase it.
还有像从左上角开始写等 基本上尽可能的多留出空间
Try to write in this top left corner etc. Basically give yourself as much space as
来写代码 如果确实没地方可以写了
you possibly can to write your code. If you do run out of space though, it’s ok
用箭头也可以 我不会从这种事上来评判你
to use arrows, that’s fine, I’m really not gonna be judging you on this kind of
更重要的一点是 编程风格在白板上
stuff. So more important things. Coding style matters even on a
和在电脑上一样重要 就是像大括号
whiteboard but on a computer as well, so that means things like braces, naming
命名习惯 即驼峰命名还是用下划线这种东西
conventions, or using camel case or underscores, things like that. Those kind
of style things absolutely matter.
我不在乎你使用那种编程风格 我不在乎大括号
I’m not that concerned over which style you pick, I don’t care if you write braces
是否换行 我在乎的是你有自己的编程风格
on the same line or the next line but I do care a lot that you have a style and you
并且风格统一 所以一定要坚持你的风格 涉及到变量名的时候
stick to it. So be consistent in your style. When it comes to variable names,
yeah I know it’s an annoying to write long variable names on a whiteboard but
但是对于一种好的编程风格来说 描述性的变量名很重要 有一种折衷的办法
descriptive variable names are important to good style. So one compromise here is
第一次时写描述性的变量名 然后询问面试者
write the good descriptive variable name first and then just ask your interviewer,
hey is it okay if I abbreviate this the next time.
So that’ll be a nice little compromise – you’d show that you care about good variable
又不会浪费大量时间 我想说的最后一件事是模块化
names but you also don’t waste a lot of time. Last thing I want to talk about is modularization.
模块化你的代码 任何小的概念上的代码块都要模块化
Modularize your code up front and just any little conceptual chunks of code,
把它们封装成函数 假设你的算法有三步
push that off to another function. So suppose you have three steps in your
分别为:处理第一个字符串 处理第二个字符串以及比较它们的结果
algorithm – process the first string, process the second string, and then compare the
results. Don’t start writing these for loops that walk through each string in the
very beginning. Instead write this overall function that wraps these three
包括第一步 第二步 第三步 然后再深入
steps. So step one, step two, step three, and then start drilling in and going
处理所有的细节 记住所有概念上的代码块都要
into all the details there. Remember any conceptual chunks of code push those off
封装到其他函数里 不要直接写在里面 一旦写完代码
to other functions, don’t write them in line. Then once you’re done with the
你就要开始测试代码 许多人常犯的一个错误是
coding you have to start testing your code. One of the mistakes a lot of people
do here is they take their big example from step 2 and throw that in as a test
问题是它太大了 会运行很长时间
case. The problem with that is it’s very large so it will take you a long time to run through
而且你是参照这个例子写的代码 即使算法中有错误
but also you just used that to develop your code, so if here’s an oversight there,
在测试中也发现不了 问题仍会存在
the problem will probably repeat itself here.
What’s a better step to do, what’s a better process to do, is just walk
一行行的遍历你的代码 思考每一行代码
through your code line by line and just think about each line up front not with
不用任何测试案例 只是思考代码是否做了正确的事
the test case but just consider, is it really doing the right thing?
仔细检查任何看起来奇怪的地方 比如说for循环中是递减而不是递增
Double check anything that looks weird, so for loops that decrement instead of increment and
any math at all is a really common place for errors. Just think, look
思索 分析你的代码 考虑最容易出错的地方
at your code analytically and think what are the most likely places for errors
并且仔细检查那里 你真正开始测试代码时
to be and double-check those. Then once you start with actual test cases start
要用小的测试案例而不是大的 小的测试案例和
with small test cases rather than big ones. Small test cases work pretty much
as effectively as big test cases but they are so much faster to run through,
实际上 因为运行地更快
and in fact because they’re faster
人们还是十分倾向于使用小测试案例 小测试案例
people tend to be much more thorough so you’re much more likely to actually find
发现错误的可能性要更大 所以刚开始使用小测试案例
bugs with small test cases than big test cases. So start with small test cases
再测试边缘情况 如果还有时间的话
then go in to edge cases after that and then if you have time maybe throw in
就可以使用大的测试案例 最后有几个测试技巧
some big test cases. A couple last techniques with testing. The first one is
第一个是在你测试的时候 要想清楚自己在做什么
make sure that when you’re testing you’re really thinking about what you’re
许多人在测试的时候 只是像机器人一样
doing. A lot of people when they’re testing they’re just walking through
运行他们的代码 他们只在输出后
their code almost like they’re a bot, and they only look to see if things made
sense at the very end when they look at
their output. It’s much better to really think as you’re testing, this way you find
这样你可以在错误发生时尽快发现它 而不是要到代码最后才发现
the bug as soon as it happens rather than six lines later at the very bottom.
第二个技巧是测试时 确保你测试的是代码
The second thing is when you’re testing make sure that you’re actually testing
而不是算法 许多人只是
your code and not your algorithm. An amazing number of people will just take
their example and like just walk through it again as though they’re just walking
through their algorithm but they’re never even looking at their code, they’re
not looking at the exact calculations their code actually did. So make sure
所以要确保你是真正在测试代码 最后一件事是当你发现了
that you’re really testing your code. Then the last thing is when you find in
a bug,
不要惊慌 只要认真思考是什么导致了这个bug 多数时候
don’t panic. Just really think about what caused the bug. A lot of times people
人们会惊慌 并且第一次只会尝试修复输出的内容
will panic and just try to make the first fix that fixes it for that output
但是却没认真思考过 然后他们就会
but they haven’t really given it some thought and then they’re in a much
陷入更糟糕的处境 因为如果你错误的修改了代码
worse position because if you make the wrong fix to your code, the thing that just
只修改了输出 却没修复真正的bug 那么你就不是在修复bug
fixed the output but didn’t fix a real bug you’ve not fixed the actual
而是把代码变得更复杂了 而且可能潜在地又导致了
bug, you’ve made your code more complex, and you potentially introduced a brand
一个新bug 你的处境就更糟糕了
new bug and you’re in a much worse position. It’s much better to just when
you find the bug,
也没关系 有bug也不是什么大问题 这很正常
it’s ok, it’s not that big of a deal to have a bug it’s very normal just really
只是要想清楚bug是什么 来自哪里
think through what the actual bug, where the actual plug came from.
现在你已经知道这7步了 我真心希望
So now that you’ve seen these seven steps I really encourage you to follow
在处理新问题时 你能使用它们 无论是在面试准备
this process on new questions both in your preparation as well as in the
还是在真正的面试中 祝你好运
actual interview. Good luck.