Detect Capital - LeetCode Interview Coding Challenge [Java Brains]

hello and welcome to this java interview recording challenge video where we don't just solve coding problems we learn how to tackle them in an actual interview setting you learn how to solve the problem and what to discuss about the problem in an interview to maximize your chances of success in this video we're going to be tackling the lead code problem called detect capital right this is lee code number 520 so here's what the problem states given the world you need to judge whether the usage of capital letters in that word is right or not okay respects the question what is right what is the usage of capital letters that's right well so there are three conditions here here's the right usage either the word should contain all letters capitals okay everything is capital in this word then you can say the usage is right are all the letters are lowercase in that word even in that case you can say the usage is right and then the third case is only the first letter of that word is capital rest or lowercase in that case also you can say the usage is right okay so these are the three conditions given a word you need to check if any of these three conditions meet in that case you're going to return true and if any of these conditions do not meet in that case the usage of capitals in that word is not correct as per this problem so you have to return false okay so this is the problem statement and if an interviewer is asking you this this is what they would leave you with so when you hear this in an interview the first set of things you're going to have to think about is like okay let's identify some words which meet this criteria and some words which do not meet this criteria right so let's look at some words which actually meet this criteria we have three conditions here so let's identify those words so here are some right usages so all caps this is an example of a word that is all caps so the usage of capitals is correct all right here is a word which is all lowercase so even this one should say the usage is correct right and here is a word where the first letter is capitals and the rest are lowercase right so this combination is also correct so here are three use cases where your function whatever you're writing it should return yep this is all good okay so if this is not meant so for example i have like a mixed case or something like that then it should return false okay so this is the expectation for your program all right so before we look at the approach uh there are some things you're going to have to clarify and this again goes back to what you would typically ask in an interview setting any tip coding challenge you would have to ask this first thing is you look at the boundary condition right what if you're you're given an empty string right the word without any characters what should the expectation be does it meet the criteria like is it is it yes or no that's a good question to ask the interviewer let's say the interviewer says yeah you can you can return true uh there is an obvious implication about what happens when there is a one letter word that's given okay if one letter is either going to be lowercase or uppercase well in that case what what is expectation well an interviewer can say well that's also valid return true uh there are other conditions you're gonna have to think about like what if the word contains like special characters which are neither uppercase nor lowercase right this can apply to the one character word as well so here again the interviewer can take multiple different options let's say the interviewer says don't worry about it right you know that what you're gonna get is is just alphabets all right so let's let's set the stage there if the interviewer say something else you know there could be special characters and you have to accommodate that in your code right you're going to have to write code which does that check just asking this question and knowing that you're you know you you're covering all your bases you're making sure you're that detail-oriented person it's gonna it's gonna benefit you in an interview so okay let's let's ask those questions get it out of the way and you're now you're gonna start with the approach right you're gonna solve this problem how are you going to solve this problem the the basic approach that you can think of is like just do a check like you would do a check right so you're checking this well what you're going to do is you're going to look at the first letter is that uppercase well okay then is the second letter uppercase well if both of them are uppercase that means that you're going to have to check all of them to be uppercase right because you're looking at the all uppercase scenario all right so let me actually demonstrate what i mean by that so if i were to look at the possible words the possible conditions let's say i have a all uppercase word okay so this is all uppercase now this is valid okay now we have first letter uppercase and the rest lowercase this is valid as well all right and then you have the everything lowercase this is valid as well okay so now what you need to do is you can basically have a bunch of if conditions which does these checks okay so first check the first letter see if it does uppercase well then from here on everything needs to be either all uppercase or all lowercase all right and then you check the first letter if it's lowercase well then from here on everything needs to be lowercase right it's a simple way to check this you basically stick a bunch of if conditions right but there is uh there are a couple of ways in which you can make this a little more elegant all right so before i get into all these different uh you know ways in which you can tackle this i want to point out one solution that i found online it's kind of like a clever way of solving the problem let's look at that and then we will see what are the disadvantages of using that approach it's clever but it's a little bit of a disadvantage so if you don't want to do this if you don't want to do this kind of if condition well there is a shortcut way to find out if these conditions mean all right so here's the shortcut way first count all the number of uppercase letters in in that word okay you want to get all of the uppercase letters in the word now the number of uppercase letters could be anywhere from zero to the length of the word right let's say you're given a 20 letter word now the number of uppercase letters in that word can be zero it could be 20 which means they're all uppercase or it could be anything in between right so if you know that the number of uppercase letters in that word is zero what does it mean it means that it's all lowercase word in that case you just return zero you just redone true right this all lowercase your condition is valid r if the number of uppercase letters you get is equal to the length of the string which means it's all uppercase well even then you return true okay so this is what you do count the number of uppercase letters if it's either 0 or if it's equal to the length of the string just return true all right fine now this leaves the third condition which is the first letter is uppercase and the rest of them are lowercase now how do you check that well that's simple as well now you it's not zero at this point and it's not equal to the length of the string it's somewhere in between what does it actually need to be for the third condition to be met it has to be one right only the first letter has to be uppercase so if the first letter is uppercase then the count is 1. so if the count is not one again here you can return false right it's not zero it's not the length it's not one it's somewhere in between that means there are more than one uppercase letters that's not that's not valid you just return false but if it is one then you just check the first letter if that is the uppercase one is that the one that you got right you just check the first letter that's the first letter is uppercase and you know that there is only one uppercase that means obviously that the rest of the letters are lowercase right so in that case you return true and if for all the other conditions you return false all right this is a a clever solution you're not dealing with the if conditions you're like okay if this is the case then i need to scan for this if this is the case i need to scan for that it's uh it's easy right you just do one pass count the number of uppercase letters and then you just make a decision based on the results that you get right that's easy and it's simple to understand so here's what the code would look like for this if you were to implement this this is what the code would look like so first of all i have a detect capital use with the method which takes in a word as an argument and then it returns a boolean right you're basically having a method which passes a judgment it's a thumbs up or a thumbs down for your word right so it returns a boolean now what does this method do first it initializes a variable called number of capitals is zero right because you need to measure the number of capital letters in this word so what you do is you do just that find i equal 0 i less than word dot length i plus plus i am basically going to check each letter i'm going to do word dot care out of i so i'm going to get each letter one by one inside this loop and i'm going to check if that get letter that i got is uppercase that's uppercase what do i need to do i need to increment this guy all right so i'm going to do that number of capitals plus plus now i finish this whole thing what do i need to do i need to check if number of capitals at the end of this loop is it equal to zero or if it's equal to word.length well then i know that in this particular case if it's equal to word dot length that means that the word is all caps if it's equal to zero that means that the word is also lower case so i'm going to return true those are those two cases right this leaves the final case which is the first letter capital and the rest of them are small then i need to return true how do i detect that i just do this if the number of capitals equals one and character dot is uppercase of word or category zero so this is the first letter i'm gonna check if it's number of capitals is one and the first letter is upper case then i return true otherwise this condition is going to be false so my method is going to return false okay simple method right simple approach makes sense it's easy and it's you know you it works right he gives you the answer that you need but there is a disadvantage to using this approach all right before we talk about the disadvantage let's look at the time complexity of this thing what's the bigger notation of this approach well the bigger is of n okay here n is the size of the word what does of n mean of n basically means that your algorithm is dependent on the size of the input here the size of the input is the length of the word right so you basically are looping through this whole word calculating all the capitals you're going to have to do one pass of the word and then you're going to find out all the capital letters so the time complexities of n right doing the decision based on the number of calculators that's constant time you don't even have to think about that right this is o n is the algorithm so can we do better if you answer this in an interview the interviewer is very likely going to come back to well can you improve this algorithm can you make it run a little faster right so what's the drawback with this approach it's good it's easy to understand but there is a certain drawback what's the drawback well the drawback is we are not quitting as soon as we can okay take for example i have a word which looks like this okay so i have a capital letter and a small letter and another capital letter okay by the time i hit the third character i know that this thing doesn't meet my requirements right this is gone when the first letter is capital and the second is small then all of the other letters in that word has to be small otherwise you're going to return false anyway right so at this point when you detect the third letter you know it's not going to work there's really no point in having to scan the rest of the word but does our smart algorithm take care of this no it's going to calculate all the capitals anyway right so if you have a long word and you have some combination like this where you can quit early you're not quitting early okay so here's the question can you quit at the first wrong quote-unquote wrong character that you encounter well you can but then we're going to deal with the the if condition mess right you're going to have to say okay if this is the case then do this if this is the case then do that well turns out the lead code recommended solution actually does something like this all right so here's the recommended way and here is here's how they come to this right so let me explain to you what the logic is it's not a lot of if conditions cannot reduce it to just one okay so here's how this goes let's uh let's repeat the the use cases that we've seen so far so we have all capitals okay everything is capital in the world this is valid or you have all smalls okay everything in this word is small which is also valid and then you have the first letter capital and the rest are small this is also valid so in theory this looks like you're validating three use cases right you have to have if conditions to check for all these three things but if you think about it it's actually just two use cases right think about these two use cases here these two what's common about this the thing that's common about both these use cases is that it really doesn't matter what the first letter is what you're doing is you are looking from the second letter onwards to see if all of the remaining letters are lower case right so you don't even need to check the first letter okay if you're just validating these two use cases then what do you what do you need to do your application needs to just check from the second letter on to see if all of them are lowercase okay so this is actually condition number one okay condition number one is when the second letter onwards the whole word is lowercase all right and then this is the only other additional condition which is condition number two which is to see all of them if the first letter and the second letter are upper case well then the check that you need to do is that all of them are uppercase right so you're basically looking at two conditions not three so this is what this code does all right this is what's the lead code supplied uh result the resolution right the lead code supplied solution so here's what it's doing here's the first case which is the all capital case all right so if word dot carrot of zero which is the first letter is upper case and word dot carrot of one which is the second letter is uppercase well then what do you need to do you need to make sure that the whole word is uppercase so i'm going to loop from i equals 2 to less than n anytime i encounter lowercase i'm going to say false right because i need to make sure the rest of the stuff is all uppercase which is what the first case cases are the second case of course the first case is what this is what this is talking about right this is number two that i've added over here this is what's looking at okay now this one case two and three is basically the the scenario of the second character onwards being everything being uh lowercase okay so i'm going to look at i equals 1 to i less than n now i need to make sure the whole thing is lowercase okay which is what these two are right the whole thing is lowercase so i'm going to see if any one of them is uppercase i'm going to return false right away okay and then here there needs to be a return true so if it doesn't return so far then here at the end it should just return true okay so this is the the thing that i found from the from the lead code page itself but i feel like we can still do better okay before we talk about that so what is the time complexity of this thing this is still of n right you're gonna have to loop through all of them all the letters but it's going to be one of these two loops right it's either going to be the first loop or the second loop you're going to have you have that in an if block so one of those loops are going to run and the advantage of this over the previous one is you can quit early you can quit at the first wrong character you encountered i'm going to say yes i'm quitting this is not valid you save some time there in some optimization that you can perform but it's still often because of the way we calculate big o okay so there is one improvement we can do for this thing so that it doesn't look this bad i'm not a big fan of doing this because you're basically having a loop which does the same thing kind of but with different conditions okay so if this condition is met what am i doing i'm checking for character is lowercase in order to exit if this condition is met then what am i doing i'm checking character rod is uppercase as the condition which causes me to exit okay so i'm what is the common between these two things i'm looking through the whole string right i'm checking for a condition every time and when that condition is met or not met whichever it may be i'm going to return false right that's the common pattern now i essentially have duplicated that code because the condition is different what if i were to kind of take that condition out how can i do that what if i have that condition be a variable you might wonder well how can i have a condition as a variable well it turns out in java you very well can with lambdas okay lambda is a way in which you can hold on to this kind of a check right some logic you can hold on to it in a variable and then inside the loop you don't have to say if this then that you just set the variable just once and then run that variable that lambda thing inside the loop it results in much more elegant code it's not going to result in any performance improvement but it results in much more elegant code so here's what it looks like so first of all the insight is that the first two characters affect what the check should be so i'm going to have a condition for identifying where the check is based on the first two characters and then we're going to use a little bit of lambdas to make our job simple okay so here's the solution what we're going to do is first of all we're going to do the boundary check okay if word.length is less than or equal to 1 i'm going to return true right because we know we've asked the interviewer that entry has told okay this is the boundary check just put that thing in there all right it's the first thing you do and then after this now i'm going to hold on to a predicate okay a predicate in java is basically a lambda which takes in something and then returns a boolean true or false okay it basically judges your value it's going to say a or nay okay that's what a predicate does it returns true or false it returns thumbs up or thumbs down so you can pass to a predicate anything you want and then the predicate is going to pass judgment on it and it's going to return a boolean okay so predicate of character is basically a predicate which takes in a character value and then it returns a boolean true or false okay so i'm going to have a predicate called correct case which is going to be initialized with the value of lowercase okay so what correct case does is it takes a character and then it returns true or false well in this case it returns true if that character is lowercase and it returns false if that character is not lowercase okay that's what i've done over here right this expression which i'm using for assigning to this thing it's basically a lambda which which runs character dot is lowercase for any input character and then it returns a boolean okay fine now if we were to just look at the condition of like everything lowercase right it doesn't matter what the first condition is imagine if you're just looking at that now what do you have to do now i'm gonna do loop through the word and i'm testing against this correct case now rather than have the condition be embedded hard coded in my code i am using a lambda to test the word dot caret of i okay which is basically similar to what we did earlier in this case we were doing is lowercase well now i am kind of doing this lowercase because you see here i'm assigning lowercase as the lambda to correct case and i'm doing correctcase.test this is how you you run predicates by the way you run predicates by doing the predicate dot test method you pass in what you wanted to test and then it's going to again return the a or name okay so now i'm checking if correct case.test of this then if not thus then i'm going to return false right i want it to be lower case right the correct case is lowercase so i'm going to scan from the second letter onwards which is where i is one and if any of them doesn't meet really then the minute i find an uppercase letter i'm going to return false okay so this is going to accommodate these two use cases right first letter is capitals rest are lower or the first letter is lower and the rest are lower as well okay so i'm going to scan from here on and i'm checking if correct case of each of these letters right here this is lowercase i'm checking if each of these is lower well then i'm going to continue if any of them is not lower well then i exit okay which is what i'm doing here if not correct case then i return false okay so that takes care of those two but now this leaves this case where you have all capitals okay now in this case this will not work i cannot check for this this is a special case where if the first two are caps then the check that i need to do from here on is upper not lower okay so that what do i do i basically hide that check over here so what i do is if the first character is uppercase and the second character is uppercase now the correct case is not lowercase anymore it happens to be uppercase okay so i'm going to check that if not this then it's going to go ahead with the check as before but if the first two characters are uppercase well then the correct case that i need to be checking for is uppercase and again the same logic holds good if not correctcase.testoftheword.carrot i'm going to return false essentially what i've done is rather than have two repetition of this loop have this loop twice and inside an if condition i have extracted the out and put that as an assignment of a predicate all right so predicate is going to decide what the check should be and that is influenced by the if condition the loop is essentially outside the f condition and you don't have to repeat this twice in the code it just is there once all right the benefit of this of course is that it makes your code a little more elegant and if you have to change it later you don't have to change two places you just change this one place because loop is in just one location and it makes it easy to maintain as well if you use this kind of reasoning and you mentioned this code in your interview you're going to nail the interview right because this is something that you would have to do in an actual job situation you're writing code for a company you need to make sure that your code not just works but it's also elegant it's also maintainable and you're not writing code which has likely to introduce bugs you know in the process in the age of the code right you're making it more uh bug-free more likely to be bug-free because you removed duplicates okay so again let's look at the time complexity what are we looking at it's the law of n okay hasn't changed but then we're making we're making it a little more optimal because we're exiting early like we discussed earlier but then we're also making it more optimal for maintainability and readability which is a big plus so this is the lead code problem detect capital i hope you found it helpful please check out the playlist for other lead code and hacker rank problems in an interview setting thanks for watching

Channel: Java Brains

Views: 16,260

Rating: 4.957356 out of 5

Keywords: java brains, java, interview, coding, coding challenge, java interview, java interview questions, interview coding challenge, interview practice, koushik, koushik kothagal, java interview videos, java interview challenge videos, kothagal, kaushik, tutorial, programming, beginner, java programming, java tutorial for beginners, java tutorial, java programming tutorial, leetcode, hackerrank, java programming for beginners, java interview questions and answers, cracking the coding interview

Id: 1VtgflWO7cE

Length: 25min 8sec (1508 seconds)

Published: Wed Sep 02 2020