hey tech lead here and welcome back to
another episode we are drinking standard
jasmine tea today this episode we're
going to be continuing with our lead
coding practice this time we're going to
do it in Python just to switch things up
a bit what I'm trying to do for you guys
is cover as much ground as I can that
way next time you see a similar type of
problem it doesn't take you by surprise
because there's only so many different
algorithms out there you just need to
know a few good standard ones understand
how to approach a number of problems and
that should get you well on your way so
without further ado let's get into it
the first of these questions is you're
given a string of unbalanced parentheses
and you need to find the total number of
parentheses that need to be added to
balance this string and this is a very
typical problem I was actually just
asked this in one of my recent interview
loops so you definitely want to know how
to solve it now there is a brute-force
technique for solving this where you go
through the string character by
character and for each character you
scan the whole entire string and see if
you can find a match and you know that's
gonna be like Big O of N squared time
and you're not gonna want to do that the
solution is going to be to use a stack
and as you go through the string you
push characters on to the stack and then
you pop them off when you find a right
parenthesis if you happen to get a right
parenthesis but the top item on the
stack is not a left parenthesis then you
know that you have an unbalanced pair
and you can just add one to your total
count when you finish iterating through
other characters then you just count the
total number of items in the stack
that's the number of left parenthesis
that were never matched that's going to
be your answer the runtime is going to
be a single pass through the characters
of the strings so that is then your time
and the space complexity well that's
going to be linear as well because you
could be in the M pushing everything
onto the stack every single character if
every single character has a left
parenthesis so that's going to be linear
as well I remember when that was fresh
out of college I would always get
stumped on questions like these because
my college courses never taught me about
queues and stacks all right moving on so
we're going
keep clicking on the next one until we
find another interesting problem and
we're looking again for easy or medium
problems now I've actually ordered
profound a problem for you guys and
solve that as well and you know the
purpose of this video isn't necessarily
for me to show you what I'm doing as I'm
solving these problems I just want to
cover the solution for you because I
think that's going to be the best use of
your time so this question is given the
string of words reverse the words in the
string if the input is the sky is blue
then the output should be blue is sky V
I think reversing words in the string is
a pretty good problem actually because
there's many different ways to solve it
and what's going to be interesting is
the analysis essentially you can go
through in one pass and you have two
variables the start of a word and then
the end of a word and as you're going
through you look for a space when you
find the space you know that that's the
end of a word so you go through you
collect other words together you have an
array of other words in the string then
you iterate through that array of words
in reverse order add those words
together and you return that result
that's going to be the words reversed
and the runtime for this should be
linear time with regards to the length
of the input and then the space
requirement here is going to be as well
linear you know if your method needs to
return a string of words by definition
that method is going to require at least
linear space just to return that output
anyway we can take a look at the
solution that put together here which
does what that describe the first
portion iterates through the characters
in the array and collects a bunch of
words and then there's that edge case
where it needs to get that last word
because the last word does not end in a
space necessarily then we reverse the
words this reversal process will
probably take linear time as well and
this is somewhat inefficient I could
just iterate through doors in a reverse
order but you know we're already taking
linear time anyways so reversing this is
just gonna be another linear passage
it's not going to actually change that
linear time and
is that the Big O of n it will be big-oh
of two in either way it's still vineyard
then we joined the words that's going to
add another pass so this probably runs
in like three n time or something like
that we can run some mints see how fast
this is gonna take faster than
20-percent Python online submissions
which is fine really I could try to make
it a little bit faster so what I did
here was I removed the code to reverse
the this upwards and iterate through the
words in backwards order that removed at
least one pass and it's a little bit
faster it's my solutions faster than 34%
of Python solutions now you know I saw
some of the solutions out there the
faster ones they're solving this in like
one line of code or five lines of code
and yeah you can do that if you know
other built-in functions for Python I
would recommend that if you're solving
this for your own benefit don't just
resort to using those built-in functions
you know functions like split which will
automatically split a string based on
the spaces and they'll do it using C
routines such that it's really fast it's
going to be better for you to go through
this assuming you didn't have so many
built-ins such that you can really
understand that time space complexity
analysis for this anyway let's move on
to the third problem I have prepared for
you guys here the third one is on daily
temperatures the way this one works is
they give you an array where you have
temperatures for each day and you need
to find how many days you need to wait
to the next warmest temperature for each
day and you return an array you know you
may say you have to wait one day one day
for days two days one day one day and if
the temperature never gets warmer than
that current day then you need to return
zero this problem I don't like so much
because number one is kind of a
difficult setup you know it takes some
time to even understand what they're
trying to ask for the other issue I
think is that it's kind of a gotcha
problem this way you either get the
solution or you don't
probably the brute-force approach which
is good to mention if you can figure it
out sometimes the brute-force approach
is a little difficult to even figure out
what they want
you know it's like it takes quadratic
time as a little bit more difficult to
calculate that out but this one is
relatively simple you just go through an
N square time because for each element
in the array you have to iterate through
the rest of the items in the array to
figure out what's the next highest
element is gonna be N squared time yeah
sure that works and in fact it's not a
bad solution if you're really limited on
space for whatever reason however most
of the time people are going to want a
faster time algorithm I believe I was
actually asked this question before too
one time
it sounds very familiar to me and you
know the way you can solve this again is
using stacks and stacks are something
you've gotta know because they're just
used all over the place anytime there's
something tricky some tricky algorithm
or something you probably need a stack
or a hash map or a queue and so the key
to this is you go through each
temperature and you push them onto a
stack whenever a new temperature comes
in you check the temperatures in the
stack and if that temperature is greater
than any other temperature in the stack
then you know that you've got a warmer
day you can calculate the difference in
index the difference in base between
that new temperature and the temperature
that was previously in the stack and
then you can just put that output into
some output array and you can imagine
that you can go through this for each
element in the array and you may be
thinking what that still quadratic time
isn't it because you're going through
each element in the array that's an
element and then you could be checking a
stack that's up to n elements as well so
that's still N squared the trick here is
to realize that you only need to check
the top element in the stack if there
was anything else that was higher
temperature before that in the stack it
would have already been popped off and
processed that's what makes this
algorithm actually in linear time
because for each element you only check
the top element in the stack your total
run time then is going to be one pass
through every temperature and then
pushing and popping the temperatures at
least once
so it's gonna be like 2n or three n time
or something like that it's linear time
Indian a very tricky little problem
funny to think about I would be
surprised if anyone ever asked you this
type of theme but somebody did ask me
this before in one problem I remember
and I think I got it too if I were to
run the solution you'll see that it's
okay it's coming in at 20% faster than
other solutions you know I'm sure a lot
of these other solutions are probably
using built-in functions and things like
that just to get their programs to run
faster it's probably not even linear
time but if you're using built-ins then
you can get your solution to probably
run very quickly without even
understanding that the big old time
analysis may not even be as fast as what
this is doing okay we got another
problem here for you the fourth one and
unfortunately a lot of these problems
that we've had today haven't been really
good problems I think like they're
tricky a lot of you seem to be pretty
tricky it's not my favorite this one is
another pretty tricky one which I didn't
really enjoy solving it is sub-arrays
son so even the setup of the problem is
a little bit difficult to understand but
they want to say that given an integer K
find the total number of continuous sub
arrays whose sum equals that integer you
know I thought about this problem for a
while I really want the best solutions I
could think of was brute force quadratic
solution you know it's a for loop inside
the for loop where you have a starting
position and the ending position and you
essentially calculate every single
permutation and as you're doing this you
add up the sum and you can find out if
that sum ever equals this integer K if
it does you increment the count and yeah
I can run this and get time limit
exceeded the funny thing about this one
is there's this totally bizarre solution
which you can solve in
time so the trick to this one is you
create a hash map of cumulative sums
which are sums that you can create from
the first number and this hash map is
the frequency of these so you go through
the elements in the array you add up the
numbers as you go through if the number
is equal to K then that's one count
that's one match what you do is then you
look into the hash map and you find if
there's any other numbers which is equal
to sum minus K and if there are then you
add those to your count as well because
those could represent potential start
points for your sub array anyway it's a
pretty tricky question
I wouldn't necessarily dwell on this one
too long let's move on to the last one
that we've got here the last one
fortunately is a little bit funner at
this palindrome linked list you're given
a linked list and you need to figure out
if that linked list is a palindrome so
I've gone ahead and I've solved this for
you and it's fairly simple right like
you can go through the linked list you
push the elements on to a stack that's
your first pass then you've got this
array you could just go through the
array and just check that the first and
last elements are the same then the
second and second and last element are
the same and so forth and that's a two
pass algorithm linear time linear space
now it becomes interesting when you
think about how can you do this without
that space requirement I can't do it in
say a constant space and there's this
clever algorithm that you can do it's
again one of these tricky things but
what you can do is you can have two
pointers and you can advance one pointer
at twice as fast as the first pointer by
doing so you can figure out what is the
midpoint of this linked list right when
the second pointer gets at the end the
first pointer will only have been
halfway through that list then from that
point on you take that first pointer and
you take it to the end of the linked
list but as you go through you reverse
each linked list then what you have at
the end is you have two pointers the
original pointers at the start and they
have a second pointer at the end
than link list and then you can traverse
both of them towards the middle checking
that the values are the same and that's
how you can determine if they are a
palindrome it is also linear time but it
will require no space which is pretty
fun actually I thought that was pretty
neat so I've got the algorithm for you
here the first portion traverses one
pointer at normal speed the second at
double speed then what they will do is
they will reverse pointers and traverse
the first pointer which is only a half
way to the end of the linked list and
then the last portion is you've got one
pointer at the head one at the tail and
just traverse them inwards and you
compare their values if they don't match
up it's false if they do match up the
answer is gonna be true I can run the
solution and I can see that it's faster
than 36% of solutions which seems good
enough personally I wouldn't have asked
a lot of these I felt that they were
just way too tricky but you know it's
always fun to practice them and you
never know what you're gonna get and so
just increasing your exposure to
different types of problems I think it's
always useful keep in mind that we use a
lot of stacks and hashmaps this time and
that's usually how it is there's gonna
be several passes with stacks and things
like that
oh I remember to check out daily coding
problems comm slash tech lead you can
get free coding questions mailed to your
inbox every day along with tips and
tricks so check that out if you liked
the video give it a like and subscribe
and I will see you next time bye