Google Coding Interview With A Facebook Software Engineer

I probably gonna use some sort of hashtable or dictionary.
Then, use some sequence of logic, true or false. Using And (logic) and length of the word.

I won't code here. But the idea is
1.) Use a hash table
2.) Iterate through the given input number
3.) Use some kind of mark numbers ex 1 if it is contained, 0 not contained -1 not yet
4.) Some logic here.
5.) Return the word if word have sequence of 1's the same as the length of the word

Just an example foo and baz
Foo. Baz
3 (def) (1) (-1)
6 (mno) (1) (-1)
6 (mno) (1) (-1) add foo to the list because the sequence of 1 from the end is not broken.
2 (abc) (1)
2 (abc) (1)
7 (pqrs) (0) don't add Baz to list because the sequence of is broken also we encounter 0.

good video

One suggestion: @clem kindly provide the question link.

It is a CP level questions. I don't think companies usually ask this question in interviews.

Damnnnn. Never thought of applying segment tree in this qn. Cp is HARD

easy problem, I could solve in 15 minutes, much simpler, but I don’t know how the performance would be compared to this guy, and in python not C.

KMP over all strings assuming m string and maximum length of phone number and each string be n will take O(m*n),
on the other hand Aho-Corasick also takes O(sum of all length *10) ie O(m*n) time only,
isn't Aho-Corasick is beneficial only in case if length of all m string are small as compare to n ?

Logically i would just convert the number into letters and do like a search for each word 🤷🏾‍♀️

Um poor thang was struggling the first ten minutes let me try to solve it and come back to watch 😂😂😂

Any tips for someone learning to code but really good at math… I.e I got the science part down just not the computer part. Most I’ve learned to do so far is code a Rock Paper Scissors game against a computer(rng)

bruh I just used a hash map. Never heard of this Aho algorithm. My time complexity is definitely slower

I'm looking at finding a job in software engineering or data engineering. I have no experience with technical interviews and am looking to see if I am ready to take one on should i be progressed. i came up with a simple solution to the problem before watching the rest of the video. After watching the video the answer given was very complex (at least for me currently). Would a simple solution be OK in this situation or are you expected to give a more in-depth answer like in the video?

Can't keep up with the answer, to difficult for me T_T

Interview: tea tea bee tea hey bee tea tea

solved this in 10 mins with two algorithmic approaches

Will KMP work here

WHAT .Language is he coding in

@clem There is a much much faster and easier solution. Find the first 10^n that is above the number to search. Calculate phone % 10^n. If does not match, divide phone by 10.
Example: Search CAR (227) in 3662277.
The 10^n just above 227 is 1000.

3662277%1000=277
366227%1000=227 <--------- FOUND!!!

Can i enter Google now? ;)

my solution for this problem: (only tested with the input in the video):

function wordsContained(phNumber, words) {
const ltrs = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
const res = [];

for (const word of words) {
if (isContained(word, 0,0)) {
res.push(word)
}
}

return res;

function isContained(word, phDigit, wordIdx) {
if (wordIdx === word.length) return true;
if (phDigit >= phNumber.length) return false;
const letters = ltrs[phNumber[+phDigit]];

if (letters.indexOf(word[wordIdx])!==-1) {
return isContained(word, phDigit, wordIdx+1)
} else {
return isContained(word, phDigit+1, wordIdx);
}
//return false
}

}

This exercise can be solved with a single line of code: result = ["".join(list(i[0])) for i in zip([tuple([str(y) for y in x]) for x in words],[tuple([str(phonedict.get(y)) for y in x]) for x in words]) if i[1] in tuple(set.union(*[set(q) for q in [[pp for pp in p if pp in [tuple([str(phonedict.get(y)) for y in x]) for x in words]] for p in [[k for k in wordsasnumberx] for wordsasnumberx in tuple( (((itertools.combinations_with_replacement(list(str(tele)),r=x)))) for x in range(0,len(str(tele))))]] if q])) ]


