function areaOfOverlap([[ax1, ay1], [ax2, ay2]], [[bx1, by1], [bx2, by2]]) { const len = ([a1, b1], [a2, b2]) => Math.min(a1, b1) - Math.max(a2, b2) const ox = len([ax2, bx2], [ax1, bx1]) if (0 > ox) return 0 const oy = len([ay2, by2], [ay1, by1]) if (0 > oy) return 0 return ox * oy }
@AlexN20222 жыл бұрын
if we start at index 0 this is so easy that 1) I would not expect this at a Google interview and 2) there's an easier solution: if we can make N steps without going out of bounds, there's a loop. Same big-O complexity, but about twice faster in reality. If however a loop can start at any index, then it becomes interesting
@IrvineMesa2 жыл бұрын
Hi Irfan .. I wanted to ask can I get a testimonial for my CV from the owner of the repository after I have done my CONTRIBUTIONS
@jamesvanvuren2 жыл бұрын
The solution for this could use a modified B+ tree where the interior nodes store the separators between the sets and the leaf nodes only store sequence start value + sequence length for each set. There would be one leaf node per consecutive sequence. The driver function would just build the B+ tree, and keep track of the largest sequence as it did so.
@zionsiton36902 жыл бұрын
Great video and approach to answering the question for a coding interview by the way. One thing I would change based on your solution would be to start the iterators at 1 instead of zero. Not only would that save iterations (as you don't need to change the cloned values when i or j are zero, but it also removes the need to check if i or j are zero. Again, great video
@fawadhassan90362 жыл бұрын
When are new videos coming
@yunuskocatas38792 жыл бұрын
main() {
@yunuskocatas38792 жыл бұрын
this is my way
@alisheheryar17703 жыл бұрын
Sometimes I got zoned out. Nice effort but still room for improvement.
@hailin7163 жыл бұрын
Bad. Most of programmers can’t even solve it with recursive, why everyone directly jump to DP without more detail in recursive way.
@pranavkumarsoni75183 жыл бұрын
very great explanation.
@wasabi_san3 жыл бұрын
In what language can a method return either boolean or int?
@prithwishdasgupta45083 жыл бұрын
If we mark the index that the current index is pointing to by making that no. Negative ...so we can check if the no. Is already negative then it's visited that means it has cycle. So time complexity will be O(N) and space complexity will be O(1) as we are using the given array for marking.
@chandrakantkumarchoudhary11443 жыл бұрын
this concept is not about which is better its about how well you understand stack and recursion'
@zemfus3 жыл бұрын
Спасибо большое, дорогой учитель Ирфан
@z088403 жыл бұрын
so, if stack is a million elements deep we are just using a million deep call STACK.... rrrrrrrrright.... well, thank you, I'm leaving - have no interest to work here :P
@dannydjx3 жыл бұрын
Dude, this man is going serious with the look and feel. He's even using blue shirts for FB videos.
@vahiagyat3 жыл бұрын
Maybe I missed it but isn't it a big assumption to consider rectangles edges will be parallel to the x, y-axis? or rather two rectangles will be parallel.
@likwidmocean2 жыл бұрын
It's addressed early in the video that the rectangles will be composed of lines oriented parallel to the xy axis. You're right in that it is a big assumption, but if you think about it, it's implicit in the input format. "Sloped rectangles" embedded in a plane need to describe at least 3 vertices, so the two edges required to form a 90° corner (a vertex) are represented. The corner becomes the local origin, use pythagoras to get the edge lengths, multiply for area. For "non-sloped rectangles" you just need 2 opposing vertices to find the edges required to calculate area. This is because rectangles by definition are composed of 4 congruent interior angles of 90°, and 2 sets of 2 congruent edges. It'd occasionally useful to consider a square as a special case rectangle. If it were a rhombus, all 4 vertices are required to find area. So the question in my opinion to ask is not, "are there sloped rectangles?" but rather "is the input format stable or variable? Will all rectangles be described with two vertices?". From that you should be able to describe the system's capacity for rectangles to the interviewer, demonstrating an awareness of how a rule, in this case the geometric identity of a rectangle, is used to omit unnecessary data from a model without losing any information about the object the model describes.
@adityabhandari66883 жыл бұрын
watched this video twice and it worked for me
@tdsora3 жыл бұрын
You spent the first 8 minutes saying you were going to do top down DP, then suddenly you started doing bottom up DP. If this was supposed to simulate a real interview, that was be pretty obvious you knew the solution already.
@_ityadi3 жыл бұрын
Time complexity for the solution would be O(n!) that is Big-O of n factorial
@_ityadi3 жыл бұрын
Thanks for showing we can cheat using a recursion call stack instead. I would have assumed this can not be done since I thought using recursion is basically using a stack and discarded this solution. Next time I would not assume things in the interview, rather just ask the interviewers if I can do it or not.
@AkshayKumar-ck1yg3 жыл бұрын
when Input= [1,2,3,4,5,0,9,8,0,1,2,3,6,0,5,4,7] ...?
@BrentSnider3 жыл бұрын
Great video
@chikinfrydsteak3 жыл бұрын
Very helpful! Thanks so much
@sumekagarwal82293 жыл бұрын
Do we have a case where one rectangle is parallel to x axis and the other not parallel (both in quadrant 1)?
@jamezjaz3 жыл бұрын
Insightful! Thanks for sharing
@debdutsaha43163 жыл бұрын
I am also thinking the same
@AlbinoCordeiroJunior3 жыл бұрын
Great video, as always
@vaibhavsachdeva22613 жыл бұрын
very nice sir well explained!
@66IOU33 жыл бұрын
I was expecting to see a different implementation because of the disconnection of E and F. Interesting to see its the same as a typical DFS.
@stephanbranczyk83063 жыл бұрын
Just a small note, do not completely rely on Grammarly. Grammarly occasionally makes mistakes. So if you're not 100% sure it's a mistake, do not submit a PR for it.
@davidjames16843 жыл бұрын
I would go about this differently... Since we know the input matrix is 4 rows and 5 columns, the largest square of 1s there can be is 4x4, so the only place that can be is at the upper left corner or 1 element to the right of that. As soon as we scan across the top row, we see a 0, and realize a 4x4 of 1s cannot be present. We repeat this logic with 3x3 and find it and then we are done. No need to fuss with squares of size 2x2 in this example because we are checking largest (4x4) to smallest (1x1) and stopping when we find one (in this case stopping at 3x3). More specifics about the algorithm at the 3x3 check step would be scan across until we find 3 ones in a row (literally), go back to that "home" position (the leftmost element), and scan down to see if there are 3 ones in a column. If so, now we have a 3x3 "outline" so check the remaining elements inside that (only 4 more elements to check). If all are ones, we are done. Actually an improvement of this algorithm can be to first count up the # of 1s. Since we only have 14, we know that a 4x4 square of 1s is not possible, so immediately start looking for 3x3s since there are at least 9 1s. There are likely many more algorithms that will solve this too. Probably dozens.
@TheSkeef793 жыл бұрын
Actually, you can solve this problem in O(log(n)) time using matrices and binary exponentiation ( I don't know us it necessary in interviews)
@samanrajaei81293 жыл бұрын
XOR would be the simplest as suggested by a few others. If I was doing your solution, I'd add the new 'unvisited' element to a stack, pop the element when I see it next and whichever elements stays in the stack at the end is your guy.