So?! Is David an absolute savage at algo problems or what?! Be sure to check out the Q&A interview I did with him here: th-cam.com/video/9ki1-xe6XzU/w-d-xo.html - as well as David’s TH-cam channel if you’re into competitive programming: th-cam.com/channels/XbCohpE9IoVQUD2Ifg1d1g.html
If somebody does not know this Aho-corasick algorithm, then the time complexity will be O(phoneNumberLength^2) with trie? Is there any better way to do it?
23 years of software development experience. I just feel the industry is getting to such a stage that you need 2 skill sets - One skill set for doing the job and one skill set to pass interviews!
@@jimmyadaro I just feel if it was a more mature industry, these interview processes would be more streamlined. Doctors and lawyers do not go through loops as they have a standard professional accredition. But in this industry as it is so new, you have to prove yourself over and over again. Past experience does not seem to count even if legitimate. The problem is unlike other professions, there is no real way to verify the experience.
that's true. An argument in favor of these interviews that I've heard is that big tech companies want to hire candidates who are so strong willed about joining the company that they will put in all the effort required for clearing these interviews.
For all those that watched this and feel stupid, remember David has spent 6 years coding and mentioned he used to do 40hrs a week with CP for his college years. So don't feel stupid, but do cry at the fact that it might take years to get this good.
@@azz111full definitely agree I have 6 years of commercial experience and feel the question itself is quite ok, but the speed David types the code is absolutely insane and so it is really hard to follow.
Normal people: watching horror films and yelling at the characters to get out Competitive programmers: watching coding interviews and yelling data structures at the interviewees
The easier solution is: 1. Reformat the strings to numbers. 2. Create suffix tree for the main number. 3. Check for each number if it is in the suffix tree. That will take O(numOfStrings*LengthOfNumber) time. O(numOfStrings + LengthOfNumber) space. This would be much easier..
I solved it with a hashmap. Converted the input number to a hashmap with the count of each digit, and did the same for every test word in the list. then you just compare the letter counts in both hashmaps to see if the test word can be created.
I think whats good to note is not the algorithm he used specifically but the part where he took the time to consider and evaluate different solutions before implementation.
Don't worry, there's actually nothing particularly complex in this video. There are two primary things that you will learn with experience (assuming you pursue an education in CS or software engineering): 1. Algorithms (and data structures), how they work, and their runtime efficiency (you'll understand deeply how nodes/trees are useful, how to code your own, and how/when to use existing libraries). 2. How to think about problems and the structures of code you need to solve them (like building multidimensional arrays or built-in list structures, how to iterate through them, etc.). Once you are familiar with a language, like Java, and using different data structures, plus coding your own data structures from scratch, and learning about different ways to get lower runtime, this stuff will flow from your fingertips. Like was mentioned in the video, this is pretty much all covered at the college level in data structures / algorithms courses, which is typically around year 2. Cheers
It’s a never ending process, and you got to really enjoy what you do. Formal education helps though. I completed my BS in Computer Science about a year ago and I’m sure if I had done this interview I would have just bombed it though. I took an algorithms class but frankly all I can recall from it is how to create iterative and recursive algorithms. Never even heard of Aho Corasick. Then again I work in Cyber Security and only really code for fun so my focus hasn’t been on that. Just keep at it I say.
I really wish in a real interview the interviewer would have allowed me to leave the hard portion of the implementation of the algorithm blank and to proceed with the rest of the bits and pieces of the program with the method signature intact 😂. You are awesome Clement! This would have made my life so much easier 😊.
I could be wrong, but after attempting this problem it's clear that you can also solve it (pretty quickly) by converting all of the input words into numbers (using a hashmap) and then checking if those numbers are contained in the phoneNumber input with a simple if "322" in "322245" check (for example). This gives you a space complexity of O(N = Lenght of Array) and time complexity of O(N*M) where M = Length of Word. I like the uploaded solution in this video a lot, but for many new grads and underclassmen looking for jobs who feel intimidated by this, then just know there's an equally valid and much simpler solution to this problem!
I thought the same thing! I guess the "in" check is a bit slow because for it to check if first is on second, it has to go through all the second string untill it finds the coincidence (if there's one). And the method he proposed is usefull in the sense that it uses information gained with previous checks. For example, we have "foo" and "foots" and we want to know if either of those are on "footage", if you do the "in" check for Both, the "foo" will be very fast while the "foots" one will take (the length of the word we're searching in) minus (the length of the word "foots"), with the method he proposed, after knowing that the coincidence "foo" appears on the word, we just gotta continue from there to find out that "foot" is in the word but then the coincidence breaks. So we just took two steps by using information gained with previous comparations. Is like the "foreach word: If word in theThing" but where you're allowed to use information you gain with each new word, so that makes it a bit faster (and for large enough arrays, way more faster)
@@obsidian8037 but he had to build that aho thing which who knows what complexity its has (both time space) to populate all words. He never mentioned that.
I think that would be a good idea to giveaway an interview with ex-Googler, but with a medium level question. Would be a dope content. Since I cannot even comprehend what this mastermind is saying
I regularly watch SecondThread videos and I knew since long back that he recently started working for FACEBOOK APP and was also a tester for Facebook hackercup
Basically is a normal exercise. The lenght of the phone number is in the praxis fix, so that is possible to simplify the solution. You just convert the words in number, and you build all possible permutations with these numbers. If the combination have a match with the given nbr., you find then word combination.
Most jobs are not this technical and algorithmic/data structure heavy. Your typical programming interview will probably not even do one of these challenges. Software engineers who have have been in development for many years probably cannot do this without a bit of training. This does not mean that the software engineer is not as good as the competitive programmer. In fact, being able to do these types of competitive programming questions does not even guarantee you to be a good developer. What's most important is your ability to understand and read code. Also, you need to understand what is being used in the industry and be familiar with frameworks. To land a job, what matters is that you understand the concepts and in the interview, what matters more than actually solving the problem, is HOW you solve the problem Break the problem down into little pieces and build upon it and don't forget to be inquisitive. Be disciplined in your studies and I am sure you'll be able to land a job
@@johnnycashcow1130 this is my fear. Next friday i have an interview for a programmer/tester position where i will get 1 python and 1 c++ question. C++ is good cause i did lots of embedded while in college, but havent touched python in years. I know it will be sthing simple like make a function that does sthing easy but am afraid that i am gonna get sthing like this
@@tnikoli40 Bet they asked something like jane has apple in her basket and john has oranges in his. Calculate the distance of the sun to the moon and code how to use a rocket to get there.
i assume ur experienced. why doesn't he just do let number = "3662277"; let phonePad = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] let words = ["foo", "bar", "baz", "foobar", "emo", "cap", "car", "cat"]; let works = []; for(var a=0; a
@@warpromo6636 because 90% of Google, Facebook, Amazon interviewers are super anal about you giving an optimized solution using tree structures in 30 minutes that excuses without errors. ( they themselves wouldn't be able to do it, the irony). Which is why these interview methods are broken and outdated
For those who want a simple alternative solution I made using JavaScript, not as advanced as the solution in this video, not using any special algorithms (after I heard the question, I decided to attempt it first before continuing the video) but I believe easier to understand, I have added in reply of this comment so that I don't flood this comment section, copy paste into a js file and use node to run it! :) If anyone have any comments that can help me improve on my code, do reply! I'm here to learn as well Explanations of my code: 1. I used a lookup table (mapToNumber) because it's efficient and easy to understand, key value pair. 2. I used multiple functions to try to make the code as clean as possible 3. I made sure the functions in my code are pure functions (meaning return value is only determined by its input values) 4. I used split function to determine if word exists, basically, after the split function, the returned string will change if the number string exists in the phone number, by literally using the converted word to number as the delimiter. so, example if foo = '366', the program will find the string 366 in the phone number, and if it exists, it will modify the phone number, and a check will come in to determine if the string has changed.
Instead of doing complex Aho-Corasik, we can do a lil tricky hashing stuff here. Suppose N= all the characters in input. We will map all the substrings we find from given number of length less or equal to √N to find matching in the strings size less than equal √N and for bigger strings we can manually hash match each with the given number string! Complexity: N√N*(some log factor for mapping)
Could you do one with a “typical” college student in college? Usually these people you interview are 1%er’s if that makes sense and it makes me as a computer scientist on my second year of college super intimidated and inferior.
But, to put it bluntly, that does nothing but make you feel better about your current situation in your career. Seeing a very competent Software Engineer tackle these problems helps you get a better understanding of how you should approach these interview problems.
Dont compare yourself to these guys expecting to be this good.. do it to give yourself something to strive for. Accept where you are and keep taking baby steps and before you know it youll be here
I feel like I might’ve not gotten my point across. I want to have a “typical” college student/person do it so I know how exactly they would go about the interview because I haven’t seen how THEY would go about the problems. Because everyone that has taken these mock interviews already know how to do it (for the most part) and breeze through it like nothing. The closest person we’ve seen to a “typical” interview was Tech with Tim’s.
@clement, I love how you ask questions that's simple enough to solve within the timeframe but will get great signals out of the candidate. This will be testing people on their problem solving skills instead of how well they can prep for an exam.
Second thought is that it's pretty cringe following through his interview since my thought process is very much top down compare to David's bottom up. So it's very interesting to see how we have such polarize types of engineers.
Damn dude, just go with the O(n^2) implementation and hard code the character to number conversion. There's no reason to worry about O(n^2) runtime when n is so small. If your code is simpler and takes less time to write, and isn't performance critical, it's more maintainable and easier to understand.
I was thinking about pre-calculating numbers ahead like every common word(s) (there is like 300k words in english), storing them with certain hash/bite-encode (idk how to explain aka shortcut) and then only regular binary search or something as B+ tree, so it would take time in pre-calculating phase but after it it has O(log2) space requirment is worse but it's price that you pay for fast search? I hope it makes sense a little :D
He probably doesn't want to switch. Every year he gets opportunity to set problems for mera Hackercup and commentate on it. Imagine getting paid to do what you love. Google stopped all it's cp contests
I can see the Facebook engineers adrenaline rush as he solves it, passion!! Reminds me of when clement is presenting in a video, passion!! Social cues like these are always so awesome to notice, Passion!! lol
The solution I had was- 1. A Map to store letter, numeric pair. Total keys 26. 2. Take a word, convert it to numeric equivalent value. 3. Check if phone number string contains this equivalent value. I think this is a simpler approach.
well this is not javascript it depends on which language you use. regardless he thinks on the spot and he has very good ability to communicate his thoughts which is the difference why he works at places like google, (in his case, facebook) and other people like on here, who "brag" that they can do it in much better way...but cant land a job at Starbucks because, can't speak their name properly ;/
@@milovanmilovanov2598 @Milovan Milovanov Did you see that I started the comment with "The solution I had", this was in no way demeaning to anyone and let alone you. I don't get why you got triggered and basically started ranting about stuff. Btw I did try it and when I got it, only then I posted this comment. Well your comment was distasteful here. On the name comment, please choose to accept people with different backgrounds and places trying to make the best softwares available.
I was thinking of something like this, too, but I'm thinking in python terms here. His solution is in my eyes - though appearing unnecessarily complex - actually much more elegant, as he does not check the words one by one, but all of them at once. Using a BFS here to navigate the graph of failure edges provides a major advantage when it comes to datasets much larger than the ones used for example here, as you basically build a "frontier" moving through the graph. It gathers much more results in one go.
Tbh this could have been done in such a simple way. I dont understand why ppl dont simply use arraylist/maps and existing built in datastructures, which already have utility methods that make our life so much easier.. None the less nice problem
I would have used an arraylist here however I'm not sure how to compute the space time complexity. So maybe they're after the lowest time complexity here.
That was fun. But in real interview this can be a really dangerous strategy, because interviewer must be ready for such turn of events. And Clément pointed that out, thanks.
It's a really bad habit to compare yourself to others. David is "this good" because he focuses his attention on learning and teaching rather than doubting his ability. You should watch this and feel inspired to learn!
you know, im so so happy when i created login form (not reaponsive) with simple html and css. if i compared myself to this guys, im nothing, but remember, there are people below you cant do things you do right now.. but im still hoping that i can be as good as this guys, i wont compare myself tho, but i learn from them..
Analogy: If you never learned how to ride a bicycle, the beginning of you deciding to ride one will be rough and make you wonder how is it even possible to have such control/balance on that 2 wheels thing! But if you perceiver you will eventually get to a point where you start getting it right because it's not magic but rather all about adaptation.
They practiced years for this kind of stuff and all they do afterwards is pattern matching and reuse the knowledge they already have. Mostly they lack some other concepts in CS. So don't think like that, just start solving some problems on yout own and you will see that it will get easier and easier.
Converting the array of words to equivalent number strings.. and then iterate each string and check phoneNumber.indexOf(str) != -1 to insert it to the output array.
cool! I actually came up with like 75% of the solution before seeing what he did. I was stuck at figuring out how to backtrack back once you've explored a path, and I guess there was a fancy algorithm (aho) that finds the fail links. In a real interview, I guess leaving out the aho algorithm would be ok as long as you were able to mention and talk about it.
That was pretty complex😵. If I were asked this question by an interviewer in some companies interview I would have said like the best possible solution to this problem is not trying for this company at all...!!!😂
What about using /10 and % length of the converted word? Then you can subtract the two numbers if the result is zero you've found it. Would be O(n*#words).
Clément: Coding interview done by regular mortal Also Clément: Our interviewee today is a professional competitive programmer with multiple known wins Anyone else see the problem here?
JavaScript can do this very quickly with built-in functions. Step 1, create an object (which is searchable) that has each letter mapped to a corresponding digit. For example: var digits = {}; digits.a = 2; digits.b = 2; digits.c = 2; digits.d = 3; ... Step 2, simple for loop that converts words in given input array to numerical representation: for (var word in words) { numbers.push(words[word] .split("").map(function(item) { return digits[item] }).join("")); } Step 3, return result by using "includes" function and filtering out nulls from the map: result = numbers.map(function(item, index) { if (phoneNumber.includes(item)) { return words[index]; } }).filter(function(item) { return item !== undefined; }); return result; While my solution may not be the fastest, given the easy readability and maintainability of the resulting code, I would opt for that solution over a more esoteric node approach. Just my 2 cents!
Did you learn how NOT to solve problems? I solved it in 30 seconds with something far simpler.... (or am i missing something - happy to be proved wrong) For each word in words If instr(word2number(word), phoneNumber) > 0 then output word VBscript implemetation... 0 then response.write word & ", " next %> Essentially 2 lines of code and 2 loops. See it working at https:/pragmatic365.org/google-interview.asp The whole idea of software engineering is to write as LESS lines of code as possible, not the most!!! But what do I know. I've only been coding for 42 years.
@@kevinleesmith well the thing is that they always look for the most efficient solution possible so, unless you're a genius, 30 seconds is not enough for that. Also, they want to see and hear you go through every piece of information that your brain processes, and I'd argue that that's the most important part of the interview for the interviewer. Moreover, your code uses "Instr", which is a builtin function with a complexity that, if you don't take it into consideration, might make your code way less efficient than it could be with a more complicated algorithm such as the one explained in the video. The fact that you've been coding for 42 years (deep respect for that) doesn't mean that you'd do well in a FAANG interview. However, I do believe that these interviews are stupid for 99% of the applicants since most of them are never going to have to think about and code such difficult algorithms for this sort of strange situations.
After 1 and half month of leetcode I'm actually able to solve this on my on 🥺🥺🥺last time I watched your video on this topic i thought i will never be able to solve these questions . If you're in the same spot don't give up you need to practice these questions and after sometimes you will be able to spot patters and solve the problems
Quick question! Back when you were a noob, and solving the leetcode questions, how long did it usually take you to finish the questions. Noob here, and it takes me an hour or two (even more) to solve questions which I haven't seen before
I'm not sure why it became so complicated when the problem is actually simple. Considering we have a constant of int=>['letters'] and then compare if the phonenumber(input) has it in the string. ->convert to int using the constants 1=a,b,c etc ->loop through the array of string ->substring to phonenumber -> true or false.
I started laughting so hard at 29:30 when David sai "kids" all those times haha (not kidding) Really good video, Clément, and really good interview David. I'll probably subscribe to AlgoExpert tbh, on each video you release my will increases haha
Python beginner here. I didn't understand the solution given by SecondThread (as expected), so I created my own solution for it. (its working perfectly in my testing. It can also deal with phrases being longer than number.) def letter_to_number(letter): if letter in ("a","b","c"): return 2 if letter in ("d","e","f"): return 3 if letter in ("g","h","i"): return 4 if letter in ("j","k","l"): return 5 if letter in ("m","n","o"): return 6 if letter in ("p","q","r","s"): return 7 if letter in ("t","u","v"): return 8 if letter in ("w","x","y","z"): return 9 num = input("Enter number: ") phrase = input("Enter phrases [separated by a space]: ").split() res = [[letter_to_number(a) for a in i] for i in phrase] for i in res: if not("".join([str(a) for a in i]) in num): q = res.index(i) del phrase[q] print(" ".join([str(a) for a in phrase])) Let me know what you guys think!
yep - but better using an array... For each word in words If instr(word2number(word), phoneNumber) > 0 then output word VBscript implemetation. Essentially 2 lines of code and 2 loops... ... 0 then response.write word & ", " next %> See it working at https:/pragmatic365.org/google-interview.asp The whole idea of software engineering is to write as LESS lines of code as possible, not the most!!! But what do I know. I've only been coding for 42 years.
@@kevinleesmith Thanks a lot for your message. At the time of writing my previous message I did not know any way other than (if) to convert letter to num. Later, I learned about dictionaries and used that. l . My latest code (inspired by your code) is pasted below. This is as compact as I could make it :) Maybe one day I'll learn enough to also do the aho-corasik way. Thanks for your time. def word_to_num(word): key = {'a':2,'b':2,'c':2,'d':3,'e':3,'f':3,'g':4,'h':4,'i':4,'j':5,'k':5,'l':5,'m':6,'n':6, 'o':6,'p':7,'q':7,'r':7,'s':7,'t':8,'u':8,'v':8,'w':9,'x':9,'y':9,'z':9} return "".join([str(chr) for chr in[key[chr] for chr in word]]) num = input("Enter num: ") phrase = input("Enter words [separated by space]: ").split() for word in phrase: if word_to_num(word) in num: print(word, end=" ")
I enjoy the format of these interviews and I’m curious if you as the interviewer, would be open to redefining the approach to attacking this toward a solution. If you or others would generally be open to allowing the interviewee basically change the use case to begin with the end defining the beginning. If your eyes haven’t glazed over yet, what I mean in this situation is to try and convince the interviewer up front; agree on an assumption which would reduce complexity. I realize you’re looking for construction ability, complexity, quality, efficiency, but if you could agree ahead of time on a logic-based route to completion, before coding begins, then I would say I would provide the customer all the available phone number combinations they could choose from, as the output and ask them to enter their word since they’ve probably settled on a company name and just need to find a number that can represent the name. Not targeting this instance in particular but I guess I am. Overall, would this taint the interview or would this generally be thought of positively, a perspective employee pushing back a bit right up front. I know for me, I try to dumb the complexity down (for lack of a better phrase), so I can begin with what feels like my idea or my internal translation of the ask. Thanks and sorry if I’ve bored everyone with my question.
Would love to hear Clement's answer to this question as this very situation happens... essentially with every project in software design and consulting.
You should try running the code to see if it actually works. This is one of the problems with these whiteboard exams. And you should have him comment his code too.
It’s funny watching him solve this. I would have immediately confidently said make a 2D array with each sub array holding the chars that the given phone number digit maps to. Then go through one at a time through the chars in the word we’re looking at and use a nested for loop to compare that char to the set of letters the current phone digit maps to. If a char matches, check the next letter in the word with the next set of chars. If chars match, the word is a substring. Upon first mismatch exit and do the next word. Do this for the length of the word we are comparing. Do this with a sliding window hence the nested loop. Now that I think about it that’s probably the slowest possible O(phone#length^2•wordLength)solution. 😂 I wouldn’t have thought to ask if the phone number can be more than 10 numbers either so I maybe would have thought this to be acceptable. I’m just getting my head around coding graphs and hash maps, I guess Tries are the next iteration in my data structure learning path. We skipped it in my data structures class but it seems very useful.
The super basic solution of 'for each word check if phoneNumber.find(corresponding number string of word)' is already O(#words * lengthOfPhoneNumber)??? Does Second Thread not know about Knuth Morris Pratt?
Right. Why do we need suffix trie even? In case of the trie we will need lengthOfPhoneNumber^2 to build the trie + # of all character in words to check all words. Looks substring search solution (KMP or Rabin Karp) is easier and even faster. Correct me if I am wrong.
@@vasylvo No, you both are right. There are lots of ways of doing this in O(inputSize^2), but I wanted a faster solution. I felt Aho would be better because it has a better runtime, which is usually pretty important in these interviews.
@@Garentei i am an nlp engineer and implmenting/designing fast text search is part of daily work lol so this kind of stuff comes up very often. i deal with graphs and trees daily lol
Well, translating the words into string of digits, loop for every digits string, if the digit string is contained in telephone number as a string of digits (first occurrence) return word is contained otherwise word is not contained... there are many methods to compare two strings, and we're not going to re-engineering the wheel... To further optimize, you can momoize the function that check if the "numerical" string is inside the telephone number.
So?! Is David an absolute savage at algo problems or what?! Be sure to check out the Q&A interview I did with him here: th-cam.com/video/9ki1-xe6XzU/w-d-xo.html - as well as David’s TH-cam channel if you’re into competitive programming: th-cam.com/channels/XbCohpE9IoVQUD2Ifg1d1g.html
Thanks for the interesting and fun problem! I really enjoyed the opportunity to work on it!
If somebody does not know this Aho-corasick algorithm, then the time complexity will be O(phoneNumberLength^2) with trie? Is there any better way to do it?
why is the facebook software engineer wearing google's tee??
@@same0533 That was google code jam competition tees
@@OG_Scratch oh
23 years of software development experience. I just feel the industry is getting to such a stage that you need 2 skill sets - One skill set for doing the job and one skill set to pass interviews!
Absolutely yes
@@jimmyadaro I just feel if it was a more mature industry, these interview processes would be more streamlined. Doctors and lawyers do not go through loops as they have a standard professional accredition. But in this industry as it is so new, you have to prove yourself over and over again. Past experience does not seem to count even if legitimate. The problem is unlike other professions, there is no real way to verify the experience.
Sumit you are a wise man and great comment I agree 1000% but add another thing landing on interview
before leetcode type of questions, there were whiteboard questions. I'd rather do LC type of questions than whiteboard questions.
that's true. An argument in favor of these interviews that I've heard is that big tech companies want to hire candidates who are so strong willed about joining the company that they will put in all the effort required for clearing these interviews.
dude be bussin out random algorithms that even the interviewer doesn’t know out here like “lemme use the ahoshinjinjutsu”
😂😂🤣🤣
😅 Panic mode ....
😂😂😂😂
ahhhhhhhhhhhhhhhh
😂😂😂💀
These are cool but it'd really help my ego if you hosted a mock coding interview with a candidate struggling to remember how binary search works.
Nah deadass bro I'm right with you 😂😂😂😂😂😂😂😂😂
Hahahahaha
Actually tho seeing someone struggle a lot with an interview would be interesting but I don't think the brutal internet would be very nice about it
YES that's a great idea
Better yet a candidate that doesn't know what binary search is.
12:45 honestly most impressed with him drawing out the trie in google docs, that's a skill in itself.
The speed was insane 😂
space bar go brrrrrr
@@mirsella6204 I think it goes like "tuk tuk tuktuktuk tuk"
we can scare our interviewer by saying different algo names
The Corbomite Maneuver Algorithm gives O( log(log(n)) time. Runs quick for even international phone numbers
@@lolerskates876 ok lets go with that
@@lolerskates876Can you give me a link to that algo??
I found throwing out these jargons and technicals terms on interviewers face very effective in impressing the interviewer.
yeah!! LOL
that's not just a facebook engineer, that is a competitive coder
For all those that watched this and feel stupid, remember David has spent 6 years coding and mentioned he used to do 40hrs a week with CP for his college years. So don't feel stupid, but do cry at the fact that it might take years to get this good.
I've been a developer for about 8 years and this video blew my mind 😂 there are levels to this shit
@@azz111full definitely agree I have 6 years of commercial experience and feel the question itself is quite ok, but the speed David types the code is absolutely insane and so it is really hard to follow.
thats why it's way more chilling to watch this when you haven't even started university (Yay I don't have to know all of this already xD)
what is CP?
competitive programming
Normal people: watching horror films and yelling at the characters to get out
Competitive programmers: watching coding interviews and yelling data structures at the interviewees
Lol I love this comment the most 🤣🤣
trie
🤣
I spend so much time going: why not a hash table?!
Programming interview tip: disable spell check, auto correct, turn on mono space font
The easier solution is:
1. Reformat the strings to numbers.
2. Create suffix tree for the main number.
3. Check for each number if it is in the suffix tree.
That will take O(numOfStrings*LengthOfNumber) time.
O(numOfStrings + LengthOfNumber) space.
This would be much easier..
Yes that's way easier its some sought of rabin Karp
This problem looks similar to word break problem. Is this correct?
I solved it with a hashmap. Converted the input number to a hashmap with the count of each digit, and did the same for every test word in the list.
then you just compare the letter counts in both hashmaps to see if the test word can be created.
I think whats good to note is not the algorithm he used specifically but the part where he took the time to consider and evaluate different solutions before implementation.
Just learned to declare a variable in Javascript today and then I watched this video! 🥺
You are on a right path young Jedi.
I know how you feel.
Don't worry, there's actually nothing particularly complex in this video. There are two primary things that you will learn with experience (assuming you pursue an education in CS or software engineering):
1. Algorithms (and data structures), how they work, and their runtime efficiency (you'll understand deeply how nodes/trees are useful, how to code your own, and how/when to use existing libraries).
2. How to think about problems and the structures of code you need to solve them (like building multidimensional arrays or built-in list structures, how to iterate through them, etc.).
Once you are familiar with a language, like Java, and using different data structures, plus coding your own data structures from scratch, and learning about different ways to get lower runtime, this stuff will flow from your fingertips. Like was mentioned in the video, this is pretty much all covered at the college level in data structures / algorithms courses, which is typically around year 2.
Cheers
It’s a never ending process, and you got to really enjoy what you do. Formal education helps though. I completed my BS in Computer Science about a year ago and I’m sure if I had done this interview I would have just bombed it though. I took an algorithms class but frankly all I can recall from it is how to create iterative and recursive algorithms. Never even heard of Aho Corasick. Then again I work in Cyber Security and only really code for fun so my focus hasn’t been on that. Just keep at it I say.
i swear😢
I really wish in a real interview the interviewer would have allowed me to leave the hard portion of the implementation of the algorithm blank and to proceed with the rest of the bits and pieces of the program with the method signature intact 😂. You are awesome Clement! This would have made my life so much easier 😊.
Most convoluted approach to solving a problem I have ever seen. XD
Now I want to see clem being interviewed XD
I could be wrong, but after attempting this problem it's clear that you can also solve it (pretty quickly) by converting all of the input words into numbers (using a hashmap) and then checking if those numbers are contained in the phoneNumber input with a simple if "322" in "322245" check (for example). This gives you a space complexity of O(N = Lenght of Array) and time complexity of O(N*M) where M = Length of Word. I like the uploaded solution in this video a lot, but for many new grads and underclassmen looking for jobs who feel intimidated by this, then just know there's an equally valid and much simpler solution to this problem!
Thank you for this comment. Really. I was sweating and crying at this video
I thought the same thing!
I guess the "in" check is a bit slow because for it to check if first is on second, it has to go through all the second string untill it finds the coincidence (if there's one). And the method he proposed is usefull in the sense that it uses information gained with previous checks.
For example, we have "foo" and "foots" and we want to know if either of those are on "footage", if you do the "in" check for Both, the "foo" will be very fast while the "foots" one will take (the length of the word we're searching in) minus (the length of the word "foots"), with the method he proposed, after knowing that the coincidence "foo" appears on the word, we just gotta continue from there to find out that "foot" is in the word but then the coincidence breaks. So we just took two steps by using information gained with previous comparations.
Is like the "foreach word: If word in theThing" but where you're allowed to use information you gain with each new word, so that makes it a bit faster (and for large enough arrays, way more faster)
yes.
@@obsidian8037 but he had to build that aho thing which who knows what complexity its has (both time space) to populate all words. He never mentioned that.
@@dionisorules it runs in linear time, just bfs
I think that would be a good idea to giveaway an interview with ex-Googler, but with a medium level question. Would be a dope content. Since I cannot even comprehend what this mastermind is saying
I regularly watch second threads TH-cam channel, but didn't know he was a facebook software engineer till now🔥
Same bruh
You should have checked his Facebook profile : p
i though he was a student.
@@ironyman7015 😂
I regularly watch SecondThread videos and I knew since long back that he recently started working for FACEBOOK APP and was also a tester for Facebook hackercup
Wondering if he refers to neighboring node in a graph as "bro" :-)
🤣
Kids and bros :D
@@clem hello sir , can you please provide or suggest any source to learn data structures and algorithms from absolute beginner to master level .
Basically is a normal exercise. The lenght of the phone number is in the praxis fix, so that is possible to simplify the solution. You just convert the words in number, and you build all possible permutations with these numbers. If the combination have a match with the given nbr., you find then word combination.
#include
using namespace std;
// Ques: from a numpad given a number and a vector of string of words, find all the possible words that can be formed from the number
vector solve(string number, vector &words, unordered_map &numpad)
{
vector res;
for (auto it : words)
{
string temp = "";
for (int i = 0; i < it.length(); i++)
{
temp.append(numpad[it[i]]);
}
if (number.find(temp) != string ::npos)
{
res.push_back(it);
}
}
return res;
}
int main()
{
unordered_map numpad;
numpad['b'] = '2';
numpad['a'] = '2';
numpad['c'] = '2';
numpad['d'] = '3';
numpad['e'] = '3';
numpad['f'] = '3';
numpad['g'] = '4';
numpad['h'] = '4';
numpad['i'] = '4';
numpad['j'] = '5';
numpad['k'] = '5';
numpad['l'] = '5';
numpad['m'] = '6';
numpad['n'] = '6';
numpad['o'] = '6';
numpad['p'] = '7';
numpad['q'] = '7';
numpad['r'] = '7';
numpad['s'] = '7';
numpad['t'] = '8';
numpad['u'] = '8';
numpad['v'] = '8';
numpad['w'] = '9';
numpad['x'] = '9';
numpad['y'] = '9';
numpad['z'] = '9';
string number = "3662277";
vector words = {"foo", "bar", "baz", "foobar", "emo", "cap", "car", "cat"};
vector res = solve(number, words, numpad);
for (auto it : res)
{
cout
hi
24:03 that's me in every coding interview
😂😂😂
I am jobless
Nice one.
Good one😂
Ive GOT to see this q&a video bc i am amazed how easily he walked thru all of this.
Wow I learned so much, including that I'm never gonna get a job as a programmer :D
Most jobs are not this technical and algorithmic/data structure heavy. Your typical programming interview will probably not even do one of these challenges. Software engineers who have have been in development for many years probably cannot do this without a bit of training. This does not mean that the software engineer is not as good as the competitive programmer. In fact, being able to do these types of competitive programming questions does not even guarantee you to be a good developer. What's most important is your ability to understand and read code. Also, you need to understand what is being used in the industry and be familiar with frameworks. To land a job, what matters is that you understand the concepts and in the interview, what matters more than actually solving the problem, is HOW you solve the problem Break the problem down into little pieces and build upon it and don't forget to be inquisitive. Be disciplined in your studies and I am sure you'll be able to land a job
@@johnnycashcow1130 this is my fear. Next friday i have an interview for a programmer/tester position where i will get 1 python and 1 c++ question. C++ is good cause i did lots of embedded while in college, but havent touched python in years. I know it will be sthing simple like make a function that does sthing easy but am afraid that i am gonna get sthing like this
@@tnikoli40 how it went bro
Depends on the industry
@@tnikoli40 Bet they asked something like jane has apple in her basket and john has oranges in his. Calculate the distance of the sun to the moon and code how to use a rocket to get there.
David is an absolute god not only with his quick solutions but his coherent ability to explain things very simply is awesome !!!
i assume ur experienced. why doesn't he just do
let number = "3662277";
let phonePad = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
let words = ["foo", "bar", "baz", "foobar", "emo", "cap", "car", "cat"];
let works = [];
for(var a=0; a
@@warpromo6636 because 90% of Google, Facebook, Amazon interviewers are super anal about you giving an optimized solution using tree structures in 30 minutes that excuses without errors. ( they themselves wouldn't be able to do it, the irony). Which is why these interview methods are broken and outdated
That Guy is a Mathematician!
I just studied for loops and came across this video. My self-esteem dropped to the ground. 😅
Second thread is my idol.. I follow him a lot for competitive programming
For those who want a simple alternative solution I made using JavaScript, not as advanced as the solution in this video, not using any special algorithms (after I heard the question, I decided to attempt it first before continuing the video) but I believe easier to understand, I have added in reply of this comment so that I don't flood this comment section, copy paste into a js file and use node to run it! :)
If anyone have any comments that can help me improve on my code, do reply! I'm here to learn as well
Explanations of my code:
1. I used a lookup table (mapToNumber) because it's efficient and easy to understand, key value pair.
2. I used multiple functions to try to make the code as clean as possible
3. I made sure the functions in my code are pure functions (meaning return value is only determined by its input values)
4. I used split function to determine if word exists, basically, after the split function, the returned string will change if the number string exists in the phone number, by literally using the converted word to number as the delimiter. so, example if foo = '366', the program will find the string 366 in the phone number, and if it exists, it will modify the phone number, and a check will come in to determine if the string has changed.
Instead of doing complex Aho-Corasik, we can do a lil tricky hashing stuff here.
Suppose N= all the characters in input.
We will map all the substrings we find from given number of length less or equal to √N to find matching in the strings size less than equal √N and for bigger strings we can manually hash match each with the given number string!
Complexity: N√N*(some log factor for mapping)
I dont understand any of the logic here.
Yet I enjoy watching the full video.🤣
u guys had me at the part where u were explaining how the words correspond to the numbers :D
You have to do a coding interview with the cherno he is SUPER SMART!!
Could you do one with a “typical” college student in college? Usually these people you interview are 1%er’s if that makes sense and it makes me as a computer scientist on my second year of college super intimidated and inferior.
But, to put it bluntly, that does nothing but make you feel better about your current situation in your career. Seeing a very competent Software Engineer tackle these problems helps you get a better understanding of how you should approach these interview problems.
Dont compare yourself to these guys expecting to be this good.. do it to give yourself something to strive for. Accept where you are and keep taking baby steps and before you know it youll be here
Just admire what people are able to do and strive to get better, thats all you need to do. Go your own path and don't chase after those guys.
I feel like I might’ve not gotten my point across. I want to have a “typical” college student/person do it so I know how exactly they would go about the interview because I haven’t seen how THEY would go about the problems. Because everyone that has taken these mock interviews already know how to do it (for the most part) and breeze through it like nothing. The closest person we’ve seen to a “typical” interview was Tech with Tim’s.
@@rousseau327 Sure, however, anyone soon to graduate and seek a new position are among the most likely demographic looking at these videos.
He's a facebook engineer? I thought he was a competitive programmer student.
New grad, dope channel btw I watch you both.
It's me
Pro tip: You can name drop Aho in an interview, but never call the interviewer Aho.
Ahh.... A man of culture I see XD
Lmaoo
@clement, I love how you ask questions that's simple enough to solve within the timeframe but will get great signals out of the candidate. This will be testing people on their problem solving skills instead of how well they can prep for an exam.
Second thought is that it's pretty cringe following through his interview since my thought process is very much top down compare to David's bottom up. So it's very interesting to see how we have such polarize types of engineers.
This just gave me anxiety about my upcoming interview at google😮
when the interviewee brings out the big algorithms
I don't know why but i like the way this guy talks and explains things
Damn dude, just go with the O(n^2) implementation and hard code the character to number conversion. There's no reason to worry about O(n^2) runtime when n is so small. If your code is simpler and takes less time to write, and isn't performance critical, it's more maintainable and easier to understand.
I was thinking about pre-calculating numbers ahead like every common word(s) (there is like 300k words in english), storing them with certain hash/bite-encode (idk how to explain aka shortcut) and then only regular binary search or something as B+ tree, so it would take time in pre-calculating phase but after it it has O(log2) space requirment is worse but it's price that you pay for fast search? I hope it makes sense a little :D
That is why you are not working at Google :D
@@Smoothie128 Hah, you're right :) I work at facebook instead.
@@slayemin dude stop you destroyed him
@@slayemin bruh, that's brutal 😂
skill 100 %, code readability 100 %, communication 100%, you have nailed it 2nd tread, Google is knocking your door. : )
He probably doesn't want to switch. Every year he gets opportunity to set problems for mera Hackercup and commentate on it. Imagine getting paid to do what you love.
Google stopped all it's cp contests
Petition for Clement to add this question on algoexpert
As a 18 year old with basics notions of programming, this makes me wanna spontaneously combust
Amazing... Really liked this one. Also, liked seeing some java.
I can see the Facebook engineers adrenaline rush as he solves it, passion!! Reminds me of when clement is presenting in a video, passion!! Social cues like these are always so awesome to notice, Passion!! lol
Passion!!
How impressive he knows such algorithms, How can he not forget that haha 😂
I have been watching his videos since a long time. I never knew he was in facebook. Congrats secondthread🤗🤗🤗🤗🤗🤗
He is grandmaster. So it is meta
So glad I'm working in small companies, don't deal with interviews like this and earn even better money
David is a Great programmer!! he explains everything very nicely
Thanks, wish everyone else would realize this
The solution I had was-
1. A Map to store letter, numeric pair. Total keys 26.
2. Take a word, convert it to numeric equivalent value.
3. Check if phone number string contains this equivalent value.
I think this is a simpler approach.
well this is not javascript it depends on which language you use. regardless he thinks on the spot and he has very good ability to communicate his thoughts which is the difference why he works at places like google, (in his case, facebook) and other people like on here, who "brag" that they can do it in much better way...but cant land a job at Starbucks because, can't speak their name properly ;/
@@milovanmilovanov2598 @Milovan Milovanov Did you see that I started the comment with "The solution I had", this was in no way demeaning to anyone and let alone you. I don't get why you got triggered and basically started ranting about stuff. Btw I did try it and when I got it, only then I posted this comment. Well your comment was distasteful here. On the name comment, please choose to accept people with different backgrounds and places trying to make the best softwares available.
I was thinking of something like this, too, but I'm thinking in python terms here. His solution is in my eyes - though appearing unnecessarily complex - actually much more elegant, as he does not check the words one by one, but all of them at once. Using a BFS here to navigate the graph of failure edges provides a major advantage when it comes to datasets much larger than the ones used for example here, as you basically build a "frontier" moving through the graph. It gathers much more results in one go.
Yeah, but it had to be faster. He reduced complexity. Nice job by the way 👍
oh man, the excitement I get every time I see the notification that clement uploaded a new video
Looking smart in this hair style sir. Also thank you for being such an inspiration person and thank you for helping us with your awesome videos
waiting for a HEALTHYUG google coding interview round!
Tbh this could have been done in such a simple way. I dont understand why ppl dont simply use arraylist/maps and existing built in datastructures, which already have utility methods that make our life so much easier..
None the less nice problem
I would have used an arraylist here however I'm not sure how to compute the space time complexity. So maybe they're after the lowest time complexity here.
That was fun. But in real interview this can be a really dangerous strategy, because interviewer must be ready for such turn of events. And Clément pointed that out, thanks.
Just using RegExp for this type of interview would be out of a question?
Aho-jurassicpark wtf. This dude just out here spitting theorems
watching this, i don't know if i can ever be this good
Why not?
It's a really bad habit to compare yourself to others. David is "this good" because he focuses his attention on learning and teaching rather than doubting his ability. You should watch this and feel inspired to learn!
you know, im so so happy when i created login form (not reaponsive) with simple html and css.
if i compared myself to this guys, im nothing, but remember, there are people below you cant do things you do right now..
but im still hoping that i can be as good as this guys, i wont compare myself tho, but i learn from them..
Analogy:
If you never learned how to ride a bicycle, the beginning of you deciding to ride one will be rough and make you wonder how is it even possible to have such control/balance on that 2 wheels thing!
But if you perceiver you will eventually get to a point where you start getting it right because it's not magic but rather all about adaptation.
They practiced years for this kind of stuff and all they do afterwards is pattern matching and reuse the knowledge they already have. Mostly they lack some other concepts in CS.
So don't think like that, just start solving some problems on yout own and you will see that it will get easier and easier.
Converting the array of words to equivalent number strings.. and then iterate each string and check phoneNumber.indexOf(str) != -1 to insert it to the output array.
Geat sir
Clement be like, "I know you work in a cool company but let's see if you're eligible to work at another cool company!" 😂
The most delightful coding editor out there -- google docs.... lolllllllll
cool! I actually came up with like 75% of the solution before seeing what he did. I was stuck at figuring out how to backtrack back once you've explored a path, and I guess there was a fancy algorithm (aho) that finds the fail links. In a real interview, I guess leaving out the aho algorithm would be ok as long as you were able to mention and talk about it.
Where do you work
Thank you Clement the video helped in giving an overview of how to communicate our ideas during an interview
After watching 30 mins I can't even under the question 😅😅🤣😂
Someone like clément can only put ad of his own company in his video.
Google Coding Interview With A Facebook Software Engineer who is wearing a Google T-Shirt! 😅
That was pretty complex😵. If I were asked this question by an interviewer in some companies interview I would have said like the best possible solution to this problem is not trying for this company at all...!!!😂
hahaha yeah... and for a simple phone number
He overcomplicates it though IMO, maybe because he wanted optimal complexity idk .
its not hard. You can solve it with a hash map . Its getting a super optimal sol that's hard
Hey Clement, do you have a front end expert in the works? I would totally buy that!
Man... I dont know shit. Thanks for the realization, great video xd
I already have a job in programming but watching this still makes me shit my pants.... I'm very far from his level
I don't have a job bro I am from india.
@@aj9706 I am laughing at all you people! reading the comments like i know everything! i don't know why LMAO
FINALLY ONE JAVA CODER
LOL @ Clem's reaction when SecondThread says "Aho-Corasick" for the first time 😂
Let me go ahead and use that “phone-a-friend” algorithm
What about using /10 and % length of the converted word? Then you can subtract the two numbers if the result is zero you've found it. Would be O(n*#words).
Top solution! Much better than algorithm which was implemented in video!
This is awesome but terrifying at the same time. This "Mock Interview" will lead to much bigger "applications" in the real world.
Clément: Coding interview done by regular mortal
Also Clément: Our interviewee today is a professional competitive programmer with multiple known wins
Anyone else see the problem here?
I don't understand anything but still watching it.
Guys don't give up🥺
JavaScript can do this very quickly with built-in functions.
Step 1, create an object (which is searchable) that has each letter mapped to a corresponding digit.
For example:
var digits = {};
digits.a = 2;
digits.b = 2;
digits.c = 2;
digits.d = 3;
...
Step 2, simple for loop that converts words in given input array to numerical representation:
for (var word in words) {
numbers.push(words[word]
.split("").map(function(item) {
return digits[item]
}).join(""));
}
Step 3, return result by using "includes" function and filtering out nulls from the map:
result = numbers.map(function(item, index) {
if (phoneNumber.includes(item)) {
return words[index];
}
}).filter(function(item) {
return item !== undefined;
});
return result;
While my solution may not be the fastest, given the easy readability and maintainability of the resulting code, I would opt for that solution over a more esoteric node approach. Just my 2 cents!
Nein
*Facts about clement*
Everyone: He worked at google and Facebook.
Me: He has a secret Black V-Neck shirt collection
his explanations was super clear, amazing !
Thanks a lot for this coding interview, Learned a lot from this!
Did you learn how NOT to solve problems?
I solved it in 30 seconds with something far simpler.... (or am i missing something - happy to be proved wrong)
For each word in words
If instr(word2number(word), phoneNumber) > 0 then output word
VBscript implemetation...
0 then response.write word & ", "
next
%>
Essentially 2 lines of code and 2 loops.
See it working at https:/pragmatic365.org/google-interview.asp
The whole idea of software engineering is to write as LESS lines of code as possible, not the most!!!
But what do I know.
I've only been coding for 42 years.
@@kevinleesmith well the thing is that they always look for the most efficient solution possible so, unless you're a genius, 30 seconds is not enough for that. Also, they want to see and hear you go through every piece of information that your brain processes, and I'd argue that that's the most important part of the interview for the interviewer. Moreover, your code uses "Instr", which is a builtin function with a complexity that, if you don't take it into consideration, might make your code way less efficient than it could be with a more complicated algorithm such as the one explained in the video. The fact that you've been coding for 42 years (deep respect for that) doesn't mean that you'd do well in a FAANG interview. However, I do believe that these interviews are stupid for 99% of the applicants since most of them are never going to have to think about and code such difficult algorithms for this sort of strange situations.
i want back my educational round explanations
I was on the Robotics team with David!
In High School!
After 1 and half month of leetcode I'm actually able to solve this on my on 🥺🥺🥺last time I watched your video on this topic i thought i will never be able to solve these questions . If you're in the same spot don't give up you need to practice these questions and after sometimes you will be able to spot patters and solve the problems
Is leetcode free or have to pay for it?
@@ribashkarki126 It's free for the most part. Some questions are locked behind a paywall, but the pros easily outweigh the con
What are you waiting for? get a job at google, already...
Quick question! Back when you were a noob, and solving the leetcode questions, how long did it usually take you to finish the questions.
Noob here, and it takes me an hour or two (even more) to solve questions which I haven't seen before
Knuth-Morris-Pratt algorithm is the key of succes
Please try to call gennady korotkevich on your channel for these kind of google interview.. It will be fun to see how he see these interviews..
Watch his live streams instead!
His solution's r just out of the box! I dont even dare to look at his code!!🙄
I'm not sure why it became so complicated when the problem is actually simple. Considering we have a constant of int=>['letters'] and then compare if the phonenumber(input) has it in the string.
->convert to int using the constants 1=a,b,c etc
->loop through the array of string
->substring to phonenumber
-> true or false.
Well I'm also confused as to why it had to be so complicated. I don't even think you have a worse complexity with your solution.
I started laughting so hard at 29:30 when David sai "kids" all those times haha (not kidding)
Really good video, Clément, and really good interview David. I'll probably subscribe to AlgoExpert tbh, on each video you release my will increases haha
Python beginner here. I didn't understand the solution given by SecondThread (as expected), so I created my own solution for it. (its working perfectly in my testing. It can also deal with phrases being longer than number.)
def letter_to_number(letter):
if letter in ("a","b","c"):
return 2
if letter in ("d","e","f"):
return 3
if letter in ("g","h","i"):
return 4
if letter in ("j","k","l"):
return 5
if letter in ("m","n","o"):
return 6
if letter in ("p","q","r","s"):
return 7
if letter in ("t","u","v"):
return 8
if letter in ("w","x","y","z"):
return 9
num = input("Enter number: ")
phrase = input("Enter phrases [separated by a space]: ").split()
res = [[letter_to_number(a) for a in i] for i in phrase]
for i in res:
if not("".join([str(a) for a in i]) in num):
q = res.index(i)
del phrase[q]
print(" ".join([str(a) for a in phrase]))
Let me know what you guys think!
yep - but better using an array...
For each word in words
If instr(word2number(word), phoneNumber) > 0 then output word
VBscript implemetation. Essentially 2 lines of code and 2 loops...
...
0 then response.write word & ", "
next
%>
See it working at https:/pragmatic365.org/google-interview.asp
The whole idea of software engineering is to write as LESS lines of code as possible, not the most!!!
But what do I know.
I've only been coding for 42 years.
@@kevinleesmith Thanks a lot for your message. At the time of writing my previous message I did not know any way other than (if) to convert letter to num. Later, I learned about dictionaries and used that. l . My latest code (inspired by your code) is pasted below. This is as compact as I could make it :) Maybe one day I'll learn enough to also do the aho-corasik way. Thanks for your time.
def word_to_num(word):
key = {'a':2,'b':2,'c':2,'d':3,'e':3,'f':3,'g':4,'h':4,'i':4,'j':5,'k':5,'l':5,'m':6,'n':6,
'o':6,'p':7,'q':7,'r':7,'s':7,'t':8,'u':8,'v':8,'w':9,'x':9,'y':9,'z':9}
return "".join([str(chr) for chr in[key[chr] for chr in word]])
num = input("Enter num: ")
phrase = input("Enter words [separated by space]: ").split()
for word in phrase:
if word_to_num(word) in num:
print(word, end=" ")
I enjoy the format of these interviews and I’m curious if you as the interviewer, would be open to redefining the approach to attacking this toward a solution. If you or others would generally be open to allowing the interviewee basically change the use case to begin with the end defining the beginning. If your eyes haven’t glazed over yet, what I mean in this situation is to try and convince the interviewer up front; agree on an assumption which would reduce complexity. I realize you’re looking for construction ability, complexity, quality, efficiency, but if you could agree ahead of time on a logic-based route to completion, before coding begins, then I would say I would provide the customer all the available phone number combinations they could choose from, as the output and ask them to enter their word since they’ve probably settled on a company name and just need to find a number that can represent the name.
Not targeting this instance in particular but I guess I am. Overall, would this taint the interview or would this generally be thought of positively, a perspective employee pushing back a bit right up front. I know for me, I try to dumb the complexity down (for lack of a better phrase), so I can begin with what feels like my idea or my internal translation of the ask. Thanks and sorry if I’ve bored everyone with my question.
Would love to hear Clement's answer to this question as this very situation happens... essentially with every project in software design and consulting.
He named the children nodes as kids because kids are much shorter to type, which is smart especially in a time critical coding interview using a doc.
You should try running the code to see if it actually works. This is one of the problems with these whiteboard exams. And you should have him comment his code too.
Great to see you are sticking to primitive int arrays instead of Arraylist
Towards the end you used ArrayDeque which might upset interviwers who dont have java background.
It’s funny watching him solve this. I would have immediately confidently said make a 2D array with each sub array holding the chars that the given phone number digit maps to. Then go through one at a time through the chars in the word we’re looking at and use a nested for loop to compare that char to the set of letters the current phone digit maps to. If a char matches, check the next letter in the word with the next set of chars. If chars match, the word is a substring. Upon first mismatch exit and do the next word. Do this for the length of the word we are comparing. Do this with a sliding window hence the nested loop. Now that I think about it that’s probably the slowest possible O(phone#length^2•wordLength)solution. 😂 I wouldn’t have thought to ask if the phone number can be more than 10 numbers either so I maybe would have thought this to be acceptable. I’m just getting my head around coding graphs and hash maps, I guess Tries are the next iteration in my data structure learning path. We skipped it in my data structures class but it seems very useful.
The super basic solution of 'for each word check if phoneNumber.find(corresponding number string of word)' is already O(#words * lengthOfPhoneNumber)??? Does Second Thread not know about Knuth Morris Pratt?
Right. Why do we need suffix trie even? In case of the trie we will need lengthOfPhoneNumber^2 to build the trie + # of all character in words to check all words.
Looks substring search solution (KMP or Rabin Karp) is easier and even faster. Correct me if I am wrong.
@@vasylvo No, you both are right. There are lots of ways of doing this in O(inputSize^2), but I wanted a faster solution. I felt Aho would be better because it has a better runtime, which is usually pretty important in these interviews.
David (aka second thread) completed his bachelor's degree in 2020.
And now he is full time Engineer i think
Indeed, I'm surprised you know!
@@SecondThread yeah.. from linkedin
Time while attending a coding interview goes faster than time watching someone else doing it.
this is perfect timing because i had to implement aho-corasick for work last week!!!!
What kind of work do you do? Lmao
@@Garentei i am an nlp engineer and implmenting/designing fast text search is part of daily work lol so this kind of stuff comes up very often. i deal with graphs and trees daily lol
@@skdx1000 Cool!
Well, translating the words into string of digits, loop for every digits string, if the digit string is contained in telephone number as a string of digits (first occurrence) return word is contained otherwise word is not contained... there are many methods to compare two strings, and we're not going to re-engineering the wheel... To further optimize, you can momoize the function that check if the "numerical" string is inside the telephone number.
Feels like I have studied all Data Structures, algorithms, and java programming language one interview.