think

Problem Solving Techniques - For Programming Problems & Interviews



Sharing buttons:

hello everybody and welcome back so in

this video I'm gonna be sharing with you

my tips tricks and advice to getting

better at solving problems now my

opinion problem-solving is one of the

most important skills that you can have

especially as a programmer the ability

to look at a complex topic question

problem whatever it may be and break

that down into smaller components that

you then solved is something that's

really important and in fact a lot of

people know this look at the big tech

companies like Amazon Facebook Google

the number one thing that they evaluate

you on when they bring you in for a

technical coding interview is your

ability to problem solve I can speak

firsthand that during my coding

interviews there was some situations

where I didn't even have to write much

code because by the time I had got done

solving the problem on the board talking

about my solution and kind of walking

through how I was about to code it the

interview was already satisfied that you

know I had come up with the solution

they had seen me code previously and

they're like hey you know what don't

worry about it you can skip this section

you don't even need to code that out so

as much as it is very important to know

your tools and know the language that's

what they really are a programming

language in my mind is a tool and you

need to be good at problem-solving to be

able to use that tool effectively to

solve problems right and that's what in

my opinion makes a good programmer

someone who knows their language knows

their tools well and can apply them into

a problem that they've never seen before

so in this video what I'm gonna do is

pop a question on the screen and I'm

going to show you my thought process and

strategy to break this down this is

hopefully going to show you how you can

approach problems you've never seen

before and immediately make them a lot

easier for yourself alright so with that

being said let's go ahead and get into

the question and talk about how you can

get better at solving problems

[Music]

all right so we'll get to the question

in just a second but I want to show you

the platform that I'm taking this

question from and what my personal

recommendation is for people that are

looking to get better at coding

interviews are problem-solving in

general so the platform on right now is

called algo expert there's a link to it

in the description as well as a discount

code if you want to purchase this this

is a premium paid platform but there's a

reason for that this is really high

quality and it is a great platform this

is really what I used to prepare for my

coding interviews and it made a world of

a difference so essentially this is algo

expert as a hundred coding questions on

it they're all ranked by difficulty and

category so you can see whatever ones

you want here but the thing that really

makes this stand out is not the

questions you can pretty much find these

anywhere it's the interface that you get

to use so it's just way easier to

actually write and test code because you

have the question on the side here you

have a bunch of hints if you get stuck

you have their solutions if you need to

look at them these are way better than

leet code sleeve solutions in my opinion

you have a full video explanation you

can look at a bunch of different test

cases and tests and all this stuff to

see what's happening and it just it's a

really encompassing interface that makes

it way easier to actually get down and

start practicing questions so anyways if

you want to purchase this platform I do

have the discount code

I believe it's tech with Tim that should

give you 15% off link is in the

description anyways the question we're

doing is River sizes so I'll read the

question out and actually we'll zoom in

quite a bit here and then I'm gonna go

to my what is it whiteboard on my

computer and actually start solving this

for you so it says you're given a

two-dimensional array a matrix of

potentially unequal height and width

containing only zeros and once each zero

represents land at and each one

represents a part of a river a river

consists of any number of ones that are

either horizontally or vertically

adjacent but not diagonally the number

of adjacent ones forming a river

determines its size write a function

that returns an array of the sizes of

all rivers represented in the input

matrix the sizes do not need to be in

any particular order so this is the

example and essentially what it's asking

us to do is find all of the connecting

ones or the number of rivers inside of

this matrix so that is somewhat of a

difficult problem and I'm going to show

you how we break this down on the

whiteboard before we even start

coding and go about actually solving

this problem so let's head over to the

whiteboard and we'll get into the

solution

so the first step whenever you're

looking at a problem like this is to

make sure you actually understand what

the problem is asking so you want to

understand what the input is what the

output is and we are actually being

asked to do you don't want to go wrong

right at the beginning because you make

an assumption or you do something that's

not actually a part of the problem a lot

of times people will read through a

problem quickly and it'll sound like a

problem that they've done before so

they'll just start coding it based off

memory but then they realize halfway

through that hey that's actually not

what they're being asked and now they've

made a huge mistake and they've wasted

so much time so you really want to make

sure that you have a thorough

understanding of what's being asked

before you move forward so what I like

to do is just state a few observations

and kind of redefine the problem in my

own words

before I move forward so what I believe

is being asked is to find the length of

all of the rivers that are present in an

array or in this matrix so that's the

problem we want to find the lengths of

all of the rivers that are present so

that would mean to me if there was four

rivers than I would have four lengths

that I would be returning in some kind

of array so the input is a matrix I'm

returning the length of the rivers okay

great

so we've defined the problem I think we

have an understanding of what it is we

need to do this is a simpler problem but

you know you get the idea that's a

really important first step okay so we

want to return the length of all of the

rivers so how do we determine the length

of a river and in fact what is a river

let's make sure we understand that

before we move any for any further we

want to really make sure that every

single thing there we can define in our

own terms and that it makes complete

sense so let's have a look at this

question again and let's look at what

says a river is because we need to know

