This channel is our initiative to add to the community of programming interview preparation. It took us a long time to realize while preparing for the first software engineering interview we felt that the resources on programming interviews are not only sparse, but there lacked an abundance of people who could explain answers to interview questions in a way that a student could easily understand.
This channel aims to prepare someone to pass software engineering interviews at "the big 4" companies and any other large tech companies.
not only did you help me understand log in computer science but u also made me understand it in calculus. i came here to solve i problem i had, but got 2 problems solved instead
To me, the foundation of KMP is not the lookup table, but simply skipping mismatched string as much as possible. The first example should be like this: S='abcabc', P='abcd', because 'a', 'b', 'c', 'd' are unique in P, that means, if any prefix of P (e.g. 'abc') matched, there is no point searching from S[1] or S[2], because none of S[1] or S[2] could possibly be 'a' (the start of P). So, after checking that 'abca' != 'abcd', we can start searching from S[3] directly, skipping S[1] and S[2]. However what if not all letters in P are unique, e.g. S='abcabcad', P='abcad', well, when there is a mismatch ''abcab" != "abcad", I cannot skip the whole matched substring ("abca"), because "a" is repeated in the matched substring, we need to start from S[3], where it might be a potential match. Then how do we figure out to start from S[3], and smartly skipping S[1] and S[2]? Well because the "abc" part of "abca" contain non-repeated letters, so we can always skip the length of it, which is 3. One algorithm we can derive from this insight is that, we can check how long the prefix of P contains non-repeated letters, so we can skip that length whenever a mismatch, it is faster than advancing just 1 in S. However it would be the same speed as naive approach, when P is like 'aa....' The lookup table in KMP is a similar thing, however not just checking letter repeatness, but substring repeatness, so while we skipping the prefix which contains unique letters, we can also skip the the repeated matched substring.
I am currently readin EPI book and have decided to cover almost all of it, and this question just threw me off the chair. But you sir saved my ass, THANK YOU ! BTW I started reading this book thx to you, you mentioned it in one of ur videos. Recursion and DP sections are significantly harder than what ive encountered so far in this book. Did you go over these questions multiple times or just moved on to leetcode after ? In thinking of re-tracing my steps because these questions are so important, more than leetcode imo.
I've been reading Grokking Algorithms 2nd Edition, and found your explanation better. Though, I love the book too." One thing that bothers me in most explanations, including in GA2ndEd, is that they rarely deal with the case where the item you are looking for is the last one. In your example, of 1, 2, 3, 4, 5, 6, 7, 8 if we are looking for "8", and using the floor division approach (which GA2ndEd uses) we start with index 3, too low. Next we look at "5" within 5, 6, 7, 8. 2nd attempt, too low. Next we look at 7 within 7,8. Third attempt, and still too low. Now, unless we know ahead of time that the item we're looking for is guaranteed to be in the set, then we must make a 4th comparison to verify that 8 is indeed the last available item to examine. The book says it is going to explain this in chapter 4 (I'm only on 3) as to why constants are not used in Big O notation, but I just wish they and others would note this nuance when the list of items is a power of 2.
row = int(input()) user_input = [] for i in range(row): user_input.append(list(map(int, input().split()))) def kadane(user_input): max_global = float("-inf") max_current = 0 for i in range(len(user_input)): max_current += user_input[i] if max_current > max_global: max_global = max_current if max_current < 0: max_current = 0 return max_global max_global = float("-inf") running_row_sum = [0] * len(user_input) for run in range(len(user_input[0])): running_row_sum = [0] * len(user_input) for l in range(run, len(user_input[0])): for r in range(len(user_input)): current_number = user_input[r][l] running_row_sum[r] += current_number best_max_sub_list = kadane(running_row_sum) if best_max_sub_list > max_global: max_global = best_max_sub_list print(max_global) acm.timus.ru/problem.aspx?space=1&num=1146
Nice video man. I like your style of teaching, this is the first ever video of yours that I've watched and I like the casual style of teaching. It would be great if you could make videos that emphasize the guiding principle behind solving a problem and then share ways to attack the problem as well, in a direct way. Thanks and Cheers!
why are you explaining things better than the people who get paid to do it? why do I have to pay 1800 for college credit to learn the material on youtube?
1. why we are ONLY able to put the new left/right Parentheses at the rightest side every time? 2. According to the above limitation, why we could say the final level leafs are the answer? Thanks 🙇♂
