Coding Interviews Be Like

what is going on here oh my god hey nick studying for interview yeah i am but i'm really nervous i mean i can't even invert a binary tree or reverse a linked list wait when's your interview uh i think it's in like five minutes okay you know what you're probably gonna fail but if you ever get stuck just throw a hash map at the problem throw a hash map what okay it's time [Music] hey nick i'm nick with a k and i'm a senior software engineer here at face on google flicks i'm just going to send over a coder pad and then we can get started yep sounds good so here's the problem given an array of integers nums and an integer target return indices of the two numbers such that they add up to target and you can just assume that there will always be a solution what an easy problem i did this last night but i'm going to pretend i've never seen this before hmm interesting yeah so i guess my initial approach would be to use two for loops and then iterate through the array checking whether the sum of the current number and each of the numbers in front of it adds up to the target yep that sounds like a good start do you want to code it up yeah sure no problem i'll start coding it up right now and then in the event that there are no solutions then we can just throw an error yeah so that should work and it's time complexity is o of n squared because for each element we're looping through the rest of the array to find its complement which takes of n time and also the space complexity is of one okay that seems all right but it's a bit slow as you mentioned it's quadratic in time do you think you could make it even faster of course i knew this was coming yeah so we can just sort the array first and then use a left and a right pointer and move those towards the middle of the array accordingly based on whether the sum is less than or greater than our target and so the time complexity of this solution would be o of n log n because we need to sort the array and then we also have just one pass through the array which is all of n and also our space complexity will be of one yes i did it i definitely passed the interview well yes this is a bit better but it's still kind of slow i want you to think of a solution in linear time what linear time i thought i already got the optimal solution there's no way you can make it even faster hmm ah well i uh i guess we we could uh maybe uh instead of doing uh what we had before we could uh instead uh do uh uh nick we only have about five minutes left so if you can't think of a better solution don't worry about it come on nick think think what could we do man i'm so stuck wait stuck if you ever get stuck just throw a hash map at the problem throw a hash map at the problem that's it i'll use a hash map yeah so we can use a hash map we can just iterate through the array and find the complement of each number and if the complement already exists as a key in the hashmap we can just return the corresponding value which is going to be an index along with our current index and the sum of the two numbers at those indices will add up to our target and if the complement does not already exist as a key in the hashmap then we're just going to store our current number along with our current index in our hash map yep that sounds like a pretty good plan we only have a few more minutes though so if you could code that up quickly that'd be great yeah sure i can start coding it up now and then again as i mentioned in the event that um the complement does not exist in the hashmap then we're just going to store our current number along with its index in the hashmap so that should work and in terms of time complexity we're only looping through the array once and since hashmaps have constant lookup times this algorithm is simply o of n in time and our hashmap would store at most n elements so it's going to be of n in space yes i finally did it i definitely passed now perfect well done nick that concludes the interview for today keep an eye out for an email to schedule your next interview alright have a nice day nick thank you you too wait did he just say next interview there's more you

Channel: Nicholas T.

Views: 1,561,554

Rating: 4.911087 out of 5

Keywords: waterloo, university of waterloo, computer science, waterloo aif, waterloo cs, waterloo computer science, waterloo aif tips, how to get into waterloo cs, nicholas t, uwaterloo, cs major, computer science student, internship, university student, cs majors be like, software engineering internship, swe intern, startup, waterloo coop, coding interview, technical interview, first internship, software engineering interview, coding, interview, job interview, intern

Id: kVgy1GSDHG8

Length: 5min 30sec (330 seconds)

Published: Tue Feb 16 2021