UT Austin算法专家教授与Google工程师的面试心得

4星 · 超过85%的资源需积分: 4 116 浏览量更新于2024-07-27 收藏 15.46MB PDF 举报

"《算法面试指南》是一本由Adnan Aziz教授和Amit Prakash所编写的实用资源，两位作者分别在计算机工程领域有着丰富的经验和专业知识背景。Aziz教授是德克萨斯大学奥斯汀分校电气与计算机工程系的教授，他的研究和教学集中在应用算法上，拥有加州大学伯克利分校的博士学位以及印度理工学院坎普尔的本科学历。他在业界也有过经验，曾在谷歌、Qualcomm、IBM和多个软件初创公司工作，业余时间他还会陪伴他的孩子们Laila、Imran和Omar度过欢乐时光。 Amit Prakash则在谷歌担任技术主管，主要专注于在线广告中出现的机器学习问题。在加入谷歌之前，他在微软的网页搜索部门工作过。他也持有德克萨斯大学奥斯汀分校的博士学位，以及印度理工学院坎普尔的本科学位。Prakash除了提升广告质量外，还热衷于解谜、电影、旅行和与妻子一起的冒险活动，展现了他的多才多艺。本书旨在帮助求职者准备面试，深入浅出地讲解各种算法设计和解决实际问题的方法，覆盖了计算机科学的核心领域。它不仅提供了理论知识，也包含了许多实用技巧和策略，适用于那些希望在面试中脱颖而出的求职者。然而，必须强调的是，本书的所有内容受版权保护，未经许可不得复制、存储或通过任何形式（电子或机械）传播，包括但不限于机械检索系统和网络传播。如果你觉得这本书对你的职业发展有帮助，支持作者购买正版是一种尊重和鼓励他们继续分享他们的专业知识。"

CHAPTER

SORTING

2.6.

LEAST

DISL

生

NCESORTING

2.7 PRIVACY

AND

ANONY

肌lI

ZATION

已 OU

t"合

。

RRAN~

在

问~~自

S1A

l'tJ

时

。民警奋民

试制喝风

τf

LATtR

、..

•

悦。

延1'

革

在:

民已

良

HH~G

l'剖

GO~

υb

运时

Mov

E:.民§

气

SEVE

捷、

HoU

尺

吮

VfH

主'Y

飞

OVI

盹玛

INE

SOON&>

so~n

时吗

时

A.s€

叫睦

