Find the intersection between arrays: Coding Interview Question

hey guys welcome to another white booth Thursday today I have a very frequently asked question in small and become knees alike which is if you have three sorted arrays how do you find intercession or the common elements between the three arrays in the most efficient way possible and at the end I also tell you which problems I'm going to cover next week so you can get a head start try to yourself before you look at the solution so let's get right into it so these are the three input arrays and they're all three sorted yep so in this case the output would be whatever are the elements are common in each of these eyes so let me just write that down over here the output will also be an array of us women right and in this case we'll have six and 13 right correct actually I don't see any repeated elements in here so is it possible then let's say they're two sixes in all three of these arrays and output is 6 is 13 yep the repeater element will be repeated at the output as well okay perfect so let's see how we can approach this I will somehow need to keep track of my index so I'll need to iterate on all three of these arrays at once mm-hmm wouldn't really make sense for me to have nested loops you know that would be a very efficient algorithm so let's say I'm iterating on all three of these at once and in that case I'll need to keep track of the index where I'm at on all three of these at once you know same time so let's say the index for array 1 I name it as X for a 2 and a minus y and for a 3 and a mid see mostly of these are 0 right now so as you can see there and started to race so now I will be inside of like for loop or a while loop you know and I'll be trading till I reach end of bounds for any of these arrays not so the first condition is that I check whether the value at X Y and Z's are all the same if that's the case then I'll push them to my results all right mm-hm and if that's not the case then I'll see that ok if X is less than Y they need to increment or the value X is less than the value to I then I'll need to increment X yeah so that's the case over here right now so let me just do that name increment X now I'll do the same thing I'll see if the values are the same they're not right so LC is X less than Y that's not the case then I will need to see is y less than Z and over here that is the case yep right so I'll say ok let me increment Y so basically I want to see at each if statement or each condition whether one thing is less than the other I basically want to see okay is s X less than Y now see if Y is less than Z at the end of these two are not met then it automatically implies that Z is less than x and y yep right so in this case I increment X right this case I increment Y and if none of these are satisfied then increment Z mm-hmm right so now none of these are satisfied right the this is an equality so X is not less than Y Y is not less than Z and so are they think I'm not equal and the three are not equal so the first condition is not met so I'll say ok let me increment Z right now it's the same thing same scenario Z is less than x and y so increment see again obviously we were checking if all three are equal every and every loop now also you are equal so we'll push that into the results all right and we'll increment also your appendices right so the X will be over here Y will be over here and Z will be over here and we'll start the process all over again so this will also catch any repeated elements let's say there is a six over here as well right and as we've implemented it the next loop will check for equality again and if all three of them are sixes then we'll push them again their results all right yeah so this looks good I'll just jump right into the function in court it out yes sure let's say I named my function find intersection mm-hmm function find inter section it takes in three arrays array 1 all right - and already 3 mm-hmm it's say the first thing I'm interested in is actual result so let me initialize the results array as an empty array next thing is we need to keep track of all the indices so let me just initialize those x equals 0 y equals now we will go into the while loop so the condition for the while loop would be that the index is not out of bounds for any of these arrays so let's say I have a function for that that's a detail take care of that later so I'll say while I'm not OB and that's a function just give me a boolean mm-hmm and then I go into the actual if statements or conditions so the first one is basically if the values at all three x y&z are the same if that's the case then push the values to my results all right so let's say if array 1 x equals array 2 y and array 2 y equals array 3 z so if this is the case then I do two things one is I push the result so result that push any of the values so our a1x next thing i do is i increment all to your appendices so x + + y + + + z bus bus yeah yeah now I'll have elsif X or the value at X is less than the value at Y so array are a 1 X is less than array 2 y so this is the case I will increment X so X plus plus else if array 2 y is less than as we discussed array 3 Z so in this case I'll increment Y and then if none of these are true the only remaining condition is that Z is less than both the value at T is less than both the value in x and y so I'll say else Z plus plus yep that would be it for the Y loop so it will stop when the our bounds is reached right so let me just return the results first and now I can take care of that round function so that's it out-of-bounds function is within the find your section function so it still has access to all three of the arise and I can quote it over there so function B doesn't take anything it just returns the value of one condition that condition is basically so say return the value of this condition the condition is that X is greater than or equal to I already won that length or Y is greater than or equal to all right to that length or Z is greater than or equal to all right three dot length if any of these three is true they will return true and the wide loop will stop so I think this concludes this function the time complexities of this would be in the worst case scenario we're looping through all the elements of all the three arrays so if let's say the length of our a one is n 1 for a 2 is n 2 and 3 then it would be off n 1 plus n 2 plus n 3 and the space complexity with we're not really using any auxiliary space so that would be constant mm-hmm what if they put arrays are not sorted in that case I think there will be a couple of solutions first one would be that I have three nested for-loops so in that case this algorithm is totally irrelevant right it could be a whole different algorithm but the time complexity of that will be very bad will be N 1 x + 2 x + 3 the other one which I would do is to sort all three of these arrays first right if I'm using quicksort and time complexities of that would be N 1 laugh and 1 & 2 log of n 2 n 3 log 4 and 3 so in that case I would have let's say all three of these arrays the size of them is the same size of them is the size of the largest one of these two your race so in let's say that is n so in that case I would have 3 + log of n plus 3 M right so boils down to just n log or friend so the most time-consuming part of this would be actually sorting me right mmm-hmm thanks for watching guys I hope you liked today's video and if you did make sure to hit the like button below and subscribe if you haven't already and next week I'll cover traversal method on graphs that we call DFS depth-first search traversal which is a very frequently absent review question at the higher stages in the interview process so in order to get notified make sure you hit the bat icon beside the subscribe button below and YouTube will send you notification so this is it for this week and I'll see you next time

Channel: Irfan Baqui

Views: 53,155

Rating: 4.8844519 out of 5

Keywords: coding interview, programming interview, google coding interview, facebook coding interview, microsoft coding interview, coding interview question, coding interview question and answer, coding interview at google, coding interview preparation, Array Intersection, google programming interview, facebook programming interview, microsoft programming interview, coding, coding for beginners, cracking the coding interview

Id: B6Tsrmgsy3k

Length: 11min 26sec (686 seconds)

Published: Thu Jan 04 2018