Hope this was fun to watch as we simulated a real world Interview over Google Hangouts. "Going Greedy does result in minimization but it comes at a cost, and that cost is Wrong Answer". Part II and other links are in the description.
Do u think in hindi? Or maybe HINGLISH?😂 Because I could catch a few hindi sounding words whenever you just started talking after a pause.😂😂 Great video by the way, I liked your approach to the problem. You should make more videos of this kind!
Hi I Have done it python please find the below code : def getmaxstr(listar): maxsrtr = max(listar, key=len) maxsrtlen = len(max(listar, key=len)) return (maxsrtr,maxsrtlen)
def main(): n="3141592653589793238462643383279" listar=["314","49","9001","14","9323","8462643383279","4","793","23846264338","15926535897","8462643383279234"] listlen = len(listar) i =0; l=list() mainflag=False while i < listlen: tup=() tup = getmaxstr(listar) i=i+1 if len(n) > 0 and len(listar) > 0: if tup[0] in n: fndpos = n.find(tup[0]) endlen= int(fndpos) + int(tup[1]) n = n.replace(n[int(fndpos):endlen],'') listar.remove(tup[0]) l.append(tup[0]) else: listar.remove(tup[0]) else: mainflag=True
if mainflag: break
for val in l: print(val)
if __name__ == '__main__': main() Please let me if I can improve that code any other way. Thanks, Dipu
i can't believe i spent 4 hour on this question, i am using Pyhton to make it work. my code: PI = "314159265358979323846263383279" IN = ['314','49','9001','15926535897','14','9323', '846263383279','4','793'] def findMatch(a,b): index = [] pos_a = 0 count_match = 0 for i in range(0, len(b)): if pos_a >= len(a): break if checkStr(a,pos_a,b,i) == True: pos_a += len(b[i]) count_match+=1 index.append(b[i]) else: pos_a = pos_a return f"{count_match-1}({' '.join(index)})" def checkStr(strA,pos_a,listB,pos_b): for i in range(0, len(listB[pos_b])): if strA[pos_a+i] != listB[pos_b][i]: return False else: return True print(findMatch(PI,IN)) I think I am fail the interview.
i remember giving interview at adobe and totally changing my code at the last while writing. It is always good to be interactive while writing code. Thanks Rachit.
@@AdityaKumar-pb4lr c# BETTER version of java :) edit: please stop replying to this. this information is false and only for entertainment purposes. still c# is most of the time better than java as a language
This is my initial reaction to the problem i paused the video at 5:20 and did not watch further. This can be solved with simple DP using O(n) space for the DP 1d array and probably a hash map DS to store the favourite digit sequences (for a O(1) lookup while doing the memoisation), the time complexity would be O(n2) worst case but should be Amortised better than this for random inputs. The algo is as follows, Lets maintain a DP 1d array 'A' this would have any value between -1 to n (where 'n' is length of the input string 'B' ), the value -1 of A[i] indicates there is no possible favourable split of input string B[0...i], but any value A[i] greater than -1 and less than 'n' indicates there is a fvourable split and it denotes the immediate previous index of string 'B' which has the space, so essentially the problem boils down to A[n-1] having any value > -1 then we have a favourable split of string else its not possible, to identify the positions of spaces we just traverse back from A[n-1] to get all indices which has the space. The memoization formula would be A[i] = { for all j , 0 =0 &&
I am not that good at programming and i am still learning. Can you explain what is the need of the array to keep track of things? Why can't we have a hash containing the prefered strings and then create a string 1 character at a time from the input array and if the charcter exists increment a count and reset the checking string and start a new string from where it was left off: for(i=1; i count++; cur=" " wouldn't that be O(n) as well?
search for 'word break', the code given in the video is not even close to be able to compile and will most likely to fail in a real google interview, to be honest
There's a minor improvement you can do to improve that solution as well. Instead of using an unordered map for storing the favorite strings, you could use a trie instead. Maintain two variables for each trie node, one which stores the list of next pointers from the current node and the other, a boolean variable which tells whether the prefix denoted by the path from the sentinel node to the current node is one of the favorite strings. The checking part is straightforward after that. The time complexity will still be O(n*max_length(favString)) theoretically, but in practice, it'll be much faster than an unordered map based solution because unordered maps have a huge constant factor, which might even be worse than an ordered map based solution sometimes.
Initially by looking at thumbnail I thought it would be cool and see if I could withstand any of the question. But once Clement dropped the question I was like blown away. Did not understand shit but still like a baby I kept looking at what Rachit was doing. 😭😭
Thing I learned from this video is to make an interactive interview session, Interviewer should be that much supportive. Please bring such topics which really gives feeling of giving interview with sense of thinking that needs to be followed by candidate while giving interviews.
They have explained the easy problem in a hard way just to promote their algo expert.... This is simple word break problem......and simple approach is start taking character from starting and when u find any match in favorite arr you have two choices either you split or continue with next charater...try both ways . And find min spaces.....add some memoization to optimize
The code written in the video is logically incorrect and never solves the problem. In a real Google interview the interviewer is gonna give a thumbs down. FYI, the problem is similar to 'Word Break' in Leetcode.
Wow. I actually did the first question with backtracking. I an 5 mins in the videos, I think i found the solution. It's awesome that I started working on competitive programming 45 days ago.its word break problem from leetcode
We can insert all the favourtie strings into a "Trie" data structure. And then while we pass thru the large string, we can check if that partial string exists in trie. If it exists, break it up.
Good, but.. both seem confused on what the program is supposed to do. In development, clarity (ie someone can come in, read the code, and understand straight away) and modularization (code re-use, organize code efficiently as possible) are two of the most important things, the naming of the variables is a huge minus for clarity. The communication between them is clearly lacking. Also, what about test inputs and walking through the code and seeing if it worked? What about malformed test inputs? etc etc..
I have my own approch to solve a mention problem. Take the pi number in a string variable then start removing numbers from favorite number array(sort the array in descending order). E.g. string pi=3456789, Array favArr = [6789,567,45,345] // After sorting NewFavArr = [6789,576,345,45] // After first iteration of NewFavArr and removed matched array value NewPi=345 MatchedValue=[6789] // After next iteration i get output like NewPi=[] MatchedValue=[6789,345] Output will be: 2(6789,345)
Wow so complex question and algo!! Finding the minimum number of spaces, my approach will be with java.1.8 For every string in fav number array just check if substring is present or not! Increment counter if present! That's it! 🤷♂️ But I'm a newbie! Sorry //assuming favArray and string input Int spaces = 0; for(string token : favArray) { if(input.contains(token)) Spaces ++; } Sysout(spaces) ;
Rachit you are doing a great job your videos are very helpful. please make videos on how to get internship in companies like microsoft,google ,goldmansachs etc from offcampus. What are the process ,what are there expectations from interns ,how there resume should look like..
this is a straightforward dynamic programming problem: partition a string such that all partitioned substrings are in some allowable list of strings. this guy needs to practice how to recognize when a problem has recursive structure
@@PoulJulle-wb9iu The basic solution is you put every word in a hash map and each time you see a match, you either take the word and continue with the rest of the string or without taking any string and moving on. You either take it or not. This then becomes like a 0/1 structure and you can do dp to avoid unnecessary repetion. In short, learn before you dare to talk like a boss.
@@PoulJulle-wb9iu The solution provided in this video *IS* a recursive solution. To improve time complexity it uses an array to store calculated result. This is not actually DP but memoization. Most people dont know that. The essence of memoization is still recursion. DP does not have recursive calls.
@@James-yz4cc DP does not have recursive calls? man, you are just a school boy, who were taught wrongly and didnt think. or why are you saying nonsense. DP can both be iterative or recursive, obviously
Since the question is asking for minimum number of spaces which is a minimization problem, we could maximize the substrings resulted by introducing spaces to given input string. Sort fav numbers array in decreasing length, check if largest number is a substring of input string. if yes, increment spacesTaken by 1 and now check if 2nd largest number is present in the input string. if yes, introduce space, else continue; .. if entire input string got split into substrings (base case where i reaches n-1) by greedy method of picking largest substring at each iteration , then in this way we could guarantee that spacesTaken will guaranteed to be minimum out of all possible answers. We could use rabin-karp style substring matching for efficient checks. I hope @Rachit/Clement would notice this comment and reply if my algo would work.
Store your favorite list in Trie Data Structure. Create 2 variables, say I and J. Use point I to irerate over each character of the string, and use J to crawl in Trie. As soon as J reaches to end of word then store that as result and reset J to root of your Trie. Overall Time Complexity: Building trie + Iterating over string characters. O(W + N) N is length of string W is number of words in favorite list Space Complexity: (Trie) O(W) W is number of words in favorite list
i have an idea, instead of using top down approach used by rachit we can have bottom up approach, which goes like this: * find the first number in pie * find the numbers in fav array which start with that number * suppose we have more than one, we go over them iteratively and marks them as used * now we check , if the number choosen in fav array, are in same sequence as in the pie number, -> if does we find the next number and start iterating from step 2, for example, 34684654684684 is pie and fav array contains 346, 35 346 has same number as the pie initials, so we start iterating from 84654684684 -> if it doesn't we go to next number in the iterations * go on till we came to the end of the number does it make any sense, if it doesn't please comment below and I would love to clear it up. I would love to know if you guys find any flaw in it.
So basically you do dynamic programming where you mark the end of substrings that occur in your hash_set of numbers, and then only start trying to build new strings from the character right after the old one. And then you cache the minimum breaks that were needed to get to a particular point.
Using a hash-table? for every term in the favArr, return a key/value pair = startIndex: startIndex+termLength. These pairs form a hash-table. Check the Big String from index 0, if there is no key in the hash-table match 0, then it is not possible to split the Big String, return Infinite. Otherwise, find all keys which match 0, for each matched key, if the value > N, then it has no valid split, return Infinite if the value == N, then return 0 if the value < N, then return 1 + ( repeat the process by check start from the value to N ) return the min of all results from keys Big String=3141592389657302, length = N = 16 favArr = ['3', '314', '15923', '4', '793', '896', '302', '89657', '7302', '896573024'] -> hash-table: {0:1, 0:3, 3:8, 2:3, -1:2, 8:11, 13:16, 8:13, 12:16, 8:17} minSplit(start=0,N=16) = min( 0:1-->1+minSPlit(start=1,N=16), 0:3-->1+minSplit(start=3,N=16) ) minSplit(s=1,N) = Infinite minSplit(s=3,N) = min( 3:8-->1+minSPlit(s=8,N) ) minSplit(s=8,N) = min( 8:11-->1+minSplit(s=11,N), 8:13-->1+min(s=13,N), 8:17-->Infinite ) minSplit(s=11,N) = Infinite minSplit(s=13, N) = min ( 13:16=N-->0 ) => minSplit(s=8, N) = 1 => minSplit(s=3,N)=2 => minSplit(s=0,N)=3 -------- Note: When Big String has repeated numbers/patterns (not like Pi), then have to be careful to get the startIndex of each term in the favArr, instead of as simple as indexOf(term), should use BigString.indexOf(term, lastFoundIndex+1). for example, Big String = 2222, favArr=[2, 2, 22, 222, 22222]....
Using trie would have a time complexity of O (N*K + M) where N is the number of strings in the array, K is the average length of each string, and M is the length of the main string. The space complexity is O (N).
Python solution def countSpace(string, targets): targets_set = set(targets) dp = [0] + [float('inf') for i in range(len(string))] for i in range(1, len(string) + 1): MIN = float('inf') for j in range(0, i): if string[j:i] in targets_set: MIN = min(MIN, dp[j]) dp[i] = MIN + 1 return dp[-1]
First of all, thank you for the video! Well done! The greedy method is purely wrong, *not only* because it may even fail to find any valid answer. It can, in fact, give a non-optimal result too. Consider S=3141592653589793, Fav=[3141592, 653, 589, 793, 314, 1592653589793]. Obviously, the optimal answer is 1 (by using 314 and 1592653589793), but the greedy way will find 3 (using 3141592, 653, 589, 793)
I would take a recursive approach using substring. As we need minimum splits ...will sort my list desc and use larger to smaller strings. If at the end of recursion if find remainders ...then that's not a solution and if I did not ....there's is your solution...👍 Rachit approach need lot of index management that makes code vulnerable to crash at few test cases ...
Rachit, you have done 2 mistakes in your code 1. if ( ans == UNDEFINED), you should not return ans. If ( ans !=UNDEFINED), then you should return the answer. 2. You have to assign dp[pos] = ans in the end. Otherwise, dp array is of no use. Thanks,
I think it's a very typical DP problem which can be solved in O(n^2) time am i right. Iike set opt(i) as belows: first we will maintain an array called M(2, n) and every column of M is for every character in the string. if we go through the string, we stop at i and want to see if we can add a space after s[i], so s[0-i] will be divided into several correctly. We go to the first place we can add space, which is the head of the string and check if s[0-i] is in the dictionary, if yes we will make M[i][0] = 1, M[i][1]= -1, otherwise we move to next j position and M[j][0] is 1. We check if s[j+1 - i] is in the dictionary, if yes then make M[i][0] = 1, M[i][1]= j, if not, we move on to next j position whose M[j][0] is 1...... Once we find a good j we stop the process for i position and move one step forward, unless we make M[i][0]=-1. After n^2 time we can get the M array and we can answer the question through this M.
Can't this be done with 1. Needle in haystack comparison of the strings in the list with the big string. O(m x n) - Can be linear time if using KMP algorithm O(n+m). 2. Get the start and end indexes and create a dependency map - Memory is O(m) 3. Traverse the dependency map with DFS and notate the min steps to reach the end index in the dependency map. The min step is the min space. Time is O(m) O(n+m) + O(m). Rachit would be interested in knowing what you think. Thanks!
hey so couldn't this question be solved by 1. arranging the list of fav numbers from largest to smallest 2.then checking if the first number is present in the number of pi. 3.if present then checking if there is any space between the number present in pi 4.if space is present we do nothing 5.if space is not present we add space on the start and end of the number in pi 6.then doing the same with other numbers in the fav number list
I have been coding for a couple years and let me tell y’all something: if you are not able to find the solution it does NOT mean you are a bad developer. It really does not mean anything, besides one thing: You didn’t practice those type of questions (leet Code style). If you Leetcode or do another similar activity you will FOR SURE get better and start to get the hang. Does it help you though in your everyday work as developer? Probably not.
This is great great...Just motivated by watching a real programmer's coding. Today I got to know how programmers solving problems and how they are coding and about the steps also. Thank you soo much.lv ya.
so basically, it might be a bit wrong, but i'm just 14 lol im not that good at coding, i came up with another solution in python : value = 31415926535 string_val = str(value) likes = [] n = int(input("Enter number of elements : ")) for i in range(0, n): ele = int(input()) likes.append(ele) likes_in_inp = "" for x in likes: if str(x) in string_val: likes_in_inp = likes_in_inp + f"{x}" + " " print(likes_in_inp)
Hey anyone plzz tell and get me out ofit, How he can check 314,once he get rid of 3 from string and get one space between 3 and 14.... once get away from one position how he can go back to the beginning of string to find the min spaces, Thank you !!!
Q. U have 2 strings as input , you have to check which string is greater but u can't use their ASCII value. Example -- XYZ and XZ It should return XZ as the greater string.( This is quit lexicography but u can't use ASCII value) Comment below for the answer ..
Shouldn't the "ans" check be like if( ans != UNDEFINED ) return ans; it should be a NOT EQUAL TO Since when ans == UNDEFINED it means that this dp[pos] hasn't been calculated yet, it isn't initialized with the other -1 or permissible index. Hence it should move forward to the loop instead of return there itself. With ( ans != undefined ) we will be saying that it already has some cached solution (-1 or index ) hence we should return the answer. Give this a thought and please correct me if I am wrong.
Basically this video teaches me not to use a lot of basically. Just kidding, please avoid using a lot filler words. Keep it sufficient enough till the point that people don't start realizing it
How about using probability to find out the maximum number of same digit numbers for.. and then just code it to find the number of spaces we need. example:- if we have three, 3 digit numbers in the favorite array out of 5, then the probability would be 3/5. which is more than 50%. So here we go
Seems some code mistakes Mistakes 1. You return ans, but where did you cache? 2. Vis[N] you mark it as visited, but it is possible that you won't get the solution at 'pos' so you may need to try some other 'x' which apparently reach to 'pos' but you code says, you can't use it again. Hence failed. 3. you're first if the condition is wrong, where you check ans=UND. as per ur explanation, UND is used to initialized dp/vis array. So they always are equal to UND until n unless you overwrite them. Since you put that condition first, you function call to return from there itself, which returns UND as output. And ofcouse there few other mistakes as well, your first function tells 'int' as return type but you rather returning printing the solution .:P
1. You are wrong - Read about references in C++ 2. From given state A, we can only reach to states B > A. So here also, the code will work just fine. 3. Yeah, that's the typo. "Your code is a wrong" is a bold statement. Happy Coding!
Well, right now I am studying assembly language and data structures in c++ for a final exam that is tomorrow. I don't even know one bit about these subject and write now I just checked my future courses like compiler construction, operating system etc. I was like "I can't do this let's give up" but after watching this video and checking your resume. I decided, if you an electrical student can learn c++ then why can't I do this. Thanks for the motivation bro.
Can't we just do it like this: def countSpace(string, llist): spaceCount = 0 for i in llist: if i in string: spaceCount += 1 return spaceCount - 1 that if we find that list element in the provided string we will simply increase the space count by 1 each time we find the element in provided string.
I'm not pro at algos but off the top of my head I'll use a sliding window to check through the string and get minimal substrings found in the array. It'll be o (n) too
Honestly I thought this was kinda bad and not a very realistic example. The interviewee, while it's ok to be confident, it's better to be a bit more humble and ask what the interviewer thinks as you go along rather than forcing your answer in. This felt more like the interviewee was saying everything they were doing was right and wasn't being collaborative at all. Sure, they might be competent, but I wouldn't want to work with them.
Thanks for sharing your thoughts, I try to not give off such an impression. I keep sure that I move forward from each step only when I get a green signal from the interviewer, which I think I did.
Jacob Barr the interviewer would have stopped him to say if something wasn't ok. Nobody needs you sitting on your high horse preaching your own moral standpoint on something so trivial as this. You don't even know the guy in real life and just because his attitude seems a bit over the top based on your highly stringent moral requirements you're going to make a concluding judgement on him? I'm more worried about your attitude now than his.
Regarding the fun intro to the interview, it hasn't been proven whether or not pi has the property that any finite string of digits occurs in the decimal representation as was described by Clement. It is only conjectured that it does.
Hold up. It is not guaranteed that the digits of pi generate every number at all. We can't even prove that Pi's digits are random! And even if they were, we still couldn't guarantee that every number exists in pi unless we actually find them!
These type of excercises are so abstract, I want to see someone at work trying to solve a problem that doesn't fit the scope of basic math knowledge. Just because you can remember a math equation and recreate it doesn't show value as a programmer since literally everything you are trying to do has been done 1000s of times and is widely available on the web. Therefor I think the ability to find instead of generate is of more value. But hey every programmer wants to re-invent the wheel anyway.
On one of the problems I solved I had used a similar logic to break down a hashtag into valid words and the optimum solution is the one which has the most number of valid words. There was no library or module at that time which could I quickly find so had it to code it up myself. It is not all as abstract as it would seem.
Hope this was fun to watch as we simulated a real world Interview over Google Hangouts.
"Going Greedy does result in minimization but it comes at a cost, and that cost is Wrong Answer".
Part II and other links are in the description.
Do u think in hindi? Or maybe HINGLISH?😂 Because I could catch a few hindi sounding words whenever you just started talking after a pause.😂😂
Great video by the way, I liked your approach to the problem.
You should make more videos of this kind!
could you have used the elements of the array to integrate and become the pi string itself...
If yes what would be it's time complexity...
Hi I Have done it python please find the below code :
def getmaxstr(listar):
maxsrtr = max(listar, key=len)
maxsrtlen = len(max(listar, key=len))
return (maxsrtr,maxsrtlen)
def main():
n="3141592653589793238462643383279"
listar=["314","49","9001","14","9323","8462643383279","4","793","23846264338","15926535897","8462643383279234"]
listlen = len(listar)
i =0;
l=list()
mainflag=False
while i < listlen:
tup=()
tup = getmaxstr(listar)
i=i+1
if len(n) > 0 and len(listar) > 0:
if tup[0] in n:
fndpos = n.find(tup[0])
endlen= int(fndpos) + int(tup[1])
n = n.replace(n[int(fndpos):endlen],'')
listar.remove(tup[0])
l.append(tup[0])
else:
listar.remove(tup[0])
else:
mainflag=True
if mainflag:
break
for val in l:
print(val)
if __name__ == '__main__':
main()
Please let me if I can improve that code any other way.
Thanks,
Dipu
i was going to use the first solution you mentioned
great video and tips
i can't believe i spent 4 hour on this question, i am using Pyhton to make it work.
my code:
PI = "314159265358979323846263383279"
IN = ['314','49','9001','15926535897','14','9323',
'846263383279','4','793']
def findMatch(a,b):
index = []
pos_a = 0
count_match = 0
for i in range(0, len(b)):
if pos_a >= len(a):
break
if checkStr(a,pos_a,b,i) == True:
pos_a += len(b[i])
count_match+=1
index.append(b[i])
else:
pos_a = pos_a
return f"{count_match-1}({' '.join(index)})"
def checkStr(strA,pos_a,listB,pos_b):
for i in range(0, len(listB[pos_b])):
if strA[pos_a+i] != listB[pos_b][i]:
return False
else:
return True
print(findMatch(PI,IN))
I think I am fail the interview.
How many other people think doing coding interview questions is fun like Rachit and I? 😂
Is algoexpert videos down?
Me
@@vidhubhardwaj9672 I've got a complicated last name, that's for sure! 😛And awesome; glad you like it!
@@SumitKumar-fn3gj Me too
@@clem man i work in jp morgan usa, i m an indian
I have 0 coding ability/experience, and I have no idea what they are talking about. Why am I watching this?!
Same here 😂😂
Same here also
Smj kuch nhi ayaa lekin sunn ke aacha laga
Shane Field haha same! I’m so lost!
mood
i remember giving interview at adobe and totally changing my code at the last while writing. It is always good to be interactive while writing code. Thanks Rachit.
Hi
Google interview in a apple mac by an ex Microsoft guy😂
Chronology samaj rahe hai ap!
Hahahahahahahaha......
Anurag Srivastava LoL that meme 😂
🤣🤣🤣🤣🤣
Yeh chronology SE zyada trilogy lag rahi hai
On youtube
i just learnt how to write hello world in c and now this video is recommended to me.
😑😑
learn c#
C# microsoft version of java😂😂
@@AdityaKumar-pb4lr c# BETTER version of java :)
edit: please stop replying to this. this information is false and only for entertainment purposes. still c# is most of the time better than java as a language
I only know HTMl🤣
Sujan Basak lets hack nasa together
I thought coding interview only caused me to talk weirdly. Now I feel better
you must be that guy who does all the work in a group project damn.
love to see how whole YT community helping each other with such collabs
getting to a solution this fast needs a great level of practice. Well Done Rachit.
Thanks
@@sasmitvaidya3594 if u practise well, u'll get it in prob 2-3 months
@@sasmitvaidya3594 no way. I would think at least a year of learning.
@@bhanupratapsinghrajawat3686 maybe if you're Einstein, but we all normal folks need years
No of "Basically" used by rachit in video is 47 damn high basically😂
man, youu have so much free time.
@@tapankumarbaral1244 what????.
It's a problem with mostly all indians. Use of the words like "Basically", "OK" etc.
@@vineethsai1575 it doesn't matter success matters
1:55 Why did Anjali cancel your order? How dare she? haha
hahaha
lol
I dn't get it
@@rakeshmehra6321 look gmail
1mg technologies pvt limited is a drug/medicine supplier. May be he ordered...... You guess.
I was asked the exact same question in the final round for SDE-2 role at Amazon. No price for guessing I was rejected ;)
Hey, I'll be entering college in few months, can I please ask you some doubts 🙏
what about now bro? Did you get a job?
@@saketpatil1306 what?
@@mymoviemania1 are u in cs engineering? I wanted to ask something
@@saketpatil1306 will be in a few days. Yet u can i ask what u want to knlw
I used to think myself as a good programmer before i watched this
Look up set theory. Could help
@@regd9297 why
This is just one area of programming.
Haha.Welcome to the world of dynamic programming.I' m not going to welcome myself there anyways because I finally found that its not my cup of tea.
This is my initial reaction to the problem i paused the video at 5:20 and did not watch further. This can be solved with simple DP using O(n) space for the DP 1d array and probably a hash map DS to store the favourite digit sequences (for a O(1) lookup while doing the memoisation), the time complexity would be O(n2) worst case but should be Amortised better than this for random inputs. The algo is as follows, Lets maintain a DP 1d array 'A' this would have any value between -1 to n (where 'n' is length of the input string 'B' ), the value -1 of A[i] indicates there is no possible favourable split of input string B[0...i], but any value A[i] greater than -1 and less than 'n' indicates there is a fvourable split and it denotes the immediate previous index of string 'B' which has the space, so essentially the problem boils down to A[n-1] having any value > -1 then we have a favourable split of string else its not possible, to identify the positions of spaces we just traverse back from A[n-1] to get all indices which has the space. The memoization formula would be A[i] = { for all j , 0 =0 &&
looks like you are genius
haha damn you must be a sr software engineer
I had thought of the exact same solution.
I am not that good at programming and i am still learning. Can you explain what is the need of the array to keep track of things? Why can't we have a hash containing the prefered strings and then create a string 1 character at a time from the input array and if the charcter exists increment a count and reset the checking string and start a new string from where it was left off:
for(i=1; i count++; cur=" "
wouldn't that be O(n) as well?
@@Blahrg Yeah but that does not minimises spaces.
Rachit: ”I’m an ex Microsoft employe.”
My head: ”Hello, welcome to Microsoft tech-support. How can I help you?”
re employ me lel
Well ,he is Indian so possibilities are endless.
I get what you did there 😂😂😂
He said he is engineer
Not cool. We educate ourselves and help others too... I get it u were joking... Funny... But not cool, Jus' saying
Have a good day.
Really nice interaction. Also i think this problem is same as word break O(n^2), chao.
Wow great insight!
Yes, that's the first thought came in my mind, it's a word break just with numbers.
This is a really interesting question... Gonna search if this question is on any coding platforms.. thanks for the question Clement and Rachit
search for 'word break', the code given in the video is not even close to be able to compile and will most likely to fail in a real google interview, to be honest
There's a minor improvement you can do to improve that solution as well. Instead of using an unordered map for storing the favorite strings, you could use a trie instead. Maintain two variables for each trie node, one which stores the list of next pointers from the current node and the other, a boolean variable which tells whether the prefix denoted by the path from the sentinel node to the current node is one of the favorite strings. The checking part is straightforward after that. The time complexity will still be O(n*max_length(favString)) theoretically, but in practice, it'll be much faster than an unordered map based solution because unordered maps have a huge constant factor, which might even be worse than an ordered map based solution sometimes.
that's happen when a iitian does hardcore competetive programming for just get an faang india offer🤣🤣🤣🤣🤣🤣
Initially by looking at thumbnail I thought it would be cool and see if I could withstand any of the question. But once Clement dropped the question I was like blown away.
Did not understand shit but still like a baby I kept looking at what Rachit was doing. 😭😭
Thing I learned from this video is to make an interactive interview session, Interviewer should be that much supportive. Please bring such topics which really gives feeling of giving interview with sense of thinking that needs to be followed by candidate while giving interviews.
I am an Computer science engineer and I literally have no idea what they are talking about!like who are in same position!
Im mechanical engineer almost understood everything.
I think coding is simple but you need some basic skills to use mathematics. And practice
Im a class 12 student and even I can do this problem that too in 3 languages
I'm 5 years old and i solved this problem in 2 milliseconds you guys are stoopid
@@theendurance Yeah kiddo I know that I'm stupid thanks for letting me know it.,😄✌️
They have explained the easy problem in a hard way just to promote their algo expert.... This is simple word break problem......and simple approach is start taking character from starting and when u find any match in favorite arr you have two choices either you split or continue with next charater...try both ways . And find min spaces.....add some memoization to optimize
Pie = 3.14blablabla
thanks for the info, I can use this in tomorrows math test. I am sure that I will get A+ grade. Thanks once again.
For a second I thought it was Ex-Google TeahLead. Damn.
Ex Google, Ex Facebook*
@@adityapaithon6499 Ex Husband too. :D Sad, but he makes it somehow funny.
This thread is all I needed for the day 💞🤣
@@karthikmucheli7930 😂😂😂
Hey Rachit,
I owe you a lot for my learning weekends.
Thanks a ton!! :)
Thanks
The code written in the video is logically incorrect and never solves the problem. In a real Google interview the interviewer is gonna give a thumbs down.
FYI, the problem is similar to 'Word Break' in Leetcode.
Wow. I actually did the first question with backtracking. I an 5 mins in the videos, I think i found the solution. It's awesome that I started working on competitive programming 45 days ago.its word break problem from leetcode
@Lokesh Nimawat the best is to get better algorithms and data structures.
@@karthikmucheli7930 which site you prefer for c.p.
@@hmmmm4193 leetcode
12:45 he was dreaming dude!!!
We can insert all the favourtie strings into a "Trie" data structure. And then while we pass thru the large string, we can check if that partial string exists in trie. If it exists, break it up.
Good, but.. both seem confused on what the program is supposed to do. In development, clarity (ie someone can come in, read the code, and understand straight away) and modularization (code re-use, organize code efficiently as possible) are two of the most important things, the naming of the variables is a huge minus for clarity. The communication between them is clearly lacking. Also, what about test inputs and walking through the code and seeing if it worked? What about malformed test inputs? etc etc..
I have my own approch to solve a mention problem.
Take the pi number in a string variable then start removing numbers from favorite number array(sort the array in descending order).
E.g.
string pi=3456789,
Array favArr = [6789,567,45,345]
// After sorting
NewFavArr = [6789,576,345,45]
// After first iteration of NewFavArr and removed matched array value
NewPi=345
MatchedValue=[6789]
// After next iteration i get output like
NewPi=[]
MatchedValue=[6789,345]
Output will be: 2(6789,345)
man now i am also becoming pro in python, i have successfully done hello world
Why they are talking in alien language
Wow so complex question and algo!!
Finding the minimum number of spaces, my approach will be with java.1.8
For every string in fav number array just check if substring is present or not! Increment counter if present! That's it! 🤷♂️
But I'm a newbie! Sorry
//assuming favArray and string input
Int spaces = 0;
for(string token : favArray)
{
if(input.contains(token))
Spaces ++;
}
Sysout(spaces) ;
Was thinking same, I don't know c++. So & this symbol was difficult for me understand.
Yes we have contains in Java and that should solve it easily
Probably a typo here:
if (ans == UNDEFINED) return ans;
Yeah thanks.
Read the comments just to find this comment. :)
What's the typo here?
Also, I think, in addition to returning the answer, he should also store the ans in that dp array...
Have no idea what I just watched but it was interesting
Rachit you are doing a great job your videos are very helpful. please make videos on how to get internship in companies like microsoft,google ,goldmansachs etc from offcampus. What are the process ,what are there expectations from interns ,how there resume should look like..
this is a straightforward dynamic programming problem: partition a string such that all partitioned substrings are in some allowable list of strings. this guy needs to practice how to recognize when a problem has recursive structure
recursion is for fking noobs....
@@PoulJulle-wb9iu Nope.
@@PoulJulle-wb9iu The basic solution is you put every word in a hash map and each time you see a match, you either take the word and continue with the rest of the string or without taking any string and moving on. You either take it or not. This then becomes like a 0/1 structure and you can do dp to avoid unnecessary repetion.
In short, learn before you dare to talk like a boss.
@@PoulJulle-wb9iu The solution provided in this video *IS* a recursive solution. To improve time complexity it uses an array to store calculated result. This is not actually DP but memoization. Most people dont know that. The essence of memoization is still recursion. DP does not have recursive calls.
@@James-yz4cc DP does not have recursive calls? man, you are just a school boy, who were taught wrongly and didnt think. or why are you saying nonsense. DP can both be iterative or recursive, obviously
Since the question is asking for minimum number of spaces which is a minimization problem, we could maximize the substrings resulted by introducing spaces to given input string. Sort fav numbers array in decreasing length, check if largest number is a substring of input string. if yes, increment spacesTaken by 1 and now check if 2nd largest number is present in the input string. if yes, introduce space, else continue; .. if entire input string got split into substrings (base case where i reaches n-1) by greedy method of picking largest substring at each iteration , then in this way we could guarantee that spacesTaken will guaranteed to be minimum out of all possible answers. We could use rabin-karp style substring matching for efficient checks. I hope @Rachit/Clement would notice this comment and reply if my algo would work.
Store your favorite list in Trie Data Structure.
Create 2 variables, say I and J.
Use point I to irerate over each character of the string, and use J to crawl in Trie.
As soon as J reaches to end of word then store that as result and reset J to root of your Trie.
Overall Time Complexity:
Building trie + Iterating over string characters.
O(W + N)
N is length of string
W is number of words in favorite list
Space Complexity: (Trie)
O(W)
W is number of words in favorite list
Nope, in case you have: '31', '41', '5' and '3', '1415'. Your code will choose three elements instead of two, so you will not minimize spaces
i have an idea, instead of using top down approach used by rachit we can have bottom up approach, which goes like this:
* find the first number in pie
* find the numbers in fav array which start with that number
* suppose we have more than one, we go over them iteratively and marks them as used
* now we check , if the number choosen in fav array, are in same sequence as in the pie number,
-> if does we find the next number and start iterating from step 2,
for example, 34684654684684 is pie
and fav array contains 346, 35
346 has same number as the pie initials, so we start iterating from 84654684684
-> if it doesn't we go to next number in the iterations
* go on till we came to the end of the number
does it make any sense, if it doesn't please comment below and I would love to clear it up.
I would love to know if you guys find any flaw in it.
So basically you do dynamic programming where you mark the end of substrings that occur in your hash_set of numbers, and then only start trying to build new strings from the character right after the old one. And then you cache the minimum breaks that were needed to get to a particular point.
Using a hash-table?
for every term in the favArr, return a key/value pair = startIndex: startIndex+termLength. These pairs form a hash-table.
Check the Big String from index 0, if there is no key in the hash-table match 0, then it is not possible to split the Big String, return Infinite. Otherwise, find all keys which match 0,
for each matched key,
if the value > N, then it has no valid split, return Infinite
if the value == N, then return 0
if the value < N, then return 1 + ( repeat the process by check start from the value to N )
return the min of all results from keys
Big String=3141592389657302, length = N = 16
favArr = ['3', '314', '15923', '4', '793', '896', '302', '89657', '7302', '896573024']
-> hash-table:
{0:1, 0:3, 3:8, 2:3, -1:2, 8:11, 13:16, 8:13, 12:16, 8:17}
minSplit(start=0,N=16)
= min( 0:1-->1+minSPlit(start=1,N=16), 0:3-->1+minSplit(start=3,N=16) )
minSplit(s=1,N) = Infinite
minSplit(s=3,N) = min( 3:8-->1+minSPlit(s=8,N) )
minSplit(s=8,N) = min( 8:11-->1+minSplit(s=11,N), 8:13-->1+min(s=13,N), 8:17-->Infinite )
minSplit(s=11,N) = Infinite
minSplit(s=13, N) = min ( 13:16=N-->0 )
=>
minSplit(s=8, N) = 1
=>
minSplit(s=3,N)=2
=>
minSplit(s=0,N)=3
-------- Note: When Big String has repeated numbers/patterns (not like Pi), then have to be careful to get the startIndex of each term in the favArr, instead of as simple as indexOf(term), should use BigString.indexOf(term, lastFoundIndex+1). for example, Big String = 2222, favArr=[2, 2, 22, 222, 22222]....
Using trie would have a time complexity of O (N*K + M) where N is the number of strings in the array, K is the average length of each string, and M is the length of the main string. The space complexity is O (N).
I'm a CRUD boy, I don't need to deal with such problem, lol
Damn understanding that question will take me 45 minute and when to solve it lmao 🤣🤣🤣🤣
Ya I thought I'm the only one
Python solution
def countSpace(string, targets):
targets_set = set(targets)
dp = [0] + [float('inf') for i in range(len(string))]
for i in range(1, len(string) + 1):
MIN = float('inf')
for j in range(0, i):
if string[j:i] in targets_set:
MIN = min(MIN, dp[j])
dp[i] = MIN + 1
return dp[-1]
I had an Online Coding round like this for DE Shaw and I remember changing my code to cover all the edge cases.
Did you got selected??
@@VY-zt3ph did you *get*
@@chiragsharmaCZcams bro thanks for correcting. But kya karein aadat se majboor hain. Even my gf always pinch me for these mistakes.
@@VY-zt3ph glad ur gf is an expert in this.
@@rtxmax8223 ab breakup ho gya
I dont think the answer works because when you reach N = 0 you return 0, then take the min which will always be 0 after all recursive calls end.
Clement should be interviewee sometimes too. It would be a lot of fun.🤗
I was waiting up on you to take care of that -1 part which you obviously did in the end. I think you even made a vid earlier on this type of question.
First of all, thank you for the video! Well done!
The greedy method is purely wrong, *not only* because it may even fail to find any valid answer. It can, in fact, give a non-optimal result too.
Consider S=3141592653589793, Fav=[3141592, 653, 589, 793, 314, 1592653589793].
Obviously, the optimal answer is 1 (by using 314 and 1592653589793), but the greedy way will find 3 (using 3141592, 653, 589, 793)
Yeah, greedy one is wrong - that's what I also tell in the video.
I would take a recursive approach using substring. As we need minimum splits ...will sort my list desc and use larger to smaller strings. If at the end of recursion if find remainders ...then that's not a solution and if I did not ....there's is your solution...👍 Rachit approach need lot of index management that makes code vulnerable to crash at few test cases ...
Rachit, you have done 2 mistakes in your code
1. if ( ans == UNDEFINED), you should not return ans. If ( ans !=UNDEFINED), then you should return the answer.
2. You have to assign dp[pos] = ans in the end. Otherwise, dp array is of no use.
Thanks,
1 is a typo. And 2 is just fine, you are mistaken. Read about reference in cpp.
Yes you are right. Thanks.
I think it's a very typical DP problem which can be solved in O(n^2) time am i right. Iike set opt(i) as belows: first we will maintain an array called M(2, n) and every column of M is for every character in the string. if we go through the string, we stop at i and want to see if we can add a space after s[i], so s[0-i] will be divided into several correctly. We go to the first place we can add space, which is the head of the string and check if s[0-i] is in the dictionary, if yes we will make M[i][0] = 1, M[i][1]= -1, otherwise we move to next j position and M[j][0] is 1. We check if s[j+1 - i] is in the dictionary, if yes then make M[i][0] = 1, M[i][1]= j, if not, we move on to next j position whose M[j][0] is 1...... Once we find a good j we stop the process for i position and move one step forward, unless we make M[i][0]=-1. After n^2 time we can get the M array and we can answer the question through this M.
I was hoping he was going to answer the question 😒
he did..that was the answer
Loved the idea of doing mock interviews for Big Companies. Really helpful. Please keep doing it for other companies also. Thanks.
Can't this be done with
1. Needle in haystack comparison of the strings in the list with the big string. O(m x n) - Can be linear time if using KMP algorithm O(n+m).
2. Get the start and end indexes and create a dependency map - Memory is O(m)
3. Traverse the dependency map with DFS and notate the min steps to reach the end index in the dependency map. The min step is the min space. Time is O(m)
O(n+m) + O(m). Rachit would be interested in knowing what you think. Thanks!
Something that doesn't blufff....i heard the question, and Subscribed. That's really what interview is 👏👏
Thank for creating close to real senario..... very soon I realised -> I can not be a Google engineering!.😂😂
hey so couldn't this question be solved by
1. arranging the list of fav numbers from largest to smallest
2.then checking if the first number is present in the number of pi.
3.if present then checking if there is any space between the number present in pi
4.if space is present we do nothing
5.if space is not present we add space on the start and end of the number in pi
6.then doing the same with other numbers in the fav number list
I have been coding for a couple years and let me tell y’all something: if you are not able to find the solution it does NOT mean you are a bad developer. It really does not mean anything, besides one thing: You didn’t practice those type of questions (leet Code style).
If you Leetcode or do another similar activity you will FOR SURE get better and start to get the hang. Does it help you though in your everyday work as developer? Probably not.
This is great great...Just motivated by watching a real programmer's coding. Today I got to know how programmers solving problems and how they are coding and about the steps also. Thank you soo much.lv ya.
so basically, it might be a bit wrong, but i'm just 14 lol im not that good at coding, i came up with another solution in python :
value = 31415926535
string_val = str(value)
likes = []
n = int(input("Enter number of elements : "))
for i in range(0, n):
ele = int(input())
likes.append(ele)
likes_in_inp = ""
for x in likes:
if str(x) in string_val:
likes_in_inp = likes_in_inp + f"{x}" + " "
print(likes_in_inp)
Hey anyone plzz tell and get me out ofit,
How he can check 314,once he get rid of 3 from string and get one space between 3 and 14.... once get away from one position how he can go back to the beginning of string to find the min spaces, Thank you !!!
Again Quaility content from this channel Thanks a lot
Who all remember the song
Oh my darling oh my darling
Oh my darling clementime
You are lost and gone for ever
Dreadful sorrow clementime
Thanks for the great mock interview!
Q. U have 2 strings as input , you have to check which string is greater but u can't use their ASCII value.
Example -- XYZ and XZ
It should return XZ as the greater string.( This is quit lexicography but u can't use ASCII value)
Comment below for the answer ..
below
Can this be solved using a trie instead? just add the fav array in there, and then check the main string. ?
Don't u think that it was quite similar to finding a substring in a string type question and it could be covered in 25 mins instead of 45 mins?
Hey yo!
Correct added monkey masala to make it big
Careful rachit, be careful about your personal emails and stuff, read 2 email subjects of yours!
sooo??
Meanwhile white hat junior chintu op 😂
Shouldn't the "ans" check be like
if( ans != UNDEFINED ) return ans; it should be a NOT EQUAL TO
Since when ans == UNDEFINED it means that this dp[pos] hasn't been calculated yet, it isn't initialized with the other -1 or permissible index. Hence it should move forward to the loop instead of return there itself.
With ( ans != undefined ) we will be saying that it already has some cached solution (-1 or index ) hence we should return the answer.
Give this a thought and please correct me if I am wrong.
Basically this video teaches me not to use a lot of basically. Just kidding, please avoid using a lot filler words. Keep it sufficient enough till the point that people don't start realizing it
Hahahaha, you got me there! I know I have a lot to work upon when it comes to fluently conversing. Hopefully, will become better soon.
aight, imma head out.
X_X real classy
How about using probability to find out the maximum number of same digit numbers for.. and then just code it to find the number of spaces we need.
example:- if we have three, 3 digit numbers in the favorite array out of 5, then the probability would be 3/5.
which is more than 50%. So here we go
Seems some code mistakes
Mistakes
1. You return ans, but where did you cache?
2. Vis[N] you mark it as visited, but it is possible that you won't get the solution at 'pos' so you may need to try some other 'x' which apparently reach to 'pos' but you code says, you can't use it again. Hence failed.
3. you're first if the condition is wrong, where you check ans=UND.
as per ur explanation, UND is used to initialized dp/vis array. So they always are equal to UND until n unless you overwrite them.
Since you put that condition first, you function call to return from there itself, which returns UND as output.
And ofcouse there few other mistakes as well, your first function tells 'int' as return type but you rather returning printing the solution .:P
1. You are wrong - Read about references in C++
2. From given state A, we can only reach to states B > A. So here also, the code will work just fine.
3. Yeah, that's the typo.
"Your code is a wrong" is a bold statement.
Happy Coding!
@Rachit Jain I apologies for that, I did not mean to disrespect you. I know you personally. [i'm also from IIT Roorkee, ]
Holy fucking god you are really good. The reason why you got in Microsoft.
Hahaha thanks
@@RachitJain I just finished watching part 2. Dammmmm you are good.
Lol thanks again
Well, right now I am studying assembly language and data structures in c++ for a final exam that is tomorrow. I don't even know one bit about these subject and write now I just checked my future courses like compiler construction, operating system etc. I was like "I can't do this let's give up" but after watching this video and checking your resume. I decided, if you an electrical student can learn c++ then why can't I do this.
Thanks for the motivation bro.
I can done it with recursive ,, calling check thrive
Can't we just do it like this:
def countSpace(string, llist):
spaceCount = 0
for i in llist:
if i in string:
spaceCount += 1
return spaceCount - 1
that if we find that list element in the provided string we will simply increase the space count by 1 each time we find the element in provided string.
Great collaboration...i saw algo expert and it is something that i need the most... thanks...
I'm not pro at algos but off the top of my head I'll use a sliding window to check through the string and get minimal substrings found in the array. It'll be o (n) too
We can do it in better complexity by using aho corasick algorithm. This will give time complexity of O(n + m).
me not understanding anything but still watching this with full concentration. hahahha
:p
Why I watched the whole video though everything went over my head🤣...
The condition to check whether we have already calculated for the position should be if(ans !=undefined) returns ans
I'd just do:
string piNums = "3141592653589793238462643383279";
string[] nums = new string[] { "314", "49", "9001", "15926535897", "14", "9323", "8462643383279", "4", "793" };
string newNum = "";
foreach(string num in nums)
{
if (piNums.Contains(num))
{
newNum += num + " ";
piNums = piNums.Replace(num, "");
}
}
Awesome video, well done!
The DP array was supposed to be populated within the function. @Clement missed it, but good walkthrough overall.
Honestly I thought this was kinda bad and not a very realistic example. The interviewee, while it's ok to be confident, it's better to be a bit more humble and ask what the interviewer thinks as you go along rather than forcing your answer in. This felt more like the interviewee was saying everything they were doing was right and wasn't being collaborative at all. Sure, they might be competent, but I wouldn't want to work with them.
Thanks for sharing your thoughts, I try to not give off such an impression. I keep sure that I move forward from each step only when I get a green signal from the interviewer, which I think I did.
Jacob Barr the interviewer would have stopped him to say if something wasn't ok. Nobody needs you sitting on your high horse preaching your own moral standpoint on something so trivial as this. You don't even know the guy in real life and just because his attitude seems a bit over the top based on your highly stringent moral requirements you're going to make a concluding judgement on him? I'm more worried about your attitude now than his.
I got confused in the beginning already. I don’t even know what the question is. I’m coding in Java right now, but this made sense.
Teekha hai ye launda!
Amazing work putting up these videos man! Thanks
He is an ex_Microsoft Software Engineer and uses a MacBook. Do you know the reason why doesn't he work there?
Regarding the fun intro to the interview, it hasn't been proven whether or not pi has the property that any finite string of digits occurs in the decimal representation as was described by Clement. It is only conjectured that it does.
Hold up. It is not guaranteed that the digits of pi generate every number at all. We can't even prove that Pi's digits are random! And even if they were, we still couldn't guarantee that every number exists in pi unless we actually find them!
I am wondering🤔💭 when will I become experts like you guys....?
These type of excercises are so abstract, I want to see someone at work trying to solve a problem that doesn't fit the scope of basic math knowledge. Just because you can remember a math equation and recreate it doesn't show value as a programmer since literally everything you are trying to do has been done 1000s of times and is widely available on the web. Therefor I think the ability to find instead of generate is of more value.
But hey every programmer wants to re-invent the wheel anyway.
I bet you can't even do it, shut up.
Offence to coders.
On one of the problems I solved I had used a similar logic to break down a hashtag into valid words and the optimum solution is the one which has the most number of valid words. There was no library or module at that time which could I quickly find so had it to code it up myself. It is not all as abstract as it would seem.
@@arunghontale3189 How'd you determine what was a valid word?
@@samb9439 I'd used a dictionary of words (I guess around 2 million of them) to lookup whether a word is valid or not.