Google Coding Interview with an ex-Microsoft Software Engineer
ฝัง
- เผยแพร่เมื่อ 16 มิ.ย. 2024
- ✅New TH-cam Account - Developer Bhaiya 👉🏻bit.ly/developer-bhaiya-youtube
👀rachitiitr.com - My Personal Portfolio and things I recommend for Coding Interviews.
Rachit, an ex-Microsoft Software Engineer and Clement, an ex-Google Software Engineer do a Mock Coding Interview.
Part II: • Mock Coding Interview ...
🔥 System Design Course: Educative - Must for experienced SDEs
➡ www.educative.io/collection/5...
💰First 100 Users can use "Rachit" as coupon code to get 10% off.
🔥 DailyCodingProblem: Access to Facebook, Google Interview Questions
➡ dailycodingproblem.com/rachit
💰Use "rachit" as coupon code to get 10$ off.
SUBSCRIBE AND HIT BELL ICON TO CHECK MORE OF MY CONTENT
th-cam.com/users/RachitJain?sub_con...
Social Profiles -
👀rachitiitr.com
👀 / rachitjain2095
👀 / rachitiitr
👀 AlgorithmsWithRachitJain
👀 / rachitiitr
================
Important Playlists:
================
🔥 30 Days of Interview Prep ➡ • Day 1: Interview Prep ...
🔥 Software Interview Experiences ➡ • CureFit Interview Expe...
🔥 Life Lessons I learnt for Success ➡ • How To Rock Your Softw...
MyProgrammingBlog
===============
Programming Blog ► rachitiitr.blogspot.com
Github ► github.com/rachitiitr/DataStr...
MyProgrammingProfiles:
===================
CodeForces ► www.codeforces.com/profile/rac...
CodeChef ► www.codechef.com/users/rachitiitr
![[TH] VCT Pacific Stage 2 - Week 1 Day 1 // DRX vs ZETA | BLD vs TS](http://i.ytimg.com/vi/AWaOqaxN6Y0/mqdefault.jpg)
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
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
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
Hey Rachit,
I owe you a lot for my learning weekends.
Thanks a ton!! :)
Thanks
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
Really nice interaction. Also i think this problem is same as word break O(n^2), chao.
Wow great insight!
Yes, that's the first thought came in my mind, it's a word break just with numbers.
This is a really interesting question... Gonna search if this question is on any coding platforms.. thanks for the question Clement and Rachit
search for 'word break', the code given in the video is not even close to be able to compile and will most likely to fail in a real google interview, to be honest
Rachit you are doing a great job your videos are very helpful. please make videos on how to get internship in companies like microsoft,google ,goldmansachs etc from offcampus. What are the process ,what are there expectations from interns ,how there resume should look like..
This is 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.
getting to a solution this fast needs a great level of practice. Well Done Rachit.
Thanks
@@sasmitvaidya3594 if u practise well, u'll get it in prob 2-3 months
@@sasmitvaidya3594 no way. I would think at least a year of learning.
@@bhanupratapsinghrajawat3686 maybe if you're Einstein, but we all normal folks need years
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🤣🤣🤣🤣🤣🤣
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.
Thanks for the great mock interview!
Loved your channel keep this good work going...hats of man
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
Loved the idea of doing mock interviews for Big Companies. Really helpful. Please keep doing it for other companies also. Thanks.
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.
Awesome video Rachit bro.. thanks.. it's helping a lot
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 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.
Again Quaility content from this channel Thanks a lot
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.
Awesome video, well done!
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 ...
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.
Thanks dude. your way of thinking helped me learn a lot !!
Great collaboration...i saw algo expert and it is something that i need the most... thanks...
I can done it with recursive ,, calling check thrive
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).
Something that doesn't blufff....i heard the question, and Subscribed. That's really what interview is 👏👏
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.,😄✌️
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
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.
Can you please make a separate video explaining the detailed analysis on time complexity of this solution.
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
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. 😭😭
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 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*
@@chiragsharma5594 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
Teekha hai ye launda!
Amazing work putting up these videos man! Thanks
The condition to check whether we have already calculated for the position should be if(ans !=undefined) returns ans
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.
12:45 he was dreaming dude!!!
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.
Task was quite simple.. it has to be bit more complex by adding more strings which could possibly be part of one big string indexed prior to the major string like 143, 2468 and then 2468143371337 then 337 and 7133 and there should be duplicate strings in the array . Task has to be finding the largest number of combinations.. I would have considering that the bigger string could have reduced the opportunity of finding more starting array from the major I would have started with the smaller one by identifying the place in the string and reserving the place I would have moved on to the other bigger one but there is only one challenge because may be a string with 3 integers May Block the possibility of getting 2 separate strings like if 314 is in middle and I reserve it let’s say before this there is a possibility to get something like 2231 and then 42356 since I chose smallest number say 314 and it not only blocked crating 2 more separate strings it would also minimise the chances of other strings for that I would try to create an nxn array to store the possible combinations it means if you have been given an array of 12 different strings then your main string should be split into 12x12 giving equal opportunity to each string to be placed first this would give you the best result with cyclomatic complexity of nxn/2.. voila
The DP array was supposed to be populated within the function. @Clement missed it, but good walkthrough overall.
I have my own approch to solve a mention problem.
Take the pi number in a string variable then start removing numbers from favorite number array(sort the array in descending order).
E.g.
string pi=3456789,
Array favArr = [6789,567,45,345]
// After sorting
NewFavArr = [6789,576,345,45]
// After first iteration of NewFavArr and removed matched array value
NewPi=345
MatchedValue=[6789]
// After next iteration i get output like
NewPi=[]
MatchedValue=[6789,345]
Output will be: 2(6789,345)
Wow. 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
Why they are talking in alien language
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
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 😂😂😂
Great video ! Can it be converted into iterative solution ?
Thanks Rachit for such kind of good discussion. Last Week I attended Microsoft interview and able to crack all rounds except Managerial (Including System design). I know only theoretical concepts and never get chance to work on real time systems Design.
Could you please suggest how/where can I learn more stuffs about system design. So Bdw you are doing great job 👍 and you videos are really helpful.
Awesome Video!
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.
Hey Rachit, could please share the problems in detail discussed in the video. I am attempting to take a different approach towards solving those and hence i need the exact statements of the problem. Thanks in Advance. :)
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!
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.
awesome bro also please do small video on content related to rust
Have no idea what I just watched but it was interesting
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
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
Would it have made sense to clarify the priority? I.e which is more important (and what trade off is acceptable) between number of matches and number of splits?
Clement should be interviewee sometimes too. It would be a lot of fun.🤗
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.
Great it was great video well done
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.
Thank you #Rachit this video is really helpful.. Thanks a lot ...
I think it can be more optimized by using index and mapping
Thanks a ton!
What if we use substr function and for each positive index that we get, we add the substring (or the favorite number) to our answer array
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.
hey!
could you tell me how vectors are better to use compared to arrays of the same datatype? in the question, u used vector to store fav array, could we have used an array there??
other than length flexibility, random access is much faster in arrays isnt it?
Please keep making such videos !! It was very helpfull and intresting
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.
We can do it in better complexity by using aho corasick algorithm. This will give time complexity of O(n + m).
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...
Rig8 now i have no idea of coding c++ and Python but i have started learning and i found it verry intersting ...or loving it...
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'm a CRUD boy, I don't need to deal with such problem, lol
Iterate over favArray instead of pi in the check function. Although the time complexity seems higher, the average best-case scenario would probably be better (say if length(favArray) is smaller and/or length of each value in favArray are longer). Is my assumption correct?
How do u do the iteration?
Good, but.. both seem confused on what the program is supposed to do. In development, clarity (ie someone can come in, read the code, and understand straight away) and modularization (code re-use, organize code efficiently as possible) are two of the most important things, the naming of the variables is a huge minus for clarity. The communication between them is clearly lacking. Also, what about test inputs and walking through the code and seeing if it worked? What about malformed test inputs? etc etc..
I am wondering🤔💭 when will I become experts like you guys....?
Maybe we could use a max heap to always start searching the biggest number, till no leftover strings are left.
Nice I like to cuss codeinterview since you can have them run their code with test cases
@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.
Amazing bro.
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.
Can this be solved using a trie instead? just add the fav array in there, and then check the main string. ?
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.
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]....
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..:)
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
I was hoping he was going to answer the question 😒
he did..that was the answer
bro do u have any idea about machine learning and AI courses.