[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]

Thanks for the upload

When she said she was gonna throw a wrench into the mix I felt the pain lol.

I find this valuable, thanks a lot!

Great job googlers! Keep em coming please 🙂

This video was very helpful, thank you. Please do more videos like this.

just a minor typo, it is comp.end() … doesn't change the general idea but still :p

Such a nice video. Very well conducted by both.

Lovely!

The value that you are looking for should be the complement (ie sum-value), not the value itself, great video btw

Stupid video

Who writes the music for these videos. Hahahaha jk. It's very relaxing.

I realize I've got a long way to go. This gives me motivation, though.

At time =15m44s,

I want to know about complexity of

line —— if(comp.find(value)! —–

As I implement same in C,

When I compare/Find like function as —

~~comp.find(value) —~~Complexity of this step becomes N i.e. for finding element in compliment array,

so total complexity becomes N^2 in worst case , average it less than N^2.

I know its been a year since the posting of the video, but I have a question regarding your code which I hope you would explain it to me. First, I like the way you solved this problem. This is really clever solution. second, My Question is: why do you need ( != comp.end ) part? Since you are checking before inserting, its always going to check only the previously added complements. Thanks for posting the video anyway.

I m coming google get ready for world best programmer👌😊

Very intense, super interesting. Also, fun problem!

I loved it !

をよの（やしらむむやはみから

I love the way in which he thinks 🙂

Great video. Thanks for the tips, they're certainly helpful.

i think its easy like this

int sum= (1*2)+9-3; //i think its 8 at first 1

Wow great job brilliant solution. but am worried what if the set was of the form [1, 2, 2 ,4]. This algorithm seems to dual mostly on two digits that sum to the required number and not when we have multiple digits.

i want job in google but iknow only 3 programing languages

1] java

2] php

3] html

i am 14 year young from india

what language is this

😩 just when I thought 1 + 1=2

A new for of mathematics comes

I haven't watched video yet, just problem. First idea I am having to solve it is, looping through all the numbers in array, then using binary search to find the needed matching pair to make 8, if any. This will be O(nlogn). Let's how I did. Will continue watching video now.

How much math do we actually have to know for this software programming becz like fuc i hate math and i love computer

in problem 1 : we can simply use map storing values and index .

For the last part of the problem, wouldn't it have made sense to do some pruning along the way for repeat complements? It would have bumped up the running time, but for a case where space seems to be the main issue, that would be a necessary sacrifice for the problem if you were to not use multiple systems, wouldn't it?

Hi

def checkSum(myList, s):

start, end = 0, -1

for x in range(len(myList)):

k = myList[start]+myList[end]

if k == s:return True

else:

if k > s:end -= 1

elif k < s:start += 1

return False

print(checkSum([1, 4, 4, 5], 8))

#did that in 2 minutes in python, before he writes the code…!

try this algo: (a[0]*a[1]) + a[2] +((a[3]/a[2])*(a[2]-a[1]))

can someone please tell me what does comp.end do.

Thanks for the video!!

How can he think the solution too fast, or it is already practiced?

That noob man…

He crossed the first array 2:00 …. and then asked her if he could repeat the elements… and they are making 'example interview'

I thought of a better solution than him that would work in half the time of what he is proposing.

So does this mean I can get an internship??