How Linked List will screw your Interview - Do this in O(1) space!
ฝัง
- เผยแพร่เมื่อ 20 พ.ย. 2018
- ✅New TH-cam Account - Developer Bhaiya 👉🏻bit.ly/developer-bhaiya-youtube Gaurav challenges Rachit with a hard interview question on Linked Lists.
The problem becomes extremely difficult when the interviewer asks to solve this in O(1). Watch till end to see how to tackle that part also.
Watch the video to see how Rachit tackles this problem.
Want more such collabs? Let us know in comments :)
================
Important Playlists:
================
Famous Interview Questions You Must Know ► • Bit Xor - Watch till e...
Tips & Tricks for Success in Career ► • Mentorship - My Life L...
How to Improve at Data Structures ► • Playlist
OOPS Interview Questions ► • If you don't understan...
Gaurav Challenges Rachit ► • AlgoWorkout - Coding I...
Lectures & Tutorials
================
Dynamic Programming: Zero to Hero ► • Dynamic Programming: F...
Dynamic Programming on Trees ► • Dynamic Programming on...
Graph Theory for Beginners ► • Graph Theory for Begin...
My Code Library
==============
Github ► github.com/rachitiitr/DataStr...
Follow me:
==========
Instagram ► / rachitjain2095
LinkedIn ► / rachitiitr
Facebook ► AlgorithmsWithRachitJain
Programming Blog ► rachitiitr.blogspot.com
Twitter ► / rachitj55307787
Programming Profiles:
===================
CodeForces ► www.codeforces.com/profile/rac...
CodeChef ► www.codechef.com/users/rachitiitr
Watch video description for links to important playlists ;)
V
Hello gaurav and rachit,
I starting my life with a low salary in a startup company as a developer. Whether it is going to be good or not?
Hey Rachit... How is this O(1) space . It's O(n) right?
@@shubhmishra66 The solution without the map was O(1) extra space
Will this solution holds true for lists having 1000 and lakhs of nodes?.
1:56 Literally looking backwards, Saying "looking backwards"
Hahahaha
haha... connecting the nodes looking backwards.
RIP: Steve Jobs
Lol
@@manthanchauhan6954 haha
In first solution, instead of creating 2 separate maps and then using position to identify the newly created node, we can simply create single map of …..where key would be old node and value would be new node with same value.
What a clever solution/trick. I’m not sure how someone would ever be able to come up with this without a hint or having seen this done before
Disclaimer: I was asked this in one of my interviews... And I struggled for a loooooot of time...
Algorithms With Rachit Jain 😮
Which company was it, if you'd like to share the name... :)
@@RachitJain I appreciate this comment..coz no one ever tell that they struggled...they just make their viewers think that they solved the problem in one go like Tony Stark in Marvels. You gained a subscriber buddy...😊😊😊
@@RachitJain I was able to in O(1) space but i didnt use this approach. But glad to know the trick.
How someone can get this trick on the spot without prior hint 🤯🤯
While I was giving an interview for amazon on campus internship interviewer asked the exact question which I couldn't answer efficiently but this solution was awesome
Did u get placement in Amazon?
You need To be on tons of ganjaa before starting this at your own.
oi lad
I did and waste 12 hour's. 😂😂
Linked List questions are the kind of questions that once you realize the O(1) trick, you’ll never forget it. You can eventually come up with the solution if you never seen certain problems, just know that you have a high level of comfortability of traversing a linked list and manipulating their pointer references. Also LL problems can almost certainly be done in O(1) time
O(1) time ? waah bhaiiii
@@desiqna5223 he mean space.. Not time
That moment this explaination hit me, my mind was blown. Great question.
Easy solution but quite counter intuitive. I loved it!!
Well explained man! Appreciate your teaching!
That was an "ohhhh ... Snap that's how it can be done" wow great question liked it 😀
Great job on explaining! And great job on clarifications ! Keep making sure the concepts you present are clear! Great job
I am really excited for this one.
Hey ,Can you please tell how can we create a map pointer and corresponding random pointer position.
Wow!! What an approach. Simple to understand and yet effective.
good question with very good explanation...
Thanks!
literally awesome concept sir!
This series is fun to watch!! Thnx!
Rachit and Gaurav I have became a fan of both of u
Amazing trick rachit, think out of the box solution
Hats off to your logic... Smart logic
Thank you for explanation.Finally it is crystal clear to me
I have to say it was amazing.. Literally
Thanks Mridul
YT recommended me this video yesterday, Today this is the Leetcode Daily Change problem. 🤫
When you are high af !!!
I was high till you put that line in middle of this video. XD
This is a standard gfg problem rachit... please share with us more of some tricky or complex problems thanks. You doing great job man
Awesome logic loved it
Nicely explained!! Plz also explain coding for this in c++
Loved it gurus, thank you for this awesome one.
Thanks a lot :D
Hey Rachit preetty amazing. Learnt something new. Glad to learn something new
Mind blowing 🔥🔥🔥
Miss those days🙈
Excellent and simpler!
good explanation! thanx
Happy birthday to you Bhaiya 🎂🎂🍻🍻. Thanks for nice video
It was yesterday but thanks
simply love it mam perfect
The final solution is bloody brilliant!
this one's national treasure ✨
enjoyed it thoroughly !!
Awesome explaination really. You approach was crystal clear in your voice. Thanks by the way.
Thanks!
Super video and excellent explanation, very clear and concise. Thank you so much.
Very very clever. Thumbs up!!!
This is Amazing 👌👌😊 great approach!! ✌️✌️
But he is using extra space for storing duplicate ....?
The 2nd solution was literally exploiting the links between the linked lists,while creating the new linked list while keeping in mind about the random pointers....awesome....
Same question was asked to my friend for codenation placement interview R1 round.
Good explaination.Were you able to come up with second approach on your own totally?
I was thinkg like a BFS traversal. But that will use extra memory (queue) , this was an amazing trick. Thanks
That was a good explanation and solution was very excellent thanks bro
very simple and straight explanation 👌👌👌
Thanks kuldeep
Wow the solution was just awesome 😍
Thanks Adarsh :D
This solution is 200 IQ. Really enjoyed the explanation.
So cool .. that was really fun !
I could get to map approach but this approach is goddamn amazing man
Quite a nice explanation , thanks a lot .
Deep copy LinkedList with random pointer, I got asked this question on Bloomberg’s sde interview!
Outstanding explanation
THIS IS AMAZING !!
very Nice trick and explanation
Hey Rachit, this is a really brilliant solution...
But he is using extre space for storing duplicate ?
Wooow!!! Great video !!!
Thaaanks!
In the map solutions
How about
map
And then it reduce the space ... I know it doesn't take it to O(1) but it saves the space used for indexing the first linked list ...
Good job, you did well
The end of this video was something like the end of a really good movie.
Wow :P Thanks!
can you please provide us with the code for better understanding
Great content!
That was nice didn't understand question at first😂😂 . Elegant solution 🔥🔥.
the dirty trick is so simple and ...feels like eureka...thanks
A linked list is stored in potentially arbitrary order because the physical order doesn't matter. However as long as it's in the same contiguous area of memory no matter the order what I'd do is just copy that contiguous area with a simple memcpy thus duplicating the full list then go through and perform very basic arithmetic on the pointers in list adding or subtracting the exact same offset to all the pointers so they all point correctly to the new list. By far the quickest and simplest approach to me and one that can be the most easily optimized. ---- Downside it will only work on mid-level languages like C or C++ and it can't use the heap but I do embedded programming anyways so I'd fit the requirements and thus my solution seems the simplest and most straightforward.
Dude ive prolly hit the like button like 10 times! Love your work man and keep posting your videos!
Thanks Rahul, means a lot
Excellent explanation Rachit bhaiya
Thanks Kartik
Nyc question
Well explained man
Thanks Harsh
I loved it...😍
Done this problem, it took me a day to understand the solution
Sir please make videos on how to prepare on datasructure and algorithms
I was thinking of a different approach. Let me know if this will work.
Create new set of linked list from next pointers as usual. Also, connect random pointer to previous nodes when doing this process. Then, start from the last node. Search in the entire linked list using previous pointers where the random should point and point the random there. Move 1 step back. Search the entire linked list forward (using next) and backward (using prev, i.e. random) until you find the actual random pointer and point it. Repeat this for all nodes till first node !
We want more collabs!!
Amazing!!!!!
Nice explanation 👌👌
Thanks Manish
In episode 6...What if the maximum element has the least cost and if we remove it then array length will change? please explain that case also
Yes but position may be out of range for integers
We have finite number of integers in our machine
Wowwwwweeeeeee. This trickk is fabbbb
awesome explaination
Thanks
I am just started learning data structure basics stack linked list etc can you give some suggestions to achieve the level in DS which you have
Amazing!!
Are you really Ashish Gupta , Senpai?
@@shubhmishra66 what is senpai?
That laugh......I can feel that situation...LOL
It is similar to b+ tree .... like we have duplicate nodes at lowest level of the tree pointing to the records respectively.....
You are beauty , nice explanation
really good explanation
Thanks
Thanks bro
Awesome trick
Hey, I get the first approach and I could come up with this myself. But the 2nd approach is still going over my head. Can someone help?
Kaise karlete ho Rachit bhaiyya 😂🎉
Wow. I wish I had watched this earlier
Please send me some resource to this.. I think I didn't get the question right. Or please tell me the topic name
hello in the last part of the video didn't you change the structure of the linked list that it had two next node?
Mind blown away
I can relate to it.
Is there a way to do this in constant space without modifying the initial list in the process?
So basically inserting a node between original linked list nodes preserves the path if we decide to travel original using just random pointers
7:37 how?
I am good at python and I would like to learn DSA so which language will you suggest do you want me to stick with python or you want me to learn c++.I also learned basics of c++ so that I can some understand about of other codes in c++ and write it in python. Please suggest me whether to stick with python or learn c++