If you guys need help with anything leave a comment and let me know!
@JaspreetSingh-bh5hc
5 жыл бұрын
I never understand when i should use graph to solve a given problem. Any tricks? Need help with graphs algos
@KevinNaughtonJr
5 жыл бұрын
@@JaspreetSingh-bh5hc Hey Jaspreet if you want to check out my newest video it's a graph problem: kzitem.info/news/bejne/lYKsv6SVnWiKl5w (dfs)! Otherwise when a matrix is involved it usually has to do with graph or when you're asked is one thing reachable from a certain point, or you're asked to find a path or paths in a problem. I hope this helps!
@helenhan4577
5 жыл бұрын
@@KevinNaughtonJr Can you try LeetCode-409. Longest Palindrome
@prakad97
4 жыл бұрын
How to get to your level proficiency in java..!
@swati7731
4 жыл бұрын
please read my comment, in case you haven't got the notification for my public comment:)
@sunnilabeouf
4 жыл бұрын
For anyone who might be watching this in the future, please note that the problem was updated slightly such that intervals is now just a 2D array rather than using the custom class Intervals. So for sorting, you'd just use a[0] - b[0] as the comparator
@sk8sbest
3 жыл бұрын
thanks
@vaibhavbhardwaj2244
3 жыл бұрын
For those who are looking for an intuition I will try to explain.. suppose you need to schedule n number of meetings for your company . Now you will first schedule the meeting which has the first start time and then go one by one as per the start time ( This explains the sorting part) . Now suppose while scheduling the second meeting you check when is the first meeting getting over - if the first meeting end time is less than the second meeting start time so we could use the same room . So what he has done is - find the meeting which is ending earliest and if the current meeting happens after the earliest meeting end we could use the same room so he just updated the end time for that room ..... but suppose there is a conflict between the earliest meeting and current meeting so we need to push this current meeting separately in the heap and we cant really use the same room..... Visualise the elements in the heap like the rooms and the end time represents when each room will get free .. Hope this helps
@shelendrasharma9680
3 жыл бұрын
nicely explained
@fufuto
2 жыл бұрын
My question is that why are we changing the times? Can't we just increment an integer (number of conference rooms) whenever times conflict.
@arpanbanejee5143
2 жыл бұрын
@@fufuto with this approach if we don't increment the end time after each comparison, when there is no conflict then we would not knw which meeting will end at the earliest for the next iteration. Suppose we have [[5,9],[10,15],[12,13]. In meeting room 1 -- first meeting will end at 9, so we can accommodate next meeting in the same room which starts after the first meeting ends, now the Meeting room 1 is occupied till 15. Now comes the third meeting at 12, so we cannot use meeting room 1 anymore, since it is occupied till 15, that is why we update the time every time there is no conflict. And like in this case there is a conflict, we simply push it in the heap, meaning we have two meeting rooms now. Hope this clears things up!
@galanoth17
Жыл бұрын
Thank you sir. Wouldn't have understood this from the video at all.
@ligmaball69
3 жыл бұрын
Heya, a small feedback: I think if you can explain the concept rather than walking through the code, that can be more useful to folks. For example, if you explain why did you pick priority queue or how did you come to this certain approach, that would be more beneficial than watching you writing code, imo.
@fatcat22able
Жыл бұрын
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms. We start by adding the earliest-starting meeting (0th meeting) to the priority queue. If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need. On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed. Drawing a visualization should help visualize what is happening in the priority queue For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40): This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time. 0--------------------------------10 11--------------15 22------------------------------31 5--------------------------------------------------20 25-------------------------------------------------------------------------40 7----------11 15-----------------------------------------------30 And since we're merging the intervals, here is what the intervals in the pq will look like by the end. 0-----------------------------------------------------------------------------------------------------------------31 5--------------------------------------------------------------------------------------------------------------------------------------------------40 7--------------------------------------------------------------------------------30 Priority Queue: (7,30), (0,31), (5,40) Hope this helps!
@adeelzafar3299
4 жыл бұрын
Please spend more time on the intuition and less on coding. That would really help a lot.
@rushabhpicha6577
4 жыл бұрын
Worst Explanation
@wessamyaacob1505
4 жыл бұрын
@Adeel Exactly! it's very easy to find the problem solution on the Internet and this way of making videos it's just kind of reading the internet solutions without giving us any idea behind how to think about the problem , how to find the brute force solution and how to optimize it!
@rakshith3547
4 жыл бұрын
exactlyyy... simply typing the answer is not a big deal.. Instead spend 80% of time explaining the algorithm on whiteboard and 20% time displaying your typing skills!
@maganaluis92
4 жыл бұрын
Looks like he just looked up the answer and made a video, this has ZERO explanation.
@shamiulhasan7442
3 жыл бұрын
Anyone can write code dude. Explain how you came up with the concept, what processes you went through while arriving at the concept. This is not a Java coding tutorial session.
@fatcat22able
Жыл бұрын
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms. We start by adding the earliest-starting meeting (0th meeting) to the priority queue. If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need. On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed. Drawing a visualization should help visualize what is happening in the priority queue For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40): This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time. 0--------------------------------10 11--------------15 22------------------------------31 5--------------------------------------------------20 25-------------------------------------------------------------------------40 7----------11 15-----------------------------------------------30 And since we're merging the intervals, here is what the intervals in the pq will look like by the end. 0-----------------------------------------------------------------------------------------------------------------31 5--------------------------------------------------------------------------------------------------------------------------------------------------40 7--------------------------------------------------------------------------------30 Priority Queue: (7,30), (0,31), (5,40) Hope this helps!
@wardenofthenorth-w5d
4 жыл бұрын
Nice and clean solution! I knew a heap should be used, but didn't realize size should be returned.
@go_cool_travels
4 жыл бұрын
Can we get answer if we return number of overlapping events? def findMeetinHallsUsingHashSet(arr): st ={} count=0 for each in arr: start=each[0] end = each[1] for i in range(start,end+1): if i not in st: st[i]=0 else: count+=1 break return count Please help me I dont have leetcode premium account to run this.
@wardenofthenorth-w5d
4 жыл бұрын
@@go_cool_travels No. Ran your code didn't work out. You can think of a counter-example.
@go_cool_travels
4 жыл бұрын
@@wardenofthenorth-w5d Thanks bro!! I will try to fix.
@sivan2878
Жыл бұрын
Awesome Kevin!
@KevinNaughtonJr
Жыл бұрын
ty!
@amoghasoda
3 жыл бұрын
Why returning size gives the answer is not explained. I think, if you solve it on whiteboard (considering all edge cases) and then type code it will be very helpful.
@bhaveshthawrani7383
4 жыл бұрын
[5,10],[8,15],[17,20],[12,30] Here if we extract the min value from the heap then answer would be 3 .But if we extract the max value and compare with the start time and if the start time is greater than the value which is extracted or extract the next maximum value and compare it and so on .At the end put all the extracted value back into the heap.In this approach the answer would be 2 which is the expected one.
@ishank2160
2 жыл бұрын
the answer would be 2. Last 2 meetings are not sorted by their start time in the your input that's why you get 3 rooms
@ninehoursful
4 жыл бұрын
Why are we using priorityQueue here? We can simply solve this problem with sorting array & checking if interval[i][1] > interval[i+1][1] & than increment an integer variable Can someone explain why exactly we need PriorityQueue here?
@marcchen4574
3 жыл бұрын
this is what I came up with, the intuition is to put all meeting time slots into a grid, assume each row represents a meeting, if from 5 to 30 is meeting, then i fill index 4 to index 29 with 1, rest leaving as 0, then if we look at each column, the column containing max amount of 1 . ex. 3st 1 then 3 is the rooms required. Not sure if i am right though. using System; namespace ConsoleApp1 { public class MeetingRoom { public void Solution() { int[][] timeSlots = new int[][] { new int[] { 0, 30 }, new int[] { 5, 10 }, new int[] { 15, 20}, new int[] { 3, 6}, }; int columns = int.MinValue; for (int i = 0; i < timeSlots.Length; i++) { var timeslot = timeSlots[i]; columns = Math.Max(columns, timeslot[1]); } int rows = timeSlots.Length; // after this grid population we have following grid //111111111111111111111111111111 //000001111100000000000000000000 //000000000000000111110000000000 //000111000000000000000000000000 // index5 contains most 1 (3st) at the same timeslot. so it requires least 3 rooms int[,] grid = new int[rows, columns]; for (int i = 0; i < rows; i++) { var slot = timeSlots[i]; for (int j = 0; j < columns; j++) { if (slot[0]
@sushantsrivastav3251
4 жыл бұрын
For python, we can follow this code, as I found it easy to understand as well: n=int(input()) a=list(map(int,input().split())) if len(a)
@lokesh4585
3 жыл бұрын
Looking forward to contents on System Design.
@275phuongvy
3 жыл бұрын
you should draw the heap so that people can see how the time is allocated visually instead of just talking
@ishitarathi1186
5 жыл бұрын
It would be a great gesture if could make a video on someone's interview experience with Google and/or Facebook, the questions asked during interview, etc.. Thank you!
@KevinNaughtonJr
5 жыл бұрын
That's an awesome idea! Questions that people are seeing during their interviews are discussed in the Discord server but making a video on someone's general experience interviewing would be great!
@lloydlasrado
2 жыл бұрын
Hi Kevin, can you please make video on Google code review interviews?
@nivasreddy6946
4 жыл бұрын
What if we sort according to end times and use a dequeue to store the intervals returning the size as answer at the end of the process
@DyNuHMiTee
5 жыл бұрын
Sweet video, deffinetly a great question to know
@KevinNaughtonJr
5 жыл бұрын
Thanks Yoni!
@myfriendshankar
4 жыл бұрын
We can do something like this in O(n) Have an array with index 0 to endoftheday iterate list and mark a[starttime]+=1 a[endtime]-=1 now iterate a array from 0 to EOD sum+=a[i] max=max(max,sum)
@AbhishekChaturvedi7
4 жыл бұрын
That is not O(N) . That is actually O(MAX - MIN) , if max - min is very large it will be worse.
@ninehoursful
4 жыл бұрын
Why do we care about the earliest ending meeting? Can someone explain that?
@TheVitorkid
5 жыл бұрын
Hi @Kevin. First of all, great video! If you want to make your solution even more efficient, you can replace a minHeap by a variable holding the earliest available room (i.e. earliest end time). Every time you have a conflict with the earliest available room, you gonna need another room, so here you also keep a counter to increment whenever this happens. That approach you end up saving O(n) space (all meetings conflict) and O(nlogn) time (n insertions) in the worst case, since you dont need to maintain a heap anymore. Keep on posting those videos! I really like them.
@KevinNaughtonJr
5 жыл бұрын
Awesome optimization Vitor thanks for sharing! Don't worry I'm going to keep posting these videos!
@NitishUpreti
5 жыл бұрын
How would you update this earliest "end time" variable in constant time if we schedule another meeting in the same room and end up increasing its end time?
@seunghunlee6778
4 жыл бұрын
Great idea! But, your pseudo code doesn't work on this case [[2,15],[36,45],[9,29],[16,23],[4,9]]. var minMeetingRooms = function(intervals) { intervals.sort((a,b) => a[1] - b[1]) let earliestEndInterval = intervals[0], rooms = 0 intervals.forEach(interval => { if(interval[0] >= earliestEndInterval[1]) { earliestEndInterval = interval } else { rooms++ } }) return rooms }; How would you decide which one should be the earliestEndInterval ?
@mahanteshhiremath1168
4 жыл бұрын
Can you share list of important problem for amazon sde2?
@jayeshborgaonkar9166
5 жыл бұрын
your approach explanation and code are awesome, thanks for this video
@kshitishsorte2918
3 жыл бұрын
can you give a C code for this?
@aparnagopal5201
4 жыл бұрын
We can do a simpler greedy approach without the use of priority queue
@darod6098
4 жыл бұрын
Btw I'm going to have a Facebook Intern Interview at the end of this month. If you have any advice or want to have a quick chat I'd be grateful :) Cheers!
@KevinNaughtonJr
4 жыл бұрын
daro d that’s awesome congrats!!! If you need help preparing check out my Patreon page: www.patreon.com/KevinNaughtonJr. I’d recommend the “study buddy” or “onsite” tier!
@oscaropdyou
4 жыл бұрын
Good solution Kevin. Thanks. My version. Have made it slightly more readable. private static int findMinMeetingRooms(int[][] input) { Arrays.sort(input, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0])); int previousEnd = input[0][1]; PriorityQueue endtimes = new PriorityQueue(); endtimes.add(previousEnd); for (int i = 1; i < input.length; i++) { int currentBegin = input[i][0]; int currentEnd = input[i][1]; if (currentBegin > endtimes.peek()) { //If meeting room freed up endtimes.remove(); endtimes.offer(currentEnd); } else { //If no meeting rooms available endtimes.offer(currentEnd); } } return endtimes.size(); }
@deepakanuraagsathyanarayan9666
4 жыл бұрын
i understood what is a min heap but why a priority queue is used instead of min heap im not able to connect
@kevin_m7
4 жыл бұрын
A priority queue in java is a min heap
@niileshraaje9061
5 жыл бұрын
The above code gives wrong output for test case - [[1,5],[8,9],[8,9]] .o/p =1 expected = 2 Here is the same code that i used.. Am i missing anything ? Code is below - public int minMeetingRooms(Interval[] intervals) { if(intervals == null || intervals.length == 0){ return 0; } Arrays.sort(intervals , (a,b)-> a.start - b.start); PriorityQueue minHeap = new PriorityQueue( (a,b) -> a.end - b.end); minHeap.add(intervals[0]) ; for(int i=1 ; i< intervals.length ; i++){ Interval current = intervals[i]; Interval earliest = minHeap.remove(); if(current.start >= earliest.end) current.end = earliest.end; else minHeap.add(current); minHeap.add(earliest); } return minHeap.size(); }
@suriveer
2 жыл бұрын
if(current.start >= earliest.end) current.end = earliest.end; should be earliest.end=current.end;
@amir.hessam
4 жыл бұрын
I am not sure why you choose such a complex way to solve this! You can just use DP! def minMeetingRooms(intervals): """ :type words: List[List] :rtype: bool O(NLog(N)) """ sorted_intervals = sorted(intervals, key=lambda x: x[0]) roomEndTime = [sorted_intervals[0][1]] for i in range(1, len(sorted_intervals)): start = sorted_intervals[i][0] end = sorted_intervals[i][1] first_meeting = min(roomEndTime) if start < first_meeting: roomEndTime.append(end) else: roomEndTime[roomEndTime.index(first_meeting)] = end return len(roomEndTime)
@mmenjic
4 жыл бұрын
But if you reference real life then you should know that there is no chance if one group finishes in 14h that another group will be able to start in 14h exactly and few minutes added to that one meeting will bee added and multiplied with each meeting after and if you have 10 meetings today and add just 2 minutes to each your start and end times will not be even close to your schedule.
@KevinNaughtonJr
4 жыл бұрын
You get the point and either way meetings IRL do get booked back to back in the same room i.e. my meeting in room #1 is from 12pm-1pm and you book room #1 for 1pm-2pm
@JM_utube
4 жыл бұрын
@@KevinNaughtonJr so true. showcase your personality and joke about how this class won't help you deal with engineers & pm's standing outside the meeting room door waiting awkwardly for yours to end. "we have this room from 1-2......" LOL
@manansurana2416
3 жыл бұрын
Was asked this question for bloomberg
@wahoobeans
4 жыл бұрын
what if i'm coding in a language that doesn't have a heap built in like JS? would i be expected to create a heap class?
@JM_utube
4 жыл бұрын
it's probably easier to learn to solve these heap problems in java or python than it would be to implement a heap in JS. you could also explain to interviewer that JS doesn't have a native heap/pq class and at least provide the interface to a pretend library without actually implementing it. or say you would include one of the many open-source js libraries for the heap. remember - interviewing is just as much explaining HOW you solve problems than solving them. your interviewers are trying to determine what it would be like to work with you, not scoring you on a test
@swagatpatra2139
3 жыл бұрын
i think we can just solve it the same way train platforms question is solved. Add when start, subtract when end time comes. Keep track of max no of rooms. // leetcode.com/problems/meeting-rooms-ii/ class Node{ int time; String type; Node(int t, String s){ this.time = t; this.type = s; } } public int minMeetingRooms(int[][] intervals) { PriorityQueue pq = new PriorityQueue((x, y)-> { if(x.time == y.time) { if(x.type.equals("end")) return -1; if(y.type.equals("end")) return 1; } return x.time - y.time; }); for(int[] i : intervals){ pq.add(new Node(i[0], "start")); pq.add(new Node(i[1], "end")); } int count = 0, min = 0; while(pq.size()!=0){ Node curr = pq.remove(); if(curr.type.equals("start")) count++; else count--; min = Math.max(min, count); } return min; } Pls let me know what you guys think.
@akshatjain6854
4 жыл бұрын
If we know the intuition we can also code , your purpose is to teach intution, not to write the code
@BrianTanWah
4 жыл бұрын
There are ways to do it without a priority queue :/
@fionamatu4996
4 жыл бұрын
I used a HashMap instead
@90krishika
5 жыл бұрын
Hello Kevin, any idea why the lambda thing is not working in my eclipse? Arrays.sort(intervals, (a - b) -> a.start - b.start); Also when I type and submit your code, leetcode doesn't accept, it says- Line 18: error: ')' expected Arrays.sort(intervals, (a - b) -> a.start - b.start);
@foroozs390
5 жыл бұрын
There is a typo on line 17. Should be corrected as followings: PriorityQueue minHeap = new PriorityQueue((a,b) -> a.end - b.end);
@ishitarathi1186
5 жыл бұрын
Hey Kevin! Can we create a heap without using array?(Asking this with reference to the question "stream of integers coming and we have to find the median". We use two heaps in that question and heaps are implemented using arrays internally, stream can be of any size then how can that be stored in array? Would be a great help :)
@KevinNaughtonJr
5 жыл бұрын
Hey Ishita! I think I might know the question you're talking about, but I'm not sure honestly sorry :( if there's anything else I can do to help or if you have any other questions lmk and I'd be happy to try and help :)
@ishitarathi1186
5 жыл бұрын
@@KevinNaughtonJr No problem Kevin :) Thank you very much for the vdios.
@KevinNaughtonJr
5 жыл бұрын
@@ishitarathi1186 Anytime!
@iamabean
4 жыл бұрын
anyone knows how to implement the minheap neatly in python ?
@JM_utube
4 жыл бұрын
look up heapq - tons of examples online and similarly solved leetcode problems. the basic idea is you have a basic array and use static heapq library functions to remove / add elements. however, the python implementation uses the first value passed in the element tuple/array to do the sorting, so for min-heap you have to convert values to negative
@nishant1877
4 жыл бұрын
Hey ...What advice do u give to a person like me who knows the logic to a program but is unable to code it.I can write algo pretty easily but somehow can't run on compiler
@aamike82aa
4 жыл бұрын
Become a product manager?
@CarlosRomero-ef4uv
4 жыл бұрын
Honestly, just sit down and practice. Work on easier problems and work your way up. Start with the fundamentals and build a strong foundation. Read cracking the coding interview. That would help a lot with studying and overall guidance.
@JM_utube
4 жыл бұрын
learn to code
@niileshraaje9061
5 жыл бұрын
Hi Kevin - I have a FB onsite. What coding and design questions should i prep for onsite?
@YameenYasin
5 жыл бұрын
Hey Nilesh .. How did your interview go ?
@niileshraaje9061
5 жыл бұрын
@@YameenYasin I have postponed it
@praveerdas4817
4 жыл бұрын
@@niileshraaje9061 Can you share the interview questions ?
@kalpkumudkumar8163
3 жыл бұрын
i lost at line 20 :P
@ishitarathi1186
5 жыл бұрын
Hey! Can you please tell how a fresher should apply for SDE role at Facebook and Google? Like applying through their careers page or pinging the recruiters on LinkedIn
@KevinNaughtonJr
5 жыл бұрын
Hey Ishita I've got a video like this coming soon don't worry thanks for your support!
@hirenpatel6702
5 жыл бұрын
Hey Man, You are doing amazing work. Kudos!!! Could you help to cover below google problems. I am having difficulties in solving these problems Redundant Connection II Number of Music Playlists Rectangle Area II
@KevinNaughtonJr
5 жыл бұрын
Thank you so much! It's hard to keep track of all the requests that come in for questions...I actually made a Discord server and one of the channels is specifically for requesting questions to be solved, but I'll see what I can do. Thanks for your support!
Пікірлер: 104