Google Coding Interview Question - Longest String Chain
Vložit
- čas přidán 17. 02. 2020
- 11th May 2022 update - I have two slots in my interview-prep group classes! errichto.com/classes
Longest String Chain is a coding interview question asked by Google. This is a little bit of string manipulation, graphs, recursion and dp... yeah. The problem is available on Leetcode: leetcode.com/problems/longest....
For coding interview preparation, I recommend www.algoexpert.io/errichto
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming #CodingInterview
Gotta love those coding interview questions! Keep it up, Kamil!
Thanks :)
What I hate though is how trite the questions are 😕
@@duckymomo7935 maybe that's also one way to detect originality in a candidate?
@@IsaacAsante17 It is so bad how companies are raising their bar these days?
@@yolopassion No, if your work has to do with optimized code and clever algorithms, then it's very reasonable for companies to expect you to know how to solve coding interview questions (especially complex ones).
You're a great teacher. The part by part breakdown was very good. I appreciate your hard work.
Thanks man. It's very hard these times to find a great content of algorithmic coding. Keep it up man!
Straight question,no bullshit and this is our Errichto
Great video! Learned a lot about problems like this. The c++ syntaxes are a little bit difficult to follow (I program in Java), but I'm gradually learning c++ so I can actually compete against others on the same plane. I saw the video that Clement posted about the rectangle problem, that problem would have probably taken me over half an hour to solve but you slaughtered it in 5 minutes, that's what led me to your channel. Keep up the good work!
Fun starts at 18:35, for those interested. The beginning of the video is also massively helpful. I've been checking several LC submissions with no luck, finally got the point with this video. Great stuff, thanks.
Such a clear cut explanation 😍
Hey bro! You are very calm composed and knowledgable! You seem like a really nice person! Thank you so much for putting in efforts to get us this content. Really thankful! And wish you a great success ahead :)
Great video with awesome explanation. Looking forward to more videos like these. Thanks a lot
I could not stop myself but to comment here. Well explained !! loved the overall approach, starting from basics and taking it all the way to lower the complexity
Thanks for awesome video !
Love your channel Errichto
Great video! I find it amazing the way you explain how to improve the complexity of a solution
This is great and really helped me a lot! Thanks Errichto!
Continue these series. Love your work
Excellent explanation Kamil! This really cleared my concepts
If L is large and A is small, a non-deterministic solution would be to compute hashes with some large prime mod.
Very elaborate explanation, really expands your understanding about the topic👌
Thanks😊
great way of explaining things.. please keep making these kind of videos
Thank you errichto.......very well explained!!
Thanks Errichto for this video.
Great question! We will have to use this one.
Very helpful!i had solved this problem before but i didnt consider removing the characters instead of adding them...thus i had an AL*2 helper function instead of L^2 ike yours wanted to see and learn how your thought process works...i too will now start analysing the problem from right to left...i have solved a lot of problems which were solved in reverse order but I guess that i still usually miss analysing from that angle...
very well explained thanks!
Awesome explanation, man!
Keep it up.
I have already solved the problem, but not in a optimised way, you are really good. while preparing for interviews i found optimising the solution is more difficult than just solving the problem.this is the kind of stuff i am looking for,Thank you for that.Could you also cover 2 pointer category which is the most asked category i noticed, like leetcode 1248,1234,1004,930,992.i found that people solve very uniquely and optimised way, that i have never seen before, if possible please make a video on this category.Thanks in advance.
For this problem, I found that python code is very short.
```
class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = {}
for word in sorted(words, key=len):
dp[word] = max(dp.get(word[:i]+word[i+1:], 0)+1 for i in range(len(word)))
return max(dp.values())
```
I tried to translate to C++. Essentially, it has the same idea. I feel that during the interview, especially for the black board coding, the code length sometimes also matters. I put the code here for reference.
```
class Solution {
public:
int longestStrChain(vector& words) {
unordered_map dp;
for(auto &word:words) dp[word] = 1;
sort(words.begin(), words.end(), [](string &a, string &b){
return a.length()
Sorting is O(N*L*log(N)) where L is length limit. Some explanation is just: sorting is slower for longer strings because in comparing two strings requires O(L) time.
I haven't tried this yet but sorting by length seemed to me the obvious first step
@@Errichto Thanks for the correction. It helps a lot.
@@Errichto isnt sorting by length with a custom comparator still O(nlogn) as you just need the length of each string which can be accessed in constant time
@errichto can you please create an udemy course for algorithms and competitive programming for beginners to advance
I think you can find out if you can go from wordOne to wordTwo in O(L) time with this approach (please correct me if im wrong):
- init two pointers for both words at index 0
- iterate over each char of the longer word (increase pointer of second word every iteration)
- increase pointer of word1 ONLY IF both characters match
- after the whole loop, check: pointer1===(pointer2-1) => valid transition, otherwise not.
i am simple nigga
i see a polish competitive programmer( erichto )
i like it
have pressed subscribe countless but even number of times
🙂
really great explanation
sheesh came in my placement test yesterday wasn't able to do that though, great video anyways thanx!
Hi thanks for the video, when I first saw this problem, I thought about graph by grouping same idea but thought it's too much writing in Java in a real interview and stop digging into it, and it's surprising to see this relatively simple implementation with graph with memoization.
questions about home office setting.
Q1: which device/application do you use for writing and drawing in the online? saw your pen.
I'm also thinking about buying something to write/drawing for zoom/skype meeting. My company mainly use windows 10 even though dev is on linux vm.
Q2: I've been setting up a home office and looking for comfortable chair as well and your chair looks good, what chair are you using?
It could be done with O(n*k) complexity using polynomial hashes with modulo to get the tiny probability of collisions prooved
Actually O(n*L) or O(sum of length of all words).
You can also have deterministic solution O(n*L*log L) using Karp-Miller-Rosenberg dictionary of basic factors up to length L.
It is possible to get rid of "log L" and obtain O(n*L) deterministic solution using using suffix array + level ancestor queries. But this overkill and probably in practice it would be slower for reasonable inputs than O(n * L^2) solution presented in the video.
Please create an course on algorithms and competitive programming from basics it's helps many like me
ayy you're doing great job!!!
Awesome solution
I am wondering if the 'removing single char from string' and then looking it up in the dictionary is actually better. We are generating another string each time, which is also O(L) work and also hashing a string is strictly speaking also not free, as hashing a string can take O(L) time -> just the hash function that internally has to map it to a hashcode.
What about just comparing all strings from one level to their next level (e.g build a hashmap of strings of length 1, 2, 3 etc.) - then we can simply compare string 'bcd' to 'bc' and give 'one free pass' if one of the chars isn't the same, something like:
let i = 0;
let j = 0;
let addedChar = false;
while (i < word.length && j < lastWord.length) {
if (lastWord[j] !== word[i]) {
if (!addedChar) {
i++;
addedChar = true;
}
else {
return false;
}
}
j++;
i++;
}
return true;
Cool stuff
Please solve some project Euler problems and give some insights into how someone should go about solving them
BTW, generally you can use unordered_map::count(key) != 0 as an alias for .contains(key) instead of using find() and comparing iterator to .end() (if not also using the iterator). It's a little bit quicker to type ;)
Notice that I needed an index anyway. Using count and then map[something] again would be double the running time. But yeah, I would just use count(key) for checking if it exists.
@@Errichto yes, agreed. That comment was a bit hasty - I didn't see you used it again at first; I edited to say generally. It's something I do - using find() != end() because there's no contains(), just out of habit.
Man...that's really cool
I am always curious to know which software do you use for writing and do you use some Apple Pencil?
Thanks a lot. The code is nice clean and efficient. I have a tiny question, could you please explain why we need (int) before the s.length() in the loop? I found some other people are also using it. I feel it is unnecessary. Could you please explain a little bit about the reason of using it? Thanks a lot.
Around line 27:
for(int j = 0; j < (int) s.length(); j ++ )
Jimmy Shen if you use geany, you don’t want warnings , that’s why !
Mainly because length returns `unsigned int`. Sometimes it can create unintentional problems, like `i < s.length() - 1` when s in an empty string, so its a good practice to typecast it to an int, so that you don't encounter them. ;)
@@ayanbanerjee3169 Thanks a lot. It is very helpful.
@@rohitgrim7383 Thanks a lot. It's a good habit to put (int) before the something.size() ..
its always better to do an initialisation of size btw... it makes code clear and easy and error free..
int n= s.size();
Now no type casting and stuff is needed and you can use just n everywhere..
what's the best complexity that we can get using trie data structure?
Easier way: sort by string length. Load dictionary with all words with value = 1. Remove 1 character from all positions for each word and check if it is in your dictionary. If it exists, then dict[predecessor] = dict[successor] + 1 where predecessor is a word with 1 less character and all its characters are in successor.
hey Errichto please make solution video for codeforces 1285E - Delete a Segment. I am not able to understand it.
Thank you
Please solve code jam problems
It’s weird how you go into detail on some simple stuff like substr() and not the algorithm part. I’ve noticed a lot of good teachers do that as well
because the substr function involves kmp algorithm which requires another explanation
thanks for the great tutorial
Could this question be solved using Trie ? if we sort the letters of each word O(N * L*log L) and insert these words into Trie, then we iterate over the Trie to get the longest path
is it my imagination, or is this a particularly involved question for an interview? There are a lot of moving parts to this one. Good to show that the interviewee has their hand on several techniques but I would think it's more than a typical applicant would be expected to come up with in less than an hour. Guess that's why I'm not a googler.
An interviewer can give you some hints, and there is a variety of solutions, including not optimal ones. The goal is to see how the candidate thinks, to just if they are able to solve the problem.
Kamil, how many offers have you gotten so far from top tech companies, also do you plan to work for google in the future?
I'm not going to Google anytime soon. I shared my thoughts on this in FAQ github.com/Errichto/youtube/wiki/FAQ
funny that YOU are solving leetcode and promoting algoexpert
If he solves those problems here, algoexpert will be dead :p
Kind of curious, how did you know that this question was asked at Google Interview. Did you get leetcode premium..
Yup, I bought Leetcode premium. I covered that in my streams at www.twitch.tv/errichto
@@Errichto
i really wanted to ask why did they reject your application for google
they must have given some feedback
i would like to know this as i am a bit confused what was it that went wrong with a coder like you
was it systems design
or some other thing
@@techwithwhiteboard3483 When did he applied tho?
Useful ;-)
What about building a trie?
If you find a new character, delete it, and then check if the previous string is equal to the current string
Errichto can you please solve this using bottom-up dp,by not using graphs.I solved it using top-bottom dp and got TLE on test 32😅
It would be really helpful if you suggest group of problems to solve to master DP in your next video. Please consider this request.
Hey guys can someone help me with the solution in java or python to this problem? im stuck and its for a job!!
Kattis has 𝑘 spare beds for visiting kittens. To make things a little bit easier to keep track of, she has made a booking system where kittens can request a bed for one or more nights.
She has just looked into the system, and realized that there are many requests for beds. In fact, there are too many to handle manually. She wants to offer beds to as many different kittens as possible, but she only has 𝑘 beds. Can you help her figure out how to accommodate as many kittens as possible?
Note that a kitten will only come if it can stay the whole time it wants to borrow a spare bed.
Input
The first line of input contains two integers 𝑛 and 𝑘 (1≤𝑘
Are these type of interview questions only asked at big tech companies?
Nope, smaller companies often try to mimic big ones, while not necessarily they should.
hmm, seems like a good one to trie.
Hi, how can i improve my thinking to your level? I mean you are fast, and your different solutions are great!
Practice :>
Get 2 place in Google code kek lul:,
@@Errichto i am 90% math person, will solving maths problems help me to get better at solving coding problems?
@@asurp7173 Yes, math helps.
what if words vector may contain duplicates
Sir do a video on important tips and tricks in and while writing code like using modulo and types of for loops and usage of auto keyword
Nice and very clean implementation !
But isn't it faster to use a Trie than hash table?
Many problems when using hash tables get solution hacked with a case full of collisions!
Niiiiice, very nice, thank you! PS: could you please put a link to the soft you're using for drawing?
This was on inside in Google
Nice.
ill just stay at mcdonalds....
Mate why u r still not in google ? Or any other FANG company ?
see Joma interview - he prefers doing competitive coding including setting questions in contests rather than being a droid for big tech
Efficient code != Maintainable and readable code
Why should I be there? ;p
Errichto, like Peter’s Parker uncle said: big power requires big responsibility, so intelligent is the same and I believe that you can use ur head on 100% load in FANG companies.
I got this question in Google Interview 😭 I failed though I hope I'll get it next time
Better luck next time brother
@@raghavkhanna6090 yeah
fail
Leet code has much simpler and faster solution using dp whithout the graph part .
Why russia s so strong in CP, what's about your discrete mathematics
because generations have passed doing CP,also culture of CP, Maths Olympiads, also many more historic and political reasons.
@@navneethingankar6486 to hum abhi tak kyo gaand mara rahe hai
great
This looks like a hard problem to me .... why is it medium :D
longest string chain
Can you help me with a more advance version of the problem, output the biggest chain of words?
Isn't this problem to find the biggest chain of words?
@@Errichto Yes, but the problem also asks to output the chain, if input is 6 B BABA BB BBA C CD, the program should output 4 B BB BBA BABA
@@ivanzanov9424 Any link? This general method is described as "recovering the best solution for optimization problems" here - codeforces.com/blog/entry/43256
@@Errichto here mendo.mk/Task.do?id=869, this was an olympiad problem in my country (if the statement isn't in english you can changed it at top right part of the site)
When you store the max value for each node, just store a pointer to the child that induced that maximum, and when you are done, print out the children in sequence.
21:46 is actually a bad practice :) It's better to reverse the condition and do nothing otherwise, i.e. remove continue. Otherwise good job!
is it only me who thinks this video is slow as compared to kamil's other videos .
wow
Yeet
fukin legend
can i be like u? :>
can u teach me the basic of coding :>
Read about islam man ♥
only watched till about 0:40 and am confident you can do this via regex instead of lame sorting. good on you google for selecting the low end of the gene pool for employees. someone needs to give these special kids a job.
all tongue in cheek ofc ;)
-_-
Pls.doo all questions from scratch by explaining them
1) leetcode
2) hackerrank
3)codechef
4) codeforces
5) hackerearth
Plsss dooo coding questions now a days people are using 80percent android...so teach and development from scratch
He has a life of his own you know :)
great