what a river is to be able to do this a

river consists of any number of ones

that are either horizontally or

vertically adjacent okay good so that

means that this would be a river so I

can't highlight it but this one here

this one here so there's all these

rivers in here that seems just to be

vertical here but I guess they could be

horizontal as well so that's something

we're going to want to make sure we

understand what is a river is the one up

here I don't know if you can see my

mouse connected dying

- those ones want to make sure we get

that so let me now go ahead and draw a

few examples and see if these will be

rivers see if I could determine myself

if this would be a river so I'm gonna do

a little example I'll actually do it on

this side of the screen here I won't do

too many numbers but let's just do zero

zero zero I'll just do like a three by

here one one one one zero one zero zero

zero okay so this is my example and this

kind of moves us into step two so I

understand the question I'm kind of

trying to figure out what a river is now

so my initial instinct is to start

drawing because in my opinion you know I

need to explain to my interviewer or to

myself or to anyone for that matter what

it is I'm doing and I can do that better

when I'm drawing something out on the

board I can make some illustrations you

know even if they're rough which all of

my stuff is still helps quite a bit so

the question I want to ask myself now is

well what is a river here is this two

rivers or is this one river do we

include these two bottom ones in the

river so that's a good question so that

might involve me having to ask the

interviewer to go back and read again

now I know that this whole thing would

be considered a river because it says

that they're horizontally or vertically

adjacent then that's a river and since

all of these are connected together

that's one River I guess it's just too

wide at this point right because we

didn't have any diagonals up here

because if I added the diagonal you know

we wouldn't do that but oh wait that

would even still be a river because I

could connect all of them vertically and

horizontally adjacent so that's what I

start doing I start playing around with

a few examples seeing if there's any

examples that I can think of off the top

of my head that maybe I'm not clear on

right away and make sure I clear that up

so that when I start doing this

algorithm I really understand that and

sometimes you won't see these kind of

edge cases until you start going through

the algorithm but it's important to try

to think about them and say okay what

could mess me up here I understand what

a river is okay good I understand the

problem let's draw it out

let's make ourself an example that we

haven't seen and see if our

understanding holds on that new example

that's a really important thing make

your own examples because the example

they give you can sometimes be a little

bit of a trick and they almost want you

to draw it out yourself great so we have

the example up here we kind of

understand what a river

now and I'm gonna say it's now the time

that I'm gonna start thinking about how

I'm actually to solve this so we know

that rivers are represented by once we

know zeros aren't here so the first

thing that I'm probably gonna have to do

if I'm solving this problem is well this

couldn't be this might not be the first

thing but look through all of the

elements in this matrix right so say 2d

matrix right so these are technically

arrays like this or lists or whatever

you want to call them so my first step

is gonna be to start looking through all

of these different elements so I'm gonna

say one look through oops

elements now excuse my handwriting it's

quite messy with this drawing table but

hopefully this at least gives you an

idea so look through elements so what I

mean by that is go one by one and start

you know searching through all these

elements looking for something specific

so in fact what am I looking for well I

want to find the length of all of the

rivers so I need to find the start of a

river and then see how long that River

goes for right so the first thing I'm

actually gonna be looking for I guess we

could say maybe not a sub point maybe

let's put part to check if element is

one if the element is one that means

that I've hit the start the middle some

point of a river and well I should

probably do something with that right if

I hit the start of River so that's my

thought process you guys might have a

different idea but I'm thinking that I

want to look for ones because that's the

start of a river and something that I

care about okay so I want to check if

the element is a one what do I do if the

elements a one what should I do if it's

a one well I'm thinking if I find one

what I should do is find all of the ones

that would be in that River so find the

river that contains that one because in

that case then I can determine the

length of that River I can add that

River into something I can do something

with it so I'm thinking that when I hit

a one what I should do is start looking

for all of the other ones that are in

that River so I'll say three start

looking for rest of River

okay so rest of

River like that okay so that's point

three so I'm saying that once I hit a

one now what I want to do ideally is

find all these other ones so find the

river that contains this one that's what

I'm looking for

nice all right so that's step three what

do I do after that

well once I find all of these ones what

I probably want to do is store or

determine the length of this river so

I'm going to say determine length of

river great so now I've found a one I

found the river that contains it and I

found the length of that river good

we're moving towards what seems to be a

solution here so what I'm gonna do now

is I'm gonna store the length of that

river I need to put it somewhere I need

to print it out right so I'll say store

five store lengths of river great okay

so after we store the length of the

river what should we do next well we

could just go back up to step one and

repeat the process so let's actually see

if this works and this is what I'll do

in interviews you know I don't know if

I'm at the solution yet I just keep

practicing and I keep going through and

seeing if anything messes up so okay so

currently we have look through all the

elements

so let's look through them blah blah

blah look through all the elements go

through all of them okay let's follow

next step so look through them find a

one I found a one nice check of element

is one yes it's a one start looking for

the rest of the river okay great so

let's look for the rest of the river and

let's find this so determine the length

of the river that could be like the

finishing step like we found all the

