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?
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.
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.
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..
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.
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..
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.
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
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.
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 ...
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) ;
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).
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.
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!
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
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.
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.
Nice video Rachit. loved this channel, specially solving coding questions like this, like Codejam-problems, specifically, I liked your solution on "Decryption Problem". BTW, Are you giving Google's Codejam tomorrow? if yes then all the best Rachit. :)
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 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.
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.
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 would cut the string off whenever the longest string is found in the pi. Pass the new pi and new fav string for recursive call till the pi is empty or no fav string in pi. The run time is probably high. So far is what I think. Maybe a better way. Please share.
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
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.
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
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
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
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
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.
Hi Rachit, I have a doubt about your solution. Lets take this sample case(i have cut the lenght of Pi to make it bit more simple) Sample Input:- pi = 31415926535 favourite_words = [314,31415926,15926,535] I think as per your given approach the result will give 3 as the minimum space required but we can do that in 2 spaces as a minimum. Please can u or anyone explain
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)
49-COMP A -Aakash Gupta C++ would be your best bet if your going into computer science, but any high level object oriented language would suit you, like Java. I’d recommend C++ over it though since it’s basically a higher level version of C.
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 ..
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.
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,
Is this the kind of Interview that happens in Google or Microsoft? I guess no because we don't write code while explaining the algo. It's the work of Pseudocode which is easy to understand either of the sides. Moreover, if my understanding is correct, the question is to find the string which is in the array and put the spaces if those string found in the pi values. In that case, you should have mentioned Boyer-Moore algo to search quickly. Correct me if I am wrong? It will help me to learn further.
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.
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
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.
@Rachit Rachit please correct me if my approach is wrong. For me I will start with largest string in given array and find out if it is present in main string if it is then I will delete that substring from main string and increment space count and similarly will repeat this process for next large strings in given array.
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!
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
you must be that guy who does all the work in a group project damn.
I thought coding interview only caused me to talk weirdly. Now I feel better
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 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
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.
getting to a solution this fast needs a great level of practice. Well Done Rachit.
Thanks
@@bulletprooftrading if u practise well, u'll get it in prob 2-3 months
@@bulletprooftrading 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
love to see how whole YT community helping each other with such collabs
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 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.
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🤣🤣🤣🤣🤣🤣
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.
12:45 he was dreaming dude!!!
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.
Hey Rachit,
I owe you a lot for my learning weekends.
Thanks a ton!! :)
Thanks
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.,😄✌️
Why they are talking in alien language
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..
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
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.
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..
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.
I can done it with recursive ,, calling check thrive
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
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 😂😂😂
I'm a CRUD boy, I don't need to deal with such problem, lol
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.
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.
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*
@@chiragsharmaTH-cam 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
Again Quaility content from this channel Thanks a lot
Have no idea what I just watched but it was interesting
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 ...
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
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]....
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...
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).
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.
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.
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!
Great collaboration...i saw algo expert and it is something that i need the most... thanks...
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
Thanks for the great mock interview!
aight, imma head out.
X_X real classy
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.
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.
man now i am also becoming pro in python, i have successfully done hello world
Awesome video, well done!
Damn understanding that question will take me 45 minute and when to solve it lmao 🤣🤣🤣🤣
Ya I thought I'm the only one
Loved your channel keep this good work going...hats of man
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.
Nice video Rachit.
loved this channel, specially solving coding questions like this, like Codejam-problems, specifically, I liked your solution on "Decryption Problem".
BTW, Are you giving Google's Codejam tomorrow?
if yes then all the best Rachit.
:)
Thanks
Ah it’s sorting the favorites list order by string length.. and do a for loop match with exist and add a space...
no. what about "abcde" and [ab,abc,cde,d,e]. you will check first abc and then add d and e, and the best solution will be ab cde.
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]
The condition to check whether we have already calculated for the position should be if(ans !=undefined) returns ans
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.
Loved the idea of doing mock interviews for Big Companies. Really helpful. Please keep doing it for other companies also. Thanks.
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.
Awesome video Rachit bro.. thanks.. it's helping a lot
I was hoping he was going to answer the question 😒
he did..that was the answer
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.🤗
Meanwhile white hat junior chintu op 😂
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
Can you please make a separate video explaining the detailed analysis on time complexity of this solution.
The DP array was supposed to be populated within the function. @Clement missed it, but good walkthrough overall.
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 would cut the string off whenever the longest string is found in the pi. Pass the new pi and new fav string for recursive call till the pi is empty or no fav string in pi. The run time is probably high. So far is what I think. Maybe a better way. Please share.
Finding right positions of the cut off part may be impossible here
Vatte Vaii i am thinking using a map with position as their key since the index is fixed.
We can do it in better complexity by using aho corasick algorithm. This will give time complexity of O(n + m).
Thanks dude. your way of thinking helped me learn a lot !!
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
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.
Something that doesn't blufff....i heard the question, and Subscribed. That's really what interview is 👏👏
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
I want to be a software engineer and after that video i getting afraid of the interview. If they ask me like this what can i do?
....just cry 😢
hehe
me too :(
Get up, shake the interview's hand, thank him for taking the time to see you, and then walk out the room without saying a single word.
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
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
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
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.
Hi Rachit,
I have a doubt about your solution.
Lets take this sample case(i have cut the lenght of Pi to make it bit more simple)
Sample Input:-
pi = 31415926535
favourite_words = [314,31415926,15926,535]
I think as per your given approach the result will give 3 as the minimum space required
but we can do that in 2 spaces as a minimum.
Please can u or anyone explain
I think it can be more optimized by using index and mapping
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.
Thank for creating close to real senario..... very soon I realised -> I can not be a Google engineering!.😂😂
I am wondering🤔💭 when will I become experts like you guys....?
I just completed with C and Don't know what to do next, Anyone please help me Which language should I go for next?
49-COMP A -Aakash Gupta C++ would be your best bet if your going into computer science, but any high level object oriented language would suit you, like Java. I’d recommend C++ over it though since it’s basically a higher level version of C.
@@ramonriddler228 thank you so much, I will be getting started with C++
Python
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
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.
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.
Is this the kind of Interview that happens in Google or Microsoft? I guess no because we don't write code while explaining the algo. It's the work of Pseudocode which is easy to understand either of the sides. Moreover, if my understanding is correct, the question is to find the string which is in the array and put the spaces if those string found in the pi values. In that case, you should have mentioned Boyer-Moore algo to search quickly. Correct me if I am wrong? It will help me to learn further.
Hi, 2 questions:
1) where are u assigning the values to dp[] during memoization,
2) Also the statement should be: if ans!=UNDEFINED then return ans
1) As he is initializing ans as a reference to the dp array element it will get updated during the computation of ans in the function below.
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.
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.
Careful rachit, be careful about your personal emails and stuff, read 2 email subjects of yours!
sooo??
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.
Great video ! Can it be converted into iterative solution ?
@Rachit Rachit please correct me if my approach is wrong. For me I will start with largest string in given array and find out if it is present in main string if it is then I will delete that substring from main string and increment space count and similarly will repeat this process for next large strings in given array.
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, ]