How to solve coding interview problems ("Let's leetcode")

hey tackle 8 here and welcome back to another episode I thought what we would do today is go through a few coding problems these are standard coding whiteboarding problems that you may see at the coding interview and figure out we'll just solve a few of these for you get to as many of these as we can and kind of give you guys an idea about how to go about practicing for the whiteboarding portion of the coding interview as well as solving through them you may have noticed that it is indeed coffee time and I have a very nice cup of joe right here in front of me this video by the way is sponsored by daily coding problem comm slash tech lead it's entirely free just send them for their mailing list they give you one coding question every day and you can just practice it if you have time if you're bored pull your phone out of your pocket start reading through it and just start thinking about it so check that out I'll be doing those questions too and you can feel free to ask me about any of them on Twitter as well so with that said let's get into it and what we're going to be using here is leet cocom very popular website for practicing interview questions and sure they do provide you a interface to write code and run it but it's just not very good and I would recommend that you get something else set up such that you can run the code locally you can run it very fast I'm going to show you what I do and it's up to you if you want to do something similar I might use something like Visual Studio code and you can install an extension known as code Runner which will be able to run code for you so I can just select the code I want to execute and then I can just run it very quickly and that gives me a really quick feedback code runner supports a variety of languages including like JavaScript as well and then if you're really into JavaScript which I'm pretty into actually if I were doing leet code I might actually be using JavaScript as my default language just because it's very quick to develop for me chrome actually has a very good toolset for this as well you go into developer tools and you can create snippets and these JavaScript snippets are really great too you can just execute the code and you can start seeing the output in the chrome console so that's good too now I have one more tip that I want to tell you about before we get going here and that is your choice of language and it's kind of interesting actually that if I were to tell you my progression into Elite code master when just got other college the main languages I knew were the ones that my courses taught me which was like Java C++ and using these languages I found that my algorithm performance suffered somewhat because these languages aren't that great I think in terms of data structure support whatever language you choose you're gonna want to make sure that you have good command over cues stacks and hashmaps these are going to be absolutely a center you're gonna need these things you know I thought that like C++ for example you have to import at the hashmap or the SCT vector and sure yeah once you import it then you can get things going but it's just one extra mental leap for you to do that and it may be enough for you to just not even go into using a hash map even using Java you may have to import a hash map and then you may have to put in strong typing using templates to indicate what type the key and value of these hash maps are going to be the verbosity of these languages for me at least just made me more hesitant to be using these data structures and I found that once I began programming in PHP and JavaScript and PHP is a commonly hated on language but I think it's actually a very good language it's great actually you can get so much done if all you care about is having a good time as you're shipping tons of code PHP is actually really great for that just just don't tell anybody I said that though but once you start using languages that are less strongly typed and which have native support for hashmaps two stacks I think that your algorithm whiteboarding performance will also improve because it's going to just be so easy to start putting these data structures together like in one line of code you can put together a hash map of a race of stacks which may just be the data structure that you need this would be more difficult to do if you were to use a heavier weight language like Java C++ but you know it's whatever language works well for you really if you're already a master at Java or C++ then go with it but I would say that if you're just writing fresh maybe look into something like Python or JavaScript so what I do these days is I think about how I myself the problem using say JavaScript PHP some pseudocode and then translate that into the language that the interviewer is looking for like if I'm interviewing for an objective-c role I'm going to translate that code from pseudocode in my head into objective-c code and read that down so this is leak here and what we're going to do is just keep clicking until we find one that's easy or medium I don't think the difficult level the hard level problems are really worth doing they're just too involved and most interviewers probably are really going to ask them I think they'd rather go through a bunch of easy medium ones instead of asking for a single hard one okay so we found one here Pascal's triangle - given a non-negative index K where K is less than 33 returned the k2 index row of the Pascal triangle so probably what we would do here is just go through row by row generating the digits just a little bit of arithmetic and for example if you want the third row it's gonna take three iterations that means the runtime will be linear in regards to K and then the space complexity is going to be depends how you're gonna do it you could be using a linear amount of space in regards to K because for each row you go through you would need at most an array of size say K or so let's try getting the code down these easily called questions are just so much fun alright there we go so what I did is I just iterated through the items inside each row and just added the digits from the prior row and then made that the new row so we're always using that same array helps save on space we're not creating a new one every time and if I have to run this what I'm getting is that correct answer and you know maybe it's now time to just try plugging this in run the code on the code and it looks like it's passed a smoke test if I click Submit we can see yeah my solution did succeed the runtime is faster than only 6.8 percent of JavaScript all nice submissions which means my function is probably kind of slow let's see if I can make that a little bit faster actually so that was funny what I did was I just pre-allocated the size of the array because I already knew what size it was gonna be just like that my solution is not running faster than 87% of online solutions which is pretty fun pretty Nia okay that's great so we got through one and you may have noticed that I didn't create any classes or data structures really here and I probably should have if there's are an actual interviewing question I'll probably start with just creating class definitions that gets me just a few extra points for showing that in the object-oriented programming or classes I just get that extra point in there for myself I liked how great this helper functions like the item that just helps me do the edge case scenario checks every didn't have time for this I probably didn't you have to fill that in you'll notice now that actually running through the code is pretty slow having to write down the actual code making it actually compile if I actually practicing I'll probably mostly just think about the solution but not necessarily write the whole thing maybe I would just write down some pseudocode until I'm convinced I could do it this is another problem longest palindrome and that's just saying given an input of a random set of letters what's the longest palindrome that you can make other this the thing to notice here is that the letters the order that they come in it doesn't really matter so you may sort just go through and first create a hash map indicating for each letter how many characters do you have and you know to me that kind of boils down to input into a data format that is much more manageable you know really all you need to do then is just go through each character count how many pairs of characters that you have for each pair that you have that is a palindrome right because you can have one letter at the beginning one at the end and then if you have any letters are left over that don't have a pair then you can also increase the length of your palindrome by one more because that can be in the center position the time complexity is going to be a series of passes and usually that's how these programs are done it's a series of passes right the first pass is maybe you create the hash map with the count of characters and then you maybe do a second pass through that hash map to figure out how many pairs do you have so two passes given the length of the input that's going to be linear time space complexity is going to be also a linear space because you have to create hash map that is going to be the size of the input we can write down the function what that may look like here so the first portion creates the hash map and then the second portion scans the hash map or pairs and it will also figure out as a scanning through if it finds any odd number of letters and if it does it would just remember that and then Indian and we just returned the total number of pairs times 2 plus 1 if there's a remaining character we run the code we can see that it will pass that smoke check if I amid the solution i'll see that yeah it's faster than 80% of javascript online solutions great done we got another problem here it's a medium leak code question insert into binary search tree and this is really pretty standard I would say you're given the binary search tree it's ordered and what you need to do is insert a value into the tree and this is normally going to be more difficult if you have to keep it balanced in order to do this what you want to is just traverse the tree and check the value in each node and if the value is greater you want Traverse down the right side of the node and then if the value is less than that in the node then you want Traverse down the left side and so forth it's recursive as you might imagine I've put together a solution here which essentially does what that was just saying if the values greater checks that right node if there's no node then it creates that node and then we're done if there is a note that already existed then it would traverse that and just recall recursively in certainty BST on that note we can run the code and we see that it passed the smokecheck runs submit and we can see that it is faster than 29% of JavaScript online solutions which is funny because once I saw that I thought okay doing something a little bit wrong here does a much faster way to be doing this I like to hit at least save 5060 percent performance and what I realized was that this can actually be done using an iterative solution and you know I would say that's really one of the first things to be thinking about whenever you do these things is think about doing it iteratively because even though recursion is very funny it's very cool and schools love to teach you this stuff in the real world you don't see recursion all that often because recursion has a lot of limits what is this limited to that stack space and so in real life systems a lot of software is much bigger it's going to hit that stack space limit immediately so there's almost always a way to do something iteratively and that's often the simpler and preferred solution and it's going to be running faster too because you don't end up building up a bunch of stack space I converted this into an iterative algorithm and really all that has to do is it goes through as a loop and it creates a node and then this node gets assigned to the current value of the node as traversing through if I have to run this code I will see that it is faster than 99% of JavaScript online submissions which is amazing I don't know if that's accurate but it sounds about right for a tech lead what's the run time right well it's going to be traversing the binary search tree and if the tree is balanced we could say it's going to be logarithmic because it won't traverse every node it's going to be just the height of that tree which is log 2 but in the worst case scenario the tree could be entirely unbalanced it could just be a single branch all the way down and then it would be linear in time complexity so that's really going to be the answer linear time in terms of space complexity we're using almost no space we're just traversing each node as we go through we're using like a one variable basically so space complexity is constant let's see if we can do one more easy one just for fun longest word in dictionary so given them lissa words find the longest word within that set that can be created by the other words within there this could probably be done using like a tree or try data structure or there's like a tree structure and each node has a character a letter that it represents and so when you get a new word you just reverse that tree and you count what's the maximum length that you can reach the trick here is how do you create that tree data structure I think what I'm going to be doing here is I would just create a hash map of hash maps of hash maps and yeah I think that could probably do it the time complexity will be linear with regards to the number of letters in the input because you'll just be traversing each letter and then the space complexity will also be linear with regards to that because we're just going to be building a data structure that contains the total number of letters that we see in the worst case scenario so this is fun you know I'm just having a blast doing this stuff it's so much fun you know I'm just having too much fun here ok all right so I've completed the algorithm here and there's two passes really the first pass constructs the tree and then the second pass traverses it and I have a little bit of trouble actually with this because I was first ready to do it in a single pass and just while constructing the tree also be traversed and I realized then that that wouldn't quite work because I first needed to construct the tree first so I separated it out into two passes and then in order to indicate that award had been completed I inserted a dot into the tree to indicate that then in my second pass I would traverse the tree and check that there's this thought at each character as I'm traversing to make sure that each character is accounted for and that a path exists to create the word so that's that as submitted the solution was faster than say 60% of other solutions which seems fine and this was the tree solution if you think about that there were probably a bunch of other different solutions you could have tried like say sorting the words or doing brute force where for each character you just check the number of other characters and it says some of these brute force approaches are actually more difficult to implement and tried to calculate some of that time complexity is more tricky right because it's going to be like for each character in the word you need to check all the other words so if there's n words and J characters is going to be like J times N or something like that in terms of time complexity and yeah I think there's a few interesting things about this data structure that I had chose to use probably the data structure could have been better formatted like I just used the hash map of hash maps and if I had just actually created like a tree data structure probably would have been a lot cleaner and then maybe would have gone for something like that if I had actually been doing this in an interview since I was doing likely coding and I just wanted to get a fast efficient solution going I just said if I inform what they the structure but I think that's one thing to think about is whichever language you choose sometimes you may need to be creating hash maps of hash maps and you want to make sure that your language supports that easily I think Python overall is a pretty good language and just remember that anytime there's a chance to show off your knowledge of data structures like creating custom classes you want to think about doing that if you can which is again why I don't necessarily advocate spending all your time solving every single whiteboard question in detail and getting it to compile because sometimes that just takes a little bit too long to correct compilable code so that'll for me and you guys can continue practicing some of these questions remember to sign up for daily coding problem Val comm slash tech lead if you the video give it a like and subscribe and I'll see you next time but

Channel: TechLead

Views: 384,621

Keywords: interview, whiteboarding, leetcode, code, algorithms, techlead, hackerrank, science, coding, programming, computer, questions

Id: dIrS31CCITM

Length: 15min 31sec (931 seconds)

Published: Thu Nov 15 2018