How Linked List will screw your Interview - Do this in O(1) space!

alright guys welcome to the seventh episode of ratchet challenge is gonna in this case I am channeling him alright 6 4 6 July Kevin alright guys this is the fifth episode of matcha challenge this quarter although in this episode I will be challenging ratchet I have a question on a doubly-linked list so as we all know doubling lists are basically linked lists which have next pointers and the speciality about them is that they also have previous pointers alright and the previous pointer points to the previous node but this w Inglis is a little special the next pointer is exactly as in a single linked list but there is also a random pointer in each node so if I number these nodes 1 2 3 & 4 then the random pointer for one could 0.233 good point to itself two good point to one and four could point to let's say - alright so you're saying that one kind of pointer is something that we understand one kind of pointer is entirely random what I want to do is I want to duplicate this list to get the exact same structure of the previous doubling list but I also want to do this in constant space in a sense I want four nodes to be created because those words are very heavy for me and that's my chance to rupture today let's see if we can do this so nice Gaurav has given me a doubly linked list with a random pointer not the simple pointer that points backwards fine so I have to create n different nodes and return the pointer to the new linked list that I have created which is exactly same to the one that core of that so looking backwards that we so looking backwards what we had was a 1 2 3 & 4 and then we had random pointers of this fashion right so this is what we were having and we were supposed to create new four nodes with having similar topology of the linked list so the first thing that I will do is create this simple linked list and how will I do that I will do so I'm having appointed two I will take a temporary pointer and create the first node which is one and then I will move pointer to the next one which comes to two I will create a new node to store the next to that and then you know move to three create a new node with value three and store the next pointer for that and so in this fashion I have created four nodes the next is pointing exactly fine but the problem now comes is about setting the random pointers in this linked list so if you will see we know that random pointer for the first node and that's the third node over here so many people can say that we can have a map where we can store the values so we can basically say this is number three we can look for the pointer in this linked list which is having value three so in this case we get appointed here and we can simply do this but this will fail because what if the linked list is having duplicate to reiterate what I am saying is a simple solution that comes to mind is we know that the random for one is pointing to the node having value three so we can store a map and in that map you can have the value three and we can store the pointer which points to that so we can build this map when we were building this linked list so basically we are having four pointers let's call them pointer one pointer to pointer 31.4 so basically this is pointing to this this and this so once we have this thing and we have a map ready map of end two pointer so we can perform a lookup in this map to get the pointer which is having value three right so this is what I'm trying to say so if this was thirteen so the in this map this pointer three wouldn't be mapped to the value thirteen right so based on the contents of a node I am storing the corresponding pointer for that which I will be using to mark the random pointers but this will of course fail if we have duplicates so let's say so now we have duplicates over here so now in this map from in to pointer we were mapping the values of the node to the pointers which are pointing to them this approach will fail because for 113 we are having two candidates and map and store only one so here is the ambiguity which we can solve or which we can resolve by storing in this map not the contents of the nodes but the position of the nodes because the position will always be different so what I mean to say is the position of this is 1 this is 2 this is third and this is 4th so this is the first second third and fourth and similarly we know this is the first this is the second this is the third and this is the fourth let me just clear this up so that I can explain my approach in a bit clearer way all right so now what we are doing basically is the pointer one is mapped to the end 1 the pointer 2 is mapped to the pointer 3 is mapped to 3 and the pointer 4 is mapped to the fourth root so now in this map we can easily get the pointer to any key node that we want so if you want the pointer to the third node and it simply perform a lookup in the snap and we get this pointer in login time if you are using an ordered map and if you are using an unordered map which is based on hashing we can get this in oh one time so think about this what we have achieved we can get it oh one time the pointer to any kieth node the third node the hundredth nodes the 70th node we can get that into one time so how is this useful to us so it is useful to us in this way so now when we want to mark the random for this we know that this is pointing to 30 and it is the third node so how do we get that is a different question but let's say for now we know that 13 is the third node so now in this map I will just look up the third node get the pointer to that and I know that the random for node 1 should be 0.23 so in this fashion I do this marking of the random pointers so again for number 2 I know that this is put into the first node the map will tell me in overtime that this is the pointer to the first node and I map there and up for this two pointer one which is pointing to one so in this fashion you can build the linked list and if I think you are smart enough that you already know how will we get what is this random node pointing to what is the position of that node again we can have a map here from pointer to it so using this map of pointer to it what we can do is so you know the random pointer it's pointing to some node but what is the position of that we can leverage this map again to get that position in overtime so in this fashion by using extra space of course we can clone a doubly linked list with their fancy random pointers but here is another twist what if the interviewer says to you that I don't want this approach I don't like this approach I don't want you to use extra maps I want you to do it in a way so that you are not using any extra memory of course since there are four elements and original linked list there will be four elements in the result so we have to create four nodes but what the interviewer is trying to say is don't create these maps because they are they are taking again four plus four eight extra memory slots and that's something we want to get rid of so how do we do that all right nice the problem that we have this we are having at updating this with some with some random pointer in eh node right and we have to clone this all right and we don't have to use any extra memory fine so I'm just trying I'm just drawing this linked list with some extra space like I am drawing it in some expandable form so I'm not doing anything fancy but what I am doing it here is 13 and here is the fourth node with value 30 all right so this is what we have 1 2 13 and 13 and we also have the random pointers like this so 2 is here 13 is this 30 is pointing to itself this is coming all the way here and where is 2 and will is 1 you Ernest to this all right I have not done anything fancy I am just writing in a bit stretched form right so I have to create 4 nodes what going to do is I'm going to use red color to basically make the linked list that I'm going to return later on so what I am doing is is a little dirty trick I would say and I'm going to insert the duplicates so the duplicate of one is one I'm going to insert the duplicates in between and why am i doing that just hold on for a second and you will come to know so here is a two here is the 13 and here is another 13 all right so I have distorted my original linked list sorry for that but just hold on with me for a couple of minutes and we will know what exactly is going on alright so I know that the black linked list that I was having originally the black notes or I would say they are having their next pointer a bit disturbed right now but I know that the random pointers are still intact for my original link list and for my new link list which is for the red nodes they're linked their next pointer is also not set correctly right now and the random is also not not set correctly right now but in this diagram or in this structure that we are having there's a very interesting observation so for my third node in my original linked list now I can easily refer to the third node in my red linked list by just moving on to its next pointer right so the third node and original linked list is 13 and the third node in my new linked list is this one and they are linked with their next property this is very important for us why we'll come to know about that because the next for any node for the red node the next pointer is nothing but the next to next one of that so the next pointer of node two should be the next and the next so basically the second pointer from current position will give us the exact next pointer in our new linked list and similarly that goes for our original English the second node from the current node will gave us the exact next node position will give us the exact next nodes pointer that's fine but what about the random one I know that to set the random of this red road I can set it by using this property that the random of the previous node and the next of that will be the random of that if this looks like a tongue twister or something I am sorry about that but what I am trying to say is here out very carefully the random of this is nothing but the next pointer of something the next pointer of what the next pointer of this so I know that random of this it's perfectly linked correctly but I can exploit that information this is how I can exploit that the random to the black node gives me 13 and the next of that gives me the corresponding node in the red linked list so using this I can set this to this and how I can do that what I can do is for this black node let's call this pointer I can say pointers next which will become a red node because for every black node it's next is a corresponding red node in linked list in new linked list so this is a red node and I can set its random to what so basically pointers next random can be set to what it can be said to the pointers random which is a black node in original linked list and it's perfectly set with correct values so this is the black node and the next of that is a red corresponding red node and using this I can simply set the random pointer of red nodes so the so pointers next random is nothing but pointers random next so one is linked to 30 let's talk about 13 and then I will close this so for 13 the next random will be nothing but it's random snakes so it's random is itself and the next is this so this is said to this and in this way we will set the random pointers and they and then you simply separate out these two linked lists because we know how to set the next pointers and then we will simply return the head to this one over here and in this way we did not use any extra space and we use this little dirty trick to just you know exploit this question and I hope you liked it oh nana so guys i think this was a fantastic explanation by ratchet for a problem which is is is very your so guys i think this is a fantastic explanation by ratchet for a problem which doesn't strike people in the first go and this is actually an interview question which is asked quite frequently so thanks watching and if you liked the video then you know what you have to do subscribe below and of course like share you know what you have to do like share and subscribe see ya bye

Channel: undefined

Views: 172,224

Rating: 4.8206921 out of 5

Keywords: linked list, linked list hard, linked list interview, competitive programming, coding interview, coding interview problems, coding, python tutorial, c++ tutorial, oops interview, google interview, microsoft interview, microsoft software engineer, google software engineer, dynamic programming, backtracking, graph theory, codeforces, codechef, leetcode tutorial, geeksforgeeks, algorithms, data structures, rachit gaurav challenge

Id: xbpUHSKoALg

Length: 14min 32sec (872 seconds)

Published: Wed Nov 21 2018