('..o£.

，

GIi铲

£l

每创\

leAN

MoR

怠

民

试

cos, of

I'4飞

P\l\f;.

Figure

The Massachusetts

Group

Insurance Commission

had

bright

idea

back

the

mid

1990s-it

decided

release

"anonymized"

data

state em-

2.6

LEAST

DISTANCE

SORTING

You come across a collection of

stone statues

a line. You

want

sort

them

height

with

the

shortest statue

the

lef

t.白

statues are

very

heavy

and

you

want

move

them

the least possible distance.

Problem

2.6: Design a sorting algorithm

that

minimizes the total dis-

tance

that

the statues are moved.

且

change-if

A beats B

one time-trial

and

Bbeats C

another time-

trial

then

A is

guaranteed

beat

C if

they

are

the same time-trial.

Problem

2.5: Wh

is the

minimum

number

of time-trials

needed

to de-

termine

who

send

to the Olympics?

一

large

array

whose

entries are

random

numbers.

一

large

array

htegers

that

is already almost sorted.

一

large collection of

htegers

that

are

drawRfrom

very

small

range.

-Aljfze

collectionofnumbersmostofwhich

are duplicates

-Stabiiityis

叫

蚓，

, the relative

order

two

records

that

have

the

same

sorthg

key

should

changed.

FINDING

THE

MIN

AND

MAX SIMULTANEOUSLY

iven a set of

numbers

you

can find either the

min

max

of the set

N-lcomParisoms

each.whm

you

need

fiI1d

bothy

you

better

than

- 3 comparisons?

Problem

2.4:

Find

the

min

and

max

elements from a set of N elements

usi

吨丑

than

- 1 comparisons.

2.5

EFFICIENT

TRIALS

You are the coach of a cycling

缸

with

members

and

need

to deter-

mine

the

fastest, second-fastest,

and

third-fastest cyclists for selection to

the Olympic

缸孔

You will

evaluating the cyclists

using

a time-trial course

日

which

dy5cyclists

race

time.You

use

the

completiOIItimes from a

time-trial

rmk

the

5cyclists amORgst

themselves-no

ties are possible

e cOI1ditions

caRChmge

over timer

you

camot

compare

perfop

mmces

across differeI1t

time-trials.The

relative

speeds

of cyclists does

2.3

FINDING

丑

WINNER

AND

RUNNER-UP

There are

128players

participathg

h a tenI1is tourI1ameIIt

Assume

that

the

beats

yry

relatimship

is tymsitiver

i.e-F

for

allplayers

and

if A beats

Band

Bbeats C,

then

A beats

Problem

2.3: Wh

is the least

number

of matches

need

to organize

fhd

the

best

player?How

maI137matches

you

I1eed to

fhd

the

best

and

the second

best

player?

2.2

TERASORT

The

sorthg

algorithms

alluded

above

assume

that

all

the

data

you

need

sort

will

fit h the

RAM.What

your

data

will

fit

恒

the

memory?

Problem

2.2: Sort a file containing

100

byte

strings.

If you find the book helpful, please purchase a copy to support the authors!

CHAPTER

SORTING

2.10.

MERGING SORTED

ARRAYS

ployees

that

showed

every

shgle

kospital visit

they

had.The

goal

was

help

the researchers. The state

spe

丑

time

removing

identifiers such

name

, addressy

social security

IIUmber-TM

Governor of

MaSE

sachlmtts

assured

the

public

that

this

was

suffideI1t

pmtect

patmt

privacy-TheI1a

graduate

studeI1tr LataI1ya sweeIIey>

saw

significmt pita

falls h

this

approach.She

requested a

copy

the

data

aRd

COIlathg

the

data

hmultiple

ColumRSrshe

was

able

idmtify

the

health

records

the

GoverI1or.This

demonstrated

that

extreme care I1eeds

takerl

OIIymizing

data.One

way

msuriIIg

privacy

aggregate

data

such

that

any

record

mapped

least k iI1dividualSF for some

large

value

Problem

2.7:Suppose

you

are

giveIIa

matrix

where

each

row

rep-

resents m iI1dividual

each

Colum

represeI1ts m attribute

about

the

hdividual

such

as age

geI1der.GiveI1a set of

ColumI1s

deletedy

vouwmt

determhe

if each

row

has

least k duplicate rows

with

缸

tly

the same contents

the

remaini

吨

仙

mns.

How

would

you

verify this efficiently?

2.8

VARIABLE

LENGTH

SORT

Most sorting algorithms

句

口

basic

swap

问.

records are of

different lengths

, the

swap

step becomes

nontrivia

Problem

2.8: Sort lines of a text file

that

has

a million lines such

that

the average

length

of a line is 100 characters

but

the

longest line is one

million characters long.

2.9

UNIQUE

ELEMENTS

suppose

you

are giveI1a set of

mmes

your

job is

produce

a set of

UI1iqm first

names.If

you

just remove

the

last Ilame from all

the

you

may

have

some duplicate first names.

Problem

2.9:

How

would

you

create a set of first

names

that

has

each

name

occurring

∞

lyonce?

Specifically, design

efficient algorithm for

removing all the duplicates from

array.

岛

fax-heap

other data-structure

that

is useful

diverse

口

texts

is the max-heap,

sometimes also referred to as the priority queue. (There is

relationship

between

the

heap

data-structure

and

the

portio

口

memory

a process

bythe

samemme.)Aheapis

akiMofabimrytree-itsupports

O(logn)

iI1serts

COI1stmt

time lookup for the

max

element.(The

mbheap

a completely symmetric version of the data-structure

and

supports

con-

stant time lookups for the

min

elemen

t.)

Searching for arbitrary keys

has

O(η)

time

complexity-a

町

thi

吨

that

can

done

with

heap

can

done

with

a balanced

BST

with

the same complexity

but

with

possibly

some space

and

time overhead.

2.10

MERGING

SORTED

ARRAYS

You are given 500 files, each containing stock quote information for

SP500 company. Each line contains

update

of the following form:

1232111 131

B 1000 270

2212313 246 S 100

111.01

The first

number

is the

update

time expressed as the

number

of millisec-

onds since the start of the

day's

trading. Each file individually is sorted

this value. Your

task

is to create a single file containing all the

up-

dates sorted

the

update

time. The

individual

files are of the

order

1-100 megabytes; the combined file will

the

order of 5 gigabytes.

Problem

2.10: Design

algorithm

that

takes the files as described

above

and

writes a single file containing the lines

appearing

the in-

dividual files sorted

the

update

time. The algorithm

should

use

very

little

memory

, ideally of

the

order

of a few kilobytes.

2.11

ApPROXIMATE

SORT

日

sider

a situation

where

your

data

is almost

sorted

一

-for

缸口

pIe

，

you

are receiving time-stamped stock quotes

and

earlier quotes

may

arrive af-

terlater quotes because of differences

serverloads

and

network

routes.

would

the

most

efficient

way

of restoring

the

total order?

Problem

2.11: There is a

very

long

stream of integers arriving as

in-

put

such

that

each integer is

most

one

thousand

positions

away

from

its correctly sorted position. Design

algorithm

that

outputs

the in-

tegers

the correct

order

and

uses only a constant

amount

of storage,

, the

memory

used

should

independent

of the

number

of integers

processed.

2.12

RUNNING

AVERAGES

Suppose

you

are given a real-valued time series (e.g.,

temperature

mea-

sured

a sensor)

with

some

noise

added

to i

order

extract

meaningful trends from

noisy

time

series

data

, it is necessary to

perform

smoothing.

the noise

has

a Gaussian distribution

and

the noise

added

to successive samples is

independent

and

identically distributed,

then

If you find the book helpful, please purchase a copy to support the authors!

2.13

CIRCUIT

SIMULATION

the

running

average does a good job of

smoothi

吨.

However

if the noise

口

have

arbitrary distribution,

then

the

running

median

does a better

job.

Problem

2.12: Given a sequence of trillion real

numbers

a disk,

how

would

you

compute

the

running

mean

every

thousand

entries, i.e.,

the first

point

would

the

mean

α[0

]，…

，

a[999]

，

the

second

point

would

the

mean

ofα[1

]，

...,a[1000], the

third

point

would

阳

nean

α[2

]，…

7α[1001]

，

etc.? Repeat the calculation for

median

rather

than

口

lean.

CHAPTER

SORTING

Chapter

Meta-algorithtns

While

performing

timing analysis of a digital circuit, a component is

characterized

a Boolean

functio

日

the Boolean values at its

inputs

and

the

delay

叩

agating

changes from

the

inputs

to the

outpu

For

example

, a gate

may

compute

the

AND

function

and

have

a delay of 1

nanosecond

from each

input

to the

output

wire

may

simply

prop-

agate signal from one

end

to another

0.5

口

anoseconds.

order to

simulate

how

the entire circuit

would

behave

when

a set of

inputs

are

given to the circuit

use "event

如

simulation". Here each event

represents a change

the signal value

and

triggers one

more events

the future.

Problem

2.13: You are given a set of

nodes

, V

. . . ,V

such

that

the value

for each

node

at time

event

,v,

is a triplet

that

represents

change

the

value

for

node

v at time t to

pote

且

tial

can

either 0 or

1). You are given a set of

