Hacking a Google Interview Handout 3 （黑客攻击谷歌面试材料3）.pdfVIP

Hacking
a
Google
Interview
–
Handout
3
 
 
 
 
 Course
Description
 
 Instructors:
Bill
Jacobs
and
Curtis
Fonger
 Time:
January
12
–
15,
5:00
–
6:30
PM
in
32‐124
 Website:
/iap/interview

 
 Question:
Deck
Shuffling
 
 Given
an
array
of
distinct
integers,
give
an
algorithm
to
randomly
reorder
the
 integers
so
that
each
possible
reordering
is
equally
likely.

In
other
words,
given
a
 deck
of
cards,
how
can
you
shuffle
them
such
that
any
permutation
of
cards
is
 equally
likely?
 
 Good
answer:
Go
through
the
elements
in
order,
swapping
each
element
with
a
 random
element
in
the
array
that
does
not
appear
earlier
than
the
element.

This
 takes
O(n)
time.
 
 Note
that
there
are
several
possible
solutions
to
this
problem,
as
well
as
several
 good‐looking
answers
that
are
incorrect.

For
example,
a
slight
modification
to
the
 above
algorithm
whereby
one
switches
each
element
with
any
element
in
the
array
 does
not
give
each
reordering
with
equally
probability.

The
answer
given
here
is,
in
 our
opinion,
the
best
solution.

If
you
want
to
see
other
solutions,
check
the
 Shuffling
page
on
Wikipedia.
 
 Binary
Search
Trees
 
 A
binary
search
tree
is
a
data
structure
that
keeps
items
in
sorted
order.

It
consists
 of
a
binary
tree.

Each
node
has
a
pointer
to
two
children
(one
or
both
of
which
may
 be
null),
an
optional
pointer
to
its
parent
(which
may
be
null),
and
one
element
that
 is
being
stored
in
the
tree
(perhaps
a
string
or
an
integer).

For
a
binary
search
tree
 to
be
valid,
each
nodes
element
must
be
greater
than
every
element
in
its
left
 subtree
and
less
than
every
element
in
its
right
subtree.

For
example,
a
binary
tree
 might
look
like
this:
 17