# if we only count the algorithm :) , the whole code has 5 lines
import itertools
tele=3662277
words=['bar', 'foo', 'car', 'cat','foobar','cap','emo']
phonedict={'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, }

result = ["".join(list(i[0])) for i in zip([tuple([str(y) for y in x]) for x in words],[tuple([str(phonedict.get(y)) for y in x]) for x in words]) if i[1] in tuple(set.union(*[set(q) for q in [[pp for pp in p if pp in [tuple([str(phonedict.get(y)) for y in x]) for x in words]] for p in [[k for k in wordsasnumberx] for wordsasnumberx in tuple( (((itertools.combinations_with_replacement(list(str(tele)),r=x)))) for x in range(0,len(str(tele))))]] if q])) ]
print(result )
['bar', 'foo', 'car', 'foobar', 'cap', 'emo']

He will create a graph that know adjacent nodes based on the list of elements, then match the phone number nodes. 🤪 Why don't just convert the dam input list to number string and just check if it existing in phone string? 😂

Hit me on my pager you better have a code lol

I just started to learn to program . Is it just me that felt this was an easy one ?
I have my own solution to this
Just let me know if my noob ass just misinterpreted the question

ref = { '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
words = ['foo','bar','baz','foobar','emo','cap','car','cat','prem','clement','clemdot']
def practice(words,Number,ref,n=0):
if n==len(Number):
return words
considered = []
for i in words:
if len(i)>n and i[n] in ref[Number[n]]:considered.append(i)
return practice(considered,Number,ref,n+1)
Its based on recursion and n is the index that we need to check and works good on all cases i tried .Please do leme know if im mistaken

Programming is a life denial occupation

20yrs ago my friend came from india as a software engineer hired by Ford on H1-B visa, he wouldn't have been able to do any of this. Back then if you could write a function and use a Sam's book or "bible" to find a method you were a hireable software engineer.

Would you guys study things like this if you didn't need to do it in order to get high paying jobs? I want to off myself before the video is even over

Going directly for a complicated algorithm is seldom recommended. Usually data is small and a simple and straightforward solution works fine. In this case, the phone number can be expected to be relatively short, not more than 20 digits. The words will also be short. But the number of words might be large. Therefore, it's probably okay if the algorithm is O(N²) in the length of the phone number, but it should be O(N) in the number of words.

Google can just keep their job if this is what they expect.

Do I really need to be this good at algorithms to get a job at Google these days? That’s just honestly discouraging.

I like your funny words Mr Aho man

the weird part is how he sees the trie as a trivial thing. If I consider using a trie in a problem, I feel happy that I could think about it :D

kids 😄😄

Nice work you're hired! Now go turn this button green.

I don't understand any shits here but still enjoy watching

This is the most stupid type of question one could receive in a coding interview, and here I’m referring to the part “any length of a phone number”. This just breaks the principle behind the exercise and the idea itself of translating the phone number. The industry is being led to an assured destruction moving forward like this. It feels like it’s past the time when Google was this kind of geeky, community-feel type-of-place where you’d code up something cool and it would then become a useful tool used by others. It’s ridiculous, and at fault is the recruitment industry that turned the most vain ideologies (“ex-this”, “ex-that”, etc etc) which makes one work 10x as hard as you used to before JUST to land an interview. It’s long past the time when your average SWE working at some medium-sized company developing websites would “volunteer themselves” into Google to create, or help create, “cool things used by millions across the globe”. I’m just so sick and tired of it. Looking for a job becomes a full-time thing in itself. Just drop it guys… It’s hurting the industry.

i'm going shifting from technician to test dev eng'g works. very interesting to see dis tuts

I would have just simplified the problem to find() in the string phonenumber after I recoded the words in the arraylist. I would have failed so bad : )

Time while attending a coding interview goes faster than time watching someone else doing it.

Just got hit by imposter syndrome

Man... I dont know shit. Thanks for the realization, great video xd

The optimal solution requires you to turn it around, find the digit representation of the words (As a string), then search for that digit-string in the original number. You lose the one-to-many complication this way, and it can be done with much less code.

I think interviewer doesn't even verify what is typed is correct, he hasn't gone through any edge cases or anything, he be like you filled the doc it must be correct

I would never hire this guy ) he cant make simple solutions that work

Damn I have been a dev for like 8 years. There is no way I would pass an interview like this 🤣🤣🤣

Man!! what a 50 min horror show, chills all over my body and that godly alohomora shit!!

Pretty cool that he implemented the hard algorithm I hadn't seen that one on a while but I think other commentators are correct to point out that the interview process has gone out of control but I like this particular problem because imo Dave is a bit too smart for his own good here, an experienced software engineer would have come up with a much faster solution which happens to be the naive one with a few bells and whistles:

two digits can comfortably fit in a byte so 15 digits can fit in 8 bytes which a modern processor can compare in one instruction. Encoding the phone number and the words into 32bit integers and then carefully shifting and comparing is extremely efficient on modern hardware. On the other hand trie traversals cripple speculative execution and the ROB usage, modern CPUs hate hierarchical data structures (or more precisely they love simple ones).

In this particular problem we would probably not have too much of a cache miss/page fault problem but generally that is another important concern with hierarchical datastructures.

I guess there is some important advice to be extracted here: asymptotic complexity virtually always lies. If we were dealing with platonic Turing machines maybe it would be important but taking advantage of the actual material conditions of the problem is what imo makes a really good engineer.

map foo to number string "366" then if(strstr(phonenumber, "366") !=null), match found.. hurray 😀. PS: Just Kidding