Google Coding Interview With A Facebook Software Engineer

what's up everybody how's it going it has been far too long since we've done a google coding interview on this channel it's been almost four months this is unchartered territory but fear not this hiatus ends with this video that's right this is another google coding interview but this time conducted not with a software engineer at google but with a software engineer at facebook no ordinary facebook software engineer though this is the one and only david also known as second thread online he is a very good competitive programmer and i know i have a thing for competitive programmers with these google coding interviews it's just so fun i will try to do a google coding interview with a non-competitive programmer in the future but this one was just super good david is a really nice guy really smart guy he is a grand master on code forces and i gave him one of the hardest questions that we have on algo expert as part of our coding interview assessments by the way if you're preparing for your coding interviews or systems design interviews do check out my company go to algo expert dot io you support clem clem for discounted platform algo expert has helped tons of software engineers land jobs at google facebook all sorts of tech companies but going back to the google coding interview i conducted this one just as i conducted any interview when i worked at google that's 45 minutes on the clock using the most delightful coding editor out there google docs at the very end of the video we did a little bit of a debrief and with that i hope that you enjoy the google coding interview okay david so are you ready to start the interview i think i am yeah we'll see all right great so i'm going to press start on the 45 minute timer now and let's begin so if you were to take out your phone right now either an iphone or an android phone and you were to look at your keypad on your phone you would likely see something like this you would likely see something like this where you've got the numbers right the digits one two three all the way to nine but you would see like on the digits you would see letters right so like under the two you would likely see abc under the three you would likely see def and this is something that was like really common in old phones they still have it in modern phones but it was really common in old phones and the reason it was common is because it allowed you to have phone numbers that kind of read like english so i don't know if you've ever heard of the company like 1 800 flowers i'll copy paste it here 1-800 flowers it's the name of a company but it's also a phone number and this phone number is actually let me copy it here this phone number is actually 1-800-356-9377 does that make sense yeah that makes sense to me i think yeah so the point that i'm trying to get across here is that if you've got a keypad like this with digits numbers phone numbers can represent different words i'll give you one more example like this phone number here can represent either clement or clem dot okay or any other like there are a bunch of other combinations of words now i want you to write an algorithm or a function that is going to take two inputs it's going to take a phone number which is going to be a stringified phone number as well as a list of words okay so i'll give you a sample input right now sample input would be these two things you've got a phone number and you've got a list of words and i want your algorithm to determine which of the words in this list of words are contained in this phone numbers kind of like the word flowers here is contained in this phone number and so for this particular input you would return something like this because these i'll put output here because these words here happen to be in this phone number so i'm looking for ones that occur anywhere in the phone number right anywhere in the phone number any substring like any continuous range yes continuous is the key word there i see i see um interesting okay so um i guess maybe first it might be helpful for me to do some simplifications okay of the of the problem a bit so yeah okay so for these words if we just want to see if some word corresponds to like some number um it's probably easier if i replace each letter with whatever number it would correspond to right so in the first instance like 3 6 6 could be a bunch of things but it might be easier like if i'm looking for foo for instance foo would be well it'd be 366. so instead of looking for for these words it might be easier if for each word i have so like for foo i could turn it into like 366. now i want to see does 366 occur anywhere in the like as any substring in this so that might be helpful um and then i can do this for for each word so for each word in the order size of input then i can look through through each of those um yeah so on one hand it seems like maybe this is possible to do some some aho classic sort of thing here but that might be a bit a bit unnecessary um i guess for like one question that i want to ask is is the phone number any specific length is the phone number might be like really really long or can i assume the phone number is just like the length of a normal phone number like seven digits or something uh you can say that the phone number can be of any length so it's effectively like any contiguous or continuous amount of digits um but you know don't worry too much about the fact that it might be past some gigantic number so i guess my point is it's not necessarily seven numbers it could be you know like 15 numbers or something like that sure but don't worry about too large of inputs so um like one solution path that i can go down would be something where the final run time would be order uh phone number length squared that would be one solution path that i might be able to use and the idea behind that would be i can find some representation for every continuous range of this phone number so if you consider every start point and every endpoint of the phone number um you'll have some some big value but what i can think about is like i can compress that value into some other value where um if some word is also equal to that value there's a very good chance those are the same and that's a thing called string hashing so i guess i'll get there if this would be a solution that would be helpful but it's about the length wrong gth there you go um so yeah so that's one one thing that i could try another thing might be if all of my words are short if i know all of my words are like some relatively small length then i can only look at the substrings that are of that length so if i know maybe all of the words aren't super long um then i can check only substrings of that length so that would be order uh like number of different word lengths times the length of the phone number so let's assume that for the words they are of any length between one so they can't be empty between one and the length of the phone number [Music] okay so yes that's a good thing to keep in mind so i guess that means this solution wouldn't be very helpful at all because it would pretty much just be the same as this this top solution um all right so then yeah i guess it might be interesting to consider um what if we what if we tried some aho karasik here so basically um we can imagine let's say i have some some try basically and the try consists of all of these words okay then what i want to find out basically is for um like for each prefix i want to see for some suffix of that prefix what's like the longest suffix that exists as some path in the try okay and then that'll have like a a link back to well the the details i guess are a little complicated but we'll be able to see like where this goes in the try and then from based on like where that goes we can take several steps um up and like repeatedly look at that and then we can mark all of the different words that we see there so yeah so i guess basically the idea is like we're gonna or one thing that i might consider for the solution path is maybe i'll build some try of um all of the words and then after that i'll have like some links for each note in the try all right yes there are only 10 digits right so i won't have 26 links i'll have 10 links um for like which trino do you reach after each step or after like reading every next possible input and i guess uh david just to cut you off here when you say you're gonna have a try of all the words will you be putting the words in the try as strings so this current format or as digit digit strings um i'll do it as digit string so basically i'll convert all of these words into digit strings and then when you enter in order to validate some yeah yeah at the end i'll have just like a bunch of digit strings and then at the end i can just say if some word matches i can just check does that digit string match as well gotcha okay um yeah okay so maybe um it might be helpful for me to draw an example for myself just to kind of remind because it's been it's been a while since i've coded aho crazy myself okay by the way i i'm not sure what uh what that is um what is it so if you want to just explain to me what the ajo classic is yeah okay can i understand i understand what you said with the with the try but i'm not sure what that that like word is or name for something is okay yeah so like um well i can explain the general idea i can definitely so like if you're if the the solution path you're looking for is n squared i can definitely go down the n squared route the thing with that is that road is completely different from the uh linear time route that i would be considering here so like going down that route i guess might be helpful if that's what you're looking for but if you're looking for something linear that like this is completely unrelated um but the idea for ajo classic is that you've got like some try so maybe let's do let's have some words maybe we have like uh bat we have the word at maybe we have att like aat for instance so the try for that would look like you have an a then you have a t but you also have it's kind of confusing because these are like the the letters i'm drawing are really the edges so you've got like this is a node here yep and then yeah i'm sure i'm sure you know know what i mean by this but yeah this is just helpful to just visualize it okay yep sure yeah um okay so this is the att i'll build this i guess i'll hold and underline it because that means that's the end of some node this is also the end of some other node and then that adds these two words we also have a80 so in in code these would be ordered but just for simplicity i will make them unordered sure and this is a t okay and then we also have bats so so this is kind of what the try would look like now the idea with ahokarasik is when we have some of these like if we have some big string oh uh okay so i guess this example is with letters but the the real example will be with digits instead of letters but i guess it's not that's fine too different so if we're looking through some string that looks like uh this maybe i guess maybe yeah yeah let's say we're looking through that string then the idea is we're going to consider every possible prefix so we'll consider the prefix a then we'll consider the prefix a t then we'll consider atb um and we'll keep going from there yep and for each prefix we want as much as possible of that prefix to be sorry there's a motorcycle that's i'm going to to be um in this try as possible yeah so in this case let's say we're looking at um just a t at the second prefix we can follow that down the try and we'll get to this a and then we get to this t yep so that would be a prefix of length two then when we see this following b we can't actually take a a b from this t so we need to follow whatever the failure link is from from this t um to the next thing that has a b so in this case if we try going up or we'll like we'll we'll try looking at the suffix like tb and if tb exists somewhere in this tri then we'll follow the tb um in this case we don't have a tb we can't do tb so we just have to look at just the b so we try just the b from the original and we get to just this node so then after reading the b we would be at this node here right then we would try to read the a um since we were at this node we follow the a link and now we get here so now we're here after reading the a then we read this t and go to this node here so the idea is that um for for each node in this try we want to say if we can't reach one of the nodes that we're looking for we want to see we're going to go up we're going to go back up to some other node and then we want to see if we go up to this node um like how far do we have to go up so that we're at some suffix of ourself like what is the the early like the best thing in the try that's some suffix of this in this case we have att we want something that would be a suffix of it it would be tts that doesn't really exist in the graph um let me look at a better example so if we're at bat if we read in this b-a-t and then we read another t yep then when we do this first after we read the b-a-t we'd be here then when we read the second t we'd be like okay well there isn't actually an outgoing edge labeled t here so we have to find the last time that that exists yeah we have to find like the the earliest fail fail link for this so this would be the suffix a t and a t does exist in the try it's this one here so we would jump to this and now we're like okay but now we can take the t link so you take this link here and then you'd end up at this node that basically tells you if you take a bunch of steps you want to know like which tri nodes do you hit basically interesting and so this is how you are able to kind of optimally like because with your example of b-a-t-t when you get to this t here and like you said you don't see the second t the fact that you're you're somehow able to jump back to this a t up here and then you get to the att this is sort of like the the optimal aspect kind of broke up for a bit oh sorry can you hear me i can now yeah yeah until like yeah you said until you said jump back was the last thing i heard yeah so i was just saying like the fact that you can quickly jump back to this a t up here is what allows like the optimal aspect of what you're describing right yeah that allows in order one i can figure out if i'm at this node and i read a t which node will have yet in the next step gotcha okay yep so the idea is there's a there's a really common algorithm that that can or i guess it's not common but there exists an algorithm to build this thing uh basically you build a try and then on top of building the try you do something else and to be honest i don't totally remember that so we'll have to figure that out live and that'll be uh i guess fun fun to watch me do but um in addition to that once you have this thing built then we can find all of the nodes that we visit in the try across reading the entire phone number right so we'll read the entire phone number we have all of these nodes in the try then we can do like a bfs from all of these nodes in the try to figure out which nodes are actually reachable and for each one of these nodes you can follow the node or the failure link for that node those are all fine okay and then um yeah so now we have all of the nodes in the try that are reachable across any substring of this phone number and now for each of these words we can just say all right the word corresponds to some node in this in the try uh was that reachable or not so that'll just give us our answer so do you mind um david writing out just very briefly like you know like i don't know maybe a bulleted list or something of the steps that you're gonna go through from start to finish sure yeah that's a good idea for sure um let me it's probably helpful for me as well um yeah okay oh i don't want it there so it's right under the output section yeah yep so the first thing i'm going to do is um build the try then as i build the try i guess this needs to be at the same time if i remember i'll cross it correctly i need to calculate the failure links for each node in the try so these two need to kind of happen in the same uh the same path i think or maybe maybe not maybe this is just second yeah i'll just do this one second so then once i have this try then um i'm going to walk through the phone number keeping track of which node in this try i'm at at each position [Music] uh like at each digit in the phone number okay that'll just use the failure lengths to find the next one in constant time and then finally once i have that like this will tell me which um which nodes are reachable like which nodes in the try are reachable and then i want to do a bfs on the like directed graph of the failure tree so now i want to do a bfs from all nodes that i was at um like in step three yep along the failure edges and by doing that once i've looked through all of these as i do this bfs along failure edges then i can see this will tell me all nodes all tri nodes that are some sub string of the phone number gotcha um and then like once i have that then i can just iterate through hitter 8 through each of each each word i guess and then check if it was visible and then just print out the answer there okay and just one quick question so this thing that you that you keep um calling aho classic is that the algorithm to build the tree or is that what that is the part that does this part right here calculates the failure links and then where you go after each step so in usually i wouldn't uh write this myself because like i don't have it memorized because it's just like a thing on paper uh so like i would always just reference that but um yeah that would do that would do this part for me it's like oops it was like a research paper that maybe people named ajo and karasik invented so yeah so that's what that's what this part does but once i have that part then uh the rest of it is all pretty straightforward so aho crosstalk just does this part to answer your question yeah i understand and so um for the sake of this interview though how about we do this let's let's skip this part for a second like let's skip the part that you just said you know is going to be difficult for you to reimplement um let's assume that we have that at that point and you can tell me you know what what whatever the the structure looks like and you can just implement this part sure okay sounds good yeah so i'll just like uh i guess write a blank method for it um and then if this were like a coding contest or like a real job then i would look it up and just paste that part in this method yep so yeah so uh is it all right if i start coding then go ahead sounds good so um like this would all be inside some class but i won't actually write the class because it'll kind of use up my indentation space so i'll just start with like some main method and then i'm going to be using java if that's already totally fine so like that's my my main method um actually maybe i'll just is it all right if i just write a method that takes in this as input like you mentioned this phone number in this words array yeah in other words yeah it can be as simple as possible as far as like the function signature you don't need to like read from standard input or something so you're going to give me this phone number and then you're also going to give me an array of all of the words that are interesting so the first thing i'll do will be static void uh two number i guess static to number um and then we'll call this phone number letters and then i'll make uh enter a phone number equals new interray so then i'll convert all of these to like a more reasonable format yes i choked so now they're just indexed zero through nine instead of the characters zero through nine so then two number um this will like convert the like some some character array into a number array um a word and then some interrelated numbers so then yeah i guess let's see is there an easier way to do this they don't all have three letters which is kind of annoying uh it would be nice if i could do some math there but it might be easier to just like card code some array for what what works here um i guess are these these words are all going to be lower case right yeah let's assume that everything is lowercase and for simplicity here um if you can just write like the first letter mapping or whatever you're describing but you don't have to write all of them because i understand what you're saying sure yeah so um so it would be something like this um so a b and c are all two the next three are all three uh et cetera so that would be like it shows like for some character what does it match to um the character is starting at a and then the rest of the method would just look like this or minus yeah minus letter so now from this we can turn some word into the phone number digits that it would represent yep yes and just to to confirm the phone numbers or the the two number gives you a list of integers you said yeah so if you pass in uh i think foo would go to 366 like we talked about earlier so but as a space array would go to 366 as an array that's an array okay yeah okay um awesome okay so now um i'm going to make a an array of integers here because i think that might be easier to handle so it'll be word letters.length by something two number of word letters so this just converts each each of these into numbers so now i'm dealing with things zero through nine uh that's a little bit easier um okay so now this is like the the ajo part i guess so um well i guess yeah yeah let's let's just i'll write out the general structure for how this ah thing works and then i'll worry about the actual algorithm in a minute all right we'll make a try node maybe i'll just call it node for try node and then this is gonna have some node array of like kids in the try so this is going to be some new node array of size 10 because there are 10 different our alphabet is of size 10. okay and then it's also going to have some node like a failure link and this would be calculated by aho and then it's also going to have a node array um like repeat fail or like uh like next with fail um and this is also connected via and this is an array actually not a not a single node so what this does is this is like if we read some letter a like i mentioned in this example up here if you have bat and then you read a t it'll say okay which node do you go to after reading the t so in this case you would go to this this node in the bottom bottom left yeah so this is what this this failed thing does um okay so i'll have this adwords signature here this will have some array word and then which index i'm at and now we want to build this try here so we'll have a try close new node and for uh enter a for each array in words then we want to add that to our try [Music] the the word and the index will be zero um i'll talk about how this like how we build this into the kids i guess because that's pretty simple so if index is equal to word word.length then we return um yeah that's fine and then um also have this return a node maybe because that might be helpful okay um just for later on and then otherwise so we know which kid we want to go to so in kid will be the word at this index this is what character of the word we're about to add to the try so now if kids at this kid is equal to null then kids that this kid will be a new node and then we want to return oh this would just return this node here but then otherwise we would return kids at kid dot add word um the same word and then the index plus one like go to the next character in that so this will build our triforce basically so okay so now where was i so we add each of these um we also it's probably helpful instead of doing a forage loop here i probably want to do a regular for loop to make looking up the answers more easy so we'll also make a oops on node array like end at those new node array so now i can store um for each word which node in the try that word corresponds to since this part is just linear then this whole thing runs in order size of input so order total number of characters in the words okay so now um like at this point i would want to build the yahoo so we'll worry about that in a minute if we have time uh then after that i want to go through the phone number so for i and phone number um we want to work with that we also want to store which node we're at so this is like it starts at the tri node the root of the try after each step we will take this next with fail link uh to see which node we are after reading the next character so at will be um adjust this index we also want to mark all of these as visited i guess all yeah yeah or false um so now we'll say at dot visited equals true up here then also in this case after we visit after we visit a new node visited so we know all of the nodes that are visited here uh now i want to do a bfs so this is the bfs part um first i need to get all of my nodes that are visited here so i'll have a dfs method to add stuff to some some q so in c plus plus you could just use a q it would look like this q of node um i think you said earlier that you don't usually code in java but the java equivalent of this is called an array deck okay oh we already dq yeah yeah yeah so it's like a double enqueue i'm only going to use it as a normal queue but this is like the fastest equivalent for it so this is what people usually use okay um so this is the the bfs list so now for node kid in nodes um if this kid is not equal to null then bfs.add last this kid or i guess we'll just dfs from it right so dfs from dfs pass in the same same queue and then finally if i'm visited so if visited then bfs.ad okay very cool um so now we yeah i need to add these all this q so this is array deck of nodes which i'm calling dfs and now i want to say uh the root of the try which is just try called try.dfs pass in this list this will fill up all of the start nodes for my bfs so now any node here is one of the nodes that we were at when we were looking through the phone number to see which node in the try we were at okay so that's that's like what's going on so far now finally i just need to do this bfs so while not bfs dot is empty um node next will be dfs.remove first if next dot fail link is not equal to null and next dot fail link dot visited or if it's not visited then uh next dot fail link dot visited equals true and then add that to our bfs um okay so yeah so this will now mark all recursive like suffixes so in this case if the string were just uh if the phone number were just like the equivalent of the word bat then we would have this but in addition to marking you can see b you can see b and you can see t i need to recursively say okay you can also see a t and then you could also see just t as well sure so that's what this bfs is doing yep right um awesome awesome so now finally i just need to return this answer so um what did i say i just wanted to turn i'll say we'll return an arraylist of uh should i do you want me to return like the indices or the actual words i can do either same difficulty for me let's return this the words and in no particular order sounds good i'll just do the same same order as input that's all right sure so now for um for each of these what did i call this for each of these end at nodes i just need to see okay this each of these words corresponds to some place in the try i just want to see whatever this corresponds to was that something i was able to visit in my bfs so for um zero i is less than end at that length plus then we'll have this arraylist of strings to return your arraylist so yeah okay so if end at i dot visited that means this occurs as some substring of the target string so then what i want to do is add this to the list of things that i can visit and this will be word letters um and then i just return that at the end um okay very cool so yeah so there's there's one part that i'm still missing here i guess and that's this build aho part this is the the black box that i've left um would it be maybe a good idea for me to just walk through this whole thing for you first or should i start working on like reinventing the wheel here yeah let's let's start by having you walk me through uh the entire algorithm and you can see if you feel like confident in it and also if you can walk me through um the overall time complexity and space complexity i suppose um by going through it all sure yeah so okay so here's like the i'll kind of separate this with some comments on what's going on here so this first part is just like use a format that i'm comfortable with which is just all numbers that way i can index things without having a bunch of empty space so this is just like make it more comfortable all this does is use numbers instead of letters everywhere uh so the great part about this instead of 9e is we do get spell spell check you do get there's one upside if there's one offside decoding in google docs that's it yeah so then google docs isn't delightful otherwise i mean if it had a dark theme maybe they changed my mind you just gotta you gotta have that um all right so anyway yeah so for this part this is just like build a try um and then the yahoo crosstak just runs on top of this try okay so um i guess let's walk into this adword method so i'm gonna scroll down to that and then talk about that yep so the edward this is just like kind of classic um college level intro uh to data structures build a try so the idea is we're going to pass in this array and c plus this is like pass by reference so in c plus plus it's equivalent to that in java this doesn't copy the whole thing it just passes a reference to it so this is like order one calling this method yep um but anyway yeah so if uh this means if we're at the end of some word then we just return this node so this will return whatever trinode corresponds to this word assuming we've already processed index number of letters in it okay then we want to look at which kid we should go to from this node so that'll be this part right here and then um if that kid is null that means we haven't seen so like let's say we're at like 80 or whatever we haven't seen another t yet so we need to make a new tri node for that so we don't have a null pointer exception that's just what this does yep um and then we just recursively ask our kid well for the rest of the word what would we be at so since the rest of the method works that part will work as well because we have our base case here sure so yeah so that's how we build the try uh then we would run aho which i'm pretty sure we can do just with the bfs going down the try um but yeah so anyway but then just moving on from there sorry david just to cut you off could you can you um add also the like time complexity of each of these parts sure yeah for sure so um this part here this is like order sum of sizes some of uh of word sizes yeah the total number of characters in the entire words array is what you're saying yeah exactly exactly uh and it's both that size and space complexity worst case yes um and then uh yeah what else is this so this ajo is the same thing so it's order uh sum of the word lengths as well so run size it runs in linear time it's just a bfs yeah just a clever bfs um and then this part what am i doing here um oh okay yeah this is just like we mark like we we literally just traverse through this thing so it might be more helpful to put this here this is like uh we just walk through the phone number part so this part here will just be order um length of phone number for that much time and then order one space um but i guess we're already storing the phone number here so we're not going to be order like the phone number space anyway like in the in the grand scheme of things but i guess that's not too important so what this does is just aho will give us if we fail for each letter where do we go to and that's calculated uh in this oh i've done something that's calculated in this part here if i were to write that method um so we can just walk through the try for each next step saying what character do we go to and then we mark all of those as visited saying like you can get here from some prefix of the characters and then by doing this bfs right after we want to say for the rest of the characters that are some suffix of each of these trinodes that are visible which ones of those can you hit right so then this bfs here it's just a normal bfs so since the total number of nodes is the total length of the sum like the sum of the word lengths then this bfs will run in that time because the number of edges is just the same as the the number of nodes because the number of edges is a tree basically yeah so this part is also order um some of the word lights okay very cool and then yeah finally at the end we just iterate through so we stored for each word that we're considering which trinode does this correspond to um so i just iterate through each of those and say okay if this node was something that's a suffix of one of the trinomials we were at while iterating through the phone number that means you can make it by some suffix so i add it here right and uh yeah that's the idea behind it this this dfs just like looks through all nodes so that's not really worth covering i don't think yep and so i'm pretty confident in the general idea it might not compile i might have like i might be missing a semicolon or something uh but that would be pretty easy to fix if i had like uh if i were able to compile it yep exactly um yeah and i don't think we need to check that right now um i think you know we could check that if we wanted to but i don't think it's too super important here and so overall um the the total complexity of this algorithm is oh sure yeah yeah i should definitely cover that so overall it's order uh length of phone number plus sum of word lengths uh that size and space now if you don't count the space of the phone number letter so if you don't count the space of this array then it would just be this much member this much time and the memory would just be so it'd be this much uh time the space would just be the sum of word lengths for the space oh yes that's not true no no because i i make an array somewhere so it's both this time and space okay uh just kidding uh like the the reason the reason it uses that much space is because i make this end at array wait a minute um hang on give me give me like 10 seconds here then i can get you an answer take your time yeah so it's not it's not uh it's actually the space complexity is order sum of word lengths this is just the time and for you're still there right i am yeah yeah and so the the the reason it's some of the word lengths especially with regards to the tree is because in the tree we're in the try um effectively like you have each word at most once and even some characters are repeated like some characters will be kind of like duplicated okay yeah so it's probably going to be a little bit less but like worst case it might be you might have every character or almost every character right okay and then of course we have also like the the digit phone numbers and all that but those are all either the same or or less than that yeah yeah okay i suppose yeah this might make it linear on the phone number length as well but that's kind of like uh small details i guess that aren't too too relevant oh yes if you're yeah if you're creating also the phone number if you're storing that as an additional thing but yes okay so yeah okay great awesome well yeah thank you for the interview i appreciate it it was a fun problem for sure at this point i think we're we're done thanks so much uh david but this is like right on time we've got one minute left so maybe now we can do like a quick uh debrief so maybe like why don't you start by telling me and the audience like yeah what did you think about the problem and how do you think you you did and all that well it was a it was a really good problem i really enjoyed the problem um it was super cool i guess it would have been helpful if i had like coded this recently because it would be easier to like not have to i guess black box that when i'm explaining how it works it would be easier to just not say this is like a well-known thing and instead just explain it like for the first time um but yeah so i guess like this is the main thing that i wish that i had done better this uh having this black box here right um but but beside that i think i don't know i feel like uh i was pretty comfortable for for most of it and i think it went pretty well i guess i don't think it's possible to do better than this runtime if you're doing everything in a single processor i think this is the best you can possibly do so i don't think there's like a better solution out there that i'm missing maybe i don't know i'd love to hear is there just a simpler way of doing this that i just didn't see no so i guess like if you want to i'll give you like my thoughts um so i think you did super well from an algorithmic point of view i think you did um you know really fantastic and i really want to emphasize this to the viewers like the solution that david covered is not the solution that i personally would expect in an interview um i went with it like at the very beginning you even asked me you were like do we care about this solution or do we care about the like n squared solution or whatever at the top like if you if you scroll up you had written a different solution path uh david and in an interview i would i would not expect someone to go to go through this with the um the like aho algorithm and all that um and i was expecting more of a you know you can build kind of a uh what's the word like a a simpler version of a suffix tree kind of structure that would run in and squared time uh with respect to the length of the phone number for example if you if you dump every every suffix in the phone number in that in that tree and that would be like acceptable in a coding interview but david like knew about something even fancier and even better went with it i think it was great um i think it was better to not have you write out the aho algorithm because like at that point like i trust that you are that you are familiar with that and that you kind of know how it works and it's i think it's a i've gotten enough signal from your you know algorithm skills i don't need you to jump into that and to try to reinvent the wheel like you said and you would probably just use that from like a library or something if you if you really needed it on the job and then yeah you were communicating really well i didn't lose track of you at any point the the one like super tiny knit that i will give you david if you want is just like here with the bfs i got a tiny bit confused because you named oops because you named um yeah i just use my here's my i hope by the way but yeah anyway sorry what were you saying for about the bfs yeah i was just saying uh that you you named the um you named you named the the the cue bffs which i found a tiny bit confusing because like you used dfs as a verb but here bffs effectively is like as like a noun of the key the name of my cue yeah yeah maybe i could have done a better job there for sure but i mean that's like an unknit and i ended up following you but you see like here like tree.dfs passing in bfs like reads a little bit like a bit confusing yeah yeah but apart from that like yeah great job like like i said um yeah all the the rest of the code was great and uh you your communication is like fantastic you you walked me through everything totally understood like and again like you know i gotta commend you for being able to explain something that is a complex algorithm with a with a an even more complex solution than maybe the the expected one um to someone who might not be familiar with you know the way the algorithm runs and everything on google doc so great job well thank you i appreciate it and it was a fun interview for sure i enjoyed the experience awesome well um maybe you know if anybody's curious they can go check out uh they can go look up aho maybe i'll put the a link in the description below to that uh thanks again so much to david for for being down to to do this interview um go check out his channel i'll put the link to it in the description and in the comments below he's got a great channel great guy great competitive programmer and um thanks a lot for for doing this david yeah thanks for having me if you made it this far don't forget to smash the like button subscribe to the channel if you haven't already and i'll see you in the next video

Channel: Clément Mihailescu

Views: 486,189

Rating: 4.8713202 out of 5

Keywords: google coding interview, google coding interview questions, google coding interview preparation, coding interview google, coding interview, coding interview questions and answers, mock coding interview, technical interview with a google engineer, real coding interview, competitive programming, google coding interview with a competitive programmer, SecondThread, facebook coding interview, facebook coding interview questions, facebook software engineer interview, facebook interview

Id: PIeiiceWe_w

Length: 49min 59sec (2999 seconds)

Published: Thu Sep 17 2020