10 Common Coding Interview Problems - Solved!
ฝัง
- เผยแพร่เมื่อ 1 มิ.ย. 2024
- Preparing for coding interviews? Competitive programming? Learn to solve 10 common coding problems and improve your problem-solving skills.
💻 Code: gist.github.com/syphh/173172e...
✏️ Course developed by Inside code. Check out their TH-cam channel: / @insidecode
⌨️ (0:00:00) Introduction
⌨️ (0:00:37) Valid anagram
⌨️ (0:05:10) First and last index in sorted array
⌨️ (0:13:44) Kth largest element
⌨️ (0:19:50) Symmetric tree
⌨️ (0:26:42) Generate parentheses
⌨️ (0:37:03) Gas station
⌨️ (0:50:06) Course schedule
⌨️ (1:06:50) Kth permutation
⌨️ (1:20:13) Minimum window substring
⌨️ (1:47:46) Largest rectangle in histogram
⌨️ (2:10:30) Conclusion
🎉 Thanks to our Champion and Sponsor supporters:
👾 Raymond Odero
👾 Agustín Kussrow
👾 aldo ferretti
👾 Otis Morgan
👾 DeezMaster
--
Learn to code for free and get a developer job: www.freecodecamp.org
Read hundreds of articles on programming: freecodecamp.org/news
![โอ้มายก๊อด! ไม่ถึงชั่วโมงหมดเป็นแสน 😅 [cc] แดนแพทตี้ SS2 | EP.42 |](http://i.ytimg.com/vi/OH2ShXfO6tA/mqdefault.jpg)
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]
For the third problem, with the parethesis,
You may produce all valid parenthesis using the Catalan recursion.
I love this channel, even though my English is no accurate to understand all content i always try to collect some good ideas they share. Thank you
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
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.
This is amazing I just started applying
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.
The last problem in "heights" array there is an extra 10 in list at index 10 after 9, comapred with the histogram.
Thank you so much. As always - clear, easy to understand, useful.
You're welcome!
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
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?
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
Good night! I live in Brazil I would like to say that your channel has content that others don't.
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.
I have one in 3 hours and you guys posted this just in time! haha
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
Thank you for this content!
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🙂🙂🙂
This was very helpful. Thanks.
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.
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: th-cam.com/play/PL3edoBgC7ScW_CBHbMc0FtdXfzgpBOGIb.html
@@insidecode thank you so much ✌️
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)
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.
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.
Make more of these videos💯💯
Thanks for the video....It helped a lot !!
Sorting then comparing is genius for anagrams! So ez n fast bb how we like it 👌
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
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.
fantastic slides!
Making my life better 👍❤️
Sound of this tutorial is not clear to understand. However the topics are clearly explained. Thanks
thanks , you saved my day
this just sooo... good ,i just wanted this thanks so much
you're welcome!
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"
For the first one, you can just do:
def validAnagram(s1, s2):
return Counter(s1) == Counter(s2)
That was mentioned in the video
Thanks a lot for your work. And also side note, you sound a lot like gru which is cute.
Wow! Can't believe the timing 😮
Did you get in?
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
Definitely doing this
Great videos, thank you xxxxxx ❤❤❤❤❤
th-cam.com/video/79gTz7cCUdk/w-d-xo.html
You're welcome!
Post some product based companies like Amazon DSA with problem solving q & A
Solutions:
Valid Anagram: 3:30
First & Last Index of a Target num in sorted Array: 7:23
Kth Largest Element in an array: 15:03
That's really useful thanks
You're welcome!
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.
Thank you so much 👍🏼🎉⭐🙏❤️
You're welcome!
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)
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?
Great vidéo. Thank you
You're welcome!
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.
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
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 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.
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]])
Great sir
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))
This is Fxxking amazing
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)
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) 🙂
for the first one, cant i just convert the 2 strings to char array, sort them, check if they are the same and return the result?
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!
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.
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').
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
Once again, completely out of my range of knowledge
I feel your pain, hard stuff
Tomorrow I have a interview wish me luck 🤞
tell us how it was.. ! :D
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.
[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).
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: th-cam.com/play/PL3edoBgC7ScW_CBHbMc0FtdXfzgpBOGIb.html
You mean videos for preparing interviews help you preparing interviews? Woohoo! Fantastic! :)))
in the second problem, cant we create two loops, one starts from front of string to search the first target and second loops start from behind the string to search the last target?
Yes it works but doesn't have the best time complexity
you can get away with one loop here just by making the second iteration pointer to be lenght(array)-iterator. Nonetheless the timecomplexity would remain the same
if you want your test cases to time out, sure
@@AMX0013 this +1
ARE YOU KIDDING ME
I HAVE AN INTERVIEW IN THREE DAYS AND YOU DROPPED THIS BOMB
NUKE ME FREECODECAMPDADDY
In the 'Generate Parentheses' problem, I don't understand why we must pop the closing bracket ')' from comb after performing the second recursive function.
It seems to me that this 'comb' list will never be evaluated, so a pop isn't required. A new 'comb' list has already been passed into the next function.
When I try it in code, the final pop is clearly required - if I comment it out, the final results are longer than they should be and therefore inaccurate.
I just can't work out why! I must be missing something.
Any help would be much appreciated.
It’s always passing the same combs list, not passing a new one. To pass a new one, you should be passing the list combs[:] to create a copy with the same values.
@@notyourdan3388 thanks, really appreciate it.
I hadn't understood that the same list is modified over and over. Recursive functions make more sense now!
Thank you FCC!
You're welcome!
I would be so lucky if I’ll get one of this problems 😅
Great video, thanks for all the work you put into it. I would like to add though, if you are building a string histogram, like in the first problem, you can simply do: for k in string:
my_dict[k] = my_dict.get(k, 0) + 1
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 😅
for the anagrams, i think a 256-size array would be better tho
Second Problem:
instead of nesting loops
step 1: binary search for left
step 2: binary search for right
step 3: return low and high
It's crazy that people can just use apps like Coding Interview Champ to solve these LeetCode interview problems during the coding interview
.💕💕 love ur content
For the second problem, I don't understand how the binary search algorithm doesn't just get stuck inside of the sequence of target numbers.
Could someone please explain?
It's because of the if/else statements used to check our place with respect to the repeated sequence
Without time and space complexity limitations, most of these problems are so easy.
Respect. 🙏
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));
```
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
For the last solution of the last question, the time complexity is O(n)? It is not O(n^2)?
Isn't the cost of building a priority(or a heap) NlogN? I am super confused now, it cant be O(n )
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
Isn't creating a proper max or min heap cost N*logN time complexity. Contradictory to the given one at 18:42 ?
What does gas station problem test? This looks like dynamic programming
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
}
Nice
for the first one u can just do a
return freq1 == freq2
In 7:01, the code logic was wrong. It will fail if the target value is the last index value.
Correct Code:-
def first_last_pos(arr,target):
print(len(arr))
for i in range (len(arr)):
if arr[i] == target:
print(arr[i])
start = i
print(i)
while i < (len(arr)-1) and arr[i+1] == target:
i+=1
return [start,i]
return [-1,-1]
Thank yoooou
You're welcome!
I feel dumb but... for the first problem, can't you simply loop through each character and convert them to an int and add them together? If two words are anagrams then they should have the same value?
B + B + B would be the same as A + B + C
If A then B doesn't mean that if B then A. Basics of logic :)
@@Gazeld Now we can get into some fun compression algorithms that do preserve this trait.