I learned for those interview questions, the most important things is to ask the interviewer FOR ALL THE SPECIFIC DETAILS, whether u get a answer or not. Like the size of data, do we need to worry invalid data? what's the definition of anagram do white space count? etc For the "Kth largest element", you just need to save the largest kth numbers into a array while run through the number and compare it to the Kmin. If it's larger then Kmin, replace the Kmin, and so on.
3:19 For the anagram you can use 1 hash table but on the 2nd loop when you ask if the character of the second word is not on the table , return false. If it is on the table then rest 1 on that key. At the end ask if any value on the hash is not zero , return False. At last you can return True.
Rule for finding the middle element at 8:22 There is a chance for overflow when we are adding to massive numbers so instead of dividing directly by 2 we do either of the 2 following approaches: 1. left + (right-left)/2 2. left + right >>> 1
@@vekyll you’re proving the point I made with another comment stating he shouldn’t use python but instead use Java. People reading that line of code would assume it’s the same for other languages and would end up committing the overflow error. I’ll say it again python is not verbose, it’s not good for explaining concepts.
@@Makwayne Well, it depends on the concepts, of course. If the concept is that addition is associative, Python is almost perfect. If the concept is that numbers are sometimes put in boxes of fixed size, then obviously it isn't. :-)
There is a faster method of solving for the Kth largest element. 1. We walk through the array and put elements into the max-heap only for i = 1 to k. 2. For i = k to N, where N = len(arr), we only add arr[i] to the max-heap if arr[i] > heap.peek(). We also have to pop one element to maintain the heap length to k. 3. Once we have completely walked through the array, we return the top element from the heap. Thus we construct a heap of only k elements and walk through the array once.
The memory complexity of the first one can be further reduced by using a single hash map. The first word increments the values, the second one decrements. After that only 0 must exist as a value in the hash map
I find a lot of comments discussing about more optimized solutions and that's interesting, but I feel alone finding that most of these problems are very tricky to get right. I'm 100% sure that I'd fail most of them in an interview (provided that I haven't been exposed to that exact problem beforehand). It just feels like you really need that one completely unobivous trick that some genius discovered 80 years ago and probably wrote a PhD about. I feel so dumb and this video just makes me feel bad about myself honestly. I don't unerstand why companies ask such questions in interviews because they're completely unnecessary for whatever job you intend to apply to.
I have been a developer for more than 20 years. In the last 10 (or less) of that, I have seen a lot of "interview questions" that are basically just "show you know algorithms". What I have not seen much at all are real world examples of how these are used. For example, show me a website on the internet where the developer needed to understand how to solve the anagram problem?
Don't get me wrong... I undesrand as well as anyone (and better than most) that programming is first and foremost about problem solving. And I love the idea of algorithms, which classically is simply breaking down a problem into individual steps. But creating such specific questions (problems) that require such specific solutions doesn't really test an applicants problem solving skills as much as it does their participation in certain bootcamps. I really believe this is all realted to the massive profits seens by bootcamps as corellation with the massive turnover at FANG, et al companies. It's pretty obvious.
Website itself works based on graph algorithms. How DOM was parsed using HTML parser? (Traversal algorithms - DFS, BFS) How Database indexing works ? (Binary Search Tree) How identity columns was generated ? How Google Map works? (Random number algorithm) How files/folder ordering works in desktop? (sorting) How browser history was stored in the browser ? (stack) Can you show us any application which doesn't use algorithms ?
You may not need to solve an anagram, but you need to know when and how to use a frequency counter. You don’t calculate the big O of every piece of code, but it helps to know that some solutions are blazingly faster than others, some solutions are way more space efficient. Time and storage cost money after all.
3:10 Instead of making 2 maps and comparing (which is actually O(a) size where a is the size of the alphabet which even you mentioned could be huge) instead make the first map, then for the second string decrement the original map and if any value goes below 0 then return false (guaranteed they’re the same size so this also guarantees completeness).
What if the first string has more occurrences of a certain character? For example, if s1 = "aa" and s2 = "ab", the function returns true because the key "a" ends up with a positive value.
@@t-man9680 good question. Let's work the example. If string one was 'aa' then the map would look like {'a':2} after the "adding phase". Now we move on to string two which is 'ab'. We see that there's 'a' and decrement so now the map looks like this {'a':1} Now we have 'b' and decrement so the map looks like {'a':1, 'b':-1} and return false because we have a negative value (or semantically you could say that there wasn't a value for 'b' greater than 0) Therefore this works. Because the lengths are guaranteed to be the same and my method is essentially checking if there are at least as many of a given character in string 2 as in string 1 (and vv) then we can conclude that it's checking if there are exactly as many occurrences in s2 as in s1 qed. Definitely do not iterate the whole map, that's the entire point on this improvement. If the alphabet is large then this wouldn't even be O(n). For example, the Unicode alphabet. We would have to check millions of characters even if our strings are 100 characters.
@@bzboii we do not decrement anything we quit. If second string has character that is not in the first map you exit because it cannot be anagram. there is no need to check for 0. You either quit when one goes below 0 (extra char) or it is not found. There could be no other way because strings should be checked for equal length. Once you get to end of the loop - they are both anagram because you didn't return earlier.
If anyone was very confused at what he was saying at 31:40, it sounds like he's saying "Here, we darkly backtrack" but he's actually saying "Here, we *directly* backtrack. Also a lot of the time, it sounds like he's saying "can" when he's actually saying "can't" so watch out for that.
Wow, python has so many powerful built-in methods that make algorithm problems much easier, but I am not a python expert and I don't remember many methods in pythons... Still glad python makes the life easier for many people.
Just a note on the 'valid anagram' problem -- if you're going to use python sorted() function to compare strings you'll need to lowercase them first. Otherwise 'danger' and 'gArden' won't be considered anagrams. Sorting for that problem was not the most efficient solution, but it's good to be aware of the gotchas!
In the Kth permutation problem 1:07:40 The time complexity of the first solution is not O(n!) ? You said it is O(n * n!) but the time complexity of itertools.permutations(range(1, n + 1)) is O(n!) Thanks!
For "First & Last Index of a Target num in sorted Array" (single loop) a = [2,4,5,5,5,5,5,7,9,9] def get_start_and_end(target): start,end = None,None for i in range(0,len(a)): if start == None and a[i] == target: start = i elif a[i] == target: end = i return start,end
Thank you for this video and all your effort. About the course schedule question: for the DFS solution to maintain the ‘order’ list is unnecessary as we never actually use it or use if for any condition. Also, for the BFS solution instead of maintaining list of order, cheaper to use a counter to count how many items were popped from the queue. Your solution works better if you need to return the order. Thanks again!
Finding the Kth largest/smallest element can be done in O(n) time with QuickSelect (en.wikipedia.org/wiki/Quickselect). Tl;dr on the wikipedia description: You do Quicksort, without recursing on the side you aren't interested in. 1 - Select a pivot at random 2 - Put everything smaller than it to the left of the array, and everything larger than it to the right (reverse the logic if you're looking for Kth larger) 3 - Put pivot in it's place 4 - if pivot_idx == k, return pivot. Else, call recursively into the proper subarray to the left or right of pivot_idx There is a theoretical worst case of n^2 (when the array is already sorted and you always pick the smallest/largest element on the subarray), but it is in practice avoided by selecting the pivot at random.
Hi, I am a beginner in Python but I think the second problem has a very simple solution only in 5 lines.: def find_first_last(arr, tar): l2 = [] for index, num in enumerate(l): if num == tar: l2.append(index) return [l2[0], l2[-1]] l = [2, 4, 5, 5, 5, 5, 5, 7, 9, 9] print(find_first_last(l, 5))
He's only making sure to not have more iterations than necessary, in the first solution. Time complexity comes in to play when there's a huge amount of data to go through. For example, if we have an array of 1 million elements and our solution lies within the first 100, we'd have iterated 9,99,900 times unnecessarily. In his optimized approach he makes use of binary search which has a logarithmic time complexity.
You will need more space for this solution. Imagine a case where all your array elements are equal to the target. You will be storing O(n) indices in memory. His own solution is O(1).
Maybe this will work I guess def first_and_last(arr,target): mylist=[] for i in range(0,len(arr)): if arr[i] == target: mylist.append(i) else: print([-1,-1]) print([mylist[0],mylist[-1]])
18:58 In the Kth largest Instead of putting all the elements into the heap, make a min heap (not max heap, for the Kth largest) and put a check inside the loop which is going over all the elements to be put into the loop. The check would limit the size of the PQ to 'K' elements, something like if(pq.size() > k) pq.poll(). Once we are through with the loop, we will have our kth largest element on top of the PQ, so simple return pq.peek();
There is actually an error at 4:27. "nameless" and "salesman" are NOT anagrams. because the later one does not have two times the character "e" as it shown on the slide
3:30 this code can be reduced more like this: def sol(s, ss): if len(s) != len(ss): return False d = dict() for i in range(len(s)): if s[i] not in d: d[s[i]] = 1 else: d[s[i]] += 1 for i in ss: if i in d and d[i] > 0: d[i] -= 1 else: return False return True s = "garden" ss = "danger" print(sol(s, ss))
At 11:29, would it make more sense to set the initial left value to the value found in the find_start method? Although it wouldn't change the time complexity, I think it would result in, on average, one less operation done by the find_end binary search.
You can loop through the array from beginning ,find your target break from the array and then record it index number, Then do the same from back in another loop and break when target found .Since it's a sorted array this consume less time🙂🙂🙂
For the anagram problem, count the occurrence of each character in string one. Then for each character of string two, reduce the occurrence count of that character if it's nonzero, otherwise exit with the conclusion that it's not an anagram.
Nice coverage. Problem 5 presentation could be modified. You spend only about 4 seconds on the problem statement, before diving into definitions and sample code for several minutes.
For parentheses is Enter parentheses string s Char * c = s; Int n=0; Do { If *c==‘(‘ than n+=1; If *c==‘)’ than n+=-1; }while( *c++ != ‘\0’) Analyse your result if (-, 0 , +)
For the gas station: I looked at the assignment and got this: Python: def find_starting_station(gas, cost): n = len(gas) current_gas = 0 starting_point = 0 for i in range(n): current_gas += gas[i] current_gas -= cost[i] if current_gas < 0: starting_point = i + 1 current_gas = 0 for i in range(starting_point): current_gas += gas[i] current_gas -= cost[i] if current_gas < 0: return -1 return starting_point --This function takes in two lists: one for the gas at each station, and one for the cost to travel to the next station. It starts by initializing the current_gas and the starting_point to 0. Then it iterates through the list of gas stations, adding the gas at each station to current_gas, and subtracting the cost to travel to the next station. If at any point the current_gas becomes negative, it means it is not possible to traverse all the stations from that starting point, so it sets the starting point to the next index and resets current_gas to 0. After the first iteration, it checks again from the starting_point. If at any point current_gas becomes negative, it returns -1, otherwise it returns the starting_point index. -- Is this correct?
question for kth largest element: We can assume that in the worst case, the kth largest element would be the len(arr)th element. so in the example where arr = [4, 2, 9, 7, 5, 6, 7, 1, 3], you could call for the 9th largest element, which would be the minimum element, which by the solution, you would have to essentially either use len(arr) if either starting from len(arr) - k or from i in range(len(arr)). So could we not assume that in the worst case, k = n and say that the solution 1 would operate in n^2 time since we are characterizing the worst case? or would we technically say that the time complexity is O(kn), with the caveat that k could = n?
I think I have a faster way of solving the anagram: def findAnagram(word1, word2): for i in word1: if i in [*word2] and len(word1) == len(word2): pass else: return False return True a = findAnagram("garden", "danger") print(a)
really appreciated this. the course pre-requisite problem is not how courses work. if a course has two prerequisites, then both of those need to come first.
That anagram stuff -- why not, but much simplier (in Python anyways) is just sort alphabetically both strings and compare them. If they are anagrams, sorted strings would be same.
You probably know this already. Sorting has a bigger O complexity. O (n log (n) ). When you create a hash, you sacrifice space O(n); but you improve time complexity to Big O(n)
The speaker says O(log n), which is smaller than O(n * log n). This is because we much consider the data the program puts on the stack as we enter each level of recursion. In this case, every time we check if the left and right sub trees are mirrors, we add a frame to the stack. We do this all the way down the tree.
However, the speaker made a minor mistake. They claim that symmetric trees must be balanced binary trees. Balanced binary trees are defined as a binary tre where the height of the left and right subtrees, for every node in the tree, cannot differ by more than 1. Therefore, the height of the a balanced binary tree must be O(log(n)). The mistake is that symmetric trees do not need to be balanced binary trees. A symmetric tree height can be up to n/2 when the left subtree has all left nodes and the right subtree has all right nodes. Thus, the space complexity is O(n). Example: ``` 1 2 3 4 5 6 7 8 9 ``` In this type of structure: ``` n height log(n) n/2 9 5 3.17 4.5 11 6 3.45 5.5 13 7 3.7 6.5 ``` As we can see, the height of the tree, and thus the number of frames on the stack, scale with O(n/2), which we write as O(n).
thank you, these are useful examples. For next time I would appreciate it if you made an effort to try to enunciate your words more clearly or at least write out captions, as it's difficult to understand what you're saying much of the time and the auto caption tool doesn't seem to fare much better
This video serves 2 purposes - you can learn from it, and it can be a bed time story on the Calm app. Great material, but maybe next time have a coffee before you record
the answer to 1 is way too complicated. better answer imo: if (a b) andalso (sort(a) = sort(b)) ... sort( sorts a string so each character in the string is placed in alphabetical order ). the answer to 5 is again too complicated - but you have the idea. to improve rather than use stacks just +1 to total for "(" and -1 to total for "(", the rest is more or less the same, if total ever goes below zero its invalid, total must = 0 in the end.
Its not about whether or not the solutions are complicated or simple... it's about getting time complexity and space complexity as optimal as possible and sometimes getting to that means having a more "complicated" solution. Your solution might be simpler but it doesn't necessary mean it's optimal. Also your solution to the first one is already one of the solutions given in the video itself
@@insidecode Sorry I clearly jumped the gun. At 2:02 I heard 'the best structure for our problem is the hash tables' so I just moved on. The same with 5 when talk was of pushing and popping.
@@roblatour3511 It really is a balancing act. In most situations, I agree.. easy to understand is better, as your code is going to be read by others in a professional environment. There are cases though, where less easy to understand solutions are better, if they provide better performance. Amazon for example, has plenty of teams that deal with code that requires handling millions of requests per second.. at that level, performance is key.
For the parenthesis you could also just do this: -if it's got an odd length or it starts with ')', return false -else, if the count of '(' == count of ')', return true, else return false
thanks for this free content but the subtitles are bad and the accent too. I didn't get why space complexity is O(1) since the array is not a costant but a function parameter. thank you very much
Easy JS solution for number 1 function firstAndLastIndex (arr, target) { return `${arr.indexOf(target)} ${arr.lastIndexOf(target)}` } I'm lost after that. Long ways to go I guess!
for the anagram i used only one loop , i worked with java but idea is declaring an int counter = 0 and test if string n° 1 contains a character in string n°2 with charAt[i] if true counter++ and in the end test again if string n°1 length is equal to the counter if true then the two words are anagram for (int i=0;i
For the anagram question, would it be possible to just add the total value of each string and compare them via ASCI value? If they're equal then they're an anagram if not then it's not (make all letters uppercase or lowercase first )?
I believe that will be inaccurate as you can have a character with higher ascii value which is equal to sum of the ascii values of other characters. So the two words will be different and you may still get the same total ascii value. I hope this answer's your question.
Haven't tested it but in the Symmetric tree problem (26:24), I think are_symmetric can only give True when going all the way down and finding two nodes that they both don't have children?, I think you are missing an elif with root1.val == root2.val then return True there?. Can someone confirm this?
You would only need to go all the way to the bottom if you don't find a difference before then. Basically we're walking every possible branch in the tree until we hit a difference then we stop. You can't return True finally unless you know for sure that both tree halves are identically mirrored, and the only way to do that is to recursively walk through the whole tree but stop if you find an exception. So, there is a range of time complexity. The worst case is when the two actually are symmetric because you end up comparing every single node. Then the next worse is when the very bottom node is the only one that's different, then it gets better and better as the difference gets higher up the tree, until the best case where the top root node is different (or they're both null). If you watch the animation at 2:36 again I think it will click. There's nothing else you need to add
what if I compare string lengths and then compare the character in String 2 and then if count == len(s1) then its anagram, would it not be an anagram solution s1 = "danger" s2 = "garden" if len(s1) == len(s2): print("length is same so it can be anagram") count = 0 for ch in s1: if ch in s2: count = count + 1 if count == len(s1): print('Anagram string') else: print("Not anagram")
I learned for those interview questions, the most important things is to ask the interviewer FOR ALL THE SPECIFIC DETAILS, whether u get a answer or not. Like the size of data, do we need to worry invalid data? what's the definition of anagram do white space count? etc
For the "Kth largest element", you just need to save the largest kth numbers into a array while run through the number and compare it to the Kmin. If it's larger then Kmin, replace the Kmin, and so on.
3:19 For the anagram you can use 1 hash table but on the 2nd loop when you ask if the character of the second word is not on the table , return false.
If it is on the table then rest 1 on that key.
At the end ask if any value on the hash is not zero , return False.
At last you can return True.
Rule for finding the middle element at 8:22
There is a chance for overflow when we are adding to massive numbers so instead of dividing directly by 2 we do either of the 2 following approaches:
1. left + (right-left)/2
2. left + right >>> 1
Python's numbers are true numbers, not limited-size boxes. There is no chance of overflow.
@@vekyll you’re proving the point I made with another comment stating he shouldn’t use python but instead use Java. People reading that line of code would assume it’s the same for other languages and would end up committing the overflow error. I’ll say it again python is not verbose, it’s not good for explaining concepts.
@@Makwayne Well, it depends on the concepts, of course. If the concept is that addition is associative, Python is almost perfect. If the concept is that numbers are sometimes put in boxes of fixed size, then obviously it isn't. :-)
My professor taught it that way! Good point 👍
There is a faster method of solving for the Kth largest element. 1. We walk through the array and put elements into the max-heap only for i = 1 to k. 2. For i = k to N, where N = len(arr), we only add arr[i] to the max-heap if arr[i] > heap.peek(). We also have to pop one element to maintain the heap length to k. 3. Once we have completely walked through the array, we return the top element from the heap. Thus we construct a heap of only k elements and walk through the array once.
This would be O(n.log(k)) , there is an even faster O(n) solution that does not require any additional data structures - using quick select.
in python what if you do
list.sort()
return lis[-k]
@@adithyaravindra5596 Yeah but this modifies the original list which is usually bad. I prefer:
sorted_arr = sorted(arr)
return sorted_arr[-k]
The memory complexity of the first one can be further reduced by using a single hash map. The first word increments the values, the second one decrements. After that only 0 must exist as a value in the hash map
I was thinking about the same too!
Its funny how many problems can be made more efficient with a hashmap
I find a lot of comments discussing about more optimized solutions and that's interesting, but I feel alone finding that most of these problems are very tricky to get right. I'm 100% sure that I'd fail most of them in an interview (provided that I haven't been exposed to that exact problem beforehand). It just feels like you really need that one completely unobivous trick that some genius discovered 80 years ago and probably wrote a PhD about. I feel so dumb and this video just makes me feel bad about myself honestly. I don't unerstand why companies ask such questions in interviews because they're completely unnecessary for whatever job you intend to apply to.
its okay no one knows what they are doing just keep going and before you realize it you'll also be posting more optimized solutions
I have been a developer for more than 20 years. In the last 10 (or less) of that, I have seen a lot of "interview questions" that are basically just "show you know algorithms". What I have not seen much at all are real world examples of how these are used. For example, show me a website on the internet where the developer needed to understand how to solve the anagram problem?
Don't get me wrong... I undesrand as well as anyone (and better than most) that programming is first and foremost about problem solving. And I love the idea of algorithms, which classically is simply breaking down a problem into individual steps. But creating such specific questions (problems) that require such specific solutions doesn't really test an applicants problem solving skills as much as it does their participation in certain bootcamps. I really believe this is all realted to the massive profits seens by bootcamps as corellation with the massive turnover at FANG, et al companies. It's pretty obvious.
Website itself works based on graph algorithms.
How DOM was parsed using HTML parser? (Traversal algorithms - DFS, BFS)
How Database indexing works ? (Binary Search Tree)
How identity columns was generated ? How Google Map works? (Random number algorithm)
How files/folder ordering works in desktop? (sorting)
How browser history was stored in the browser ? (stack)
Can you show us any application which doesn't use algorithms ?
You may not need to solve an anagram, but you need to know when and how to use a frequency counter.
You don’t calculate the big O of every piece of code, but it helps to know that some solutions are blazingly faster than others, some solutions are way more space efficient. Time and storage cost money after all.
3:10 Instead of making 2 maps and comparing (which is actually O(a) size where a is the size of the alphabet which even you mentioned could be huge) instead make the first map, then for the second string decrement the original map and if any value goes below 0 then return false (guaranteed they’re the same size so this also guarantees completeness).
What if the first string has more occurrences of a certain character? For example, if s1 = "aa" and s2 = "ab", the function returns true because the key "a" ends up with a positive value.
Guess you’d check to make sure all the values are exactly 0 then
@@t-man9680 good question.
Let's work the example.
If string one was 'aa' then the map would look like {'a':2} after the "adding phase".
Now we move on to string two which is 'ab'. We see that there's 'a' and decrement so now the map looks like this {'a':1}
Now we have 'b' and decrement so the map looks like {'a':1, 'b':-1} and return false because we have a negative value (or semantically you could say that there wasn't a value for 'b' greater than 0)
Therefore this works.
Because the lengths are guaranteed to be the same and my method is essentially checking if there are at least as many of a given character in string 2 as in string 1 (and vv) then we can conclude that it's checking if there are exactly as many occurrences in s2 as in s1 qed.
Definitely do not iterate the whole map, that's the entire point on this improvement. If the alphabet is large then this wouldn't even be O(n).
For example, the Unicode alphabet. We would have to check millions of characters even if our strings are 100 characters.
@@abhi9988 not necessary. And definitely do not iterate the entire map. See my reply to the comment.
@@bzboii we do not decrement anything we quit. If second string has character that is not in the first map you exit because it cannot be anagram. there is no need to check for 0. You either quit when one goes below 0 (extra char) or it is not found. There could be no other way because strings should be checked for equal length. Once you get to end of the loop - they are both anagram because you didn't return earlier.
For the third problem, with the parethesis,
You may produce all valid parenthesis using the Catalan recursion.
Just like everytime , High quality content for free . ❤️
@@waruniadithya2630 terimakasi
You paid for device and internet connection
So not free..
@@sauravkumar3278 go to a library then...
@@carlos144 You paid for the food which gave you the energy to walk so not free 😏
@@orangesnowman7137 you were raised by your parents which costs a lot; so its not free
The last problem in "heights" array there is an extra 10 in list at index 10 after 9, comapred with the histogram.
If anyone was very confused at what he was saying at 31:40, it sounds like he's saying "Here, we darkly backtrack" but he's actually saying "Here, we *directly* backtrack. Also a lot of the time, it sounds like he's saying "can" when he's actually saying "can't" so watch out for that.
Wow, python has so many powerful built-in methods that make algorithm problems much easier, but I am not a python expert and I don't remember many methods in pythons... Still glad python makes the life easier for many people.
Sound of this tutorial is not clear to understand. However the topics are clearly explained. Thanks
Just a note on the 'valid anagram' problem -- if you're going to use python sorted() function to compare strings you'll need to lowercase them first. Otherwise 'danger' and 'gArden' won't be considered anagrams. Sorting for that problem was not the most efficient solution, but it's good to be aware of the gotchas!
That’s not the same problem.
@@lukenothere1252 That's exactly the same problem. You clearly learned nothing.
The solution provided was case sensitive in mind.
I think not only Python, but for example Arrays.sort() in Java also needs to deal with the case-sensitive stuff.
Then what's the optimal solution?
at 1:03 my anagram checker solution
def are_anagram(s1,s2):
if len(s1) != len(s2) or set(s1) != set(s2):
return False
else:
return Truetemplate = 'garden'
checker = 'danger'
anagram_check(template,checker)
In the Kth permutation problem 1:07:40
The time complexity of the first solution is not O(n!) ?
You said it is O(n * n!) but the time complexity of itertools.permutations(range(1, n + 1)) is O(n!)
Thanks!
For "First & Last Index of a Target num in sorted Array" (single loop)
a = [2,4,5,5,5,5,5,7,9,9]
def get_start_and_end(target):
start,end = None,None
for i in range(0,len(a)):
if start == None and a[i] == target:
start = i
elif a[i] == target:
end = i
return start,end
Started coding 3 years ago since i was 9 still learning a lot of things from this channel its a blessing that this channel actualy exists
you gonna be the 20 years old dude with 12 years of experience XDDD
Thank you for this video and all your effort.
About the course schedule question: for the DFS solution to maintain the ‘order’ list is unnecessary as we never actually use it or use if for any condition.
Also, for the BFS solution instead of maintaining list of order, cheaper to use a counter to count how many items were popped from the queue.
Your solution works better if you need to return the order.
Thanks again!
Finding the Kth largest/smallest element can be done in O(n) time with QuickSelect (en.wikipedia.org/wiki/Quickselect).
Tl;dr on the wikipedia description: You do Quicksort, without recursing on the side you aren't interested in.
1 - Select a pivot at random
2 - Put everything smaller than it to the left of the array, and everything larger than it to the right (reverse the logic if you're looking for Kth larger)
3 - Put pivot in it's place
4 - if pivot_idx == k, return pivot. Else, call recursively into the proper subarray to the left or right of pivot_idx
There is a theoretical worst case of n^2 (when the array is already sorted and you always pick the smallest/largest element on the subarray), but it is in practice avoided by selecting the pivot at random.
On average it is O(n) but worst case is O(n^2)
Hi, I am a beginner in Python but I think the second problem has a very simple solution only in 5 lines.:
def find_first_last(arr, tar):
l2 = []
for index, num in enumerate(l):
if num == tar:
l2.append(index)
return [l2[0], l2[-1]]
l = [2, 4, 5, 5, 5, 5, 5, 7, 9, 9]
print(find_first_last(l, 5))
He's only making sure to not have more iterations than necessary, in the first solution. Time complexity comes in to play when there's a huge amount of data to go through. For example, if we have an array of 1 million elements and our solution lies within the first 100, we'd have iterated 9,99,900 times unnecessarily.
In his optimized approach he makes use of binary search which has a logarithmic time complexity.
You will need more space for this solution. Imagine a case where all your array elements are equal to the target. You will be storing O(n) indices in memory.
His own solution is O(1).
Maybe this will work I guess
def first_and_last(arr,target):
mylist=[]
for i in range(0,len(arr)):
if arr[i] == target:
mylist.append(i)
else:
print([-1,-1])
print([mylist[0],mylist[-1]])
18:58 In the Kth largest
Instead of putting all the elements into the heap, make a min heap (not max heap, for the Kth largest) and put a check inside the loop which is going over all the elements to be put into the loop. The check would limit the size of the PQ to 'K' elements, something like if(pq.size() > k) pq.poll(). Once we are through with the loop, we will have our kth largest element on top of the PQ, so simple return pq.peek();
I think it works yes
There is actually an error at 4:27. "nameless" and "salesman" are NOT anagrams. because the later one does not have two times the character "e" as it shown on the slide
salesmen* not salesman
3:30 this code can be reduced more like this:
def sol(s, ss):
if len(s) != len(ss):
return False
d = dict()
for i in range(len(s)):
if s[i] not in d:
d[s[i]] = 1
else:
d[s[i]] += 1
for i in ss:
if i in d and d[i] > 0:
d[i] -= 1
else:
return False
return True
s = "garden"
ss = "danger"
print(sol(s, ss))
At 11:29, would it make more sense to set the initial left value to the value found in the find_start method? Although it wouldn't change the time complexity, I think it would result in, on average, one less operation done by the find_end binary search.
You can loop through the array from beginning ,find your target break from the array and then record it index number, Then do the same from back in another loop and break when target found .Since it's a sorted array this consume less time🙂🙂🙂
Question 1 has space order o(1) because it could only be as big as the alphabet, if you think 26 lowercase letters, even though `n` could be infinite.
For the anagram problem, count the occurrence of each character in string one. Then for each character of string two, reduce the occurrence count of that character if it's nonzero, otherwise exit with the conclusion that it's not an anagram.
Thanks a lot for your work. And also side note, you sound a lot like gru which is cute.
Good night! I live in Brazil I would like to say that your channel has content that others don't.
Nice coverage. Problem 5 presentation could be modified. You spend only about 4 seconds on the problem statement, before diving into definitions and sample code for several minutes.
For the first one, you can just do:
def validAnagram(s1, s2):
return Counter(s1) == Counter(s2)
That was mentioned in the video
For parentheses is
Enter parentheses string s
Char * c = s;
Int n=0;
Do {
If *c==‘(‘ than n+=1;
If *c==‘)’ than n+=-1;
}while( *c++ != ‘\0’)
Analyse your result if (-, 0 , +)
For the gas station:
I looked at the assignment and got this:
Python:
def find_starting_station(gas, cost):
n = len(gas)
current_gas = 0
starting_point = 0
for i in range(n):
current_gas += gas[i]
current_gas -= cost[i]
if current_gas < 0:
starting_point = i + 1
current_gas = 0
for i in range(starting_point):
current_gas += gas[i]
current_gas -= cost[i]
if current_gas < 0:
return -1
return starting_point
--This function takes in two lists: one for the gas at each station, and one for the cost to travel to the next station.
It starts by initializing the current_gas and the starting_point to 0.
Then it iterates through the list of gas stations, adding the gas at each station to current_gas, and subtracting the cost to travel to the next station.
If at any point the current_gas becomes negative, it means it is not possible to traverse all the stations from that starting point, so it sets the starting point to the next index and resets current_gas to 0.
After the first iteration, it checks again from the starting_point.
If at any point current_gas becomes negative, it returns -1, otherwise it returns the starting_point index. --
Is this correct?
Probaly not but i just tryed it without really watching the assignment.
ARE YOU KIDDING ME
I HAVE AN INTERVIEW IN THREE DAYS AND YOU DROPPED THIS BOMB
NUKE ME FREECODECAMPDADDY
this speaker is an imposition for my ears
moreover, learn to pronounce the words "even, inclusive, exclusive" & more correctly.
question for kth largest element:
We can assume that in the worst case, the kth largest element would be the len(arr)th element. so in the example where arr = [4, 2, 9, 7, 5, 6, 7, 1, 3], you could call for the 9th largest element, which would be the minimum element, which by the solution, you would have to essentially either use len(arr) if either starting from len(arr) - k or from i in range(len(arr)). So could we not assume that in the worst case, k = n and say that the solution 1 would operate in n^2 time since we are characterizing the worst case? or would we technically say that the time complexity is O(kn), with the caveat that k could = n?
This is amazing I just started applying
Thank you so much. As always - clear, easy to understand, useful.
You're welcome!
Such a nice one
Here for the second question another solution (javascript) and some unit tests:
```
function binarySearch(num, array) {
let begin = 0;
let end = array.length;
let m = Math.floor((begin + end) / 2);
while(begin != m) {
if (array[m] > num) {
end = m;
} else if (array[m] < num) {
begin = m;
} else {
return m;
}
m = Math.floor((begin + end) / 2);
}
return m;
}
function findFirstAndLastIndex(num, array) {
let index1 = binarySearch(num - 1, array);
let index2 = binarySearch(num + 1, array);
if (array[index1] < num) {
index1++;
}
if (array[index2] > num) {
index2--;
}
if (array[index1] != num) {
return [-1, -1]
}
return [index1, index2];
}
const arr1 = [1, 2, 3, 3, 5, 5, 5, 5, 5, 6, 7];
console.log(findFirstAndLastIndex(5, arr1));
const arr2 = [5, 5, 5, 5, 5, 6, 7];
console.log(findFirstAndLastIndex(5, arr2));
const arr3 = [1, 2, 3, 5, 5, 5, 5, 5];
console.log(findFirstAndLastIndex(5, arr3));
const arr4 = [5, 5, 5, 5, 5];
console.log(findFirstAndLastIndex(5, arr4));
const arr5 = [5];
console.log(findFirstAndLastIndex(5, arr5));
const arr6 = [1, 5, 6];
console.log(findFirstAndLastIndex(5, arr6));
const arr7 = [1, 2, 3, 3, 5, 5, 5, 5, 5, 6, 7];
console.log(findFirstAndLastIndex(8, arr7));
const arr8 = [1, 2, 2, 2, 6, 6, 6, 6, 6, 6, 7];
console.log(findFirstAndLastIndex(5, arr8));
```
Thank you for this content!
4:25 - I'm sorry, nameless and salesman are not anagrams.
sMap: Map(6) { 'n' => 1, 'a' => 1, 'm' => 1, 'e' => 2, 'l' => 1, 's' => 2 }, // for nameless
tMap: Map(6) { 's' => 2, 'a' => 2, 'l' => 1, 'e' => 1, 'm' => 1, 'n' => 1 } // for salesman
I think I have a faster way of solving the anagram:
def findAnagram(word1, word2):
for i in word1:
if i in [*word2] and len(word1) == len(word2):
pass
else:
return False
return True
a = findAnagram("garden", "danger")
print(a)
it won't work for input where there is a repetition of chars Ex. AAB, ABB.
your logic would return valid however, it won't be correct.
Make more of these videos💯💯
Second Problem:
instead of nesting loops
step 1: binary search for left
step 2: binary search for right
step 3: return low and high
Actually for first problem starting from python 2.7 at least you can just do freq1 == freq2 and equality will do the job for you
this just sooo... good ,i just wanted this thanks so much
you're welcome!
thanks , you saved my day
I have one in 3 hours and you guys posted this just in time! haha
for the first one u can just do a
return freq1 == freq2
It's crazy that people can just use apps like Coding Interview Champ to solve these LeetCode interview problems during the coding interview
Challenge2 kth largest element shld be 5.since 7 repeats itself. Correct me if I am wrong
51:05 wrong. 5 shouldn't come before 4.
Wow! Can't believe the timing 😮
Did you get in?
This is really great video. I am hopping similar content with different problems in the future also
Hey! I have a whole playlist on coding problems, you can check it: ruclips.net/p/PL3edoBgC7ScW_CBHbMc0FtdXfzgpBOGIb
@@insidecode thank you so much ✌️
Once again, completely out of my range of knowledge
I feel your pain, hard stuff
For the first exercise, don't you think it's way easier to convert the strings do an ordered list and check if they're the same?
It works but it isn’t cost effective.
really appreciated this. the course pre-requisite problem is not how courses work. if a course has two prerequisites, then both of those need to come first.
That anagram stuff -- why not, but much simplier (in Python anyways) is just sort alphabetically both strings and compare them. If they are anagrams, sorted strings would be same.
You probably know this already. Sorting has a bigger O complexity. O (n log (n) ). When you create a hash, you sacrifice space O(n); but you improve time complexity to Big O(n)
@@thugsmf True (y) 🙂
[Symmetric tree]26:10: I don't clearly understand why space complexity is O(n log n)? I have implemented your solution is C# by the way.
The speaker says O(log n), which is smaller than O(n * log n). This is because we much consider the data the program puts on the stack as we enter each level of recursion. In this case, every time we check if the left and right sub trees are mirrors, we add a frame to the stack. We do this all the way down the tree.
However, the speaker made a minor mistake. They claim that symmetric trees must be balanced binary trees. Balanced binary trees are defined as a binary tre where the height of the left and right subtrees, for every node in the tree, cannot differ by more than 1. Therefore, the height of the a balanced binary tree must be O(log(n)).
The mistake is that symmetric trees do not need to be balanced binary trees. A symmetric tree height can be up to n/2 when the left subtree has all left nodes and the right subtree has all right nodes. Thus, the space complexity is O(n).
Example:
```
1
2 3
4 5
6 7
8 9
```
In this type of structure:
```
n height log(n) n/2
9 5 3.17 4.5
11 6 3.45 5.5
13 7 3.7 6.5
```
As we can see, the height of the tree, and thus the number of frames on the stack, scale with O(n/2), which we write as O(n).
Sorting then comparing is genius for anagrams! So ez n fast bb how we like it 👌
thank you, these are useful examples. For next time I would appreciate it if you made an effort to try to enunciate your words more clearly or at least write out captions, as it's difficult to understand what you're saying much of the time and the auto caption tool doesn't seem to fare much better
This video serves 2 purposes - you can learn from it, and it can be a bed time story on the Calm app. Great material, but maybe next time have a coffee before you record
Definitely doing this
Making my life better 👍❤️
Thanks for the video....It helped a lot !!
the answer to 1 is way too complicated. better answer imo: if (a b) andalso (sort(a) = sort(b)) ... sort( sorts a string so each character in the string is placed in alphabetical order ).
the answer to 5 is again too complicated - but you have the idea. to improve rather than use stacks just +1 to total for "(" and -1 to total for "(", the rest is more or less the same, if total ever goes below zero its invalid, total must = 0 in the end.
Its not about whether or not the solutions are complicated or simple... it's about getting time complexity and space complexity as optimal as possible and sometimes getting to that means having a more "complicated" solution. Your solution might be simpler but it doesn't necessary mean it's optimal.
Also your solution to the first one is already one of the solutions given in the video itself
Hello, just keep watching the video, both solutions you mentioned are explained just after the "complicated" ones!
@@insidecode Sorry I clearly jumped the gun. At 2:02 I heard 'the best structure for our problem is the hash tables' so I just moved on. The same with 5 when talk was of pushing and popping.
@@mattnic001 perhaps, but the best solution imo is always the simplest to understand assuming performance is not unduly impacted.
@@roblatour3511 It really is a balancing act. In most situations, I agree.. easy to understand is better, as your code is going to be read by others in a professional environment. There are cases though, where less easy to understand solutions are better, if they provide better performance. Amazon for example, has plenty of teams that deal with code that requires handling millions of requests per second.. at that level, performance is key.
Great vidéo. Thank you
You're welcome!
In Python we can simply sort both strings and compare them using comparison operator.
...which is the same he already proposed... And in Python only? Of course not! Just watch actually the video before writing a useless comment.
@@Gazeld boy you must have alot of useless time to reply to useless comment 😅
if set(word_1.strip()) == set(word_2.strip()):
print("anagram")
else:
print("not anagram")
Thank you so much 👍🏼🎉⭐🙏❤️
You're welcome!
This was very helpful. Thanks.
Well, i'm glad i dont live in the US cause i wouldn't be able to come up with 99% of these optimized solutions ;/
It comes with practice
Did you find a way bro to become good in problem solving ?
If it is help me bro or give me some tips .
Bruh Im in Spain and we also do these interviews.
much more elgant solution to problem 1 is to sort both strings into alphabetical order and see if they're equivalent
It's not as fast though, because sorting is at best O(n logn) whereas counting each letter is O(n)
For the parenthesis you could also just do this:
-if it's got an odd length or it starts with ')', return false
-else, if the count of '(' == count of ')', return true, else return false
thanks for this free content but the subtitles are bad and the accent too. I didn't get why space complexity is O(1) since the array is not a costant but a function parameter. thank you very much
fantastic slides!
For the last solution of the last question, the time complexity is O(n)? It is not O(n^2)?
Your are_anagrams code seems incorrect at 4:10, in particular if freq2 has a key that's not in freq1 (consider s1='a' and s2='ab').
That's really useful thanks
You're welcome!
Easy JS solution for number 1
function firstAndLastIndex (arr, target) {
return `${arr.indexOf(target)} ${arr.lastIndexOf(target)}`
}
I'm lost after that. Long ways to go I guess!
The solution works but it gives an O(n) time complexity, which is not the best for this problem
13:19 wouldn't the space complexity be O(n)? because in the part of the first and last element function you are looping the variable "mid"
Without time and space complexity limitations, most of these problems are so easy.
Great videos, thank you xxxxxx ❤❤❤❤❤
ruclips.net/video/79gTz7cCUdk/видео.html
You're welcome!
def task(arr, k):
return heapq.nlargest(k, arr)[-1]
for the anagram i used only one loop , i worked with java but idea is declaring an int counter = 0
and test if string n° 1 contains a character in string n°2 with charAt[i] if true counter++
and in the end test again if string n°1 length is equal to the counter if true then the two words are anagram
for (int i=0;i
its O(n^2) or O(nlogn), as "contains method" could be O n or O log n
contains is not free. so you have 2 nested loops.
@@mephi5t0 exactly
Problem Solution - 1 in Swift:
func areAnagrams(s1: String, s2: String) -> Bool {
if s1.count != s2.count { return false }
var s1Frequency: [String: Int] = [:]
var s2Frequency: [String: Int] = [:]
for char in s1 {
s1Frequency["\(char)", default: 0] += 1
}
for char in s2 {
s2Frequency["\(char)", default: 0] += 1
}
for key in s1Frequency.keys {
if s2Frequency.keys.contains(key) == false || s1Frequency[key] != s2Frequency[key] {
return false
}
}
return true
}
I would be so lucky if I’ll get one of this problems 😅
Sir please make more videos regards interviews 🔥🔥 these videos help us for preparing for interview 👍
I have a playlist on coding problems on my channel: ruclips.net/p/PL3edoBgC7ScW_CBHbMc0FtdXfzgpBOGIb
You mean videos for preparing interviews help you preparing interviews? Woohoo! Fantastic! :)))
For the anagram question, would it be possible to just add the total value of each string and compare them via ASCI value? If they're equal then they're an anagram if not then it's not (make all letters uppercase or lowercase first )?
I believe that will be inaccurate as you can have a character with higher ascii value which is equal to sum of the ascii values of other characters. So the two words will be different and you may still get the same total ascii value. I hope this answer's your question.
There is a mistake at 9:57
Index mid-1 and index mid+1 could access an index outside the array. This should be changed.
Tomorrow I have a interview wish me luck 🤞
tell us how it was.. ! :D
Hi, i think i have a good solution to problem 2
function first_last(arr, target){
let start = 0;
let final = 0;
for(let x = 0;x
Better solution would be using binary search
Great sir
Haven't tested it but in the Symmetric tree problem (26:24), I think are_symmetric can only give True when going all the way down and finding two nodes that they both don't have children?, I think you are missing an elif with root1.val == root2.val then return True there?. Can someone confirm this?
You would only need to go all the way to the bottom if you don't find a difference before then. Basically we're walking every possible branch in the tree until we hit a difference then we stop. You can't return True finally unless you know for sure that both tree halves are identically mirrored, and the only way to do that is to recursively walk through the whole tree but stop if you find an exception. So, there is a range of time complexity. The worst case is when the two actually are symmetric because you end up comparing every single node. Then the next worse is when the very bottom node is the only one that's different, then it gets better and better as the difference gets higher up the tree, until the best case where the top root node is different (or they're both null). If you watch the animation at 2:36 again I think it will click. There's nothing else you need to add
Thank you thala
Should one know the method from video or find it on his own ?
what if I compare string lengths and then compare the character in String 2 and then if count == len(s1) then its anagram, would it not be an anagram solution
s1 = "danger"
s2 = "garden"
if len(s1) == len(s2):
print("length is same so it can be anagram")
count = 0
for ch in s1:
if ch in s2:
count = count + 1
if count == len(s1):
print('Anagram string')
else:
print("Not anagram")