Side note: usually you don’t have 45 minutes to solve a problem, there’s introduction, explanation of how the interview goes, some little icebreaker, and then time left at the end for interviewee’s questions. All in all, you usually have only about 30-35 minutes to actually solve a problem.
@@absence9443 no you have no idea , most people like them that can solve question this fast is because they have high knowledge of how the code works and will be able to explain it without a problem
@@absence9443 people like him are the exception, company knows how good they are and will hire them because they have skills to solve hard problems in a short amount of time with high accuracy and saving time = saving money. he is one of world fastest problem solver, do you think big tech won't want him, then you a delusional.
As an actual hiring manager for a FAANG-like (AR +$40B) corporation, you would sail through. Why? Because it's more important to watch your initial approach and how you transition into solving and coding. In most interviews we would even stop you and move on once we see that you have the 'chops' to eventually arrive at something that would work. ie; you're on the right track. The big plus was your attitude when analyzing the question. No real judgment, no 'snippiness' about wording, etc.. I've had candidates actually say out loud "This question is stupid", "This isn't a fair question", "I can't work on this without music", etc.. Lastly, we like it when there is a compile (or even better, runtime) error. We get to see how you react and where your troubleshooting skills take you first. For claiming that you are without interview experience, you did fantastic, IMO.
"No real judgment, no 'snippiness' about wording, etc.. I've had candidates actually say out loud 'This question is stupid' " You could say he's here to solve problems, not look as if he's solving problems. What do people who want to solve problems do? Not care about how they're going to look solving the problem, that's waste of effort that could go into solving the problem.
hiring manager ... No real judgment, no 'snippiness' about wording, etc... did you actually give technical interviews before? The wordings are pretty bad often the people would give a right answer to a different question than the one stated.
@@nathanielme2622 That hasn't been my experience whatsoever. Let's see.. Mon I interviewed 2 people, Tue just 1, yesterday 3 and today 2. So I give roughly 8 technical interviews per week (no interviews are scheduled on Fri). Since there is no "right" answer to the questions we ask; or incorrect answers to questions we didn't ask, I'm not sure what you mean by 'pretty bad wording'. We're always looking for very adept developers that also have excellent communication skills however.
Programming is a small part of a job as a developer. You'll spend, especially as you grow in your career, vastly more time listening to others and communicating with them about the project, their design requirements, things you uncover as the project progresses, and the challenges you end up facing. The coding interview test is mainly, can you code reasonably well in a small contrived example. These are easily gamed by practicing a few core concepts that you're likely to encounter. As an interviewer I value being able to communicate what and how you're solving something far more than can you write the perfect solution. And you'll get huge bonus points if you understand the industry and the business goals driving the project.
This is true for almost any "white collar" job. Your ability to communicate and work with others is far, far more important for your long term career than technical skills. Also, sometimes teams will prefer to hire an amicable, communicative person over a slightly more technically proficient candidate.
@trey this is incredible wrong information you putting out. Of course companies will appreciate your personal sides and qualities. But it is essential what you bring to the table as a coder that they are looking. However what Trey Dempsey trying to say is. You can "educate" a person on the fields while working. For instance - if the company hires you and you have understandable business skills. Meaning. You can be available during meetings, you understand you need to be work coherently on tasks to solve them. And don't be afraid to ask questions when you get stuck. But they also provide you 3-4 months of education activities to learn to code in whatever language or programming skills that you might wanna boost. The difference is learning while working is that you often learn with others, developing social connections and being a socially active person instead of sitting all time alone at a computer. Learning together means you also learn for a purpose. Using said knowledge in a real project will help you to "keep" that knowledge much more. Meaning you work on yourself, as well can provide quality work to the company.
I wouldn't say it's a small part of the job. It's a big part of the job. But sometimes, depending upon the project, coding is the easiest part of the job, and the hardest part of the job is figuring out what should be coded in the first place. For example, most of the issues in our tracker start as something like "we want to add something so customers can track their orders". Or "Someone in Japan tried to add something to their cart and something went wrong". Okay, well, that's helpful.
chad Competitive programmer vs virgin leetcoders ! Nice video, it was cool to see you second guessing yourself on such relatively easy questions cuz you dont trust yourself, Happens to the best of us! Keep up with the awesome content lately!
Things you don't want to do in an interview from a style perspective: 1. calling class members "global variables"; 2. creating unnecessary public members; 3. copying heavy params around (they are passed by ref for a reason); 4. using C-style arrays in C++ (one std::array cries every time you do); 5. including and using namespace std (namespace pollution and slower compilation times); 6. vector (just don't); 7. VeryLongTypeName* = new VeryLongTypeName() (use auto instead); 8. Not using const wherever you can. Overall your coding style clearly shows that you are a competitive enthusiast with not much industry experience (at least not in C++). That is generally fine for internships and entry-level positions as long as you solve the problems, but would be considered a downside for anything beyond that (at least in some companies). Other thoughts: - In q1 I would consider using dsu (not as a primary solution, but as a potential follow-up). As a data structure, it's more adaptable, in case you want to switch it to semi- or fully-dynamic connectivity later. It also reduces code duplication on the project scale that you have for dfs (unless you use visitor pattern, which I assume you are not familiar with anyway). - In q2 it's debatable whether you should've gone for the merge sort. What if you want to keep the original lists too? What if you don't want to, but you don't own them and your coworker (who owns them) wants to? Why are we using raw pointers in 2022 anyway? I would not select a policy on "in-place vs not in-place" without explicitly talking it through with the interviewer. - In q3 for even x you get that 2n is divisible by x, so you can actually do better in O(divisors), but coding it from scratch is rather painful (unless you want to resort to sieve which kind of denies the point). - In q4 using vector for static set/map is actually a competitive meta for squeezing extra logs in where setters don't really want you to (n sqrt log or ICPC being common scenarios).
Oh yeah, I totally forgot to mention the style aspect - you are totally right that I used the "cp style" since I'm not familiar with industry C++, and that's another artifact of having a lot of cp experience but nothing else. Thanks for the feedback - it will almost certainly prove useful later down the line when I end up in a real interview scenario.
@@ColinGalen 😋 I recently found out that reading certain books helps a lot with style. Can recommend Mayers and Sutter, potentially Alezandrescu later. Some of them are pretty old but still relevant, especially since you may have missed some features that were introduced to the language when you weren't around (just like me).
@@yath3681 Reddit, quora, stack overflow, and codeforces all have posts on the matter. Please look it up, as I won't do a better job at explaining it than all these communities with decades of experience anyway.
I highly recommend submitting your solution 3x. The leetcode time and complexity results have been shown to give WILDLY variable results, so the most important part is just complexity which you nailed
if interviewers are relying on "runtime" then you might as well play captchas if you can get "fast code" on run time.... as far as I know.. .they only care about O-notation complexity since runtime is heavily hardware dependent. Programming any nest for loops on an Intel 4004 in this year is just trying to slay dragons with a butterknife
@King people put so much damn effort to make it into these tech companies, that the irony of if they just made a competing product, they'd accelerate their careers. The cult mindset really breaks people
@@hil449 This, I have no interest in rising to the highest ranks and income possible for a field. I just want a decently paid position that lets me not worry terribly about finances/health and gives me space for my life
You are goddamn right! I went from 401 ms all the way to 209ms on the third submission. Gonna continue spamming with a few improvements to better my ranking XD. Hackkerank has the same issue, I went from timeout to accepted after a couple of submissions of unaltered code. These sites need to provide a Spamming option, where the system runs the code a couple 100 times and get the best timings
This guy looks and sounds exactly like what i'd expect a "competitive programmer" to be. No idea why this was in my recommendations but it's all chinese to me and i envy you
I've got mad respect for people who are good at competitive programming, but it's definitely a different skill and not the same thing as being a good professional. It's possible to be both a good professional and fast competitive programmer, but most people pick one or the other to specialize in. I think the two hardest things to master are complex algorithms (including efficiency) and software architecture. That's not accounting for the low-level computer science and knowing arcane things like how to avoid L2 cache misses and optimize instructions. I focus a lot on architecture and design patterns for large, complex software and some of the low-level computer science, but I don't know tons of algorithms off the top of my head or implement them in seconds, haha. When a deep, algorithmic approach is necessary to solve a problem or there is one that applies to something I'm doing I can go read how it works and get it done ... but since that doesn't happen really frequently I've never become a fantastic student of algorithms and problems.
Same. I'm a graphics programmer so most of my time is spent implementing theory from research papers that I don't fully understand. I just know how to wrangle GPUs. Frustrates me that knowing how to sort an array 100 different ways is a prerequisite to getting into a big company.
@@connorsmiley2294 not always the case man, but sorting arrays of data could be important for GPU drivers, rendering APIs, etc where you don't _have_ any type of framework or runtime environment to program against and you're some writing Ring 0 or Ring 1 code that has to operate on raw memory. Think about a GPU needing sorted draw calls and batching -- you've got to handle that somewhere -- and you've also got to work out depth, culling and lots of other things where your only inputs are structs describing the length and format of the contents of physical memory. Of course it's stupid if a company asks someone to implement their own bubble sort and merge sort for a front-end web developer position lol, but in a lot of low-level programming scenarios you don't have the luxury of a rich, built-in framework, no standard libraries, no importing 3rd party libraries to help you out. Those kinds of jobs will definitely ask you some heavy computer science questions and stuff about algorithms and data structures, if it's relevant to the field and the role they're hiring for.
@@connorsmiley2294 I've worked on realtime 3D engines and I'm currently working at a company doing game development with Unity, which is a lot less painful most of the time. Unity is pretty sweet compared to rolling your own engine from scratch, haha, but game dev comes with whole new sets of high and low level problems to work out and things like fluid, high quality animations often feel just as difficult as trying to bend DirectX12 to your will 😄
@@GameDevNerd Yeah depends what you like. Unity is nice for indie and beginners, but for AAA Unity is a piece of junk that is kept alive by mislead investors. I come from AAA engine dev so I know the difficulties of game development very well :)
Truly amazing! I hope you do more of these and It would be nice if you could also post your thought process in this question and how you found the solution!
For the second problem, all numbers are between -10^4 and +10^4. Since the range is twice K, you can just map all the numbers to the range [0, 2x10^4] and do a Counting Sort in linear time and map them back before returning the result.
I'm so happy to see that even fast coders do not get their tasks, because for me looking at this was like "wtf, they just start ahead writing code when I'm still reading, they are probably geniuses", and now I can see that we're all just people
Dont know why this popped up in my feed, but it's the exact kind of questions I hate to see in interviews. I hated them as a candidate and I hate them as an interviewer these days. It tells me nothing about an engineer's ability other than they are good at puzzles. I could just as easily hand out a bunch of sudokus instead. If you've never done sudokus you'll struggle, and it might be impossible if I give you a harder one. But if you have sudoku experience, you'll breeze past them. Either way, I gain nothing of value regarding actual software engineering. The typical corporate justification here is something along the lines of "But it helps interviewers see how you approach unfamiliar problems". Bullshit. I'm not hiring you for how good you are at tackling the 1% of esoteric issues you'll encounter, I want to know how well you work 99% of the time, with the normal boring stuff. Code style, structure, readability and problem modelling are far more important that working out a solution. If I don't understand something, I ask for help, and as a team, people can always come up with the solution. But it's up to the individual engineer to actually write functional, understandable, robust code.
I am actually ok with when FAANG companies push leet code interviews to filter candidates eventhough I agree with you. I hate to see small to mid corporations following the sentiment though. Man all you need is CRUD, DevOPs and apply design for 99% of the cases and for the rest you will use a third party service nonetheless. Innovation versus application. You don't need a formula 1, or a rally driver. You need a bus / truck / taxi driver who is consistent, efficient and performant while being good in communication.
@@lunarcdr3083 The premise of the video was that a vet competitive coder would tackle interview-style questions, and thus it’s fair to ask for solution explanations given the fact that explaining your thought process is a majorly important part of answering interview-style questions.
The merge sort algorithm doesn't have the same time complexity as your solution. You are essentially using heap sort on the entire input which is \theta (n log n). The "merge sort" algorithm would actually make use of the fact that the lists are already sorted and maintain a priority queue of size at most k, so its time complexity would be \theta (n log k). Edited to add: I was talking about the Apple interview problem.
a min-heap priority queue solution would be O(nlogk). the difference between using a min-heap priority queue and a divide and conquer algorithm occurs in space where div-conque is constant space while heap based in O(k) space
@@hidude1354 I don't know which "a mean-heap priority queue solution" you mean here, but the solution implemented in the video - also using priority queue - is \theta (n log n).
@@golu3990 min-heap, no such thing as a mean-heap. I agree that his solution is nlogn, but i'm saying that if you properly use a min-heap priority queue it is nlog(k) since at most your priority queue will have k elements. I'm pointing out that the difference in the merge sort/divide and conquer solution to this is in space, not time
@@hidude1354> i'm saying that if you properly use a min-heap priority queue it is nlog(k) Oh, you are merely repeating what I had already stated in my first comment. >I'm pointing out that the difference in the merge sort/divide and conquer solution to this is in space, not time What divide and conquer solution are you talking about?
Just take the values from the Linked Lists and store them in an array. Then sort the array and make a new Linked List from that array and return that new lIst. This is an easy solution to the problem but probably not very efficient.
solving hard question under 15 mins. you would easily pass the coding interview in MAANG. Maybe the only one would give you problem is amazon cause they have Leadership Principle interview and it is a mixed bag
With the Amazon problem, the solution is also just equal to the number of odd factors of the number. So I was thinking just divide out by 2 as many times as you can, return 1 if you just have 1, or otherwise check for odd factors up to the square root, double it, and add 1 if the square root is also a factor (ie the number is square). I'm not a programmer but I do study Maths and that is what I came up with.
Yes, exactly. "Odd factors" must include 1 and the number itself with the way the question is defined here. @Michel An easy way to see it is to think about the possible lengths of the consecutive strings, and notice they are symmetrical. They are either of odd length, so the centre is a whole number and the sum will be an odd multiple of that, or they are of even length, so the centre is halfway between two numbers but every pair will add to its double, which is an odd number. eg1 4,5,6,7,8 is an odd string and the centre is 6. The symmetric pairs all add to 2x6 so the total is 5x6 eg2 4,5,6,7,8,9 is an even string and the centre is 6.5 The symmetric pairs all add to 13 so the total is 13x3 It then takes a bit of proof to show that each odd factor can be used to make a sum in exactly one of these two ways, and the other way will lead to the string containing non-positive numbers. (In fact, if we allowed non-positives numbers in our strings our result would be exactly twice as big.)
Great content! I think a fun next step would be having a calibrated FAANG interviewer to do a mock interview with you. The biggest difference between cp and interviews is not about optimality. To be honest, you can actually clear interviews without finding the most optimal solution for every problem. A bunch of things matter on a real interview, to mention a few: - You need to be able to fully explain your approach before writing any code. Some interviewers will stop you when you start writing code to think, but some will just write it down as a red flag. - You need to create proper variable names and think more about code readability. - You don't absolutely need, but it helps a lot to explain your code out loud as you write it (if you don't, it looks like you just memorized things like the dx and dy vector to check all directions). - There is no auto-testing, and you would have to run your code manually out loud (which takes time), and it would be much harder to find the bugs on Q1 Don't get me wrong, I'm not implying you can't do these things. It is just that if you don't, then an interview question is just an easy CP question, because often the interview questions will avoid any kind of novelty to avoid bombing people who couldn't get a "trick" or something like that. Looking forward to watch more videos from you evolving on this!
your first point is pretty major, it's hard to really do an interview question on your own because you need someone to fully explain your solution to and they will see if it makes sense before your fingers start typing any code
@@hidude1354 It is actually quite possible to do it in your own. I did it training for interviews and even if it is of course not as good as doing mock interviews the fact you need to say out loud what you are thinking forces you to organize your thoughts.
Two things attracted me to this video : 1st Relevance of topic , 2nd I thought there was a beautiful girl in video from thumbnail. I was like "Ek dum se jasbaat badal diye "
The sad thing is that programmers have to go through the meat grinder of corporate interviews. I hope you can get back to pure programming as soon as possible!
Do have a video explaining all your solutions in this video? Edit: Never mind, I saw the follow up to this video in your profile video list, and the video is entitled “Dissecting FAANG Interview Questions”. Thanks, Colin Galen! I only understood one of these problems, so I’m a newb, yet I’m somehow still a professional programmer. I guess I’m just not very good with algorithms. That’s why I’m watching videos like this :). Have you considered putting a course together and selling it? You could use it as a side hustle and probably take in some decent cash flow! I’d definitely be willing to be $300 bucks for a beginner to hard level Leet code video. I don’t the language you do it matters, but I’d stick to either JavaScript, JAVA, or Python since they are extremely popular. Alternatively, you could just offer an alternative solutions for the different languages and do it in your language of choice. It would be a ton of work either way, but potentially worth it!
Is Q1 a trick question? The specifications don't actually require the program to make a large island, merely to [optionally] make a single node change, and then return the size of the biggest island. The simplest solution would be to make no (or a random) change, and run a graph segmentation. Or is this question just REALLY badly written? E.g : "Example 1, Output: 1, Explanation: change one 1 to a zero, leaving exactly one island of size 1." This fulfills the requirements as written. If this is not what they actually want, who-ever wrote the question fails at writing good product specifications. Should the requirements be: "return the size of the largest island _possible_ in grid after applying this operation."?
Can someone explain to my simple mind the rationale of the Amazon solution, namely the logic according to which ans is incremented and why is it correct?
first observation: if there is a sequence of L consecutive numbers that adds up to N then it is also unique, i.e. no other consecutive sequence of length L will add up to N. This is an obvious observation. from the first observation, we can say that you only need to find all the different lengths (Ls) for which there is a possible sequence that adds up to N. so you can try from L = 1 to L = N, and if for some L we can say that there is a sequence that will add up to N then we increment our answer by 1. second observation: L doesn't need to go up to N. L only needs to go up to X such that (X * (X + 1))/2 12 ... so if (N-v) is a multiple of x then we can say there is some sequence of length x that adds up to N. There are other more clean solutions to this problem too.
@@iam_a_sad_khan for the last part, i think you also say for starting number x, sum of next k numbers to equal N is N= x + x +1 + x+2 ... x+k = x(k+1) + (k-1)k/2. If you plug in an x you get a quadratic and i guess you just have to check if the root is real and positive, which takes like 2 comparisons.
I don't get why people are writing about how being a comp programmer is very different from real software development. This video is about interview questions. I only watched the first question, but we learned how to do this in the first year of college. So I do not understand why people think that he is doing magic here or feel the need to distinguish this from their "real" programming. The first question is legit a dfs, which every programmer should be comfortable with
I had plenty of interview that asked me to grab a pencil and paper and write a code there and then complained that it would not compile because i forgot semicolon.
24:45: I don't understand how a mergesort solution is going to be better. The naive mergesort solution would just be to dump all the linked lists into an array and mergesort that, but that's O(n*log n) and still takes O(n), strictly worse than using a priority queue merge. The slightly better option is to append all the linked lists together and merge those together, which can be done in place, but is still O(n*log n), which is worse than the O(n*log k) solution. The only other idea I can think of that uses mergesort is to mergesort the heads of the k lists to find the smallest one, and repeat that n times, but that is O(nk*log k) and O(k) memory, so still strictly worse than the O(n*log k) solution.
I think your idea is correct but the complexities are wrong. First off if you have K lists each with N elements and just append and sort them the complexity would be O(nk*log(nk)) - ie sorting an array with size nk. The optimal solution is to use both merge sort (exploiting that the lists are sorted) and a min-heap (keeping only the heads of the lists and selecting the smallest one at each step). Then the heap contains at most K elements making the overall complexity O(nk*log(k)) which is better but really depends on your use case. If you have only 2 lists (k = 2, the classic merge sort) then it doesn't really matter either way. Hope this clears it out.
@@lickit77 n is the total number of elements in ALL lists. That is the standard definition of n in problems like this. The solution you have described is just the solution that the video implemented, a priority queue of k elements. This is O(n*log k) and takes O(k) memory. Also there is no mergesort in this solution, only a merge. Colin Galen claimed that there was a solution that was O(n*log k) and used O(1) memory that used mergesort, but I don't see it.
@@kered13 I see what you mean. Just read up how the implementation for merge sort works. It turns out you first split up the lists into 1-element lists (so a total of n lists with 1 element). Then you merge them in pairs - so at each step we merge only two lists at a time. Not sure how we compute the overall complexity but it should be O(n*logn) regardless of what k is. This makes sense because merge sort is indeed a sorting algorithm and it doesn't assume any ordering of the elements but in the problem statement you get sorted lists so we can do better with the other solution. So yes - merge sort will be worse in this problem.
Its a really great idea to start making some interview related content. The amount of people that are interested in cp are far less as compared to interview. I wish you success and fortune. Following you from a year, best cp utuber (after william lin ( he is insane ) xD).
q1 O(n^2 - area of all islands) is pos, you only need to find the perimeters of the islands to calculate the area, and then just find the best grid of a perimeter whose islands shared have the max sum area q2 u could just O(n > 10^4 ? n : 10^4) da shi by doing counting sort
You can do it in O(n) I believe. Iterate through and find islands like he did, and while you’re scanning if you find 0s that have at least 2 adjacent 1s save them to check later. After finding all islands, iterate through possible connectors and test the combined area. It’s the same solution as his (I think) but slight optimization on the test part because you don’t iterate over every element, just potential connections.
@@YeetYeetYe huh where is this m coming from? iterating through and finding all islands is n * n so O(n^2). the input is an n * n grid not a m * n rectangle
@@hidude1354 It's just convention really. O(m*n) is a tighter upper bound than O(n^2). You're not receiving "n" as an input length, so saying that the answer is upper bounded by quadratic time can be misleading, though it is technically correct.
But tbh it was easy for you) I guess competitive programmers best suit for coding interviews. It's harder for guys who can actually build stuff that works but during interview they are forced to solve isolated tasks about numbers using bare arrays that no one really uses in every day work)
You'd smash the interview process (coming from a new post-grad who's just secured a job). I'm not coming from a FAANG perspective, I work for a big-data company. Securing the bigger roles is 90% coding skill and 10% people skills. And you've got both.
Can you ask please your followers if they know a book or multiple books that are considered gold standard for learning all the logic necessary in type theory that is used in different papers on gradual types, dependent types? Thank you
you are talking about money here most people join big tech mostly for money and experience, When you join big tech the first thing you think of is not about solving hard problems lol. Is mostly communicating with the team
@@jpppptrade Couldn't agree more, I remember the first meaningful task: I wasted 2 weeks asking for interfaces and coded for 12 hours till 4:30 am before deadline.
The problems to solve in the work environment are very different from these. You work on things you are interested in and feel have an impact or else both you and the company got a bad deal.
This is the new standard to get into a dev position, unless of course you know people that can get you in. In that case you don't even need to know how to code.
Hello idk if a legend like yourself would answer to a noob like me but would any Backtracking Algorithm be a good choice in the first task with the Island and do you often use any known algorithm or data structure or you have zero knowledge but invent everything by yourself in seconds or you have the knowledge but it isn't always the best choice so you invent everything in seconds?
To answer just one of your questions: He doesn't invent a new solution every time, rather he has solved many Similar problems before and only needs to alter small details to make that previous solution work for this new problem. When a new bigger problem presents itself, you break it down into it's many parts, and for each of these parts you will either know a similar enough solution that you can tweak slightly or you will have to come up with something new. It's a mix of remembering what you solved before and creating new solutions. I have the tiniest bit of coding experience but this is how logical problems are solved in general.
"do you often use any known algorithm or data structure" he uses vector within like the first 6 minutes into the video, which is a very basic data structure. otherwise, @lovely replied with how he breaks down problems "or you have zero knowledge but invent everything by yourself in seconds" no "you have the knowledge but it isn't always the best choice so you invent everything in seconds" also no
@@mlgpro2241 well okay then but does he even know about Backtracking Algorithm or not? I mean it's a thing you could invent on the fly without knowing about it. I didn't mean such things like a vector, come on...
@@TrooperJetI mean we can assume that he's encountered problems where that is an optimal solution, so it probably makes sense that he's used it before. "do you often use any known algorithm or data structure" I only answered your question, so dispense with the "come on"
In my experience, phone screen questions are usually considerably easier than this, and on-sites are usually around leetcode medium level. Hards are pretty rare, and if you get one they'll usually give you the full 45 minutes for one question. This is for SRE but most software engineers I know have had similar experiences. You're getting harder questions than these in interviews??
@@travbrack Actually no. Phone screen is easier for sure, they are basically checking that you are not insane and can speak english relatively good. But a lot of companies, especially popular ones, send these even before phone screen, because that way you can process people at way bigger scale than phone interviews, which are limited by suitable times and so on. So they are kind of pre-pre-screening. And in actual interviews, at least for me, there were a lot of architectural level questions, I guess because they don't calculate fibonacci sequences on a daily basis.
@@rogerdinhelm4671 You must be more senior then, where they'd ask system design questions more than algorithmic. For juniors and even mid levels, they absolutely do ask Leetcode type questions in the interview, as well as in the pre-screen and in the phone screen.
@@zzzyyyxxx Leetcode in phone screen? That is insane, never happened to me. I am always asked about technologies, last projects and so on. But I do agree, that the less experience you have, the harder you are treated on an interview, paradoxically. I guess they know they have all the leverage on their side. And this is strange, I think for juniors in real production it is far more valueable to learn programming language quirks, rather than algorithms, that already implemented as libraries anyway. Hiring in software engineering is really f-d up, but it is what it is. Companies are trying to copy Google of Facebook, without even knowing why and what are they doing.
@@rogerdinhelm4671 I am almost never asked about past technologies or projects in an interview, with 3 years of experience. It’s always an algorithms question. After a weighted graph question sunk me in a phone screen I decided to just focus on algorithms studying over practical knowledge.
@Colin Galen, I want to be as good as you are, may I ask what you do in order to continue being top .1%? I have ~10 hrs a day to study what do you suggets I focus on in order to be come the best?
Cool video! One aspect of interviews that is greatly different from competitive programming is the fact you cannot test run your code. You need to "whiteboard" test your implementation and use clever test cases to spot the problems quickly. Of course knowing how to solve the question is like 80% of the work but communication, testing and overall organization is really important too and those can get you into no hire zone if ignored.
I find it strange that people have todo leetcode stuff and such in coding interviews. I even worked for Microsoft as a Field Engineer (comparable to an IT Consultant). I never had to do any of those leetcode thingys. I do them for fun here and then and one company (small one) asked me to give them example code and another one made me test work for a day. Apart from that, I guess they just fire you when you suck :p.
#3 I have no maths background so I would just iterate through all possible solutions, but hey at least I would stop when x (x being the start) is bigger than n/2 so it is at least optimised a little bit. Am I hired?
It is really amazing you can do this, but, without "communicating your solution" you are not really doing what you set out to do in this video.... you said it yourself interviewing requires you to explain your solutions and do it efficiently and all that.... You are just doing the same thing you would be doing for CP
The first problem can be implemented quite easily and super efficiently O(n^2 * log*(n)) using disjoint-set data structure. DFS will be slower, O(n^4) worst case.
For the 1st one (Making a Large Island) you would be better off with line scanning (since it's connected only in 4 directions) instead of recursive growth of the components from each point.
I believe it is possible to solve the final problem in O(N), if you keep a stack of strictly increasing (from top to bottom) elements for odd-numbered jumps, and the opposite for even-numbered jumps.
I like your thinking, but as you yourself know and said, not having much industry experience shows :) a few little comments of the things you're talking while writing the code are nice, though many of those might be redundant once you look at the code,... 5 years later someone might stumble over the code because of a problem and not having the original problem :) so some guidance into the "thinking" of the code is always helpful in any case for an entry level position in any language you're so massively overqualified, I wouldn't say no if you applied to our company and then sit in my classroom for me to teach you ABAP xD
omg i know for competetive programming is maybe helpful but all these 2 letter variable names are unreadable. Im an engineering manager and i would be criticising that very hard.
> linked lists question > most talked bout interview question for some reason > everyone has tried to do it when they're interviewing > this guy fucking destroys it at 98% faster than everyone else
generally one interview has 45 minutes of time .
bro solved questions of all MAANG companies in 45 minutes.
bro is a programming legend !!!!!!! orz
also he is using c++ also its his first time of solving
Side note: usually you don’t have 45 minutes to solve a problem, there’s introduction, explanation of how the interview goes, some little icebreaker, and then time left at the end for interviewee’s questions. All in all, you usually have only about 30-35 minutes to actually solve a problem.
you have no idea what the meaning behind the interviews is, it's not primarily about just writing a quick solution that works...
@@absence9443 no you have no idea , most people like them that can solve question this fast is because they have high knowledge of how the code works and will be able to explain it without a problem
@@absence9443 people like him are the exception, company knows how good they are and will hire them because they have skills to solve hard problems in a short amount of time with high accuracy and saving time = saving money. he is one of world fastest problem solver, do you think big tech won't want him, then you a delusional.
As an actual hiring manager for a FAANG-like (AR +$40B) corporation, you would sail through. Why? Because it's more important to watch your initial approach and how you transition into solving and coding. In most interviews we would even stop you and move on once we see that you have the 'chops' to eventually arrive at something that would work. ie; you're on the right track.
The big plus was your attitude when analyzing the question. No real judgment, no 'snippiness' about wording, etc.. I've had candidates actually say out loud "This question is stupid", "This isn't a fair question", "I can't work on this without music", etc.. Lastly, we like it when there is a compile (or even better, runtime) error. We get to see how you react and where your troubleshooting skills take you first. For claiming that you are without interview experience, you did fantastic, IMO.
"No real judgment, no 'snippiness' about wording, etc.. I've had candidates actually say out loud 'This question is stupid' "
You could say he's here to solve problems, not look as if he's solving problems.
What do people who want to solve problems do? Not care about how they're going to look solving the problem, that's waste of effort that could go into solving the problem.
must be netflix 🤡
hiring manager ... No real judgment, no 'snippiness' about wording, etc... did you actually give technical interviews before? The wordings are pretty bad often the people would give a right answer to a different question than the one stated.
@@nathanielme2622 That hasn't been my experience whatsoever. Let's see.. Mon I interviewed 2 people, Tue just 1, yesterday 3 and today 2. So I give roughly 8 technical interviews per week (no interviews are scheduled on Fri). Since there is no "right" answer to the questions we ask; or incorrect answers to questions we didn't ask, I'm not sure what you mean by 'pretty bad wording'. We're always looking for very adept developers that also have excellent communication skills however.
@@LM-ek2hb Man, you sound so full of yourself ngl.
Programming is a small part of a job as a developer. You'll spend, especially as you grow in your career, vastly more time listening to others and communicating with them about the project, their design requirements, things you uncover as the project progresses, and the challenges you end up facing. The coding interview test is mainly, can you code reasonably well in a small contrived example. These are easily gamed by practicing a few core concepts that you're likely to encounter. As an interviewer I value being able to communicate what and how you're solving something far more than can you write the perfect solution. And you'll get huge bonus points if you understand the industry and the business goals driving the project.
not true
@@piotr780 incorrect
This is true for almost any "white collar" job. Your ability to communicate and work with others is far, far more important for your long term career than technical skills. Also, sometimes teams will prefer to hire an amicable, communicative person over a slightly more technically proficient candidate.
@trey
this is incredible wrong information you putting out.
Of course companies will appreciate your personal sides and qualities. But it is essential what you bring to the table as a coder that they are looking. However what Trey Dempsey trying to say is. You can "educate" a person on the fields while working. For instance - if the company hires you and you have understandable business skills. Meaning. You can be available during meetings, you understand you need to be work coherently on tasks to solve them. And don't be afraid to ask questions when you get stuck.
But they also provide you 3-4 months of education activities to learn to code in whatever language or programming skills that you might wanna boost. The difference is learning while working is that you often learn with others, developing social connections and being a socially active person instead of sitting all time alone at a computer. Learning together means you also learn for a purpose. Using said knowledge in a real project will help you to "keep" that knowledge much more.
Meaning you work on yourself, as well can provide quality work to the company.
I wouldn't say it's a small part of the job. It's a big part of the job. But sometimes, depending upon the project, coding is the easiest part of the job, and the hardest part of the job is figuring out what should be coded in the first place.
For example, most of the issues in our tracker start as something like "we want to add something so customers can track their orders". Or "Someone in Japan tried to add something to their cart and something went wrong". Okay, well, that's helpful.
chad Competitive programmer vs virgin leetcoders ! Nice video, it was cool to see you second guessing yourself on such relatively easy questions cuz you dont trust yourself, Happens to the best of us! Keep up with the awesome content lately!
haha😆
I love this video. Btw, interviewers expect us to speak out our minds a lot during the interview. It gets really awkward if we think silently.
Things you don't want to do in an interview from a style perspective:
1. calling class members "global variables";
2. creating unnecessary public members;
3. copying heavy params around (they are passed by ref for a reason);
4. using C-style arrays in C++ (one std::array cries every time you do);
5. including and using namespace std (namespace pollution and slower compilation times);
6. vector (just don't);
7. VeryLongTypeName* = new VeryLongTypeName() (use auto instead);
8. Not using const wherever you can.
Overall your coding style clearly shows that you are a competitive enthusiast with not much industry experience (at least not in C++). That is generally fine for internships and entry-level positions as long as you solve the problems, but would be considered a downside for anything beyond that (at least in some companies).
Other thoughts:
- In q1 I would consider using dsu (not as a primary solution, but as a potential follow-up). As a data structure, it's more adaptable, in case you want to switch it to semi- or fully-dynamic connectivity later. It also reduces code duplication on the project scale that you have for dfs (unless you use visitor pattern, which I assume you are not familiar with anyway).
- In q2 it's debatable whether you should've gone for the merge sort. What if you want to keep the original lists too? What if you don't want to, but you don't own them and your coworker (who owns them) wants to? Why are we using raw pointers in 2022 anyway? I would not select a policy on "in-place vs not in-place" without explicitly talking it through with the interviewer.
- In q3 for even x you get that 2n is divisible by x, so you can actually do better in O(divisors), but coding it from scratch is rather painful (unless you want to resort to sieve which kind of denies the point).
- In q4 using vector for static set/map is actually a competitive meta for squeezing extra logs in where setters don't really want you to (n sqrt log or ICPC being common scenarios).
Very insightful
Oh yeah, I totally forgot to mention the style aspect - you are totally right that I used the "cp style" since I'm not familiar with industry C++, and that's another artifact of having a lot of cp experience but nothing else.
Thanks for the feedback - it will almost certainly prove useful later down the line when I end up in a real interview scenario.
What is wrong with vector ?
@@ColinGalen 😋 I recently found out that reading certain books helps a lot with style. Can recommend Mayers and Sutter, potentially Alezandrescu later. Some of them are pretty old but still relevant, especially since you may have missed some features that were introduced to the language when you weren't around (just like me).
@@yath3681 Reddit, quora, stack overflow, and codeforces all have posts on the matter. Please look it up, as I won't do a better job at explaining it than all these communities with decades of experience anyway.
I highly recommend submitting your solution 3x. The leetcode time and complexity results have been shown to give WILDLY variable results, so the most important part is just complexity which you nailed
if interviewers are relying on "runtime" then you might as well play captchas if you can get "fast code" on run time.... as far as I know.. .they only care about O-notation complexity since runtime is heavily hardware dependent.
Programming any nest for loops on an Intel 4004 in this year is just trying to slay dragons with a butterknife
@King people put so much damn effort to make it into these tech companies, that the irony of if they just made a competing product, they'd accelerate their careers.
The cult mindset really breaks people
@@cpK054L not everyone is fitted for running a business, specially early in the career
@@hil449 This, I have no interest in rising to the highest ranks and income possible for a field.
I just want a decently paid position that lets me not worry terribly about finances/health and gives me space for my life
You are goddamn right! I went from 401 ms all the way to 209ms on the third submission. Gonna continue spamming with a few improvements to better my ranking XD. Hackkerank has the same issue, I went from timeout to accepted after a couple of submissions of unaltered code. These sites need to provide a Spamming option, where the system runs the code a couple 100 times and get the best timings
please keep the leetcode hards incoming as much as you can. this helps a lot
This guy looks and sounds exactly like what i'd expect a "competitive programmer" to be. No idea why this was in my recommendations but it's all chinese to me and i envy you
in Asia they have tests in school almost every day. that's why solving questions is a thing for Asians and they are really good at it.
@@jpppptrade I think he's from the US so idk what China has to do with this...
I think it's because he said it's all Chinese
I've got mad respect for people who are good at competitive programming, but it's definitely a different skill and not the same thing as being a good professional. It's possible to be both a good professional and fast competitive programmer, but most people pick one or the other to specialize in. I think the two hardest things to master are complex algorithms (including efficiency) and software architecture. That's not accounting for the low-level computer science and knowing arcane things like how to avoid L2 cache misses and optimize instructions. I focus a lot on architecture and design patterns for large, complex software and some of the low-level computer science, but I don't know tons of algorithms off the top of my head or implement them in seconds, haha. When a deep, algorithmic approach is necessary to solve a problem or there is one that applies to something I'm doing I can go read how it works and get it done ... but since that doesn't happen really frequently I've never become a fantastic student of algorithms and problems.
@@aibutttickler @aaron carter thanks for the comment i enjoyed reading it
Same. I'm a graphics programmer so most of my time is spent implementing theory from research papers that I don't fully understand. I just know how to wrangle GPUs. Frustrates me that knowing how to sort an array 100 different ways is a prerequisite to getting into a big company.
@@connorsmiley2294 not always the case man, but sorting arrays of data could be important for GPU drivers, rendering APIs, etc where you don't _have_ any type of framework or runtime environment to program against and you're some writing Ring 0 or Ring 1 code that has to operate on raw memory. Think about a GPU needing sorted draw calls and batching -- you've got to handle that somewhere -- and you've also got to work out depth, culling and lots of other things where your only inputs are structs describing the length and format of the contents of physical memory. Of course it's stupid if a company asks someone to implement their own bubble sort and merge sort for a front-end web developer position lol, but in a lot of low-level programming scenarios you don't have the luxury of a rich, built-in framework, no standard libraries, no importing 3rd party libraries to help you out. Those kinds of jobs will definitely ask you some heavy computer science questions and stuff about algorithms and data structures, if it's relevant to the field and the role they're hiring for.
@@connorsmiley2294 I've worked on realtime 3D engines and I'm currently working at a company doing game development with Unity, which is a lot less painful most of the time. Unity is pretty sweet compared to rolling your own engine from scratch, haha, but game dev comes with whole new sets of high and low level problems to work out and things like fluid, high quality animations often feel just as difficult as trying to bend DirectX12 to your will 😄
@@GameDevNerd Yeah depends what you like. Unity is nice for indie and beginners, but for AAA Unity is a piece of junk that is kept alive by mislead investors. I come from AAA engine dev so I know the difficulties of game development very well :)
Thanks Colin! Amazing work!!!
Truly amazing! I hope you do more of these and It would be nice if you could also post your thought process in this question and how you found the solution!
Your hair is marvellous, oh my god…
I feel like Patrick Bateman staring at Paul Allen card
rofl
For the second problem, all numbers are between -10^4 and +10^4. Since the range is twice K, you can just map all the numbers to the range [0, 2x10^4] and do a Counting Sort in linear time and map them back before returning the result.
I'm so happy to see that even fast coders do not get their tasks, because for me looking at this was like "wtf, they just start ahead writing code when I'm still reading, they are probably geniuses", and now I can see that we're all just people
Dont know why this popped up in my feed, but it's the exact kind of questions I hate to see in interviews. I hated them as a candidate and I hate them as an interviewer these days.
It tells me nothing about an engineer's ability other than they are good at puzzles. I could just as easily hand out a bunch of sudokus instead. If you've never done sudokus you'll struggle, and it might be impossible if I give you a harder one. But if you have sudoku experience, you'll breeze past them. Either way, I gain nothing of value regarding actual software engineering.
The typical corporate justification here is something along the lines of "But it helps interviewers see how you approach unfamiliar problems". Bullshit. I'm not hiring you for how good you are at tackling the 1% of esoteric issues you'll encounter, I want to know how well you work 99% of the time, with the normal boring stuff.
Code style, structure, readability and problem modelling are far more important that working out a solution. If I don't understand something, I ask for help, and as a team, people can always come up with the solution. But it's up to the individual engineer to actually write functional, understandable, robust code.
I am actually ok with when FAANG companies push leet code interviews to filter candidates eventhough I agree with you. I hate to see small to mid corporations following the sentiment though. Man all you need is CRUD, DevOPs and apply design for 99% of the cases and for the rest you will use a third party service nonetheless. Innovation versus application. You don't need a formula 1, or a rally driver. You need a bus / truck / taxi driver who is consistent, efficient and performant while being good in communication.
Would love to see more indepth explainations for the solutions.
Didn't he already said he wasn't gonna do that? Why don't you experiment with it yourself, even better.
@@henrikholmstrom7722 No need to be rude about it.
@@lunarcdr3083 The premise of the video was that a vet competitive coder would tackle interview-style questions, and thus it’s fair to ask for solution explanations given the fact that explaining your thought process is a majorly important part of answering interview-style questions.
For the facebook one: I worked on a very similar problem to this when i was in school and I think you still got it faster than I ever would have
So... This is the guy my gf told me not to worry about... You're damn good bro
This guy is the gf 🥵❤️
The merge sort algorithm doesn't have the same time complexity as your solution. You are essentially using heap sort on the entire input which is \theta (n log n). The "merge sort" algorithm would actually make use of the fact that the lists are already sorted and maintain a priority queue of size at most k, so its time complexity would be \theta (n log k).
Edited to add: I was talking about the Apple interview problem.
a min-heap priority queue solution would be O(nlogk). the difference between using a min-heap priority queue and a divide and conquer algorithm occurs in space where div-conque is constant space while heap based in O(k) space
@@hidude1354 I don't know which "a mean-heap priority queue solution" you mean here, but the solution implemented in the video - also using priority queue - is \theta (n log n).
@@golu3990 min-heap, no such thing as a mean-heap. I agree that his solution is nlogn, but i'm saying that if you properly use a min-heap priority queue it is nlog(k) since at most your priority queue will have k elements. I'm pointing out that the difference in the merge sort/divide and conquer solution to this is in space, not time
@@hidude1354> i'm saying that if you properly use a min-heap priority queue it is nlog(k)
Oh, you are merely repeating what I had already stated in my first comment.
>I'm pointing out that the difference in the merge sort/divide and conquer solution to this is in space, not time
What divide and conquer solution are you talking about?
Just take the values from the Linked Lists and store them in an array. Then sort the array and make a new Linked List from that array and return that new lIst.
This is an easy solution to the problem but probably not very efficient.
solving hard question under 15 mins. you would easily pass the coding interview in MAANG. Maybe the only one would give you problem is amazon cause they have Leadership Principle interview and it is a mixed bag
Where is the simulation where stakeholders ask how to connect excel to Kafka?
With the Amazon problem, the solution is also just equal to the number of odd factors of the number. So I was thinking just divide out by 2 as many times as you can, return 1 if you just have 1, or otherwise check for odd factors up to the square root, double it, and add 1 if the square root is also a factor (ie the number is square). I'm not a programmer but I do study Maths and that is what I came up with.
Why is it equal to the number of odd factors?
This seems to contradict the examples given. How would you get 4 from 15 like this?
@@GenesisAkaG 1, 3, 5, 15 are the odd factors of 15.....
Yes, exactly. "Odd factors" must include 1 and the number itself with the way the question is defined here.
@Michel An easy way to see it is to think about the possible lengths of the consecutive strings, and notice they are symmetrical. They are either of odd length, so the centre is a whole number and the sum will be an odd multiple of that, or they are of even length, so the centre is halfway between two numbers but every pair will add to its double, which is an odd number.
eg1 4,5,6,7,8 is an odd string and the centre is 6. The symmetric pairs all add to 2x6 so the total is 5x6
eg2 4,5,6,7,8,9 is an even string and the centre is 6.5 The symmetric pairs all add to 13 so the total is 13x3
It then takes a bit of proof to show that each odd factor can be used to make a sum in exactly one of these two ways, and the other way will lead to the string containing non-positive numbers.
(In fact, if we allowed non-positives numbers in our strings our result would be exactly twice as big.)
Lol i've thought the same but i'm not a math guy or anything
Hey man! You are so cool, and the video is dope. BTW I like your hairstyle LOL
Awesome video man! I hope it goes more viral for you! It was very interesting and educational.
This motivates me to code more you are awesome brother 💯❤
Wait, that algo expert guy will call you for collaboration.
Please bring back your topic streams dude. btw nice idea
Great content! I think a fun next step would be having a calibrated FAANG interviewer to do a mock interview with you. The biggest difference between cp and interviews is not about optimality. To be honest, you can actually clear interviews without finding the most optimal solution for every problem. A bunch of things matter on a real interview, to mention a few:
- You need to be able to fully explain your approach before writing any code. Some interviewers will stop you when you start writing code to think, but some will just write it down as a red flag.
- You need to create proper variable names and think more about code readability.
- You don't absolutely need, but it helps a lot to explain your code out loud as you write it (if you don't, it looks like you just memorized things like the dx and dy vector to check all directions).
- There is no auto-testing, and you would have to run your code manually out loud (which takes time), and it would be much harder to find the bugs on Q1
Don't get me wrong, I'm not implying you can't do these things. It is just that if you don't, then an interview question is just an easy CP question, because often the interview questions will avoid any kind of novelty to avoid bombing people who couldn't get a "trick" or something like that. Looking forward to watch more videos from you evolving on this!
your first point is pretty major, it's hard to really do an interview question on your own because you need someone to fully explain your solution to and they will see if it makes sense before your fingers start typing any code
@@hidude1354 It is actually quite possible to do it in your own. I did it training for interviews and even if it is of course not as good as doing mock interviews the fact you need to say out loud what you are thinking forces you to organize your thoughts.
If NileRed were a programmer
looking for this comment
He really is his doppelgänger lmfao
Two things attracted me to this video : 1st Relevance of topic , 2nd I thought there was a beautiful girl in video from thumbnail. I was like "Ek dum se jasbaat badal diye "
strongest competitive programmer
isn't monotonic stack better for the last question, since we can get the overall complexity down to O(n)
The sad thing is that programmers have to go through the meat grinder of corporate interviews. I hope you can get back to pure programming as soon as possible!
"UGH, why is this Java?" *switches to c++*
what a hero
Naur an edraith ammen! Naur dan i ngaurhoth!
Do have a video explaining all your solutions in this video?
Edit: Never mind, I saw the follow up to this video in your profile video list, and the video is entitled “Dissecting FAANG Interview Questions”.
Thanks, Colin Galen!
I only understood one of these problems, so I’m a newb, yet I’m somehow still a professional programmer. I guess I’m just not very good with algorithms. That’s why I’m watching videos like this :).
Have you considered putting a course together and selling it? You could use it as a side hustle and probably take in some decent cash flow! I’d definitely be willing to be $300 bucks for a beginner to hard level Leet code video. I don’t the language you do it matters, but I’d stick to either JavaScript, JAVA, or Python since they are extremely popular. Alternatively, you could just offer an alternative solutions for the different languages and do it in your language of choice. It would be a ton of work either way, but potentially worth it!
Is Q1 a trick question? The specifications don't actually require the program to make a large island, merely to [optionally] make a single node change, and then return the size of the biggest island. The simplest solution would be to make no (or a random) change, and run a graph segmentation. Or is this question just REALLY badly written? E.g : "Example 1, Output: 1, Explanation: change one 1 to a zero, leaving exactly one island of size 1." This fulfills the requirements as written. If this is not what they actually want, who-ever wrote the question fails at writing good product specifications.
Should the requirements be: "return the size of the largest island _possible_ in grid after applying this operation."?
I was also confused by this question.
"You are allowed to changed at most one 0 to be 1" means you cannot change a 1 to a 0.
@@Hellhound_RedFox True. Example still works if you make no changes though.
Can someone explain to my simple mind the rationale of the Amazon solution, namely the logic according to which ans is incremented and why is it correct?
first observation: if there is a sequence of L consecutive numbers that adds up to N then it is also unique, i.e. no other consecutive sequence of length L will add up to N. This is an obvious observation.
from the first observation, we can say that you only need to find all the different lengths (Ls) for which there is a possible sequence that adds up to N.
so you can try from L = 1 to L = N, and if for some L we can say that there is a sequence that will add up to N then we increment our answer by 1.
second observation: L doesn't need to go up to N. L only needs to go up to X such that (X * (X + 1))/2 12 ...
so if (N-v) is a multiple of x then we can say there is some sequence of length x that adds up to N.
There are other more clean solutions to this problem too.
@@iam_a_sad_khan for the last part, i think you also say for starting number x, sum of next k numbers to equal N is N= x + x +1 + x+2 ... x+k = x(k+1) + (k-1)k/2. If you plug in an x you get a quadratic and i guess you just have to check if the root is real and positive, which takes like 2 comparisons.
I think you also want to talk about the thought process.
Those competitive programming sites kind of act like test prep for interviews. So that part is helpful..
Codewizard but uses a microwave as a webcam.
I don't get why people are writing about how being a comp programmer is very different from real software development.
This video is about interview questions. I only watched the first question, but we learned how to do this in the first year of college. So I do not understand why people think that he is doing magic here or feel the need to distinguish this from their "real" programming.
The first question is legit a dfs, which every programmer should be comfortable with
Impressive , very satisfying to watch.
I had plenty of interview that asked me to grab a pencil and paper and write a code there and then complained that it would not compile because i forgot semicolon.
The constant ctrl-s is so relatable...
Nice hair type brotherman
24:45: I don't understand how a mergesort solution is going to be better. The naive mergesort solution would just be to dump all the linked lists into an array and mergesort that, but that's O(n*log n) and still takes O(n), strictly worse than using a priority queue merge. The slightly better option is to append all the linked lists together and merge those together, which can be done in place, but is still O(n*log n), which is worse than the O(n*log k) solution. The only other idea I can think of that uses mergesort is to mergesort the heads of the k lists to find the smallest one, and repeat that n times, but that is O(nk*log k) and O(k) memory, so still strictly worse than the O(n*log k) solution.
I think your idea is correct but the complexities are wrong. First off if you have K lists each with N elements and just append and sort them the complexity would be O(nk*log(nk)) - ie sorting an array with size nk. The optimal solution is to use both merge sort (exploiting that the lists are sorted) and a min-heap (keeping only the heads of the lists and selecting the smallest one at each step). Then the heap contains at most K elements making the overall complexity O(nk*log(k)) which is better but really depends on your use case. If you have only 2 lists (k = 2, the classic merge sort) then it doesn't really matter either way. Hope this clears it out.
@@lickit77 n is the total number of elements in ALL lists. That is the standard definition of n in problems like this. The solution you have described is just the solution that the video implemented, a priority queue of k elements. This is O(n*log k) and takes O(k) memory. Also there is no mergesort in this solution, only a merge. Colin Galen claimed that there was a solution that was O(n*log k) and used O(1) memory that used mergesort, but I don't see it.
@@kered13 I see what you mean. Just read up how the implementation for merge sort works. It turns out you first split up the lists into 1-element lists (so a total of n lists with 1 element). Then you merge them in pairs - so at each step we merge only two lists at a time. Not sure how we compute the overall complexity but it should be O(n*logn) regardless of what k is. This makes sense because merge sort is indeed a sorting algorithm and it doesn't assume any ordering of the elements but in the problem statement you get sorted lists so we can do better with the other solution. So yes - merge sort will be worse in this problem.
Its a really great idea to start making some interview related content. The amount of people that are interested in cp are far less as compared to interview. I wish you success and fortune. Following you from a year, best cp utuber (after william lin ( he is insane ) xD).
compp is much more fun, tho.
@@salsichalivre5401 why
q1 O(n^2 - area of all islands) is pos, you only need to find the perimeters of the islands to calculate the area, and then just find the best grid of a perimeter whose islands shared have the max sum area
q2 u could just O(n > 10^4 ? n : 10^4) da shi by doing counting sort
You can do it in O(n) I believe. Iterate through and find islands like he did, and while you’re scanning if you find 0s that have at least 2 adjacent 1s save them to check later. After finding all islands, iterate through possible connectors and test the combined area. It’s the same solution as his (I think) but slight optimization on the test part because you don’t iterate over every element, just potential connections.
@@awillingham you realize finding all the islands is O(n^2) since the array is n x n
@@kooltyme It's O(n*m), not O(n^2)
@@YeetYeetYe huh where is this m coming from? iterating through and finding all islands is n * n so O(n^2). the input is an n * n grid not a m * n rectangle
@@hidude1354 It's just convention really. O(m*n) is a tighter upper bound than O(n^2). You're not receiving "n" as an input length, so saying that the answer is upper bounded by quadratic time can be misleading, though it is technically correct.
this is great... want to do things like you... good video, keep it up!
But tbh it was easy for you) I guess competitive programmers best suit for coding interviews. It's harder for guys who can actually build stuff that works but during interview they are forced to solve isolated tasks about numbers using bare arrays that no one really uses in every day work)
You'd smash the interview process (coming from a new post-grad who's just secured a job).
I'm not coming from a FAANG perspective, I work for a big-data company. Securing the bigger roles is 90% coding skill and 10% people skills. And you've got both.
Awesome video, Colin! (YOOO FIRST COMMENT?!?!)
All of that in 3 years? ZAMN!
Please make topic streams for med-hard graph and dp problems
Can you ask please your followers if they know a book or multiple books that are considered gold standard for learning all the logic necessary in type theory that is used in different papers on gradual types, dependent types?
Thank you
Bruh
@@warriordx5520 Yes Bruh...what's the problem?
@@encapsulatio Ask reddit? Bruh
@@warriordx5520 Don't be rude ...bruh. No one asked you to speak on the Colin's behalf. Offer an answer relevant to the question or STFU.
Cormen is a classic
You didn't call delete on the ListNode* that you created on the second test. You did amazing though.
Should make more of these lol. The views seem to be popping too.
Good stuff. Thanks for making this.
your hair is so so pretty
Do you think you'd be happy working in a coding environment like that? Do you think the problems you'd be solving would be worthwhile?
you are talking about money here most people join big tech mostly for money and experience, When you join big tech the first thing you think of is not about solving hard problems lol. Is mostly communicating with the team
man, labor for living is as important or more so as labor for happiness
@@jpppptrade Couldn't agree more, I remember the first meaningful task: I wasted 2 weeks asking for interfaces and coded for 12 hours till 4:30 am before deadline.
@@jpppptrade well I am assuming the pay is fantastic and mainly am talking about happiness and personal satisfaction.
The problems to solve in the work environment are very different from these. You work on things you are interested in and feel have an impact or else both you and the company got a bad deal.
This is the new standard to get into a dev position, unless of course you know people that can get you in. In that case you don't even need to know how to code.
Great programming skills combined with insufficient interviewing and work politics skills leads to severe underemployment.
Do workthroughs of the Jane Street Monthly Puzzles!
Hello idk if a legend like yourself would answer to a noob like me but would any Backtracking Algorithm be a good choice in the first task with the Island and do you often use any known algorithm or data structure or you have zero knowledge but invent everything by yourself in seconds or you have the knowledge but it isn't always the best choice so you invent everything in seconds?
To answer just one of your questions: He doesn't invent a new solution every time, rather he has solved many Similar problems before and only needs to alter small details to make that previous solution work for this new problem. When a new bigger problem presents itself, you break it down into it's many parts, and for each of these parts you will either know a similar enough solution that you can tweak slightly or you will have to come up with something new. It's a mix of remembering what you solved before and creating new solutions.
I have the tiniest bit of coding experience but this is how logical problems are solved in general.
"do you often use any known algorithm or data structure"
he uses vector within like the first 6 minutes into the video, which is a very basic data structure. otherwise, @lovely replied with how he breaks down problems
"or you have zero knowledge but invent everything by yourself in seconds"
no
"you have the knowledge but it isn't always the best choice so you invent everything in seconds"
also no
@@mlgpro2241 well okay then but does he even know about Backtracking Algorithm or not? I mean it's a thing you could invent on the fly without knowing about it. I didn't mean such things like a vector, come on...
@@TrooperJetI mean we can assume that he's encountered problems where that is an optimal solution, so it probably makes sense that he's used it before.
"do you often use any known algorithm or data structure"
I only answered your question, so dispense with the "come on"
Average coding tutorial enjoyer vs Chad competitive coder
You're the real coding beauty!
These are basically automated pre-screening tasks for large companies, they are usually not considered an interview and have little resemblence of it.
In my experience, phone screen questions are usually considerably easier than this, and on-sites are usually around leetcode medium level. Hards are pretty rare, and if you get one they'll usually give you the full 45 minutes for one question. This is for SRE but most software engineers I know have had similar experiences.
You're getting harder questions than these in interviews??
@@travbrack Actually no. Phone screen is easier for sure, they are basically checking that you are not insane and can speak english relatively good.
But a lot of companies, especially popular ones, send these even before phone screen, because that way you can process people at way bigger scale than phone interviews, which are limited by suitable times and so on. So they are kind of pre-pre-screening.
And in actual interviews, at least for me, there were a lot of architectural level questions, I guess because they don't calculate fibonacci sequences on a daily basis.
@@rogerdinhelm4671 You must be more senior then, where they'd ask system design questions more than algorithmic. For juniors and even mid levels, they absolutely do ask Leetcode type questions in the interview, as well as in the pre-screen and in the phone screen.
@@zzzyyyxxx Leetcode in phone screen? That is insane, never happened to me. I am always asked about technologies, last projects and so on.
But I do agree, that the less experience you have, the harder you are treated on an interview, paradoxically. I guess they know they have all the leverage on their side.
And this is strange, I think for juniors in real production it is far more valueable to learn programming language quirks, rather than algorithms, that already implemented as libraries anyway. Hiring in software engineering is really f-d up, but it is what it is. Companies are trying to copy Google of Facebook, without even knowing why and what are they doing.
@@rogerdinhelm4671 I am almost never asked about past technologies or projects in an interview, with 3 years of experience. It’s always an algorithms question. After a weighted graph question sunk me in a phone screen I decided to just focus on algorithms studying over practical knowledge.
@Colin Galen, I want to be as good as you are, may I ask what you do in order to continue being top .1%? I have ~10 hrs a day to study what do you suggets I focus on in order to be come the best?
I just played the video to check whether this fellow is a boy or a girl.
LOL
Cool video! One aspect of interviews that is greatly different from competitive programming is the fact you cannot test run your code. You need to "whiteboard" test your implementation and use clever test cases to spot the problems quickly. Of course knowing how to solve the question is like 80% of the work but communication, testing and overall organization is really important too and those can get you into no hire zone if ignored.
What were ur roadmap to become so good ?
Can u do a video of this ?
Thankyou for helping front and header
Clicked on this video because I couldn’t tell if you were a man or a woman
I find it strange that people have todo leetcode stuff and such in coding interviews. I even worked for Microsoft as a Field Engineer (comparable to an IT Consultant). I never had to do any of those leetcode thingys. I do them for fun here and then and one company (small one) asked me to give them example code and another one made me test work for a day. Apart from that, I guess they just fire you when you suck :p.
Good for coding interviews
Love your vids man
#3 I have no maths background so I would just iterate through all possible solutions, but hey at least I would stop when x (x being the start) is bigger than n/2 so it is at least optimised a little bit. Am I hired?
I have no idea what I'm watching
is writing low-level code that that mutates anything and everything - and notusing the STL - mandatory for these things?
It is really amazing you can do this, but, without "communicating your solution" you are not really doing what you set out to do in this video.... you said it yourself interviewing requires you to explain your solutions and do it efficiently and all that.... You are just doing the same thing you would be doing for CP
The first problem can be implemented quite easily and super efficiently O(n^2 * log*(n)) using disjoint-set data structure. DFS will be slower, O(n^4) worst case.
He didn't just do the naive DFS solution... his solution visits each cell exactly once, hence O(N^2) complexity which is the optimal one.
@@ProgramadorSagaz yes. I see now. Pretty good too. But I think disjoint set aka union-find is also nice solution.
@@movax20h That's what I thought of at first as well, and to be fair log*(n) is pretty damn close to constant, so it's not really much worse.
For the 1st one (Making a Large Island) you would be better off with line scanning (since it's connected only in 4 directions) instead of recursive growth of the components from each point.
thank god i own my own software company. going back to corp america would be detrimental to my mental health.
Are those who ace the faang interviews considered vampire slayers? It’s morbin time?
can u make a sheet where a beginner should start coding for competitive programming
This exists already. It’s called t he junior training sheet.
@@patmcn9854 where?
@@patmcn9854 Could you please share the link
Adding comment for notification
@@patmcn9854 where ?
I believe it is possible to solve the final problem in O(N), if you keep a stack of strictly increasing (from top to bottom) elements for odd-numbered jumps, and the opposite for even-numbered jumps.
Great insight!
Woah, I didn't know BrutalMoose had another channel
Great job. Maybe next time spend five minutes explaining the solutions, since that’s a critical part of an interview.
I’m sure you can do it.
Apple: concatenate all the lists in one and sort?
Man, please make a detailed video on Dynamic programming questions from code forces rated between 1000 - 1500
You don't get much of those in this rating range.
Try 1600-1700
@@cross4326 Are you sure?.
I like your thinking, but as you yourself know and said, not having much industry experience shows :)
a few little comments of the things you're talking while writing the code are nice, though many of those might be redundant once you look at the code,... 5 years later someone might stumble over the code because of a problem and not having the original problem :) so some guidance into the "thinking" of the code is always helpful
in any case for an entry level position in any language you're so massively overqualified, I wouldn't say no if you applied to our company and then sit in my classroom for me to teach you ABAP xD
omg i know for competetive programming is maybe helpful but all these 2 letter variable names are unreadable. Im an engineering manager and i would be criticising that very hard.
So on the real interview there would be a guy asking you a stupid questions and forcing you to explain what are you doing after each line of code
5:30 "Shouldn't be java" 😂
Please Can you make a video on how to get interest in coding
In my little experience of few months in CP I never heard of Linked lists.
do u have cs degree? seems you dont
@@salsichalivre5401 ofc I know linked lists but didn't encounter them in any coding contests till now
@@aravind2624 Why man
@@aravind2624 cp does not have linked list questions.
I need to step my math game up...
> linked lists question
> most talked bout interview question for some reason
> everyone has tried to do it when they're interviewing
> this guy fucking destroys it at 98% faster than everyone else