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.
@@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 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.
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 😂
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?
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
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.
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.
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.
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..
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. 😭😭
@@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
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 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.
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
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 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.
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.
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
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.
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,
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!
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 ..
Bhai i got 48% in 12 is their any chance that i can become a software engineer or not what should i learn . Thora knowledge dedo please. What should i do after 12 to become a software engineer should i do Cs, Cse , BCa or bohit sare hain kya karu ek comparison video banaiye or apna experience sgare kariye please.
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) ;
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.
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 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
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.
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
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
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 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
Why they are talking in alien language
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.
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.
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
12:45 he was dreaming dude!!!
I'm a CRUD boy, I don't need to deal with such problem, lol
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.
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 😂
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 😂😂😂
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 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.
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.
Probably a typo here:
if (ans == UNDEFINED) return ans;
Yeah thanks.
Read the comments just to find this comment. :)
What's the typo here?
Also, I think, in addition to returning the answer, he should also store the ans in that dp array...
Have no idea what I just watched but it was interesting
Meanwhile white hat junior chintu op 😂
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..
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.
love to see how whole YT community helping each other with such collabs
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 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.,😄✌️
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
I was hoping he was going to answer the question 😒
he did..that was the answer
Why I watched the whole video though everything went over my head🤣...
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.
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.
me not understanding anything but still watching this with full concentration. hahahha
:p
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🤣🤣🤣🤣🤣🤣
man now i am also becoming pro in python, i have successfully done hello world
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.
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..
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. 😭😭
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
aight, imma head out.
X_X real classy
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
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
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.
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
Thank for creating close to real senario..... very soon I realised -> I can not be a Google engineering!.😂😂
Rachit is laughing when this other guy pronoun his name
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
Careful rachit, be careful about your personal emails and stuff, read 2 email subjects of yours!
sooo??
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
ek batt bolu kuch smjh ni aya sirr k uprr se gya !!!
dil ki baat chin li dost
Iam a 12 year old kid and can produce better solution than this in 10 minutes
I Know Right ! This code was just stupid!
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.
Always yep
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 ...
Ex Google Software Engineer using Apple Airpods Pro and Ex Microsoft Software Engineer using a Macbook. Whats this ;-;
this video is so helpful I can sleep faster now 😂
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.
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
I am not going to this interview...
What's your emailid rachit?
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
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.
I am wondering🤔💭 when will I become experts like you guys....?
Basically everything looks complicated to my simple brian.
Basically..!
Please code 64 bit X86 emulation on ARM for Windows. TY. Have nice day.
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.
Hey Rachit,
I owe you a lot for my learning weekends.
Thanks a ton!! :)
Thanks
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
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
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.
Junior hat teachers can solve it in 2 min based on their current claim that they can place their students in Google or spacex 😀😃😄😅🤣😆
where do I get the question you discussing??
Rachit, you have done 2 mistakes in your code
1. if ( ans == UNDEFINED), you should not return ans. If ( ans !=UNDEFINED), then you should return the answer.
2. You have to assign dp[pos] = ans in the end. Otherwise, dp array is of no use.
Thanks,
1 is a typo. And 2 is just fine, you are mistaken. Read about reference in cpp.
Yes you are right. Thanks.
I 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.
Alert alert ,Be sure to clear browsing history in any interview!!!
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!
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 ..
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
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*
@@chiragsharmaRUclips 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
We can do it in better complexity by using aho corasick algorithm. This will give time complexity of O(n + m).
Bhai i got 48% in 12 is their any chance that i can become a software engineer or not what should i learn . Thora knowledge dedo please. What should i do after 12 to become a software engineer should i do Cs, Cse , BCa or bohit sare hain kya karu ek comparison video banaiye or apna experience sgare kariye please.
I understand the problem and how to do it in no time but the thing is my Implementation sucks... Well, I just completed C data structures...
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😎
Fucking straight forward questjon by taking alot of time? Iterate and loop through the array as well as string.
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
tired of new algo website? ex google, why?
He is an ex_Microsoft Software Engineer and uses a MacBook. Do you know the reason why doesn't he work there?
"hello...yup i am following" lmao :p
Actually this question is not much more hard this is similar to word break problem + apply dp to minimize no of space
Work hard until your name will be added to algoexpert for discount 😀
Was it neccesary to show macbook and cover half of the screen. Its not a luxury nowdays ;)
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.