input

events. Each

node

叫

also

has

a function

associated

with

that

maps

input

event

to a set of

output

events

(output

events can

happen

only after

input

event).

How

would

you

efficiently

compute

all the events that will

happen

as a result of the

input

events?

The

important

fact

to observe

that we have attempted to

solve

maximization problem involving

a particular value

x and a

particular value

N by first

solving the general problem

involving an arbitrary value

and an arbitrary value

"Dynamic Programming

Bellman,

1957

Dynamic

Programming

There are a

number

of approaches to designing algorithms: exhaustive

, divide-and-conquer,

greed

)T,

randomized

, parallelization, back-

tracking

, heuristic, reduction, approximation, etc.

Problems

which

are

naturally

solved using dynamic

programming

(DP) are a

popular

choice for

hard

interview questions. DP is a general

technique for solving complexoptimization problems

that

can

decom-

posed

into overlapping subproblems. Like divide-and-conquer,

solve

the problem

combiningthe solutions of multiple smaller problems

but

what

makes DP efficient is

that

are able to reuse

the

intermediate re-

sults

and

often dramatically

reduce

the time complexity

doing

sol.

illustrate the

idea

, consider the simple

problem

computing

Fi-

bonacci

numbers

defined

十

一

，

口

，

and

lThe

word

"programming"

