Cycle Sort - Amazon, Google, Microsoft Interview Questions
VloĆŸit
- Äas pĆidĂĄn 3. 07. 2024
- One of the most important video for Amazon, Google and Microsoft interviews where we cover the cyclic sort algorithm and solve LeetCode easy till hard interview problems in the most easy to understand manner.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
đ Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Complete Java DSA playlist: âą Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
âĄïž Connect with me: kunalkushwaha.com
=========================================
Timestamps:
00:00:00 Teaser
00:00:08 Introduction
00:01:10 Cyclic Sort
00:04:26 Algorithm for Cyclic Sort
00:10:09 Worst Case
00:14:36 Code for Cyclic Sort
00:21:06 Q1 : Missing Number
00:37:56 Q2 : Find All Numbers Disappeared in an Array
00:51:30 Q3 : Find the Duplicate Number
01:04:15 Q4 : Find All Duplicates in an Array
01:11:40 Q5 : Set Mismatch
01:21:03 Q6 : First Missing Positive
01:35:19 Outro
#sorting #placement #dsa #interviews
I purchased the geeks for geeks dsa self paced course .. that course is good but yrr this is gem i have started following ur course and just using this knowledge to solve questions there... Wish u came early my 3000 rs would be savedđđ please don't stop posting
Hey @Rakib Mondal I was also thinking of buying the complete interview preparation course from geeks for geeks. After your experience with them what do you recommend?
Same bro..i also did same
@@intellectualsrestroom2001 Don't take that
same .. i did the same. and after left it in the middle
Have anyone purchase an Interview Preparation Course from Coding Ninja?
Important Time Stamps for Future Revision
4:05
11:10
16:30
When Kunal say " ase he haua bna rakha hai" It motivates at another level
solving that hard leetcode problem by myself without seeing the solution was really motivating! Thanks for these videos!
Great to hear!
@@balibhadrasingh6730 Bro, cyclic sort will work if array contains 0 to N elements , means if arr.length = 4, it should have 0 to 4 but in any order, so you sort and find out which element is missing, it will not work for random numbers in an array
@@arjunnarayanasamy6317 bro, did he covered Tree BFS, Graph BFS, Tree DFS, Graph DFS and Heap concepts in this Bootcamp?
@@manjindersingh8677 nope
@@manjindersingh8677 Not yet...Tree Data Structure is pending
When he says " you will solve like this like this.. this is nothing . this course is more than enough to crack Amazon etc etc " I feel more confident đđđ. Your real teacher ..huge respect to u .. đș
where did you reach?
hahaha love Kunal's vibes
In my life , this was the first time I did medium level question in just 1 minute . great videos .
Excellent!
same bro
Kunal broke the "hard" question myth.. I solved that question before watching the answer and I was like "very simple stuff" .. Thank you Kunal for the effort you put into creating this bootcamp. I appreciate it đ
i never commented on any DSA video but after watching this video............the only one dialouge comes in mind .....
Jahanpanah! Tussi great hoâŠTohfa kabool karo!....jai ho
I am not believe myself that after this video solved 2 hard leetcode questions.
Thank you soo much for shocked me
Keep up the good work!
@@KunalKushwaha i m bca student can i apply for google or any other faang ?
There's no single day.. When he doesn't uploads any video..
Hats off to the great work bro..
Just love the way you explain things in the most simplistic way..
Thank you.. â€
Thank you đ
@@KunalKushwaha which book do u prefer for java??
@@KunalKushwaha Your explaination is far better than others. I am not writing this for any comparison but fact is fact. Noone can deny it.
in Q2 if im swapping the elements inside while loop instead of creating a separate function for swap, it is showing TLE.....why?
Really?
no one is teaching DSA in India like this.
Great Work!
Kunal, your teaching has been absolutely outstanding. I watched your explanation of the Cycle Sort algorithm from the beginning and, remarkably, I was able to solve all the questions without watching the LeetCode answers. Your guidance and support have been invaluable. Thank you for your exceptional teaching!
After you explained the sorting algorithm the questions felt so easy even the leetcode hard as you said were not at all tough, thank you for making DSA easy for us Kunal bhai!đ
Great to hear!
in Q2 if im swapping the elements inside while loop instead of creating a separate function for swap, it is showing TLE.....why?
@@nikhilnaidu1383, I also did inside while loop, and it works fine, check again if you are doing something wrong
@@nikhilnaidu1383 did u do i++?
@@KunalKushwaha can you kindly do videos on dp, graph, trees and complete the video :")
Now. I am able to solve the questions just by seeing the question explanation and understanding the pattern. Thank you Kunal Bhai for these videos.
Tumahara college name and where are you from?
Before watching this video I almost solved all the problems which Kunal solves here by using the intuition method but after this video, I optimized them with the Cycle Sort algorithm and the time and space complexities have improved. Thanks for the hard work and your dedication.
Best course ever. The way you teach the approach development and intuition. Next level stuff. Thanks very much
Today I was solving one leetcode medium question, and after thinking for 10 seconds, I found that I have to just copy-paste insertion sort algorithm đ + no changes required. Literally hauwa bana rkha h
Thank you Kunal For bringing this high quality content for free â€ïž
Leetcode kya hai?
I am a beginner or will begin soon after joining college.
Your college name please and your subject?
@@VivekSingh-xk5rk hi
@@VivekSingh-xk5rk leetcode is a library of coding questions based on Data structures and algorithms.
Thanks for this course. It's really the best course I've seen so far.
Literally i am falling in loveđđđ with your teaching skills and approaches you are showing to solve a problem. Though I am from non-IT background, working in IT but always very curious about coding with self learning. Your explanation is easily understandable by a non IT candidate too. Keep up the good work. Hope to see much more videos on the various cutting edge technologies going forward. You are helping peopleđđđđ rather doing videos for views/monetary benefit. Keep sharing your knowledge. Because it is the most prestigious thing one can do without any selfishness. Thanks
I just love how this guy has burst the FANG bubble. Freshers really needed to know this.
last question was like " jo dikhta hain woh hota nahin aur jo hota hain woh dikhta nahin" . Superb session.loved it.
today I completed previous assignments.Really enjoying doing practice after theory. Thank you so much for making such a grt content and providing questions for practice after theory.
Hey nidhi , I am also following Kunal bhaiya but I am getting some problems and unable to solve some assignment questions so how did you managed with this issue ?
@@lokesh5371 same problem here I am not able to solve assignment question. They use other data structures and algorithms to solve those questions.
@@cdrrjt5005 I hope Kunal bhaiya reply to this :)
@@lokesh5371 I am also getting stucked in 4-5 problems even not solved yet,add those problems to your list and try it after some time with fresh mind.
Hey guys can we have a small group, so we can interact with each other regarding doubts and any conceptual take away ? Discord community is great but if we will have a smaller group i think it will be more beneficial as we are at the same point know. Will love to here your opinion on this đ
i have never seen anyone before like you,you are just amazing
Your words keeps me going. Thank god i found ur dsa playlist
As always Awesome đ
Actually this is the best DSA course ever in CZcams â€ïž
Thank u Kunal đ
I have a simple solution to Q1 Missing Number but it doesn't use the Cyclic sort algorithm. Since you know N you can use the formula N*(N+1)/2 to get the sum if the array would contain the missing number, than just sum up the given array and subtract them.
Also would like to thank Kunal for amazing course so far! Enjoying it really :)
That is a very interesting solution. Thank you
Even I had similar thinking. But if the missing numbers are more than 1, this approach won't work. Whereas cyclic sort approach works very well in all conditions!
Binary search is good
@@KRiSH-ei6fy there will be only one missing number since the array size is N. But in some other cases like duplicates question cyclic is best.
Best boot camp i have come across on the youtube, thank you soo much Kunal.
Best Course Ever !! Kunal Bhaiya Op !!
The best way to teach something is getting clarity in a concept and doing 5-6 similar questions to reinforce it. This course does that. Great!!!
Glad it was helpful!
in Q2 if im swapping the elements inside while loop instead of creating a separate function for swap, it is showing TLE.....why?
cyclic sort is not working for arr[] = {20,10,6,18,17,33}, how it will work for this array acoording to kunal shah concept
do you know
@@balibhadrasingh6730 Cyclic sort only works for 0 to N element
@@balibhadrasingh6730 it works only in the range of 0 to N or 1 to N, your array doesn't have elements in b/w that pattern
THIS IS BEST JAVA COURSE TILL DATE ,understood all the concepts taught , Was able to solve a medium question from assignments soooo easily! Rather than jumping on to complex solutions go for this video it has helped me a lot to build logic to solve questions.
You are most welcome
The best explanation for cyclic sort so far. Hats off to the good work you are doing. Thank You !
Thank you for your efforts Kunal. I haven't seen a video where people go through each iteration in a loop with patience just to explain how it is working and most of them won't even type the code in live and they just give the code at the end after explaining the algorithm. I hope you complete this when you get time. I have seen every in this playlist even if I know the fundamentals because you covered some topics I forgot and missed when I learnt the basics. I graduated in 2019 and I am currently working in a mass hiring company for sh*t salary and I am trying to make the shift. This bootcamp is really amazing and I know you know that too. Please complete when you have time. Thank you.
Thank you bro for uploading such an awesome content, it will help many students who didn't afford to buy the expensive courses to study.
So nice of you
"Minimum swaps to sort an array of distinct elements"
Solved this one also using cycle sort. This question is great one, everyone must try it
Hey can you share your code for this question?
I couldn't come up with a O(n) time and constant space solution!
@@AdritoDey create a vector of pairs with first as array value, second as index. Now just sort this array according to first value. Now u just have to take every index value to its original position using swaps, that's what we do in cycle sort.
Yeah
Best dsa course cycle sort is now crystal clear too.
Genuinely the best Dsa course I came across..
thalaiva nee vera level đ€©đ€©đ€©
It feels nice to solve problems of cyclic and the way you teach is awesome . This course is addictive/habit forming for solving problems.
Yes bro. Absolutely true
Today i solved a hard problem cos of you. Thanks man for this wonderful bootcamp.
You are most welcome
I have watched lots of DSA videos on youtube but No one can give logic building like this and littery I am very thankful to my friend who suggested me this playlist
Thanks a lot for this video .Was able to code every single question on my own .Undoubtedly the best DSA bootcamp .đđ
Most welcome!
Bro please keep uploading such videos,thanks a lot,please bring such new and hard interview problems on regular basisđđ
I will cover it completely dont worry
best teaching video for coding , till then i have watched numerous channels but because of u i am now able to understand how to actually do it . a hearty thanks brother
Grateful for Kunal Kushwaha, what a great man!âšđŻ
The way you have been explained is phenomenal! Keep going brother :)
Glad to hear that
Kunal, in Q3: It was mentioned that nums shouldn't be modified right? But Cyclic sort modifies nums.
Love the way you teach bh the wayâ€
You can use indexOf() method also, you don't have to modify the array using this
Constraints aside, he's showing how you can apply this algorithm to this problem. Then when the interviewer would ask to do it without modification, you have to move to another approach. For that you can watch Striver's video for this problem.
For the first time I was able to solve a Leetcode question and that too without taking a hint or looking at the solution/explanation. It felt amazing. This playlist is nothing short of amazing.
Never ever I thought I would be able solve a leetcode hard problem this quick. Great job Kunal !đ
This is literally a gold mine! I code my solutions in python and these are helping me immensely. Keep up the good work!
Great to hear!
Your comment made my day.
in Q2 if im swapping the elements inside while loop instead of creating a separate function for swap, it is showing TLE.....why?
cyclic sort is not working for arr[] = {20,10,6,18,17,33}, how it will work for this array acoording to kunal shah concept
do you know
//this code will be helpfull to understand the algorithm in an efficient way
//great work kunal anna
class Main
{
static void cyclicSort(int[] nums)
{
int i=0;
while(i
I can see my progress! Thank you Kunal
Thanks for teaching us like no one did till now!! One small request, please make lectures on dynamic programming as well!!
should be a high request. without having proper knowledge of each concepts how u suppose to crack interview.
Just finished the previous assignment today and was thinking when the next video will come and then your notification popped up , man you are hearing mind or whatâ€ïž
Bhaiya... I got stuck in many problems while solving... How do u manage all the problem!?
Have u solved all the prblms or some good questios only!?
@@mehandiWithPrity hey can u write the questions which you got stuck and regarding me I was doing the questions given by Kunal as well as some prblms in that specific topic on hackerrank
I am impressed by seeing your video. Now the problems look so easy.
I am a BCA student and I never thought I can solve this type of questions but after watching your bootcamp JAVA&DSA my reaction to FAANGM, u're kidding me you asked so easy questions in your Coding Interview now I am also able to solve those problems
So Thankyou Kunal Bhaiya or Sir because You have all the qualities and again Thank you for giving us valuable knowledge
Thankyou
if u r able to solve the questions ,it doesn't mean those are easy problems. Its ur problem solving skills
It means u are working at faang. Companies??
Nice work @kunal, not only upcoming college grads but it's helping experienced one like me in clearing my basics(ps: working as R&D Engineer in a leading MNC)
Glad to hear that!
Hitachi?
Thank you Kunal! Love your channel and teaching style. Love from Kazakhstan!
Best lecture to learn Cyclic Sort!!
I'm still at 17:50, but I think we can write it better. The code is in C++
void sortArr( vector &arr)
{
for(auto i = 0; i < arr.size(); i++)
{
while(arr[i] != i+1)
{
swap(arr[i], arr[arr[i]-1]);
}
}
}
I did the same way, but I felt his way was better as there's a only one loop making it easier to read (though the complexity is the same). Why do you feel this is better?
I did Q3 in little bit different by using previous method
Q3: Duplicate number
Input: a[ ]={3,4,1,2,2}
First sort by cyclic sort
Then it becomes
a[ ]={1,2,3,4,2}
Then
Sop(a.length-1)
Tq you kunal
same here
Same bhai
Thank you Kunal for this. I could never believe myself solving the medium and hard questions in just a snap just by following the understanding pattern as you are teaching. Kudos to you đ
U R SUCH A GREAT FRIEND THAT EVERY AVERAGE STUDENT WISH TO HAVE.
Never learned such things in deep
@kunal kushwaha bhaii
For find duplicates, you cant use Cyclic Sort as the question clearly says we should not modify existing array.
wondering same
@@prettylilnerdy6802 Same here. Maybe they don't let you modify the values but they do let you sort it :)
don't know about multiple duplicates but if it is a single duplicate we can just xor whole array and the result will be answer
@@mukul-kr you need to xor the whole array, then xor that with all the numbers that should be in 1..n, no?
Yeah same I wonder, I think XOR can be used for that Ques, as we are modifying the array by sorting it.
Thankyou soo much for making this bootcamp . Never found this kind of teaching in any other channel . Love the way you explain n make problem solving fun . Really appreciate your effort . Would be very glad to see more such videos. â€â€â€
Great thanks for motivation. When u say that everything is easy and SHOW it, it makes me a lot confident! Thank u very much
Great Man :)
I have been consistently doing leetcode for more than 40 days now, but still this one is quite new and very interesting for me. Keep up the good work :)
Keep it up
I feel the missing number question can be solved by simply addition property, and maybe that might be slightly better.
I agree
It can be solved using xor as well.
This course is so much better that every other course, It is like I am getting a therapy and also getting educated, the satisfaction on completing the question on my own is the best feeling. Thankyou so much.
Hey! I have a question regarding programming language used. I am familiar with Python, will that be a problem for understanding this course as it is in Java?
Keep up the good work Kunal â„
Yes you can implemet solutions in python as well , just understanding logic is important part which u can comprehend with these videos.
hey Kunal your videos are great I can solve medium to hard-level questions of LeetCode đ„°, but the playlist is incomplete can you please provide the remaining topics such as DP, trees, and graphs it really helpful if you continue this playlistđ„ș.
He's too busy for that
@@vansh9857 Now he is working on it again!!
submitted first leetcode solution by myself, thanks man. Keep up the great work.
Thank you for giving me the pleasure of solving a LeetCode hard question on my own.
at 52:30 , the question wants us to solve the problem without changing the array. But why does he use cycle sort then, it changes the arr. ????
I also had the same doubt ?
Upload accordingly to u ....not fast becouse quality is more important ...don't listen to anyone please
Don't worry I always maintain quality
Best course ever made for DSA.
Thanku so much ...
Upon completing the whole video...gave me a lot of confidence!!
Thanks a lot
is it only me or every one can see suryanshu tomar's comment is older than the video itself? for me its showing 24 minutes
because videos are uploaded very early and published later. hence people can see those directly from playlist.
@@KunalKushwaha oh so no magic thats sad. bye gotta go, i have to wait in playlist section.
I don't understand why do people care about such irrelevant things. Just focus on learning my friend. These type of questions won't get you anywhere.
can't we do
if(arr[i] != i+1)
arr[i] = i+1;
for every element in array?
Not always. What if the numbers in the array are not consecutive? Something like [4,6,9,2]. Think about it.
@@live_mocha then cyclic sort won't be applied to that array .... It applies for consecutive numbers only
@@srikanthmacha7990 That's only one case, I found many examples where cycle sort is used for non consecutive elements. The correct position for an element is not i+1 in every case. It is the number of elements lesser than the current plus one.
Outstanding explanation on cycle sort!! Thank you Kunal!
the guidance is amazing, couldnt get impressed more, i have even started solving questions without even going through complete video.
đđđđđ
Love this boot-camp series :)
thank you so much kunal, this course is boosting my confidence and please continue this course.
love you man, finally solving some problem
Mostly, the things are categorized according to its benefits but sometimes somethings just sets a reference to be a league of its own and I am glad to say that this playlist is the one of its kind and just great.
one of the best course i ever watched for java&Dsa (kunal sir is changing my life in better way)
This is next level of teaching ....
Thanks bro
Wonderful.. No more words to explain this video, just Wonderful ..
Please keep doing this great work , coz I see a lot of people aiming at you ,and just want to discourage you , but you are putting up amazing content , please keep doing it for us ...thanks
I solved Q2, Q3 and Q4 by myself. Just from the explanations from the video. My confidence as a programmer has literally sky rocketed. Thanks
I've watched it again. Still feel it's the best algo video I've ever seen! Thanks a bunch Kunal!!!
I loved this video. I solved and submitted all that questions by myself. It feels so good. I don't think I would ever forget this concept.
I watched the working of cyclic sort and solved every question mentioned in the video myself. After solving that one hard question cyclic sort became crystal clear to me. Thanks Man!!!â€â€
I am glad that I found your channel sir. you just cleared my concepts that I was never able to understand the logic behind them. HUGE RESPECT TO YOU SIRâ€â€
You humble me. Thank you very much!
Thank you kunal for making these amazing videos đđ
Hats off to you man....the way you explain every questions looks like very easy
Great Kunal đ One of the best DSA series.
Before, i used to memorize the problems. But now i am memorizing the patterns and that's a game changer, thanks kunal.
Now I got confidence in cycle sort, thanks bhai