Top Competitive Programmer vs. FAANG Interview Questions
Vložit
- čas přidán 24. 07. 2024
- A top competitive programmer from the Codeforces/CodeChef realm (with zero prior interview experience) takes a look at some FAANG interview questions to answer: is competitive programming alone enough to crack the coding interview? Or are they fundamentally different games? Find out in this video experiment.
Questions:
Facebook/Meta: leetcode.com/problems/making-...
Apple: leetcode.com/problems/merge-k...
Amazon: leetcode.com/problems/consecu...
Google: leetcode.com/problems/odd-eve...
Support me with money: www.buymeacoffee.com/galencolin
Music: Local Forecast - Slower by Kevin MacLeod
Link: incompetech.filmmusic.io/song...
License: [yt dislikes this link, removed]
(yes, I was lazy and only used a single track for the whole video)
Timestamps:
00:00 Intro
01:02 Format
01:58 Facebook/Meta
15:10 Facebook/Meta - Recap
16:08 Apple
24:16 Apple - Recap
25:39 Amazon
31:22 Amazon - Recap
31:49 Google
42:07 Google - Recap
43:19 Conclusion - Věda a technologie
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.
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!
please keep the leetcode hards incoming as much as you can. this helps a lot
Thanks Colin! Amazing work!!!
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.
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😆
Awesome video man! I hope it goes more viral for you! It was very interesting and educational.
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.
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.
This motivates me to code more you are awesome brother 💯❤
isn't monotonic stack better for the last question, since we can get the overall complexity down to O(n)
Please bring back your topic streams dude. btw nice idea
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
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 it takes him 15 minutes for one of these problems what hope is there for me...
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
@@cpK054L ive made entire frameworks. Got a leetcode hard in an interview and got destroyed.
I guess I'm going to spend two weeks prepping but this is super lame and I dont really think this will make me a better coder but we shall see.
@@king6530 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
@@cpK054LI mean it's the top 1% of jobs, i've made many things and have recently built an AI training method that surpasses multiple benchmarks on paperswithcode yet am incapable of doing these silly puzzles.
Yeah I want to work on my stuff instead. I don't know i think it will take me two weeks aof hardcore practice on leetcode whereas my project will likely take 6 months.
Good stuff. Thanks for making this.
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.
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.
Hey man! You are so cool, and the video is dope. BTW I like your hairstyle LOL
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
Please make topic streams for med-hard graph and dp problems
Where is the simulation where stakeholders ask how to connect excel to Kafka?
is writing low-level code that that mutates anything and everything - and notusing the STL - mandatory for these things?
#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?
Impressive , very satisfying to watch.
Love your vids man
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.
Your hair is marvellous, oh my god…
I feel like Patrick Bateman staring at Paul Allen card
rofl
@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?
Hey, does anyone know what is the keyboard in this video?
this is great... want to do things like you... good video, keep it up!
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.
Should make more of these lol. The views seem to be popping too.
Awesome video, Colin! (YOOO FIRST COMMENT?!?!)
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.
@@jptraderr 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
Are those who ace the faang interviews considered vampire slayers? It’s morbin time?
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!
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
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.
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.
Wait, that algo expert guy will call you for collaboration.
What were ur roadmap to become so good ?
Can u do a video of this ?
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 :)
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"
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.
You didn't call delete on the ListNode* that you created on the second test. You did amazing though.
Is it possible to learn this power?
Those competitive programming sites kind of act like test prep for interviews. So that part is helpful..
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
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.
I think you also want to talk about the thought process.
Great insight!
Please Can you make a video on how to get interest in coding
Apple: concatenate all the lists in one and sort?
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
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.
If NileRed were a programmer
looking for this comment
He really is his doppelgänger lmfao
How to get so good at programming?
Thankyou for helping front and header
How long before AI will answer these questions in a few seconds if not milliseconds?
AI already can. That said, AI can't think.
Codewizard but uses a microwave as a webcam.
Make video on how to learn minimum maths to be good at dsa?
The constant ctrl-s is so relatable...
Can someone summarize the video its took long
Thank you : )
So the stripey socks do work
Do workthroughs of the Jane Street Monthly Puzzles!
This is really helpful
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 ?
That's great but it's not really how interviews work. As someone that's been working for 13 years I've been on both sides a hundred times. In my opinion the two things that matter the most are 1. the approach to the problem and the thought process (perspective) and 2. being a good fit with the team (soft skills). If either one is missing you are out. Hope this helps, cheers.
Nice hair type brotherman
All of that in 3 years? ZAMN!
is it just me or was the apple problem too easy?
Is Netflix really a big, sought after tech company? Or is it just tossed in there to make the acronym more palatable?
What are these loops? It looks like a maschine was coding that loop! Crazy this dude is crazy. Thing I would want to know can he program all the solutions in other languages? Like Java, Kotlin, Python, Typescript`?
There is only one programming language, and He used it.
He just used c++
Woah, I didn't know BrutalMoose had another channel
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
How old are you, and at what age did you start coding?
bit late but hes i think 20 or 19 now and he started in 9. grade
So... This is the guy my gf told me not to worry about... You're damn good bro
This guy is the gf 🥵❤️
Absolute Chad programmer!!
You're the real coding beauty!
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.
very informative
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
Good for coding interviews
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.
"UGH, why is this Java?" *switches to c++*
what a hero
your hair is so so pretty
Thank you
I need to step my math game up...
i get stuck on complicated stuff... bruh.
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!
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.
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
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 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.
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
@@jptraderr 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.
@@jptraderr 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.
Naur an edraith ammen! Naur dan i ngaurhoth!
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?.
You look like one of the Elves in LOR. That is all, I'll show myself out.
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
What is this?