坦

dynamic

programming

does

not

refer

computer

programming-the

word

was

chosen

Richard

Bellman

describe

program

the

sense

schedule.

If you find the book helpful, please purchase a copy to support the authors!

阳

is easy to define a recurrence relationship

forμ

(i,j). This is essentially

the

largest sequeI1ce

sum

till

j-l

added

A[kl(or

zero if

that

sum

happens

negative).

Henceμ

A(i

，

max(O

，

A(i

，

+ A[j]).

Using this relationship,

can tabulate

A(l

，

for j

ε[1

，叫

linear-

time. Once

have

all these

value

吮

鸟，

the

丑

lswe

凹

rtωo

our

倪

培

ginal

严

伪

blem

妇

simply

工丑

缸，

托

[口

，卢冉

饥川

pass.

Here

are

two

variants of the subarraymaximization problem

that

缸

solved

with

minor

variations of

the

above approach: find

indicesα

and

such

that

二

?=AHl

一

(1.)

closest to °

and

(2.)

closest to t.

common

mistake

that

people

make

while solving DP problems is

trying

thhk

the

recursive case

splitting

the

problem

irlto

two

equalhalvesFOla

Q11icksortr

i.e-F

somehow

solve

the

subproblems for

arrays

A[l

，

η/2]

and

A[n/2

十

，叫

and

combine

the

results.

However

most

cas~s

，

the~e

two

subproblems are

not

sufficient to solve the original

problem.

Figure

"Be fearful

when

others are greedy"

-W.

Buffett

t'>'f

瓦时

己

P~6(

马民

叫叫It崎

t.\.龟

aVEυ$

l'钝巨

orτ1

附

叫

r~τri

C，

飞

.OSS~

飞~

tVE

3.2 FROG CROSSING

3.1 LONGEST NONDECREASING SUBSEQUENCE

In genomics, given

two

gene sequences,

try

to find if

parts

of one

gene are the same as

the

other.

Thus

it is

important

位

the longest

common

subsequence of

the

two

sequences.

One

way

to solve this prob-

lem

is to construct a

new

sequence

where

for eachliteral

one sequence,

insert its position into

the

other

seque

丑

and

then

find the longest

nondecreasing subsequence of this

new

subsequence. For example, if

the

two

叫

uences

are

,3,5,2,

and

,2,3,5,

would

construct

anew

seque

丑

where

for each

positio

丑

the first sequence,

would

list its position

the second

seque

丑

like so,

,3,4,2,5).

Then

find

the

口

gest

nondecreasi

吨

sequence

which

,3,4,5).

Now

, if

use

the

numbers

of the

new

sequence as indices into the second sequence,

get

,3,5,

which

our

丑

gest

common

由

sequence.

Problem

3.1: Given

array

of integers A of

length

n, find

the

longest

sequence

,… ik)

such

that

十

and

A[i

]

三

A[i

叫

for

any

一

1].

3.1.

LONGEST

NONDECREASING

SUBSEQUENCE

CHAPTER

MEL

ALGORITHMS

function to

compute

that

recursively invokes itself to compute

~η-1

and

-2

would

have

a time complexity

that

is exponential

How-

ever if

make

the observation

that

recursion leads to

computing

贝

for

i E

，

η-

repeatedly,

can save

the

computatio

丑

time

时

创

恒

丑

these results

口

reus

店

sing

them. This makes

the

time complexity linear

凡

albeit

the

expense of

叫

storage.

Note

that

the recursive imple-

mentation

requires

O(η)

storage too,

though

the

stack rather

than

the

heap

and

that

the

function is

not

tail

recur

咀

since

the

last operation

performed

is +

and

not

a recursive call.

The key to solving

any

DP problem efficiently is finding the right

way

break

the

problem

into subproblems

such

that

一

the

bigger

problem

can

solved relatively easily once solution to

all the subproblems are available

and

you

need

to solve as few subproblems as possible.

some cases, this

可

require

solvi

吨

slightly different

optimiz

时

口

problem

tharIthe

original

proMem.For

exampley

COI1sider

the

follow-

ing

problem:

give

口

array of integers A of

length

凡

find

the interval

indices

and

such

that

~=α

A[i]

is maximized.

Letrs

try

solve this problem assumiRg

have

the

s0111tiORfor

the

subarray

A[l

，

饥-

1].

this case, even if

knew

the

largest

sum

subar-

ray

for

array

A[l

，

η-I]

，

does

not

help

solve

the

problem

for

A[l

，

η].

Now

, consider a

variant

of this problem. Let

If you find the book helpful, please purchase a copy to support the authors!

3.3

CUTTING

PAPER

now

consider

optimum

planning

problem

two

dimensions. You

are

given

L x

rectangular piece of

kite-paper

where

and

Ware

positive integers

and

a list of n

kinds

of kites

that

can

made

using

the

paper.

The

i-th

kite

鸣

，

ε[1

爪]

requires

叫

rectangle

of kite-paper; this kite sells for Pi'

Assume

li'

ωi

，

are positive integers.

You

have

machine

that

can

cut

rectangular

pieces of

kite-paper

either

horizontally

vertically.

Problem

3.3:

Design

algorithm

that

computes

pro

自

maximizing

strategy

for

cutting

the

kite-paper. You

can

make

many

instances of a

given kite as

you

wan

There is

cost

cutting

让

e-paper.

is often

used

compute

pIa

口

for

performing

task

that

consists

of a series of actions

optimum

way.

Here

example

with

interesting twist.

Problem

3.2: There is a

river

that

isηmeters

wide.

every

meter

from

the

edge

there

mayor

may

not

a stone. A frog

needs

cross the river.

However

the

frog

has

the limitation

that

让

has

just

jumped

meters

then

its

肌

jump

must

between

x-I

and

十

meters

, inclusive.

Assume

the

first

jump

can

∞

1 meter.

Given

the

position

of the

stones,

how

would

you

determine

whether

the

frog

can

make

it to the

other

end

not?

Analyze

the

runtime

your

algorithm.

Table

Number

Electoral College votes per state and Washington,

abama

diana

Nebraska

South

Carolina

Alaska

耳气

Nevada

South

Dakota

izona

Kansas

NNNeeew

JMHeraesmxeiy

pco

shire

Tennessee

kansas

口饥

Icky

Texas

California

Louisiana

Utah

Colorado

社

NewYork

Vermont

Con

工

lecticut

Maryland

North

Carolina

wmV

飞

fVilAaexsgsschtuoVuinx

ksgapto1

Delaware

Massachusetts

North

Dakota

Florida

Michigan

Ohio

Georgia

泣

mesota

Okl

址

lorna

Hawaii

Mississippi

Oregon

WTwoaytsaOhl

江

山

Il1eg1cg

ttOoIrU

Idaho

Missouri

pmemodse

yIlvdmanid

Ill

inois

Montana

538

.5.

TIES

A PRESIDENTIAL

ELECTION

3.5

TIES

PRESIDENTIAL

ELECTION

The US PresideIIt is elected

the

members

the

Electoral

College.21e

umber

of electors

per

state

andWashiI1gtOIL

DCF

are

givezlh

Table

A11electors from

each

state

well

as washingtOIU

cast

their

vote

for

the

same

candidate.

probkm3.5:Suppose

there

are

two

cmdidates

hthe

presidential

deem

EOWW0111dyo

叩吨

rammatically

伽

'mine

if a tie is a possibil-

........

CHAPTER

MEL

ALGORITHMS

飞叮

ORD

BREAKING

Suppose

you

are

designing

a search engine.

addition

getting

key-

words

from

page's

content

you

would

get

keywords

from URLs.

For

example

bedbathandbeyond.

com

should

associated

with

"bed

bath

and

beyond"

(in this

version

the

problem

also allow

"bed

bat

hand

beyond"

associated

with

it).

Problem

3.4:

Given

a dictionary

that

can

tell

you

whether

string

valid

word

not

constant time

and

given

血

s of

length

凡

provide

efficient

algorithm

that

口

tell

whether

can

reconstituted

as a

seque

口

valid

words.

the

event

that

the

string

valid

your

algorithm

should

output

the

corresponding

sequence of

words.

The

three

problems

have

very

similar structure.

Given

a set of

objects of different sizes,

you

need

partition

them

various

ways. The

solutions also

have

the

same

common

theme

that

you

need

explore all

possible

partitions

way

that

you

can

take

advantage

overlapping

subproblems.

3.6

RED

OR BLUE

HOUSE

MAJORITY

suppose

you

want

p1ace a

bet

the

outcome

the

coming

elections.

specifiedly}you are

betthg

the

House

of Representatives

will

have

a Democratic

Republicmmajority.A

polli

吨

compa

町

has

com-

puted

the probabiHty

winRing

for

each

cmdidate

the

individual

dectiom.You

a?e

interested

iRjust

onemmber-whatis

the

probability

that

the

Repubhcm

Paz-ty is

going

have

a majority h

the

House?

Problem

3.6:

Given

that

party

needs

223

seats

win

a maior-

武

牛

FOuseyhowwouldyou

compute

the

probability

ofaItepubIL

-f

ASS?m?eachrace

indepmdent

thattheprobability

Republican

winning

the

race i is Pi'

3.7

LOAD

BALANCING

suppose

you

want

build

a 1arge

distributed

storage

system

mthe

web.

MiniOI1s

users

wiH store terabytes

data

your

servers.One

way

desig1tke

system

would

hastleach

11ser-Fs

logh

idr partitiOI1the

hash

rmges

into

equal-sized bucketsr

and

store

the

data

for

each

bucket

If you find the book helpful, please purchase a copy to support the authors!

剩余110页未读，继续阅读

flyelite

粉丝: 0
资源: 9

UT Austin算法专家教授与Google工程师的面试心得

Algorithms for interviews

Data-structures-algorithms-for-interviews

leetcode每日一题在哪-10-algorithms-for-interviews:在Python编码面试之前要解决的10种算法。在这个存

Python-for-Algorithms--Data-Structures--and-Interviews, 关于算法和数据结构的Udemy课程文件.zip

Coding Interviews

Algorithms Illuminated Part 2 1st Edition

Think Data Structures: Algorithms and Information Retrieval in Java

Problem Solving in Data Structures & Algorithms Using Java 2nd Edition

Problem Solving in Data Structures & Algorithms Using Java, 2nd

Data.Structures.and.Algorithms.Made.Easy.epub

最新资源