3个算法策略 – 译学馆

• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 3个算法策略

3 Algorithm Strategies

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.

Today I’m going to talk about three algorithm strategies that I find super useful for solving problems.

These three strategies are called BUD, space/time trade-offs, and DIY, do-it-yourself.

The first one we’ll talk about is BUD. BUD means to walk through your brute force,

or whatever your best algorithm is right now,

and look for bottlenecks, unnecessary work, and duplicated work.

Let’s talk about bottlenecks. Consider the following problem – you have two arrays, both which have

distinct elements, how would you compute the number of elements in common between the two arrays?

So one way of doing it is we take each element in the first array

and we walk through the second array and check if it contains that element.

That will give us an O of A times B algorithm. So with the bottlenecks technique what we’re doing is

say ok where is the bottleneck and how can we get rid of it, or how can we reduce it?

So in this case the bottleneck comes from these continuous contains operations.

Is there 1, is there 5, is there a 12?

What’s the fastest way of doing contains operation?

Well we could use a hash set – take everything in B and throw it into a hash set,

and then we can get an O of A plus B algorithm. So that’s the bottleneck technique.

Identify the bottleneck and really focus on getting rid of it.
BUD的下一部分是不必要的工作 让我们来考虑这个问题
The next part of BUD is unnecessary work. So let’s consider this problem.

b c and d are integers between 1 and 1000. So one way of doing this is just a brute force.

Walk through all possible solutions and check to see if a cubed plus b cubed

equals c cubed plus d cubed. So this will work. It’s very slow, it’ll give us an n to the fourth

algorithm but one thing we might notice is, hey, you know, once we find

a value of a b c d that works we can add a break statement after that because there

can’t be more values of d that work for the same value of ab&c. And that should

make us think well is there a faster way of getting to that? And yes there is,

If there’s only one value of d that works for every given ab&c we can just solve for d.

And so this unnecessary work is, pay attention to all these little break

statements and these little, these kind of minor optimizations. Sometimes

they don’t change the Big O time in and of themselves, but they’re related to bigger
BUD的第三部分是重复工作
changes that actually will. The third part of BUD is duplicated work so let’s

go back again to this a cubed plus b cubed equals c cubed plus d cubed problem.

One thing you might notice here is that we’re repeating the c/d loop over and

over and over again. For every element for every pair a/b we’re generating all

pairs c/d and checking for matches in every single one. That happens over and

over again, how can we leverage that work? Well one thing we could do is create

this table of all c/d values and the c cubed plus d cubed result and then for each a/b

pair look for the a cubed plus b cubed in that column there. If we want to do that

though, let’s really restructure the table as a hash map that maps from a c cubed plus

d cubed to each pair that got us that. Then for each a/b we can compute a cubed plus b cubed and

pull out that match from that hash table. So that’s duplicated work. When you

notice yourself doing work over and over again, really think about how can you

leverage that. So that’s the BUD technique. Walk through your brute force or whatever your

best algorithm is and look for the bottlenecks, look for the unnecessary work,

and look for the duplicated work. The second technique is space/time

trade-offs. So often this means using a different data structure very very

frequently as a hash table and seeing if you can apply it to that problem.

So you’re using more space but hopefully getting a time optimization in the

process. We can see this technique applied to the previous problem. You have
a³+b³=c³+d³ 我们能通过更多地使用一整个空间
this equation a cubed plus b cubed equals c cubed plus d cubed. We were able to save ourselves

time by using a whole bunch more space. So one just little technique is have

hash tables at the top of your mind. A lot of times in problems you save

yourself time by using a bit of extra space. The final technique to discuss is

what I call DIY or do it yourself.

So let’s consider this problem. You have two strings –
s是小的字符串 b是大的字符串 找到s在b中的所有排列
s is a small string b is the big string – find all permutations of s within b. So

one brute force way of doing this is generating all the permutations of s and

looking for every single one within b. But that’s going to be really really slow.

We’re talking about an algorithm that’s going to take at least s factorial times b time

and it might be even worse than that.

Let’s scrap that and go back to step 2, which was a draw big example. So here’s a

really big example. Now I encourage with this point to pause the video and

actually go in and find all the permutations of s within b. So literally just pause it,

do it right now, pause the video and compute the answer here.

However you want to do it don’t worry about algorithms, just do it however you want to

do it. So one thing, that if you’re like most people, and you actually did this as I asked,

you might have noticed that you never actually generated all the
s在b中的所有排列 是吗？你从未生成所有
permutations of s within b did you? You never actually generate all
s的排列 你做的可能更像是这样
permutations of s. What you probably did was something more like this. You

probably moved through b, in windows of size s, saying is this a permutation, is this

a permutation, is this a permutation? Or maybe you did something else like take the first

character s, look for that within b, and then look at the surrounding

characters. Whatever you’re doing your algorithm is probably somewhere between s

squared times b and maybe even as fast as O of b and this happens for a lot of

problems, there’s a lot of problems where people’s algorithm is really really

complex or really really slow or they just get completely stuck, but given an

actual example, the way that your brain will just intuitively find the right

output is actually often a pretty good algorithm. So part of why I push so much to

come up with a really big example and making sure it’s, you know, really generic

and doesn’t have special cases in it, is that if you put yourself in position

where your brain has to do work, you might be able to just have an

algorithm just flow out very naturally from that. So make your examples large and

let your brain do its thing, get the output manually, however you want to do

it and then try to reverse-engineer that thought process and figure out what

exactly did your brain actually do to get that result.

So those are the three techniques I use all the time for solving problems. BUD is
BUD是瓶颈 不必要和重复的工作 时/空权衡 这很多都
bottlenecks, unnecessary work and duplicated work, space/time trade-off so a lot of that

means hash tables, and then do it yourself, really rely on examples and

these we use for a huge variety of problems and can really help you make a

lot of progress on otherwise difficult problems.

So now that you know these three techniques try them out on a few

problems of your own. Good Luck.

##### 译制信息

《程序员面试金典》的作者 盖尔·拉克曼·麦克道尔应对难题的三个算法策略。

B11101001