没有合适的资源?快使用搜索试试~ 我知道了~
首页算法面试宝典:实战与机器学习问题解析
算法面试宝典:实战与机器学习问题解析
需积分: 9 7 下载量 100 浏览量
更新于2024-07-18
收藏 22.04MB PDF 举报
"《算法面试指南》是一本由Adnan Aziz教授和Amit Prakash联合编写的书籍,专注于帮助求职者准备面试过程中常被问及的各种算法问题。Aziz教授是德克萨斯大学奥斯汀分校电气与计算机工程系的教授,他在实际算法设计和教育领域有着深厚背景,拥有伯克利大学的博士学位以及印度理工学院坎普尔分校的本科学位。他曾在Google、高通、IBM等公司工作,并参与过多个软件初创公司的项目,业余时间则专注于陪伴家人。 Amit Prakash是谷歌的技术成员,他的主要研究集中在机器学习领域,特别是在在线广告中的问题解决。他在微软的搜索引擎团队工作过,持有奥斯汀大学的博士学位,同样来自印度理工学院坎普尔分校。除了技术工作,他还对谜题、电影、旅行和与妻子共同的冒险充满热情。 本书《Algorithms for Interviews》以问题解决的方法论为核心,提供了丰富的算法示例,覆盖了面试中常见的数据结构、搜索算法、排序算法、动态规划、图论等多个主题。它不仅有助于求职者提升算法技能,也适合那些希望深化理解或更新算法知识的专业人士。此外,由于版权原因,所有内容未经许可不得复制或重印,确保了知识的原创性和专业性。这本书对于希望在IT行业取得成功并经历面试挑战的读者来说,是一份宝贵的资源和指导。"
资源详情
资源推荐
10
Graph
modeling
Drawing
pictures
isa
great
way
to
brainstorm
for
a
potential
solution.
If
the
relationships
ina
given
problem
can
be
represented
using
a
graph,
quite
often
the
problem
can
be
reduced
to
a
well-known
graph
problem.
For example, suppose you are given a set of barter rates between com
modities
and
you
are
supposed
to
find
out
ifan
arbitrage
exists,
i.e.,
there
isa
way
by
which
you
can
start
with
a
units
of
some
commodity
C
and
perform a seriesofbarters whichresultsin having more than a units of
C.
We
can
model
the
problem
with a graph
where
commodities
corre
spond
to
vertices,
barters
correspond
to
edges,
and
the
edge
weight
is
set
to
the
logarithm
of
the
barter
rate.
If
we
can
find
a
cycle
in
the
graph
with
a
positive
weight,
we
would
have
found
such
a
series
of
exchanges.
Sucha
cycle
canbe solved using the
Bellman-Ford
algorithm
(cf.
Prob
lem
4.19).
J'
Write
an
equation
Some
problems
can
be
solved
by
expressing
them
in
the
language
of
mathematics.
For
example,
suppose
you
were
asked
to
write
an
algo
rithm that computed binomial coefficients, (?) =
,„"*„
x '
\kJ
k\(n-k)\'
The
problem
with
computing
the
binomial
coefficient
directly
from
the
definition
is
that
the
factorial
function
grows
very
quickly
and
can
overflow
an
integer
variable.
If
we
use
floating
point
representations
for
numbers,
we
lose
precision
and
the
problem
of
overflow
does
not
go
away.
These
problems
potentially
exist
even
if
the
final
value
of
(£)
is
small.
One
can
try
to
factor
the
numerator
and
denominator
and
try
and
cancel
out
common
terms
but
factorization
is
itself
a
hard
problem.
The
binomial
coefficients
satisfy
the
addition
formula:
n\ =
fn-l\
fn-1
k]
V * /
U-l
This
identity
leads
to
a
straightforward
recursion
for
computing
(?)
which
avoids
the
problems
mentioned
above.
Dynamic
programming
has to be used to
achieve
good
time
complexity—details
are in
Prob
lem
9.1.
Auxiliary
Elements
Consider
an8x8
square
board
in
which
two
squares
on
diagonally
oppo
site
corners
are
removed.
You
are
given
asetof
thirty-one
2x1
dominoes
and
are
asked
to
cover
the
board
with
them.
PROBLEM
SOLVING
TECHNIQUES
11
After
some
(ora
lot)
of
trial-and-error,
youmay
begin
to
wonder
if
a
such
a
configuration
exists.
Proving
an
impossibility
result
may
seem
hard.
However
if
you
think
of
the
8 x 8
square
board
asa
chessboard,
you
will
observe
that
the
removed
corners
are
of
the
same
color.
Hence
theboard consistsofeither30white squaresand 32blacksquares or vice
versa. Since a domino will always cover two adjacent squares, any ar
rangement
of
dominoes
must
cover
the
same
number
of
black
and
white
squares.
Hence
no
such
configuration
exists.
The
original
problem
did
not
talk
about
the
colors
of
the
squares.
Adding
these
colors
to
the
squares
makes
it
easy
to
prove
impossibility,
illustrating the
strategy
of
adding
auxiliary
elements.
Variation
Suppose
we
were
asked
to
design
an
algorithm
which
takes
as
input
an
undirected
graph
and
produces
as
output
a
black
or
white
coloring
of
the
vertices
such
that
for
every
vertex,
at
least
half
ofits
neighbors
differ
in
color
from
it.
We
could
tryto
solve
this
problem
by
assigning
arbitrary
colors
to
vertices
and
then
flipping
colors
wherever
constraints
are
not
met.
How
ever
this
approach
does
not
converge
on
all
examples.
Itturnsoutwecan
define
a
slightly
different
problem
whose
solution
will
yield
the
coloring
we
are
looking
for.
Define
an
edge
to
be
diverse
if
its ends have different colors. It is easy to verify that a color assignment
that
maximizes
the numberof diverse edges
also
satisfies
the constraint
of
the
original
problem.
The
number
of
diverse
edges
can
be
maximized
greedily
flipping
the
colors
of
vertices
that
would
lead
to
a
higher
num
ber ofdiverse
edges;
details are
given
in
Problem
4.11.
Parallelism
In
the
context
of
interview
questions,
parallelism
is
useful
when
dealing
with
scale,
i.e.,
when
the
problem
is
so
large
that
itis
impossible
to
solve
it
on
a
single
machine
or
it
would
take
a
very
long
time.
The
key
insight
you
need
to
display
is
how
to
decompose
the
problem
such
that
(1.)
each
subproblem
can
be
solved
relatively
independently
and
(2.)
constructing
the
solution
tothe
original
problem
from
solutions
tothe
subproblems
is
not
expensive
in
terms
of
CPU
time,
main
memory,
and
network
usage.
Consider
the
problem
of
sorting
a
petascale
integer
array.
Ifwe
know
the distribution of the numbers, the best approach would be to define
equal-sized
ranges
of
integers
and
send
one
range
to
one
machine
for
sorting.
The
sorted
numbers
would
just
need
tobe
concatenated
in
the
correct order. If the distribution is not known then we can send equal-
sized
arbitrary
subsets
to
each
machine
and
then
merge
the
sorted
results
12
using
a
min-heap.
For
details
on
petascale
sorting,
please
refer
to
Prob
lem
2.2.
Caching
Caching
is
a
great
tool
whenever
there
is
a
possibility
of
repeating
com
putations.
For
example,
the
central
idea
behind
dynamic
programming
is
caching
results
from
intermediate
computations.
Caching
becomes
ex
tremely
useful
in
another
setting
where
requests
come
to a
service
in
an
online
fashion
and
a
small
number
of
requests
take
up
a
significant
amount
of
compute
power.
Workloads
on
web
services
exhibit
this
prop
erty;
Problem
7.1
describes
onesuch
problem.
Symmetry
While
symmetry
is
a
simple
concept
it
can
be
used
to
solve
very
difficult
problems,
sometimes
in
less
than
intuitive
ways.
Consider
a
2-player
game in which players alternately take bites from a chocolatebar. The
chocolate
bar
is
an
nxm
rectangle;
a
bite
must
remove
a
square
and
all
squares
above
and
to
the
right
in
the
chocolate
bar.
The
first
player
to
eat
the
lower
leftmost
square
loses
(think
of
it
as
being
poisoned).
Suppose
we
are
asked
whether
we
would
prefer
to
play
first
or
sec
ond.
One
approach
is
to
make
the
observation
that
the
game
is
sym
metrical
for
Player
1
and
Player
2,
except
for
their
starting
state.
If
we
assume
that
there
isno
winning
strategy
for
Player
1,
then
there
must
be
a
way
for
Player
2
to
win
if
Player
1
bites
the
top
right
square
in
his
first
move.
Whatever
move
Player
2
makes
after
that
can
always
be
made
by
Player
1as
his
first
move.
Hence
Player
1
can
always
win.
For
a
detailed
discussion,
refer
to
the
Problem
9.13.
Conclusion
In
addition
to
developing
intuition
for
which
technique
may
apply
to
which
problem,
it
is
also
important
to
know
when
your
technique
is
not
working and
quickly
move
toyournextbest
guess.
Inan interview set
ting,
even
if
you
do
not
end
up
solving
the
problem
entirely,
you
will
get
credit
for
applying
these
techniques
in
a
systematic
way
and
clearly
communicating your approach to the problem. We cover nontechnical
aspects ofproblem solving in Chapter 12.
Parti
Problems
Chapter
1
Searching
Searching
isa
basic
tool
that
every
programmer should keep in mind
foruseinawidevarietyof
situations.
"TheArt of Computer
Programming,
Volume
3-
Sorting
and Searching/' D. Knuth,
1973
Given
an
arbitrary
collection
of
n
keys,
the
only
way
to
determine
ifa
search
key
is
present
is
by
examining
each
element
which
yields
9(n)
complexity.
If
the
collection
is
"organized",
searching
can
be
sped
up
dramatically.
Of
course,
inserts
and
deletes
have
to
preserve
the
organi
zation;
there
are
several
ways
of
achieving
this.
Binary
Search
Binary
search
is
at
the
heart
of
more
interview
questions
than
any
other
single
algorithm.
Fundamentally,
binary
search
is a naturaldivide-and-
conquer
strategy
for
searching.
The
idea
isto
eliminate
half
the
keys
from
consideration
by
keeping
the
keys
in
a
sorted
array.
If
the
search
key
is
not
equal
to
the
middle
element
of
the
array,
one
of
the
two
sets
of
keys
to the left and to the right ofthe middle elementcan be eliminated from
further
consideration.
Questions
based
on
binary
search
are
ideal
from
the
interviewers
per
spective:
itisa
basic
technique
that
every
reasonable
candidate
is
sup
posed to know and it can be implemented in a few lines of code. On the
other
hand,
binary
search
is
much
trickier
to
implement
correctly
than
it
appears—you should implement it as well as write corner case tests to
ensure you understand it properly.
14
剩余221页未读,继续阅读
weixin_43718574
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- zlib-1.2.12压缩包解析与技术要点
- 微信小程序滑动选项卡源码模版发布
- Unity虚拟人物唇同步插件Oculus Lipsync介绍
- Nginx 1.18.0版本WinSW自动安装与管理指南
- Java Swing和JDBC实现的ATM系统源码解析
- 掌握Spark Streaming与Maven集成的分布式大数据处理
- 深入学习推荐系统:教程、案例与项目实践
- Web开发者必备的取色工具软件介绍
- C语言实现李春葆数据结构实验程序
- 超市管理系统开发:asp+SQL Server 2005实战
- Redis伪集群搭建教程与实践
- 掌握网络活动细节:Wireshark v3.6.3网络嗅探工具详解
- 全面掌握美赛:建模、分析与编程实现教程
- Java图书馆系统完整项目源码及SQL文件解析
- PCtoLCD2002软件:高效图片和字符取模转换
- Java开发的体育赛事在线购票系统源码分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功