Hi I'm Sam! Ex-Google/Amazon Sr. Software Engineer in robotics research 8+ years. I love to share what I've learned in a way that's understandable for all levels.
Follow along as I time myself trying new Leetcode questions live, explaining how I would approach it in a tech interview!
That's a really cool way to do it! I bet it's pretty fast too since it'll go to C pretty quickly. I had a quick look into how python & others do log2, often it goes to a C backend implementation which is constant time O(1) which is great, but a lot of overhead for all the extra checks to get there, stackoverflow.com/questions/59255921/what-is-the-time-complexity-of-math-log2x-in-python-3#:~:text=log2%20works%20on%20floating%20points,itself%20runs%20in%20constant%20time. Since this offloads the majority of the algorithm to the backend, I probably wouldn't suggest this approach in an interview (except to point out), it feels similar to finding a palindrome by reversing a string and comparing to itself (a valid solution, but extra steps).
Have you implemented piece detection? If so I know who's job you're gonna take away (not really) There's russian channel that is reviewing chess games from various movies and cartoons. And he spends conciderable amount of time recreating the game from slivers of information.
I've done some casual stuff in the past, but no real attempts yet! What's the channel? I think the step up from finding a chessboard to detecting pieces *accurately* is a pretty big one (I've seen some attempts at piece detection that work in very limited settings), part of the tough part is getting good data, synthetic data seems to have a lot of potential, so perhaps generating synthetic data with a comic-style rendering (perhaps even a stable diffusion Lora) may make this more possible. However, recreating games is a much larger problem than single image board or even piece detection. I appreciate the watch and comment, thanks!
@@stayqurious That's very nice of you to say! My suggestion: Try to find some toy application, game, or small project which uses computer programming techniques (say dsa) and also really excites you. Just start trying to code it up, start simple, and add on to it as you want, even if it takes years (...like this video heh), it's fun to do and since you're doing it by yourself you will pick up the skills of learning/researching/comparing/etc. as you go along. This is just one way to do things that worked for me, but I like it!
This was an interesting watch! It was cool to see how different ML techniques could be used to solve the problem you were trying to solve, and your explanation on their respective drawbacks and advantages is fascinating. Would love to see part two of this!
Cheers thanks for watching and glad you liked it! Yes I love trying to convey that often there isn't one 'true' algorithm for any problem, but different tradeoffs depending on what we're doing, which does surprisingly apply to the leetcode tech interview process too haha. And definitely, I'm working on the 2nd part now, stay tuned!
You could use your idea of not comparing past halfway in the second form of the solution: ``` class Solution: def firstPalindrome(self, words: List[str]) -> str: for word in words: forward_slice = slice(0, len(word)//2) reverse_slice = slice(-1, -(1+len(word)//2), -1) if word[forward_slice] == word[reverse_slice]: return word return "" ```
Were you able to figure it out? Here's the answer and explanation below and in the related video : The Answer is Euclid's algorithm, sometimes called the Euclidean algorithm or the division algorithm! en.wikipedia.org/wiki/Euclidean_algorithm This ancient mathematical method was written around 300 B.C and is one of the oldest algorithms still used today as a simple and efficient way to find the greatest common divisor of two numbers. The short and related video show how this can apply to dividing a field into squares, which is mathematically equivalent to all sorts of things like simplifying fractions, dividing resources, cryptography, number theory and more. Thanks for watching! Are there any other algorithms you'd like to see visualized?
Thanks for saying that and following along! Yes I've been trying out different things and it's both fun and a tad stressful trying to figure out where to apply the right kind of effort to make enjoyable and better quality videos. Feedback like these comments and hearing you like this helps a lot!
This advice is great, I would add one tip.If you are in a very fast interview (ex. 20 min/question for mediums/hards) don't spend too much time at the start of your interview providing an explanation as you will be very time crunched.
Thanks Hersh and woah! Yes agreed, if one only has ~20 min to solve medium or hard questions then there isn't really much time to do anything besides identify and write a solution, I've never had or given interviews like that, what a tough experience that sounds like!
The top leetcode problems are about exploiting weird quirks of languages and are completely removed from the code most people write while solving business problems.
Yep there are definitely a ton of leetcode questions that are arbitrary and I don't like those questions either! Not sure I've seen most of the top ones being like that though. I think of leetcode as a tool just like weightlifting is a tool, even if lifting heavy weights isn't 1-1 to being a great construction worker it can help in aspects.
Thank you, Sam, for sharing these invaluable tips for tech interviews! I appreciate your dedication to providing valuable content. I understand you have a busy schedule, but would it be possible to arrange a mock interview session with you? Your expertise would undoubtedly be instrumental in refining my interview skills. Looking forward to hearing from you! Keep up the fantastic work! :)
Hi Deep, thank you for the kind message and sure! I list my services at www.tetralark.com/schedule and if it makes sense for you then there's a form to contact me there.
When solving Leetcode problems, do you read if ever other people’s solutions? I mean would you recommend to avoid reading solution and keep on fighting on one’s own till the end? I hope my question is clear, though English is not my native language.
Hey that's a great question, I'll make a short answering this but here it is too: The answer isn't very satisfying, I think it depends! 1 - If you're staring at a problem for ~10min and you haven't the faintest idea of what the solution might be, then yes, look up the solution, it's not productive trying to recreate centuries of research to figure out say quicksort (unless you're excited by algorithms and are doing it for the love of it, then absolutely yes!). So if you don't know the existence of the algorithm at all, then yes look it up! 2 - However, if after ~10min you kinda know that say you'll need to use a hash map to track entries in an array, but you're not sure how to write it yet, then here I think it would hurt yourself to look up the answer instead of spending < 30 min to an hour trying to solve this, because then you'd lose out on that experience gain. So, when you feel like you could write a solution (even if just brute force ish), then it's worth writing the solution first because it'll make your pattern-matching skills, connecting the dots, etc. skill grow and the next time you see a problem like that you'll know you can already do the brute, and can start trying to apply more optimized solutions. After you've solved a problem, it's great to go over a couple of the solutions / discussions. However often the discussions have people saying VERY wrong solutions or ideas, so keep a critical eye.
Hey Sam! First of all, I wanted to thank you for your videos. I've been following along with you, tackling beginner-level Python problems, and it's been incredibly helpful! Secondly, I wanted to ask if you learned Python from any specific sources or books back in the day? Or perhaps you just jumped around different resources like I'm doing, which feels like a bit of a time sink. Thanks again, and wishing you all the best! :)
Hey Dan thanks for the kind words! I'd say coursework forced me to spend a lot of time in this world, but I have found books like cracking the coding interview are a great overview as well, finding a personal project you enjoy coding I think is another way. I'll make a video on ways to learn Python for you at some point (say a series of concepts to learn that gets a good foundation)
Agreed, I feel generally anything under 20-30ms variance falls under runtime variability, unless I see a distribution that is unusual in the submission graph. And yes removing branches is such an interesting way to optimize algorithms outside of algorithmic efficiency
Can you make a video on the tutorial on the shortcut and how you move everything around so fast? I know how they work but the way you did it is so magical
I feel like most other videos didn't quite explain things this well. I had no idea what anyone was talking about regarding the pattern in the power of 2s. Thank you!
Hi Sam, first of all, your videos are great! I have a question about the difference between the space complexities between the "array approach" and the "dictionary approach". Since the dictionary can have a maximum size of 26, because both the strings contain only "lowercase English letters", shouldn't the space complexity of both approaches (array and dictionary) technically be the same? so O(n)? Maybe, on average, the space complexity of the "dictionary approach" could be lower than that of the "array approach, although I'm not sure about this 😅 P.S.: English is not my native language, so I apologize for any mistakes. 😅
Appreciate the kind words, and thanks for asking, this is a great question! Yes, you're correct that both the dictionary and array approach have a max size of 26 each in this case. So the space complexity for both is constant O(1) technically, or we could say O(K) for K unique chars, K = 26 for lowercase English letters in this case. So yes, though both of them have the same big O space complexity, there are 2 things that still can differ: 1 - big O is worst case, not average case, on average dictionary will use only as many unique chars as given, whilst array will always use exactly 26 2 - 2 algorithms with the same big O can still have different speeds, example A and B are both O(N) in worst case, but A does 3 operations for every 1 operation of B, so on <average> A O(3N) vs O(N) for B The relationship between worst/average time complexity isn't always described well for algorithms, www.bigocheatsheet.com/ goes into it a bit. Getting back to our problem, build a hash map, insert/removes are amortized O(1) ops but can become O(N) in worst case, this isn't a problem here, but worth keeping in mind. However, in python building a hash map, dynamically allocating memory and increasing the hash map size etc. all take non-negligible amounts of time, and this adds up when compared to the much simpler array approach with a single static allocation. as K >> infinity the hashmap will outperform the array. So that's where we're getting the speedup, but again, from a tech interview point it's better to choose an option that conveys the logic clearest to an interviewer versus the one that is 'leetcode fastest' Also, your English is fantastic.
Speak of the devil ;) I actually finished recording the video recently! I have some other videos in the pipeline, but once I'm finished editing it I'll bump it up in the queue, ie it'll be public within the next 2-3 days :) What a fun problem by the way, thanks for sharing it!
Good question, for me I have a general mental checklist I apply to problems, there is usually a brute force solution that does it in the simplest possible way, then there may be some alternate data structures or algorithms that could be used in other approaches to solve it better, and then sometimes there are mathematical reframings of the problem that could solve it too. So i just try to go through that checklist in my head and see if it applies to the problem or not, so you'll see I often say a potential approach but then rule it out as I decide it doesn't work etc. I'll see about putting a video together on this
Ah! What a great point, I completely missed that! I wanted to see if this generalized for anything, and it's almost everything, except when the two values have a common factor (eg. 12 divisible by 3 and 6, but not 3*6=18). So for a given number if it's divisible by x & y and they have no common factors, then they are also divisible by x*y, which in this case for x=2, y=3, x*y=6 it's true. Nice find!
For some reason I struggled with this one too, but still managed to solve it. Thanks again for the video, I come up here to compare my solutions with yours.
This is really helpful for understanding why you made the decisions you did in the original video. This answered some questions that I had when you were developing the solution for the problem. Keep up the great work!
I would suggest you to zoom in more cause I always have to zoom in on your videos. I like how you approach new problems and really like the process. I'm currently having difficulty on the problem strong password check. Can you go over that one in the future?
Thanks for the suggestion and kind words! Regarding zoom, thanks for asking and yes, I have a couple videos already recorded but after those I'll see about increasing the font size. For the question: Is this the one? leetcode.com/problems/strong-password-checker/description/ Looks fun, I'll try it out soon if so :)
Nicely done and well explained! My first thought would be to iterate (i) the nums and get a slice of itself plus the next k elements from nums. cast that to a set and check to ensure it has k elements. if not, return True. I believe this is O(N) space and time, but am not sure if python is doing anything extra expensive behind my calls here :) Psuedo Code: for i in range(len(nums)): if len(set(nums[i::i+k])) < k: return True
That's a clever approach! I like how compact it is. I think if I look at your pseudo code: for i in range(len(nums)): <-- O(N) time for N elements if len(set(nums[i::i+k])) < k: <-- O(K) time and space for building a set on K elements in nums[i:i+k] return True = Total O(NK) time, O(K) space. So we reduce space complexity by increasing time complexity through repeated work building a set N times. I think a potential disadvantage is in the worst case of K ~ N, then this would devolve to an O(N^2) time O(N) space solution.
@@samobot I plugged it into leetcode myself after a few adjustments to clean up the psuedo. It timed out on a large list of 60K elements where k=25000, so set casting a list seems to not be efficient whatsoever in python relative to other options. Well, fun to try it!
@@Specialk840 Hey good to hear you tested it, and yes that tracks, making a set from a list of K elements will be a linear O(K) operation (in any language), so that will be expensive when k is big (like the k=25,000 case it sounds like), hence worth looking for a solution that is constant time O(1) within the O(N) main loop, such as the dict with index approach
I did this one kind of easily, but the performance statistics showed that my solution outperformed only 17% out them of all. Lol :) Instead of a set I used a 2d-array to mark visited cells. And I think the faster approach here would be to modify the original grid.
Nice work and agreed! I later went and looked at this one and found keeping a separate visited set (or grid) really slowed the process down versus just updating the original grid (even with numpy arrays etc, which makes sense I think. Good idea with having a visited grid instead of a set/dict as that reduces the need to dynamically allocate memory, I may post an update video discussing this
Hehe you are correct, I don't always post videos in the same order I record them (pretty close though), so I still have a couple gdoc videos in the upload queue! I haven't decided yet if I'll fully switch to code editors or do some sort of balance with gdoc (or others). I'll make a post with a poll to see if there's a preference. I do like having the gdoc for organizing notes in videos over the code editor markdown at the moment, but I'm going to keep trying it!
