Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)

exact how's it feel to be on camera do you just going on her laptop dude I'm so intrigued really this is my first time seeing it his first time seeing the chin six are you ready yeah oh man is it good [Music] got a lot of code here Ben do this can be one of those videos you just don't want to watch you can be a lot just like all over the place yeah Daniel what's up you know I just got Twitter today dude but I can't eat until everyone eats so we got to do a question today all right guys so today we're going to do a question that I got during my Facebook interviews this was in like my first rounds which I actually passed so didn't you uh not get an offer from Facebook all right so today we're gonna do the question total occurrences of K and a sorted array so like I said this is a question I got um during Facebook interviews and it's actually a really good question that demonstrates the process of walking through from a bad bad solution to the most optimal solution so for example we have three cases here we have dinner right here and K equals 1 so we've returned the answer is three we see that one occurs three times K is one it occurs three times K is three three curves one time K is K is one it's an empty array so the answers zero so the key information in this question is the array is sorted and it's a search problem these are two key things we're going to have to factor in when we're factoring in our approaches so moving along to the actual approaches so there are three approaches to this question so when I first got this question I really didn't know what the optimal solution was but I immediately knew if an array sorted the first thing you should be thinking is binary search which is very fast but first I said how would we do this just the naive way so we can do a linear skin so taking this example if K is 1 we could just do a linear skin our first occurrence should we grab that index and then we skin once we see the last occurrence we know we've counted three elements this would take Alvin time on average and it would take constant space because we wouldn't be creating a top or space that would scale with the input so this this is linear time always but we know that our best solution is going to run in log n because it's binary search so let's move on to what I proposed next which is approach 2 we can do a binary search which runs in log N and then do a linear scan to count the elements until we find a different element so we'll do binary search and get the zeroeth index here and then we would do a linear scan upwards so this runs in log n log in for the first search and then all event for the linear scan and then it'll have all event on just like our first solution and our binary search if we do it recursively we'd have log n for space complexity because of stack space but it would be all of one so the thing is this approach is ok but it's not the best approach because if we have our worst case if we have an array of all ones and key is one then we're going to be touching n elements and automatically our worst case becomes linear time and then instantly my interviewer told me what if we could do this in log n time only in average case log n time so instantly I knew it had to be binary search all the way so then what I thought is how I need the last element how am I going to get that and then what I realized was what if we do two binary searches what if we get the first occurrence and the second occurrence and then we can see that that would be indexed to that be indexed to index 0 so then how we have three occurrences here what how can I mathematically get that so then we could just do 2 minus 0 which is 2 and then add 1 because we're indexing lofts 0 so then we would get our answer of 3 occurrences so that was the optimal solution and then that's basically what went through and what I ended up coding so just to nail down the time complexities this is going to do two binary searches so it's going to be log n plus log n which is going to stay log n Big O of log N and then recursively if we do recursively we'll have log n because of stack space but if you do it iteratively you're going out constant space so this is a very fast algorithm it's going to run and log n having our search space and it's going to have constant space if we do it non recursively so now that we've nailed down the approaches we can go and look at the code for this this is the code I was really rushed to write it and I didn't have it like written down on my laptop so I literally had to make this as I walked in the room so it's kind of sloppy but it gets a point across so our main function up here is get occurrences of K so this is our main function so this is what we're going to do we're going to get the first occurrence if we don't find the first occurrence why would we search for the second occurrence then we're just automatically going to then if we don't find the first occurrence we can stop we can say we found zero occurrences because why would we search for the second one if we couldn't find the first one and then we find the last occurrence and then our answer is the last occurrence - the first occurrence index plus one like we deduced before in the approaches we just looked at so that's the overarching algorithm and as you can see I abstract the binary search away I abstract all the other details this is our high-level algorithm this is how we're going to answer the problem and now we can get into the nitty-gritty details of the actual search so basically I have an in here just I don't want to use a magic number they're called magic numbers when you try to encode a certain meaning using numbers or boolean's like true or false is I just said search type first and last I like using enews that's a very way to avoid magic numbers and stuff like that so here we have binary search so what we pass in is the array the item we're looking for left and right and then the type of search as you can see for finding the first element we pass in the search type find the first element for this we do a search type finding the last element both of them are buying a searches but we just tweak the base case as you'll see this is our base check so if the array if the array is empty or or left has gone past the right then we know that the either the element is not even in there or we've searched the whole search space and left has passed right so at that point we can just return minus 1 we have not found an answer so then we get the midpoint this is actually key you don't want to do left + right / - you want to do you want to do see you left + right - left / - because this is prone to overflow this is a really subtle point and it's really impressive you tell your interviewer that this is probably over flow this is the right way to do it because it shows you have an attention to detail so now we go into the binary search so we grab the midpoint and if our midpoint equals K then we're going to process it here but let me just show you the other houses if if our mid middle value is less than K that means we need to be group find values that are greater that means we need to go to the right our search type stays the same we make our left bound the middle plus one we make our right bound we leave it the same right and then we pass in these two this takes our search to the right if array mid is less than K we need greater values so that's why we take our search to the right so it's the opposite for left so in this case the final else statement it says if if our element K is if our array index the the item at array mid is greater than K that means we need to lower our value so we keep left the same and then we do min - 1 as our right bound and we keep the search set the same and then if all else fails then we just return negative 1 at the end so that's that that's the and end stuff but the meat of it the in the main part is this part what if we do find K what if we do find the element that we're looking for if our search type is the search where we're trying to find the first occurrence do we want to just stop if we find one K is one do we want to stop our search we can clearly see we don't want to stop our search so we see that we want to keep going to the left when do we know to keep going to the left so now let's return to our code so we know we want to keep going left when the item to the left if we have anywhere to go if if we have nowhere to go if this is the first element in the array we're finished we found the first occurrence of K if the item to the left of us is the same as us then that means we want to keep searching so that's why we going to be ending so if if there's an item in balance to our left to provoke to prevent / / indexing on our array if we can go to left and if the item to the left is the same item that we're at right now same value then we continued our search because we're not finished there's lesser ending indices to our left that are the same value so this is if the search sock is first if it's search type last if we're looking for the last occurrence we say is the guy to the right of me in balance if he is look to the right and if where I'm at is the same as the guy my right neighbor then I need to keep going to the right so I keep searching to the right so if both of these fail then we're just going to return the middle index that means we've either found the first element in the array or we're in them we're in the midst of the array and we have an element and the element to the left of it or the right is different we've found the first or last occurrence of the item we're looking for so this is the gist of the search so this is basically what the algorithm pans out to so we have login time because we're having our search space and we have all of one space in this case it's log n space because we're recursively having our search space and we're going to have log n stack frames on our on our stack so now let's go to the takeaways from this problem so what do you need to take away from this problem in this solution so first off if an array is sorted immediately think binary search even an array is sorted you automatically have the invariant of the array being sorted and you can cut it in half those space order and you can do binary search on it so that's something you should tell your interviewer because it's fast and and your inner detail impress your interviewer because you immediately shows that you're thinking about it so also be vocal to your interviewer about where you're at in the process I started out saying linear search and then in the middle of the I was like wait binary search and then the linear search and then the interviewer was like no all binary search so progressively you're going to slowly get towards the answer if you just vocalize what you're thinking vocalize what is going on in your mind and then finally this is just I was rushing and there were like four or five parameters in that function it's bad practice that anymore like to parameters in a function but in a lot of these coding questions you see three to five parameters in the interview it's fine but in real life this is not really a good idea and it's bad practice coding so I was just in a Russian that's why I pinned out that way but yeah so basically this is the solution so we find the first occurrence if we don't find it we're finished and then if you do find the first occurrence by the last occurrence do the math and then we have our answer so that's basically it that was a lot sorry it's still going [Music]

Channel: Back To Back SWE

Views: 36,001

Keywords: Back To Back SWE, Software Engineering, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies, facebook software engineer, facebook software engineering, arrays, sorting, searching arrays, searching, sorting data

Id: RlXtTF34nnE

Length: 14min 4sec (844 seconds)

Published: Wed Dec 12 2018