ones now we sum them up and we determine

that this is like five store the length

of the river okay so I probably need an

array or something to do that so I'm

gonna store lengths of River like that

five boom great okay we got that in

there now what do I do next well let's

go back up to the top let's look through

all the elements I was at this element

right when I stopped so now we go here

hmm okay so I'm already starting to see

that there might be an issue here I

start looking for the rest of the river

now cuz this elements a one determine

the length of the river store the length

of the river well if I did that then I

would get another five because I would

find this one here this this this I

would find all those ones but I've

already used them okay so this is a

little bit of a breakthrough for me this

is telling me that once I find all of

these elements in the river what I

probably need to do is store

summer or save those or say hey we've

already used this river so what I'm

going to say is store the length of the

river and six store positions maybe I'll

store the positions of the ones that

I've used so store positions of ones

used so the ones that have already been

a part of some of those rivers great so

now at step two I'll check if element is

one and we'll say not used so I know

this is really messy I'm just trying to

fit it in here but I'm just trying to

say and we haven't used that one so now

I've kind of came up with an algorithm

that I think might make sense let's look

through all the elements check if the

element is one and we haven't used it

yet then we'll start looking for the

rest of the river if that's true if

that's true we'll determine the length

of the river will store the length of

the river and we'll store the positions

of the ones that we used and then

finally at the end we can just return

all the lengths of the rivers because we

would have found them all when we reach

that last element so there you go I've

kind of successfully came up with an

algorithm and a series of steps that I

want to follow here so now all I need to

do is think about the tools that I know

in my programming language to accomplish

this so look through all the elements

hey that's gonna be a double for loop

because it's a duck two dimensional

matrix great we know it's not

necessarily square that's something to

keep in mind when we do that okay check

if the element is one and it's not used

well we're gonna see if the elephant's

is equal to one and then we're gonna

check in some set or some hash table

whatever it is you may decide to use if

the current position that we're on was

used in in another River because we'll

store that in a set or a hash table

great part three start looking for the

rest of the rib how am I gonna look for

the rest of the rivers starting on a

position well I'm probably gonna do that

in a breadth-first way or a depth-first

way that's a tool that I know in

programming that's a fairly easy

algorithm to implement a depth-first

search to look for all the other ones

that are potentially in this river

great how am I going to determine the

length of the river well every time I

find a new one let's add one to it

variable and we'll just keep track of

how long the river is that we found

storing the length of the river okay so

once I've guess I found all of the

elements that were in the river I need

to store that length which would have

been in a variable and I need to store

the positions of all the ones that were

used so maybe while I'm looking for all

of these

when I find a one that's attached to

this one so a part of that river I just

throw it into the set and say hey this

has been used I've used that before then

we reach the end of this you know I've

just kind of even told you verbally how

I would go about solving this and we

have an array that's storing all the

lengths of our rivers boom so we'd have

five six whatever it is we can return

that we've successfully complete

completed the problem so I've taken this

problem it might not have seemed that

complex and I've just broken it down

into the steps that I need to take and

now I have kind of a rough idea of what

I want to do and I'll take this and

translate it into code in whatever

languages that I'm gonna use so that is

kind of my idea of doing this the

process I followed again was define the

problem make sure I really understand

make some observation some things that I

might notice about the problem things

that you know I'm gonna have to consider

for my solution and then what do I do I

make sure I know all the definitions so

I know what a river is I think about any

edge cases I've drawn a diagram and

thought of some examples that might

break my current understanding once I

really make sure I understand it I start

breaking it down into really small steps

that I can easily follow and try to come

up with some kind of algorithm maybe my

first version of the algorithms not

correct I reach something that doesn't

make sense to me so I go back and I

modify it a little bit and I change the

steps around now at the end of this

problem I've thought of these steps they

make sense to me and what I'll do is

I'll take these steps and I'll translate

them into code notice that I didn't

really talk about any coding stuff here

there wasn't anything with depth first

search breadth first search I was just

discussing in my mind how I would go

about solving this problem the steps

that would need to be taken if I was

just doing this as a human for one

example then I take that and I can

convert that into an algorithm that I

can apply for any example of course

there's a lot more things you need to do

than just this but I wanted to walk you

through how I mentally break down and

think about a problem and hopefully this

gives you an idea of what you can start

doing when you see a problem that you

don't immediately know how to solve

don't necessarily just think about the

coding aspect think about logically what

you need to do the steps that need to be

accomplished and then solve them one at

a time I think we can all agree that B

SEC six steps are easier to solve than

just reading that problem at the

beginning

like it is right so again this video is

really designed to just help give you an

idea of how you go about solving

problems the thought process that's

involved and if you do really want to

practice this kind of stuff I would

highly recommend algo expert which again

is the platform I took this question

directly from and that I used to prepare

for my coding interviews so I think with

that I'm gonna wrap up the video here I

know this was long but I really did want

to try my best to give you guys all the

knowledge I could in this area so with

that being said I hope you enjoyed like

the video if you did subscribe to the

channel and I will see you in the next

one