How to: Work at Google — Example Coding/Engineering Interview

How to: Work at Google — Example Coding/Engineering Interview


[MUSIC PLAYING] EDGAR: Hi, I’m Edgar, and I’m
a software engineer at Google. BECKY: Hi, I’m Becky, and I’m
a software engineer at Google. So Edgar, the question I’m
going to give you today is I’m going to give you
a collection of numbers. And I need you to take
this collection of numbers and find a matching pair
that is equal to a sum that I give you as well. EDGAR: OK. BECKY: So for example,
the collection of numbers could be 1, 2, 3, and 9. And the sum that I’m
looking for is 8. EDGAR: OK. BECKY: And then
another example, just for another set
of numbers, could be a 1, a 2, a 4, and a
4, and then again the sum that I’m looking for is 8. EDGAR: So in this
case, there– I guess what I’m
trying to figure out is you’re looking for a pair
of numbers that add up to 8. BECKY: Yes. EDGAR: Right. So in this case,
there isn’t a pair of numbers that add up to 8. BECKY: That is true
in this example. EDGAR: And in this case,
it is because the 4 and 4 add up to 8. BECKY: Correct. EDGAR: OK. So this would be like
no, and this is yes. OK. BECKY: Yeah, so you
ultimately have to tell me if the pairs [INAUDIBLE]. EDGAR: OK. So how are these numbers given? Can I assume that
they’re like in memory, an array, or something? BECKY: Yeah, they’re in memory. You can go with an array. You can also assume that they’re
ordered in ascending order. EDGAR: OK. Oh interesting, OK. So how about repeating elements? Can I assume that there will
be– like for instance here, what if I didn’t have that 4? Could I use like the 4
and the 4 to get that 8? BECKY: You can’t repeat the
same element at the same index twice, but certainly the
same number may appear twice like you just saw [INAUDIBLE]. EDGAR: OK, so like
that would be a yes. How about these numbers? Are they integers, or are
they floating point or– BECKY: You can assume
they’ll always be integer. EDGAR: OK. Negatives, positives. BECKY: Negatives could happen. EDGAR: OK. Cool. Well, the simplest
solution, of course, is just comparing every
single possible pair. So I could just
have two for loops, one scanning the whole thing
and then the second one starting from, let’s say,
you have the i loop and then the j loop starting
from i plus 1 so that I don’t
repeat the same value. I’m just testing all
of them if the sum is equal to the target sum. I mean, that’s obviously
not very efficient, but that would be
a way to solve it. BECKY: That would work. It certainly would
be time-consuming, I think is where– EDGAR: Yes. BECKY: —-[INAUDIBLE] is
concerned So is there any kind of example that could
be a little bit faster? EDGAR: Yeah, I think
that would be quadratic, so better than quadratic. Well, since it’s
sorted– I guess I need to figure out,
when I have a number, what I’m looking for is if there’s
another number that sums to 8. So if I have a 1, what
I’d need to figure out is if there is a 7
somewhere in the array. And if that’s the
case, if it’s sorted, then I can just do
a binary search. I guess if I go here and
I binary search for a 7, then I go here and
I binary search for a 6, which is the
complement of that. And when I go here, I
binary search for a 5. And the end, I just
don’t do anything. And so in this case, I
would solve it like that. So that’s a bit
better than quadratic. I guess binary search is a log
algorithm in a sorted list. BECKY: Also a good answer. EDGAR: OK. BECKY: But still kind of slow. EDGAR: [SIGHS] OK. BECKY: So what if you took
a look at– instead of going a binary search which
is unidirectional, what if you started with a
pair of numbers to begin with– EDGAR: OK. BECKY: –and then worked your
way– and work from there? EDGAR: Let’s see. So if I– OK. Let me try to bound this thing. So the largest
possible sum, I guess, would be the last two values. BECKY: That would be the
largest possible sum, yes. EDGAR: And the
smallest possible sum would be the two
smallest, right? BECKY: Right. EDGAR: So anything
in between– oh, OK. So the range of the possible
values is that, right? So there’s nothing that can
be smaller than this value. BECKY: Right. EDGAR: There’s nothing that
can be larger than that value. BECKY: You have
somewhere to move from. EDGAR: Well, that’s– OK. So if this sum is 10 in
this case, it’s too large, so I need to find a smaller sum. So I could just move
this one over here. And if that is too
small now, then I need to move that
one over there. OK, so I think I can just do it
with that in a linear solution, just moving– at each duration,
I either move the high one lower if my pair is too large. And I move my lower higher
if my pair is too small. And I end whenever
I either find two. Like, in this case, I either
find a pair that adds up to 8, or whenever they cross. At every point, I’m
moving one of them. So they would have
to at least cross. And I move exactly one so
that means that it’s linear. Yeah, so that would be a
way of solving that problem. BECKY: And how does it make that
faster than a binary search? EDGAR: OK, so in the
binary search case, I was doing log
for finding, but I had to repeat that
for every element. So that was n log n solution. In this case, I just need to do
that moving, scanning the one time. So it’s a linear solution. That’s faster. BECKY: Right, right. OK, so before– and we
can get to coding it, but before we do that,
maybe you could explain. You explained it in a
non-working example. Maybe you could follow through
that same process in a working example. EDGAR: OK, yeah. So here I would start
with this and that. So it’s 5. It’s smaller than 8. So I move this one here. So that’s 6. That’s smaller than 8. So I go here, and then that’s 8. So that’s true. And I return. BECKY: Excellent. EDGAR: Yeah. I think that would work. BECKY: OK, so what
coding language would you prefer to do this in? EDGAR: I prefer
C++, if that’s OK. BECKY: C++ works. EDGAR: OK. BECKY: Go for it. EDGAR: Ah, perfect. Let’s see. So, OK. Now I realize that
I haven’t figured out what I need to return. BECKY: Mm. EDGAR: So do I want the pair,
the indices of the pair, or whether I just
found it or not? BECKY: So for the
purposes of the example, we’ll go with whether
you found it or not. But let’s say you were
going to return the pair. How could that become a problem,
even if there was no pair? EDGAR: So, I mean, building
the pair would be easy, right? So I would just return the pair. If I didn’t find it,
then I would need to return some sort of Boolean. So I guess I could make
a data structure that has a Boolean that denotes
whether the pair is valid or not, like how
has it been found? So like a Bool found, and then
a pair values or something like that. BECKY: Combine those
together, yeah. EDGAR: And then this is
the thing that you return. BECKY: Mhm. EDGAR: I mean, it’s not very
elegant, but it’s workable. BECKY: Mhm. Rather than going
with a custom object, maybe we’ll just
return a Boolean then. EDGAR: OK. That makes it a lot easier, yes. BECKY: It is good
to know that you’ve thought about what
you might have to do if there is no viable result. EDGAR: Mhm. OK. So let’s just call it has
pair with sum, I guess. And so I’m OK just
receiving whatever. I would like to receive
it as a vector, say. BECKY: Vector’s fine. Yeah, sure. EDGAR: And we said
ints are fine? BECKY: Ints are fine. EDGAR: This is my data. And then I have an
int which is my sum. OK. So like I said, I
want an int, my low, which is 0, then my high,
which is the data size minus 1. And then what I’m going to
do is while these are– well, my low is strictly
lower than my high. As soon as they
are touching, then I know that I can’t guarantee
that they’re different. So that’s where I should stop. OK, well, my low is
less than my high. And this also solves
the problem of what happens if this is empty. Because then if this is empty,
this would be a minus 1. And then that would be violated. So I would never enter and
access any of the values. So that’s fine. So while low is
less than high, I guess if my data
at low plus my data at high is the same as my
target– my target, which is called sum– then
I have found it. That’s it. That’s my pair. And here is where I
would construct that pair if I needed to return it. But, like you say, for now,
I can just return true. Now, if this is larger than
sum, and this is lower than sum, so I think I’m better than
just doing it three times. I’m just going to store
it in a variable, which is my s is that. And then say if s is my
sum, then return true. BECKY: OK, I’m going to
stop you right there. EDGAR: OK. BECKY: Excellent solution. I see what you’re
getting at here, but I’m now going to
throw a little wrench into the mix for you. EDGAR: Oh boy. [LAUGHS] BECKY: I can no longer
guarantee for you that the numbers in this
collection are sorted. EDGAR: OK. So– BECKY: You have to
think of a different way to compare them
against each other. EDGAR: I mean, if
the first thing I do is just sort, of
course, then I solve this problem the same way. BECKY: True, true. EDGAR: So that would still
be an n log n solution. BECKY: It would. EDGAR: Which would be like
the same as the binary search as well. BECKY: Yes, but it’s
too slow for Google. EDGAR: OK. So you want faster than that. OK. BECKY: [LAUGHS] EDGAR: OK, let’s see. So if I go back to this idea–
OK, so let me erase this. If I go back to
this idea of when I look at a number, what
I need to figure out is if the complement
is in the rest. BECKY: The complement meaning? EDGAR: Yeah, the 8
minus this value, right? In this case, when
I have the 1, I need to figure out
if 7 is in the rest. BECKY: Yes. OK. EDGAR: If I cannot sort, and
searching that will be linear, so that’s not a very good idea. But maybe I can do it
the other way around. So I build it up,
little by little. And instead of just sort
of asking a blanket, is there anywhere? I just ask, have I
seen it in the past? So for instance, if I’m
here, what I need to find out is if I have seen 8 minus 3. Have I seen 5 in the past? BECKY: That would work. So you’d have to store 5. EDGAR: Or– I guess
it’s the same, but I could be storing
the complements. And I just ask, have I seen
3 as a complement of anything of the things before? BECKY: Yep. EDGAR: So like I insert
a 7 when I see a 1. BECKY: Sure. EDGAR: I insert
a 6 if I see a 2. BECKY: You insert
the complement. EDGAR: Yes. I insert the complement. And then when I get here, I
ask, is this the complement of anything I have
seen in my past? BECKY: Right. EDGAR: So I can use
a data structure that is very good for lookups. BECKY: OK. EDGAR: Right? So I can do something
like a hash table, which has a constant time lookup. BECKY: Hash table
though, [INAUDIBLE]. Do you need a key in this case? EDGAR: I guess I
don’t need– I just need the values, the elements. I don’t actually want
to store any payload. So yeah, I guess a HashSet
would be the thing to do. So I HashSet all
of the complements, and then I look for them. I need to be careful, though. How am I going to deal with
the case of repeated elements? So I don’t want to be able
to say, oh, I have a 4. Yes, of course I have a 4. I’m done. If I have this, I have a 4. I have it, so I’m done. That would be a wrong solution. I guess I need to
be careful there. OK, OK, OK. So here’s an idea. I only look for things–
so when I’m here, I only look for things
that I have seen before. So long as I check
before I insert things, that should work. And then when I add
it here, this one will find that because
it’s in the previous one. So I think that works, yeah. BECKY: Sounds good. Let’s code it. EDGAR: OK. Very well. So let’s see. BECKY: It was a good catch. EDGAR: So, like I was
saying, Bool of [? pass ?] pair with sum with my– oh,
OK, like my [INAUDIBLE]. BECKY: You can shorten it. EDGAR: Vector of int
data and then my int sum. BECKY: OK. EDGAR: So I need a HashSet. So in C++, that’s an unordered
set of integers still. And I’m going to
call it complements. Well, I don’t want
to write complements all the time, so I’m just
going to call it comp– BECKY: Sounds good. EDGAR: –and say these
are the complements. I’ve seen whatever I need
to get the target sum. BECKY: Yes. EDGAR: And so I said, I
just need to be building it up little by little. So I do a for my int value for
each of the values in the data. I am going to first
check and then insert. So if my complements– so
I check if I have seen it. BECKY: First, yeah. EDGAR: And if I have
seen it– so that means if it’s not in the
end– then that’s it. That should be our return true. Because this current element and
something that I have seen in the past add up to the sun. BECKY: Mhm. EDGAR: So, obviously it depends
on what I’ve been inserting. So that’s what I’m
going to do here. My complement is
going to be inserting. I don’t remember. I think it’s add
for an ordered set. BECKY: Probably. EDGAR: But there’s something. It’s either r or
insert or something. Yeah. So I add not the value but
the complements, like I said. So I do the sum minus value. I feel like I probably need to
go through an example to make sure that this is correct. But I think that’s it. Let me go through some
examples to make sure. BECKY: Absolutely. I’m going to erase these. EDGAR: Yes. OK. So I have a set. My complements is a
set, which starts empty. I’m going to run through both. They’re kind of the
same at the beginning, so that should be fine. So I have nothing in. I check for my first
value, which is a 1. I don’t find
anything, obviously. And then I add 8 minus
1, so I add a 7 here. OK, so now I have a 7. Then I go for the next one, 2. I look for whether
there’s a 2 there. No, there isn’t. But if I had had a 6 here,
adding the complement would have found a 2. So that would be good. So that makes sense. OK, the 7, it’s not there. So I just add now the 6. And here’s where they
start to diverge. The next case is– I get to 3. Have I seen a 3? No, well have I seen
the complement of a 3? No. So I just shove in the 3. 3’s complement– good point. And then the last
one, no, I have not. There’s no 9 here. So it would correctly
return false. BECKY: Right. EDGAR: Now, what
about the other one? The other case I get a 4. I have not seen the complement
of 4, so I put the 4 in. BECKY: OK. EDGAR: Because it’s
8 minus 4 is 4. And then when I get to
this one, I have found it. So I correctly return true. BECKY: Value is
equal to complement. EDGAR: Yeah. Yeah. So the value would be 4. I look here is my
complements, and I do find it. So I return true. OK, so that works. What happens with an empty? The empty one should
never return true because you don’t have a pair. So that’s fine. You’d have only one thing. You never would compare
again, so that’s fine. So it seems like that works. There is one issue. This could underflow. BECKY: Don’t worry about. EDGAR: OK, let’s not
worry about that. So I think this is
the right solution. So it’s linear because I am
doing constant amount of work to look at this constant,
adding its constant for an ordered set. And I do it for all of
the values in the input. So that’s linear. And the memory, it’s,
I guess, linear as well because the worst case scenario
I have added all of them to the set. BECKY: Would you do
anything differently here if there were 10 million
integers in this collection? EDGAR: [SIGH] OK. So, let’s see. So if the input is large, does
it still fit in memory or– BECKY: Probably
not at this point. EDGAR: OK, so if it doesn’t fit
in memory, what I can do– OK, so is the range of these
values limited in some way? BECKY: You can assume
they might be, yeah. EDGAR: OK, OK, OK. If my set fits in memory, but
my input doesn’t fit in memory, then I can just sort of
process it in chunks, right? I chunk it, and I
just put it in a set, and I accumulate it in a set. If we can’t do it in
parallel, then it’s kind of the same thing. So now you have
multiple computers, each one processing each bit
of it, of the input, Each. One producing a
set of complements that this bit has seen. And we just sort of merge them. BECKY: I think we
have enough computers to be able to handle it. EDGAR: Yeah, so the merging
would be a bit tricky because we want to make
sure that, again, we don’t sort of look for the
thing that we have put in. So I guess as long as each
individual computer is testing this in the right order, when
we merge them, now we can say, oh, well, those
two are correctly– so if I have a 4 in one computer
and a 4 in the other computer, when I merge them, I
would need to be careful that I reconcile them. BECKY: Yeah EDGAR: But other
than that, I think that would be the
only consideration. BECKY: Good, OK. EDGAR: Yeah. BECKY: Excellent. Great. Great job. All right, just to
recap that interview, I just want to go over
a couple of things that you should be aware of when
you’re interviewing and some of the things that
Edgar did very well. So the first thing
that he did was he asked for a clarification
of the problem. So if you don’t fully
understand the question, please feel free to ask for a
clarification or ask to have it repeated. You can write it down. You can write it down
verbatim if need be– whatever you need to do to get a complete
understanding of the question that’s being asked. And I think some of his
clarification questions were, could they be negative numbers
or floating point numbers? And the answer to
that, really, does affect the outcome of his code. So it was really great that
he asked that question. Another thing that
he did is while he was going through
his solution, even before he started
writing code down, he thought out loud constantly. Constantly thinking out loud
is probably the best thing you can do in the
interview because it gives the interviewee the opportunity
to see your thought process and use that to possibly
course correct you more towards the question
that they were asking or to feed off of
that and ask you more questions that might help
you demonstrate your knowledge even further because you
may have said something that they can expand upon. But in the very
least, it’s going to help you work
that problem out. And there’s nothing wrong
with working that problem out with somebody else. Two minds are better than one. So please, please
think out loud. Another thing that
he did really great is he thought through
everything before he started writing something down. So we thought about how
we were going to do it. We actually went
through two iterations. The first thing, the thing
at the top of his mind, wasn’t the best solution. And it’s not going to be the
best solution for anybody. So think through
what you want to do. And then you might get
challenged by the interviewer to think better, faster,
quicker, more efficiently. Think through that solution. And then ultimately,
when you both feel like you’re at a spot
where you can code it, then you can start coding it down
on the screen or on paper. So that’s another
great thing to do. Another thing that he did really
well that I would encourage everyone to do is to test it. Test it in real time. So I gave him two
example sets here. He had something that
he could test with. If your interviewer doesn’t
give you an example, please make one up. Test your solution. Does it work? Does it vet? And then think about edge cases. Edge cases can be important. So in his case, he thought about
if he had an empty collection. And he tested his logic
with an empty collection. It was really nice to see him
thinking about those edge cases and bringing them
up in the interview. So yeah, clarifications. Think out loud. Talk before you write, and
then test your solution. [MUSIC PLAYING]

37 thoughts on “How to: Work at Google — Example Coding/Engineering Interview

Leave a Reply

Leave a Reply

Your email address will not be published. Required fields are marked *