I got an idea at the beginning of the interview, i don't know if it's valid or not yet, i haven't tested it yet, Here is my solution and I would love to hear your Opinion: 1- Get the length of the smaller string 2- Get the ascii code of each char in the smaller string and multiply them 3- loop against the Large string with taking parts of the string with same length of the smaller one starting with every index in the large string and compare the multiplication of the ascii code of both, if they are the same then count it
I don't know it is because of C++. I felt like you made it quite complicated. you easily could have sliced the big string with a length of a small string while iterating. for i in range(len(bigS)-2): print(bigS[i:i+3]) cba bab abc bca cac aca ... ... .. bca While iterating, choose it. please correct me, if I am wrong.
@@sindhukumariparameswaran2168 Generating all the permutations is a task with very high time complexity O(n!), which after exponential is the worst possible complexity one can get.
@@salmanbehen4384 yes it is a brute force technique. No extra space in brute force. comparatively it is much better than the one in the video. plz share your solution for this problem.
This is really a difficult thing to do . Really amazing that you have the audacity to do it. Don't know why, I was breathing heavily while watching this.
Clément is everywhere. And so is her girlfriend Meghan. Like I literally see her AlgoExpert advertisement in every tech video I watch (Including this one).
Here's a video of me sharing the whole Interview experience- ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-5ssx01gxmWA.html If you want to understand the technique I used in the question, refer to this video - ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-SaI2PHJNNVU.html Link for algoexpert with the promo code for additional discount - www.algoexpert.io/keerti Our first Interview at @Clément Mihailescu 's channel is here - ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-rw4s4M3hFfs.html
If S is small like you say then one possible approach is to assign each letter of the alphabet to a prime number, for example: 'a' = 2, 'b' = 3, 'c' = 5, 'd' = 7, .... Then calculate a number for the value of s by multiplying all the values together. For example, for s = "ab", the value is "2*3=6". Now any sub string of b will be a permutation of s if and only if its value is 6 (This follows from the prime factorization theorem). You can calculate this "value" in a rolling basis for an algorithm to run in O(|b|) Last note: s must be small or you'll overflow the value. Running example: s="ab" so value we want is 2 * 3 = 6. Current window in b is ["ba"], value1 = 3*2=6. value1=required value so output "ba" Current window in b is ["ab"], value2 = value1/3 * 3 = 6 = required value so output "ab" Current window in b is ["bb"], value3 = value2/2 * 3 = 9 =/= required value Current window in b is ["ba"], value4 = value3/3 * 2 = 6 = required value so output "ba" This is a very similar approach to the Rabin Karp hashing function, only difference is that one searches for exact matches, this "hashing" function searches only for permutations.
Associate each character with a prime number. If we have 26 characters we associate each of them with each of the first 26 prime numbers. A string can be represent as a prime product. Two strings are anagrams if and only if their prime product is the same. For example "aabc" and "baac" are anagrams because 2*2*3*5 = 3*2*2*5. The unique factorization of integers using prime numbers gives us that only anagrams have same prime product. Compute the prime product of the smaller string, use a sliding window on the bigger string. As the window moves right, multiply the running product by the right most character's prime association and divide the product by left most character's prime association.
This sounds clever at first, but is slow and impractical. Primes increase pretty fast, the 26th prime is 101. Also he said all ASCII characters are possible, so we need the first 256 primes. There is no limit on the smaller string's length, so you could have a product of thousands of numbers. Eg smallString="A*1000", the associated number is 2^1000.
The very first thing which came to my mind is Rabin-karp with sliding window. We can create a hashCode of the smaller string based on 26 char or May be ascii values and then we can keep adding and checking that the current hashcode is mathching with current window. if yes, then it is a permutation
The question is very similar to anargam search question. Take a string array and if the anargam search is true then add the substring to the string array . At last return the String array. Mock Interview was amazing . Great job Mam. Keep Going.
Really great !! The way of clearing the doubts regarding the q and speaking out the thoughts is just amazing. It was very informative and knowledgeable !!💯
Awesome video...I was asked the same sort of question in an interview and I solved this using one map.We can keep the count of distinct characters of the small string and whenever a matching character found in big string, we can reduce its count in the map by 1 and whenever we remove a matching character, increase the count by two and whenever count becomes zero we increment the number of matching characters by 1 and when it becomes non-equal to zero we decrement the number of matching characters. So, when the number of matching characters is equal to the number of distinct characters in the small string, we find a valid combination.
Great video ! An example of interview between junior vs senior engineer by @clem. As an interviewer conducting many coding and design at Meta, this would be straight reject for E5/L5+ senior engineer role since @KeertiPurswani was not able to articulate the approach before starting to code. Even for junior or college entry level, It would be still be a medium confidence hire at FAANG companies. Unfortunately in such market where folks straight out of college can solve 2 hards in 45 mins interview, we now value thought process more than quantity.
Lady's solution will NOT work if the small string contains duplicate characters. She needs to change the condition for incrementing and decrementing the temporary counter Ctr. Increment when number of character occurrences in small string is only greater or equal to those in the current sliding window (i.e. >=, not just ==). Decrement when number of character occurrences in small string is only greater than those in the current sliding window.
I don't know if I am right, but I solved it in this way: for t in range(int(input())): bs = input() ss = input() strSum = sum([ord(i) for i in ss]) n = len(ss) cnt = 0 for i in range(0, len(bs)-n+1): tempSum = sum(ord(j) for j in bs[i:i+n]) if tempSum == strSum: cnt += 1 print(cnt)
The second for loop should run till < (n - l) as you are checking for element (i + l). For a scenario, n = 8 and l = 3 i = n - l = 5 and if you check for (i + l) = 8 , it will throw indexOutOfBounds Exception. P.S. Loved the explanation and approach , helped me think more better
Sanyam, This will also not works. In your case : If n=8 and l=3 then then our second loop will run till < (n-l) i.e < 5. so we should miss this check (5,6,7) pair. Better we can use the below to achieve. //Sample working pseudo code : for(int i=1;i
Woww that was really brave i guess. Love the courage coming up with an interview (google like) on the channel for thousands people to see. It was really helpful. Thank you so much 👏
Typescript solution: // Time O(N+M), Space O(M) where N is long string length and M is short string length export function countPermutationOccurrencesInString(longStr: string, shortStr: string): number { // Base cases if (!longStr || !shortStr || longStr.length < shortStr.length) { return 0; } const incrementCharFreq = (freqs: { [key: string]: number }, char: string): void => { if (freqs[char] === undefined) { freqs[char] = 1; } else { freqs[char]++; } }; const decrementCharFreq = (freqs: { [key: string]: number }, char: string): void => { if (freqs[char] > 0) { freqs[char]--; } }; // Get character occurrences in short string const shortStrFreqs: { [key: string]: number } = {}; for (let i = 0; i < shortStr.length; i++) { const char: string = shortStr[i]; incrementCharFreq(shortStrFreqs, char); } let currCount: number = 0; // Process the first window const longStrFreqs: { [key: string]: number } = {}; for (let i = 0; i < shortStr.length; i++) { const char: string = longStr[i]; if (shortStrFreqs[char]) { incrementCharFreq(longStrFreqs, char); if (longStrFreqs[char]
Great Video Keerti! Just a couple of clarifications on your choice of DS. Initially, after I heard the question, I too came up with a two-pointer approach. I wanted to know why you chose to use a Map instead of char[128] which helps keep track of all the ASCII characters and, ultimately, we just compare the count of characters in the small string and the count of characters in the window. The comparison takes O(1) since it's always 128 comparisons, independent of the length of the big or the small string. Please let me know if you had a particular choice you went with map
Thanks for the comment! You are right. I have taken variables n and m. The map size won't be more than 128 but n,m can be (repeating chars) But if you notice, my code doesn't woek for repeating chars. So, I could have mentioned that!
I have 6 yrs of exercise as a Software Engineer but after college I didn't kept taken this subject serious, now will start learning these DSA concepts.
for question 1 -> you can do this by 1 map also , for small string you can increment it and for your window in big string you can decrement it accordingly to get 0 as count if it's a permutation
But then you have lost your info about the chars in small string. So we need to keep the small string map unaltered as there are multiple instances in the big string we need to check.
Keerti, you're truly talented. Just take a second to pat yourself on the back for how difficult this is and how beautifully you composed yourself. Keep going. Never doubt thyself.
The way I solved it is, I added the small string into a character set and from starting point of big string, I took the sub-string of length of small string and checked if all characters are contained in small string and it gave the answer (that set search complexity is constant and we are only going through the big string one time and also not bothered by permutations as set will take care of it, so it is total O(n) complexity). I thought it was simple, not sure if I am doing some major blunder. It did give me all 6 variations in this example. (of course this is not compare real-time interview nervousness, kuddos to her for attempting it)
Thank you for this video.. I learned a lot.. U did very well.. U r very confidant during entire interview.. I'm third year CS student, I don't know why but after seeing this I'm lil scared..
The logic fails when i = 3, you need to decrement the bigStringCounter first, if you increment it, it will become 2 for character a, then count wont match, it will not increment the result counter.
How come the space complexity be O(m) + O(n)? As we are dealing with characters and total 256 ascii values are there so the max size of map could be 256 which is fixed(constant) and hence space complexity should not depend on the length of strings.
# for a fixed length of the small string (3) big = "cbabcacabca" small = "abc" permutations = perm(small) count = 0 for p in permutations: big_temp = big while p in big_temp: count = count + 1 big_temp = big_temp.replace(p, "", 1) print(f"permutation: {p}") print("--------------------------") print(f"# of occurrences: {count}")
I have one more solution : 1.) Create a vector list and store all the permutation and combination of smallest string in it without repitition 2.) In the big string find each string stored in the vector list and print it the number of times it is found in the big string . I am attaching the c++ code for this . #include #include #include using namespace std; int checkList(std::vector List, std::string s) { for(int i = 0 ; i < List.size(); ++i) { if(List[i].compare(s) == 0) return 1; } return 0; } void totalPermutations(string str, std::vector& listOfStrings){ //printf(" main string is %s ", str.c_str()); if(str.size() == 1) { listOfStrings.push_back(str); return; } for(int i = 0 ; i < str.size(); ++i){ if(i != 0) { char temp = str.at(0); str.at(0) = str.at(i); str.at(i) = temp; } string tempStr = str.substr(1); std::vector list; totalPermutations(tempStr,list); for(int k = 0; k < list.size(); ++k) { tempStr.clear(); tempStr.push_back(str.at(0)); tempStr = tempStr + list[k]; //printf(" pushing string %s ", tempStr.c_str()); if(!checkList(listOfStrings,tempStr)){ listOfStrings.push_back(tempStr); } } } } int main() { char BigStr[100]; char smallStr[50]; printf(" please input the Bigs string : "); scanf("%s",BigStr); printf(" please input the small string : "); scanf("%s",smallStr); string str1 = smallStr; string str2 = BigStr; std::vectorlist; totalPermutations(str1,list); printf(" All matched string from are : "); for(int j = 0; j < list.size(); ++j) { // printf(" %s ", list[j].c_str()); size_t find = -1; while(1) { find = str2.find(list[j],find+1); if(find != string::npos) printf(" %s", list[j].c_str()); else break; } } printf(" "); }
I have seen your interview on Clement's channel. It was a good one. I came here though your LinkedIn profile. Didn't know you also have a RU-vid channel as well. Keep doing the nice work. I am going to subscribe to it.
Really Brave of you to do this and upload for us to see. Just a quick question though, Shouldn't L be equal to the number of keys in smallStringCharCount?
i did this in python from itertools import permutations bigstring = "tttttttttcbabcacabca" smallstring = "abca" perms = [''.join(p) for p in permutations(smallstring)] len_small = len(smallstring) len_big = len(bigstring) counter = 0 for i in range(1+len_big-len_small): tempstring = bigstring[i:i+len_small] if tempstring in perms: counter +=1 print(tempstring) print(counter)
Hey Keerti, I guess your solution is incorrect. If the small string is aab. Your ctr will be 2 but it should have been 3 if the string matches. I am taking about thr second for loop, the one from 0 to l
Why complicate things. We can use something like below public static void printsoln() { String smallString = "abc"; String bigString = "cbabcacabca"; int window = smallString.length(); for(int i=0;i
Hi Keerti If there is a question related to advanced data structure such as a graph or tree, then are we also expected to write code to take a tree as input? Obviously we can always hard code a particular tree, but are we expected to take inputs from a user and construct tree from user and then pass it to the required function? So, for example, if question is to find height of a tree, then there would be a function to find height which takes tree node as input. So, are we required to input that tree from user. If question is specifically to convert given list to tree, then obviously we have to code it, but i am talking about other cases.
First I will find triplet of bigger string. The by the help of inbuilt library I will find permutations of second string. Then I will check if element in triplet is present in elements in permutations of second string we will append that elements in empty list,and we will return that list. Solved from python
Umm, if we take longString = "defabc...." and smallString = "abc", then for second for loop where we compare bigStringCharCount[bigString[i]] == smallStringCharCount[bigString[i]], will this give an error for characters = d,e,f, since they are not present in smallStringCharCount? And if it doesn't will it initialize them in smallStringCharCount with default value 0?
I havent seen her explantion but i think i had solved in leetcode long back, we can first remove all chars in big string not in small string , then use sliding window. 1 map is enough wen u find the match u decrement the value of that char , idea is if u get vals of all char as 0 then its permutation( to determine peutation fpund u can use a set along woth idea of getting 0 for all chars in map), and as u slide ch by char u can optimize in the way u slide ahead , ther can be cases u can jump by multiple places ahead not just 1. So thats the jist O(n) time n space
1-> split the bigString into [ list ] where every single index stores one individual character 2-> get length of smallString 3-> loop through list bigString with [ i, i+1, i+2] 4-> store it into separate strings with length of smallString : String1 , String 2 (here smallString len = 3 , so String1 = cba) 5-> continue till end of bigString List after 6-> count = 0 7-> split smallString into List 8-> now compare each element of ( smallString List ) with String1, if all elements available in String1 then count+=1 9-> do this for all the Strings1, 2 , 3.... 10-> final result = count
Hi Keerti, that was an awesome interview.....excellent problem solving skills.....to be honest I would be very nervous as well.....just in case was wondering that if "smallString" has repeated characters(duplicate characters e.g. abb) then "l"(length of small string) would be 3 but "ctr" would store 2 which could result into different result...just a query from my end.
I think the count needs to match the number of unique characters (which is the number of keys in the dictionary) since it’s really meant to count how many characters have the same freq in each string
i think there is another way i don't know its efficient way or the way is correct lets assume that the buildings in the dictionary is always in the same order traverse through the block and put the true and false no in an array eg gym is true and school true and store is false then array[1,1,0] if we add all the dictionary it will become a big array of 1's and 0's q=0 for(i=0;i=0){ q=q-len(req) if a[q]==1 { c++,break}c++}} j=j+len(j) if a[j]==1 {d++,break} d++,q=-1 } if c>b {z[i]=b } else{z[i]=c} }} index=0 d=0 for(i=0;i
Add all the permutation of small string in to a hashSet. Then iterate the bigger string, if the set contains sub string of bigString(0,0 + smallString.length()-1), (1,1+smallString.length()-1,.......) increase the counter. Seems simple. But not sure it is the optimized solution.
Can't we do lie this. 1. create a list and store all the permutations of the smallString. 2. then slide over the bigString and for every window check whether list.contains(currentWindowString). 3.if contains: -> count++; ?
Hi Ma'am . I have a doubt . As soon as you got the question , u immediately come to the point that u will use window sliding . So maam my doubt is if I take time in getting my 1st approach , until then will it be fine if I don't communicate to the interviewer ? And if not , them what should I communicate ?
You should keep communicating whatever's in your mind. Even if approach isn't best, talking will help him know your thinking process. That's what interviewer is looking for! 😊😊
no bro no offence, I am not an expert but I can say that you haven't done a question on sliding window. otherwise it is quite natural that that idea strikes mind first.
ctrl==l wouldn't be a correct check since l is string length and ctr is the size of character map. Which means if pattern is "aaa" then l is 3 and ctrl is 1. Am I missing something ?
This is an Anagram problem which can be solved in maximum 8-10 minutes if you have a prior knowledge about anagrams. Otherwise like Keerti, It can take alot of time to build the logic and capture edge cases.
Can't we take just a string variable and store each window to that string in each turn and then sort this string and compare with the sorted smallString. No counters would be needed here
Hey Keerti, I just watched the other interview on his channel. I think the first question in which we have to calculate the minimum walking to reach all building can also be done by Sliding window in O(N) time and O(1) space. What's your thought on that?
@@KeertiPurswani like I will create window in which all the important buildings are starting from left most block then I will move left of window one step right and also move right of window accordingly so that the window contain all buildings. I will choose the smallest window finally and will choose to live in middle of window and return minimum_window_size/2
