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.
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?
@@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
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.
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..
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).
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
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 ..
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,
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!
I just wonder that how many people cracking such coding interviews making quick & useful contribution in the companies... As these companies must be producing quick & successful products every time with such people in the teams who design perfectly & code for that quickly & perfectly... But I think reality is different.
In the simplest terms we can state the problem as: You have a large string (say S) and a list of strings (say L), now you want to split S into minimum number of parts so that all the parts exists in L.
How this would solve real production issues ? 😂 I would never prefer to have this in my production server. - "and you had to show that Apple logo yeah it's obvious 😂
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.
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..
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
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 !!!
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
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. 😭😭
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.
@@RachitJain Thanks a lot You replied, I got a relief I have been following you since long You are an inspiration to me. Q. So I don't have to shift to c++, or jave for speed n other stuffs?
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
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
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 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 ...
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.
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.
C++ solution using trie, minimumString. struct Node { char ch; Node* children[26] = { nullptr }; bool isWord; Node(char c) : ch(c), children(), isWord() {}; }; class Trie { public: Node *root; /** Initialize your data structure here. */ Trie() { root = new Node(' '); } /** Inserts a word into the trie. */ void insert(string word) { Node *t = root; for (char i : word) { if (t->children[i - 97] == nullptr) t->children[i - 97] = new Node(i); t = t->children[i - 97]; } t->isWord = true; } /** Returns if the word is in the trie. */ bool search(string word) { Node *t = root; for (char i : word) { if (t->children[i - 97] != nullptr) t = t->children[i - 97]; else return false; } if (t->isWord) return true; else return false; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { Node *t = root; for (char i : prefix) { if (t->children[i - 97] != nullptr) t = t->children[i - 97]; else return false; } return true; }
void minimumString(string s,string curr,vector allWordsByNow, vector &valid) { if (s.length() == 0) { valid.push_back(allWordsByNow); } else if (s.length() < 0) return; for (int i = 1; i insert(diction[i]); vector allwordsbynow; vector valid; trie->minimumString(s,"",allwordsbynow,valid); int max = 9999; for (vector i : valid) if (i.size() < max) max = i.size(); cout
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.
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)
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.
Hi Rachit, I'm really confused to pick the best interview programming language. I have recently started preparing interview. I have some degree of knowledge in both c++ and python, can you please help me out which lang is best for preparing the big companies like amazon, uber, google, microsoft. Thanks Sekhar Pariga
i was out when 793 ist one of your favorite numbers, "but 793 is not necessarily occouring" even when 793 was in the input number. but also im an dumb average guy ..
The only course you need to learn web development - HTML, CSS, JS, Node, and More! Join Millions of Learners from around the world already learning on Coding Blocks Jr!
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.
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!
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) ;
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 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
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.
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
love to see how whole YT community helping each other with such collabs
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
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 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.,😄✌️
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..
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 😂😂😂
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).
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
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.
Again Quaility content from this channel Thanks a lot
Awesome video, well done!
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
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.
Careful rachit, be careful about your personal emails and stuff, read 2 email subjects of yours!
sooo??
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, ]
I just wonder that how many people cracking such coding interviews making quick & useful contribution in the companies... As these companies must be producing quick & successful products every time with such people in the teams who design perfectly & code for that quickly & perfectly... But I think reality is different.
I think it should save the ans in dp[pos] before return ans or -1.
Like,
dp[pos] = ans;
return ans == INT_MAX ? (-1 : dp[pos]) ;
rachit is like near orange/purple in codeforces its a cakewalk for him .
why not just create a function to look through the given values of pi for text matches
Great video ! Can it be converted into iterative solution ?
Thank you #Rachit this video is really helpful.. Thanks a lot ...
wtf is this question? somewhat ambiguous, can somebody explain it to me?
In the simplest terms we can state the problem as: You have a large string (say S) and a list of strings (say L), now you want to split S into minimum number of parts so that all the parts exists in L.
I swear this seems so similar to word break on leetcode.
Samajh nahi aaya par sun k acha laga..
Thanks a ton!
Great it was great video well done
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
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
you must be that guy who does all the work in a group project damn.
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 thought coding interview only caused me to talk weirdly. Now I feel better
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.
Why they are talking in alien language
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.
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'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.
How this would solve real production issues ? 😂 I would never prefer to have this in my production server. - "and you had to show that Apple logo yeah it's obvious 😂
12:45 he was dreaming dude!!!
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...
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.
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..
Damn understanding that question will take me 45 minute and when to solve it lmao 🤣🤣🤣🤣
Ya I thought I'm the only one
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
I can done it with recursive ,, calling check thrive
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
Have no idea what I just watched but it was interesting
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 !!!
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.
man now i am also becoming pro in python, i have successfully done hello world
I was hoping he was going to answer the question 😒
he did..that was the answer
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. 😭😭
Meanwhile white hat junior chintu op 😂
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.
Why I watched the whole video though everything went over my head🤣...
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.
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
me not understanding anything but still watching this with full concentration. hahahha
:p
Hey Rachit,
I owe you a lot for my learning weekends.
Thanks a ton!! :)
Thanks
Can I use python for coding interviews
Or I have to shift to other languages (in 1-1.5yrs)
Do reply I m frustrated please.
Python is fine as well
@@RachitJain Thanks a lot
You replied, I got a relief
I have been following you since long
You are an inspiration to me.
Q. So I don't have to shift to c++, or jave for speed n other stuffs?
@@RachitJain or just make a video or coding interviews for python users
Thanks
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
Can this be solved using a trie instead? just add the fav array in there, and then check the main string. ?
i thought i would be a coder at google.. this video has made me stick to flipping burgers
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
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
Thank for creating close to real senario..... very soon I realised -> I can not be a Google engineering!.😂😂
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.
Rachit is laughing when this other guy pronoun his name
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 ...
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.
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.
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.
I am wondering🤔💭 when will I become experts like you guys....?
this video is so helpful I can sleep faster now 😂
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*
@@chiragsharmaUA-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
Iam a 12 year old kid and can produce better solution than this in 10 minutes
I Know Right ! This code was just stupid!
The DP array was supposed to be populated within the function. @Clement missed it, but good walkthrough overall.
aight, imma head out.
X_X real classy
ek batt bolu kuch smjh ni aya sirr k uprr se gya !!!
dil ki baat chin li dost
C++ solution using trie, minimumString.
struct Node
{
char ch;
Node* children[26] = { nullptr };
bool isWord;
Node(char c) : ch(c), children(), isWord() {};
};
class Trie {
public:
Node *root;
/** Initialize your data structure here. */
Trie() {
root = new Node(' ');
}
/** Inserts a word into the trie. */
void insert(string word) {
Node *t = root;
for (char i : word)
{
if (t->children[i - 97] == nullptr)
t->children[i - 97] = new Node(i);
t = t->children[i - 97];
}
t->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Node *t = root;
for (char i : word)
{
if (t->children[i - 97] != nullptr)
t = t->children[i - 97];
else return false;
}
if (t->isWord)
return true;
else return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node *t = root;
for (char i : prefix)
{
if (t->children[i - 97] != nullptr)
t = t->children[i - 97];
else return false;
}
return true;
}
void minimumString(string s,string curr,vector allWordsByNow, vector &valid)
{
if (s.length() == 0)
{
valid.push_back(allWordsByNow);
}
else if (s.length() < 0)
return;
for (int i = 1; i insert(diction[i]);
vector allwordsbynow;
vector valid;
trie->minimumString(s,"",allwordsbynow,valid);
int max = 9999;
for (vector i : valid)
if (i.size() < max)
max = i.size();
cout
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.
Ex Google Software Engineer using Apple Airpods Pro and Ex Microsoft Software Engineer using a Macbook. Whats this ;-;
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)
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.
Hi Rachit,
I'm really confused to pick the best interview programming language.
I have recently started preparing interview. I have some degree of knowledge in both c++ and python,
can you please help me out which lang is best for preparing the big companies like amazon, uber, google, microsoft.
Thanks
Sekhar Pariga
English Language Is Best..:)
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.
i was out when 793 ist one of your favorite numbers, "but 793 is not necessarily occouring" even when 793 was in the input number.
but also im an dumb average guy ..
The only course you need to learn web development - HTML, CSS, JS, Node, and More! Join Millions of Learners from around the world already learning on Coding Blocks Jr!
Junior hat teachers can solve it in 2 min based on their current claim that they can place their students in Google or spacex 😀😃😄😅🤣😆
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
i am 2019 passout Should I join Deloitte for BTA profile as a fresher and currently working in the startup last 3 months as a java developer plz reply
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!
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
Great collaboration...i saw algo expert and it is something that i need the most... thanks...
how long will it take to give an interview in DS&Algo if em a beginner.!?
and maybe em so late, this code "rachit" seems expired😎