Repeated DNA Sequences

[@KevinNaughtonJr]

If anyone has questions/wants help HMU on instagram or twitter instagram.com/kevinnaughtonjr/ twitter.com/KevinNaughtonJr

[@nixonatlas1371]

I dont mean to be so off topic but does anyone know a method to log back into an instagram account..? I was stupid lost my account password. I love any help you can offer me!

[@jreneew2]

With your help I've been getting past phone interviews! Thanks

[@KevinNaughtonJr]

That's awesome Drew super happy to hear that good stuff!!!!

[@codeblooded6760]

i++ + 10 😳 this guy is dangerous

[@anupampoddar7824]

you have been a constant support and motivation.thankyou sir for everything!

[@KevinNaughtonJr]

Anytime!!!

[@RagazzoKZ]

Thanks! It's an easy problem. But what about to find a 100% beating solution?

[@anonymy834]

can anyone tell me in example one, why "aaaacccca", "aaacccccaa|","aacccccaaa",etc not in the output? they also appeared more than once in the string

[@sahilbhagat5024]

same doubt

[@RagazzoKZ]

Well, you can use just two sets instead of using a hash map. Here is a javascript example: if (s.length

[@stephan24297]

In a lot languages, it's not simple to convert a set into an array. That method also requires creating more variables leading more room for error as opposed to just a simple check if it's equal to two.

[@saravanansarangan7035]

Thanks Kevin great explanation

[@KevinNaughtonJr]

Anytime Saravanan thanks for your support!

[@alexpetrash8414]

I think you are wrong with memory usage calculation, as soon as length of substring is 10 and only 4 different chars can be used, we can calculate the amount of all possible substrings, it will be 4^10 = 1048576, it is a quite big number but it is not depends on length of input string

[@rohandhekne1561]

do a video on "minimum window substring". plz

[@KevinNaughtonJr]

Rohan Dhekne I'll add it to my list!

[@ankitbug]

We can use set too.

[@ersinerdem7285]

expected rolling hash solution from you actually

[@aj9706]

Nice video.could u pls solve partition to k equal subset sum problem?

[@aj9706]

@Kevin could u solve Longest increasing subsequence and more BFS questions.

[@CodingWithPrakash_]

kzbin.info/www/bejne/Y4bIepqLpqZ5mK8

[@algorithmimplementer415]

Nice video. One question : For every character in the string, you are calling substring which is of time complexity O(n). Here n = 10, Does not it make it O((m - n) n) overall, where m = no of characters in the string?

[@algorithmimplementer415]

In my humble opinion, it would be great if you explain time complexity in generic version, not too specific to this problem, when 10 character substring is specified. Because I have seen that interviewers get happy if you explain time complexity with no assumption (which is here n = 10). :)

[@crustysoda]

you can enqueue a character and dequeue when exceed m character instead of substring. enqueue and dequeue is O(1) so overall time complexity is still O(n). In java, string is immutable so it is a bit janky and you might need StringBuilder to work instead of normal string and queue array.

[@ajr1791ze]

Which platform is best to practice for google interviews ?

[@KevinNaughtonJr]

I def think LeetCode is best

[@ajr1791ze]

@@KevinNaughtonJr Thanks I am currently using it to solve problems at least 3 / day.

[@KevinNaughtonJr]

@@ajr1791ze Anytime and that's great keep it up!

[@ajr1791ze]

@@KevinNaughtonJr Yup! Thanks.

[@thecheekychinaman6713]

This feels like it should be classified as an Easy question (as I was able to solve it lol)

[@KevinNaughtonJr]

Haha give yourself more credit!!!

[@TheTessatje123]

Thanks! I was misunderstanding the task: I thought the subsequences may not overlap (eg. "AAAAAAAAAAA" 11 chars).

[@tubedaputtar]

Can we use KMP Algorithm to find if subsequence is present in case interviewer asks for O(1) space solution?

[@cnaught0802]

Not an engineer, but love your vids. Keep it up!

[@dviyakrishnamoorthi5394]

what?

[@ninja-gh]

The same question was asked in an interview for me :(

[@vaibhavshukla444]

Which company bro

[@ninja-gh]

@@vaibhavshukla444 One of the startup company in HYD location.

[@mostinho7]

Done thanks Todo:- take notes in onenote Asking us to detect repeated substrings of length n Generate substrings of length n from original string, putting each substring generated in a hashmap, with the substring as key and value is how many times we encountered that substring. At the end return the map entries with value more than 1 O(n) because we loop through the entire original string

[@algorithmimplementer415]

@Kevin Naughton Jr. Beautiful code!

[@Gint-j9j]

Hey man, do the interviewers ask you to solve the problem in a specific language or can I solve the problem in any language I want. I'm good at Python and know only basics of Java. So if they asked me to solve the problem in any other language except for python, I'm pretty much screwed.

[@KevinNaughtonJr]

Generally speaking you're normally able to use just about whatever language you want. Some companies prefer that you stick to things like Java, Python, C, etc but it's pretty much always not a problem

[@yasvidobariya1247]

Is it accepted solution,it can't beat more than 90 percent people.

[@justinf7438]

Great video!

[@KevinNaughtonJr]

Justin F thanks Jus!!!

[@varunnarayanan8720]

Nice Thanks

[@rafailbaldal6062]

there are much better solutions out there using custom hashes , this is a very naive solution

[@sadafalam2903]

I hate that I doubt myself. I knew when he wrote the code, that the getOrDefault function would take "subsequences" instead of "seen" but of course I went against my intuition. #impostersyndrome

[@karthikrangaraju9421]

Hey @Kevin, nice solution, whenever the solution is so easy there is definitely some crazy fancy solution that is much more efficient :P I ran into Rabin-Karp: kzbin.info/www/bejne/p4Kbp4Zol9mmrqs I think we need to apply it here and we wouldn't have to build a substring for every sliding window. What do you think?

[@tushargoyaliit]

Please focus on algorithm more as many of your viewers code in C++

[@KevinNaughtonJr]

The logic should be the same regardless of the language!

[@tushargoyaliit]

@@KevinNaughtonJr yup oviously. so spend more time in logic and dont tell specifi of java that we will use that to do that. Discuss taking into account all language coders and at end might code in java. Your videos are just awesome

[@KevinNaughtonJr]

Dream Builder thanks!!!

[@joey7409]

He literally says the logic before he writes each line

[@jak0495]

@@joey7409 Everything he says is so illogical

[@SANJAYMUNDHRAindia]

The below code runs out of time on 30th test case. Can someone help me optimize it? It is in php. class Solution { /** * @param String $s * @return String[] */ function findRepeatedDnaSequences($s) { $output = []; $i=0;$j=0;$k=10; $substr = ''; $result = []; while($j