As Abhishek Somani pointed out, transposing and taking the mirror image of a matrix accomplishes the same result. However, there's no way you can guarantee that you will come up with such an elegant algorithm on the spot during an interview. She showed us how to come up with such an algorithm by dividing and conquering the problem at hand. That's the real lesson, not that there was a simpler solution.
+Ralph Schraven It's not at all "elegant" but a good coder's nightmare for sure. Think about this - Make circular arrays out of the concentric boundaries and rotate them % n times and print them out in the required manner. No need of useless same set of rotations.
If it is a nxn matrix, then you actually don't need to rotate this. We can simply add an 'adapter' type of this on top of this object and using it we can change the incoming request as like asking from the rotated-matrix. Ex: if it request the [ 0 ][ 0 ] value, we know the value of [ 0 ][ 0 ] of the clock-wise rotated matrix is the value of [ 0 ] [ n] cell of the original matrix. Therefore from the adapter what we request and return is the original matrix's [ 0 ] [ n ] cell value. We can simply create how to map the cell between original matrix and the rotated matrix pretty easily.
Just pick up the whiteboard and turn it clockwise and set it back down on what was it's right side. Done. I can even create an "Undo" and "Redo" fairly quickly if needed. You don't need a microprocessor to solve this problem. Don't over think things people.
I thought of an easy solution.... To do inplace Matrix rotation simply 1.Transpose the matrix 2.Take the mirror image of it.. 3.Loop the number of times the rotation is required!! But the matrix has to be a Square one...( :) Enjoy)
Andy Brown Abhishek is right, actually transpose requires n*(n-1) swaps and mirror n^2/2; transpose + hmirror = clockwise rotation, transpose + vmirror = counter-clockwise rotation. straightforward elegant code, much less bug-prone (shows the employer than you are able to simplify a problem by decomposing it - much more important IMO). What she does is ugly and complicated.
Andy Brown Sir, in my opinion the Complexity will be O((3/2)*n^2) ..As **satarimar**said the rotation just required an initial check for square matrix and if it does then simply run n*(n-1) swaps and after that n^2/2 swaps for taking mirror images..So swaps can be done by STL swap()..Hence an easy code and not much manipulation! :)
ABHISHEK SOMANI I did some timings: transpose + hflip (mirror) on 16kx16 matrix: 1.912 sec, direct (=Gayle's solution): 1.868 sec (2.5% faster) trans+hflip on 32kx32k matrix: 10.341 sec, direct: 10.708 sec (3.5% slower) what a surprise :) performance is basically the same!
Andy Brown I don't think you quite got the concept of big-O notation. The whole point is that if f(x) = O(g(x)), then f(x) = O(g(x)) = O(c * g(x)) = O(g(x) + g(x) + g(x) + g(x) + ... (c times)) Which proves that adding two or any other constant amount of identical O-formulas has no effect.
my code would rotate the user clockwise, because in "the matrix" it is not the spoon that bends, but your perception of it ... then I would lol, then I would go ahead and think out loud and ask questions :)
+usergroupX this is actually a pretty great solution. It is much quicker to change how you access the matrix then change the matrix. Instead have a direction variable 1-4 designating directions vertical,90o,180o,270o and then have it read the matrix differently depending on the variable setting.
as a senior java developer for 10 years.. that has been thru tons of interviews.. i honestly think these kind of questions are outdated and out of touch of reality. Better way to guage a canidate would be asking them real life business scenarios. Like you have an android phone, a tablet, and an iphone. What are some of the technologies u would use to communicate to all of them. Or discuss how you would design a MVC application for a car parts warehouse inventory tracker... this matrix interview question or asking someone to write code to do derivatives should stay in the college classroom
+Henry E It depends on what you want to test. What you have just suggested would be great if you're hiring for a more senior position (someone who already established himself as a programmer). You are emphasizing design over low detail problem solving. This interview obviously goes the other way, it is testing the algorithmic/data structure problem solving skills which is pointed towards a more junior position imo.
Yeah because if you are going to be working on image processing software (or anything having to do with data manipulation) at the company you're interviewing for, you won't be doing anything remotely similar to this example, right? Point being, each company will ask questions that will be relevant for the position the candidate is applying for, let it be matrix rotation questions or behavioural questions.
+Gherbi Hicham I actually disagree somewhat. If you're interviewing a senior, asking architecture questions seems appropriate but what about checking that they have the knowledge of the basic building blocks of object oriented programming as well so that they can assist juniors when asked a question about frameworks. In terms of problem solving, just have them develop a solution that you'd need put into place in your day to day work and call it a day. No need to go way over the top. Interview shouldn't be a pressure test unless that's what the work environment is really like. ( which I could think of other disciplines worth pursuing that much better reward a pressure test than computer programming ).
I'm sure that it's all about problems you have already seen and that you haven't. Writing code on a white board is frustrating and time consuming. So if you haven't seen the problem before, you are likely to end up spending some more time on the solution and time is limited. If you have seen the problem already you know the approach for the solution but you might not remember all the implementation details... still need time to think about it. If you remember approach and implementation you are safe, you only need to be careful to use the space on the whiteboard carefully. So to me this is down to "how many problems (solution+implementation) can you remember?" You might be faster than other in reasoning, maybe because you trained a lot. But I'm sure that during interviews, if you have never seen the problem, the time to get to the coded solution is never enough.
For those who think these types of questions are outdated... you are not thinking about it properly... if you learn basic mathematical operations, you apply them in real life... this is similar... when you are at a place where your code uses other peoples code and vice versa, you want it to be as fast as possible, and as clean as possible and as scalable as possible... if you are having more than a few years of experience in tech and you still think this is not important, best of luck...
My solution is to compose the 90-degree rotation out of two reflections (swaps): one through the vertical axis, and another around the matrix's diagonal. At each step, you are swapping two values and no information is lost. You only need one element-worth of extra storage.
This is way more complicated than it needs to be. First reflect over diagonal going from top left to bottom right (swap a[i][j] with a[j][i] for all j>=i. Then reflect over vertical line of symmetry (reverse each row) and you have a clockwise rotation.
The real question for the interviewee is "Can you write an app with the time wasted in technical interview and make more money than the job you are interviewing for?"
As an interviewer, you need to know whether the candidate can logically deduce the pseudo code and is cognizant of the edge cases and any possible optimization methods. After that, it is imperative to find out whether the potential candidate is detail oriented or not. This is often the key differentiator in determining overall effectiveness. But I agree with some of those who raise concerns about the effectiveness of whiteboard tests. I personally would never conduct those, but would rather find out about their attentiveness by asking backdoor questions they cannot prepare for.
I'd have just reflected the array on the x-y axis through the center array[i][j] = array[j][i] and then reflect it on the side y axis to rotate once clockwise array[i][j] = array[i][n - j - 1]
Having read this problem in her book a couple of days ago, I have to say I couldn't agree more. I still couldn't figure out how she computes the coordinate of these points.
It depends. Companies like Microsoft or Google do ask these questions, because they don't just need people who can program. They want top 5%, they want people who can solve these problems in their heads in a matter of minutes. Questions like these help them distinguish between top 5% and other 95% who can just program by googling 99% problems. However, if a company of 5 employees ask something like this during the interview on the "web developer" position (which is actually happened to me during my job seeking experience), then yes, it's pretty f-ed up.
Or you could map the index directly like this: int n = res.length - 1; for(int i = 0; i < res.length; i++) { for(int j = 0; j < res[0].length; j++) { // magic line res[i][j] = a[n - j][i]; } } return res; Here res is a new matrix. So we dont change the original matrix. This is not in place but has O(m*n) space complexity i.e., we duplicate the matrix. Time complexity is also O(m*n) same as the one mentioned by the author, but ease of implementation is higher in this solution. Also this solution is based on simple math(you need to figure out a function to map indices).
The point of this isn't about solving anything, but in how you would approach solving a problem. The key is to show that you can see a problem, assess it, and work it.
I have this book and I did this problem and I also have to agree that it's pretty difficult to come up with the formula to get the offset. But eventually you kind of just memorize it after you see this type of problem
Loved this video, but it might be a good idea to post an alternative solution proposed by another commenter: "flipping" the matrix horizontally and then along the y = x axis. It's much easier to code, and it has the same run time (asymptotically speaking). Again, I don't mean to take anything away from the layer approach; it is a great way of illustrating the importance of breaking up a complex problem into more manageable parts.
Q. How many people have got rejected in software engineering interviews? A. Just count the comments stating that companies need to stop asking stupid interview questions and add the likes those comments got.
I counted. It equals 149 people were asked stupid questions in software interviews, the jobs they applied for were subsequently given to people who interpret data wrong, as the interviewer was looking for like minded people to be team players. Hows that for problem solving?
Why not use a rotation matrix? It would then allow you to rotate an arbitrary number of rads (more applicable to real-life, e.g. graphics programming) instead of 90 deg intervals. The hardest thing is just to remember the form of a rotation matrix from a basic LA class, then you just do inputMat *= rotMatrix. Done. Cleaner, and makes more sense in my opinion.
I feel excited about the future, I'm a senior in high school and plan to go into either computer science, computer engineering, or electrical engineering with an emphasis on technology.
Just remember that only about 1% (yes, one percent) of job recruiters verify college degrees these days, so you'll be competing with millions of people who lie about have a college degree. Bad idea. Easier just to lie about having a degree than to actually earn one.
Joel C. Unless your job requires a professional degree, please remember: employers stopped verifying degrees a long time ago, so everybody lies about having one. It means your degree is useless, other than what you learn.
Lets visualize what happens when you go inside the layers of the square matrix: Your left-right reduces by 1 on each side. Your top-bottom reduces by 1 on each side. Hence, the bounds are reducing by 2 for left-right & up-down with each deeper level into the square matrix. The whiteboard is not reflecting this (unless I'm missing something. I too am fallible and am in no way perfect). I wrote the program depicted (I'm not going to post it here since it's an interview question). It took me more than an hour. I'm no genius. It's implementation is difficult enough, requiring a bit of debugging as what I visualized was translated line-by-line into code. I could not imagine doing it all the way on the whiteboard. Pseudo-code? Maybe. But writing code? I don't see the point. My point- how many people write code without making a mistake or two? Literally no one. Even the author is not accounting for shifting unless I am missing something here.
+Charlie B Did you use recursion by chance? I am a new student with less than a year of java experience and have been trying to think recursively as much as possible.
In my view algorithm questions are overrated, but it's hard to what to replace them with. If it were possible, I would have preferred to do a demo project as it would be much more reflective of what I can do than a 30min algorithm puzzle.
danielfromca "This is for a position as a DBA. Show me a SQL query that does the following..." "This is a position for a web developer. Create a POST request in AJAX with the following criteria..." THAT is what technical interview questions should be. Questions relevant to the jobs that test if you can do it. The bullshit tests that they do now don't test your ability to do the job.
So the first advise is "Ask questions"? Well, once I got interviewed by a company from Washington DC and the guy would not let me ask any questions. He answered rudely: "Come on! All the informations you need are already written in the PDF!"
To tilt 90 degrees, this code also would works int[][] input ={{1,2,3,4,13},{5,6,7,8,14},{9,10,11,12,15}}; // Assign row to column & column to row int[][] out = new int[input[0].length][input.length]; for (int i = 0; i < input.length; i++) { for (int j = 0; j < input[i].length; j++) { out[j][out[0].length - (i+1)] = input[i][j]; } }
I got interviewed for a position and the interviewer only asked me one question. What's is a UDP, TCP and the difference between them? Just finishing college I don't think I even had a networking class but I still knew how to use TCP AND UDP but because I could not explain it in the way he read it from his book I was rejected. Then he recommends me to read this book. If it was really important to learn about network protocol hire me and give me time to learn that.
I actually got asked the same question. Did you have anything computer networking related on your resume because I did? TCP and UDP are both transport layer protocols. TCP has reliable data transfer which means the packets will arrive in order and will have a guarantee of delivery meanwhile UDP is the opposite and is unreliable data transfer and packets may arrive out of order or may not be sent at all. The way TCP makes sure that a packet needs to be resent is when it receives a 3 duplicate ACK packet. UDP is also very fast because its unreliable making It great for uses that can handle data loss like streaming video or video calling over internet (VoIP) while TCP is for situations that require reliable data transfer like sending email, surfing the web, etc. I did take a Computer Networking class recently so it helped me. If you didn't have anything computer networking on your resume its unfortunate they asked that.
Thanks for the suggestions Dutchboy 777. Good suggestion on the lapel mic for my flip camera. Will work with the production folks next time on editing out some of the vocal missteps. Take care, Dawn Kawamoto, Dice Assc. Editor and video shooter.
yea... implementing this on the spot is tricky, thus the camera cut. I've been asked some fun ones, "implement auto complete", "implement infinite scroll", "implement search engine", "implement pig latin -> english translator n vice versa"... fun stuff indeed.
I've solved this problem by another approach. Firstly, I've transposed the matrix, and then swapped all the columns from right to left according to the center(middle column depending on the number of columns whether it is odd or even). On bigger number of N my approach worked faster.
Perhaps it's a good idea to think of conditions/invariants that hold at different points in code. You clearly have an advantage if you're skilled at proving code correctness.
But she messed up her code by fixing it... the second for loop had "i < last" which means that at layer = 1 the code would've ran from 1 (which is first), then 2, but when i became 3 the code would see that it's out of bounds and exited the for-loop. Either she could've reverted to the earlier code, without the -1, because that worked, or she could've switched to i
You're incorrect. The '3' is the '1' of the other layer. In this case the top layer she circles consists of only the first (1) and second (2) element, then the right layer begins on the first layer's 1.
Can someone explain me a bit more about the second FOR LOOP, it's a great video and I love it, I'm new to programming and trying to teach myself. Many thanks
Hey Michael. The second For loop goes through each element on the row. So iteration 1 rotates the top left box on all 4 sides. Then iteration 2 would rotate the second box on all four sides. We continue this for each remaining box on the row.
I'm going to have to watch this video multiple times to grasp that solution. This makes me feel even more terrified about my interview later. Maybe my Masters in CS was a waste of time smh.
This code will have an array out-of-bounds error. (Layer starts at 0. Last starts at n. Offset starts at 0. This leaves the index [last - offset] as n in the first iteration. Arrays are zero-indexed, so that's going to be an issue...
Honestly she is acting like a Genius, but the reality behind all this is, that she had to prepared all this, I am sure, if they ask her something similar or more complicated, the interviewer will tell her, sorry but your time is up. It is not so easy in real life as she is putting it, There will be cases will she will not be able to do it in the amount of time that the interview give her, complexity varies, and we don't know it all. We have to learn before we explain, unless we learn everything out there.
toalopez thats absolutely false, ive solved questions like these with all edge cases included in the standard 50 mins. sometimes they even give 2 problems in that 1 hour time.
This is ridiculous, why would they put these kind of stress on candidates, when all this is useless, because all this is done years ago, and we do not need to not even think about it. They just want to analyze your brain in learning how you think to solve complex problems even when you never had done it before. But this is not new to this lady in this video, she already practice all this before making this video, but I would like to see that Microsoft, Facebook, Amazing, give her a real coding test in real life examples, that she never done in all her life previously, to see, if she can do it in the same manner that she is explaining it, it is easier said than done. In reality, this is to know, how bright and how far you can go, to know how much money they are going to save with you, because they are going to make you work like a slave with so much pressure and so many projects at the same time, making you do 2 and 3 positions for one single salary. This is some type of slavery but without the weapons they use to use to torture people, but in a physiological way. It shows them if you are worth they money they are going to invest in you and making you work for 2 or 3 employees.
This is stupid, they are making people break their head trying to find a solution, when the current expert employees, can teach you how to solve different complex problems and if they cannot still solve any solution, then they will dismiss that person. which it is a much better solution of finding the right candidate. IF you can make them a clone of the expert, then you got the employee that you are looking for, if not , then the person does not qualify for the position. It is that simple!!! I cannot understand why people makes things more complicated in Life.
toalopez she actually did pass interviews for microsoft, not sure about other companies. Also, even if they do give more work (which is not anything extremely stressful and the big 4 companies repeatedly come in as top places to work), they pay a huge salary.
There's plenty of time to apply for a job at google. However, to get into a top company like Google, you must be willing to put in the time and effort. I recommend getting Cracking the Coding Interview book and going through it every day. Try doing the problems yourself before you look at answers.
I'm a sophomore pursuing a degree in computer science. In your freshman year, you will be taught arrays and array manipulation. A matrix can be thought of as an array of arrays or multidimensional arrays. So to manipulate or rotate a matrix would involve knowing how an array fundamentally works. Yes, you will be prepared for a job at Google or any company if you take your classes seriously and work hard to understand your field. Also, secure internships every summer working as a software developer/engineer at any company whether startups or fortune 500.
I dont like these interview questions. They belong to the academic world only or if you are interviewing an algorithm designer and not on the job. I have found Multi threading, OOP , MVC , reliable/maintainable code, documentation, commuincation, team work,networking and obviously the basic for/if constructs are much more important on the job
And for your next task... I want you to write code in assembly that will land be able to land a SpaceX rocket on a launch pad in the middle of the Atlantic ocean at night. You can use whatever color marker you like.
My answer: study your math! This is linear algebra and there is an equasion that can be derived that can rotate a square matrix through an arbirary angle.
... she obviously never cracked a linear algebra book, and never passed a linear algebra class. You can tell by the way she is inventing her own terminology. Since when did a matrix have "cells" and "layers"? LOL Gaussian-eliminate this chick...
***** hey man correct me if i'm wrong, as far as i can remember 2d matrices can be rotated by an angle Theta in the xy plane simply by multiplying them with the corresponding transformation matrix (would be rotation matrix in this case), can't they ??
Aritra, largely correct. Matrix rotations are only defined for square matricies. A 2D square matrix is essentially 2x2. Three dimensions is much more interesting. There are three possible rotations that you can do. In the coding example, she appears to be rotating about the z axis with a special case of 90 degrees. Here is the rotation matrix, I used google to refresh my memory. cos(a) -sin(a) 0 sin(a) cos(a) 0 0 0 1 I suppose you could inserting cos(pi/2)=0 and sin(pi/2), perform the matrix multiplications, and get an answer, but I like reusing stuff, so I would keep everything very arbitrary and make 3 functions that takes in 3 arguments: reference to source matrix, reference to a destination matrix, and an arbitrary angle. Each of the 3 functions would be an arbitrary rotation in one of the dimensions, (x,y,z). In the documentation I would specify that the source matrix needs to be 3x3, the destination be 3x3 and the angle measured in radians. It has to be three functions because matrix rotations depend on the order of operation.
***** yeah that's something which faintly remember... After all its been quite a long time since I completed my grad. But a 2D square matrix means any NxN matrix not necessarily a 2x2. I too was suspecting that she might be rotating it about the z axis. But the next question is how to rotate it for any NxN ??
***** Mike, while your mathematical approach is technically valid for linear algebra it is being applied in the wrong context here. The question being asked refers to moving the data items within a matrix of memory locations, not rotating an object or set of vectors through a specific physical angle in space. Visualize the problem for a 4x4 array of characters in computer memory e.g. char myMatrix [4][4]; a b c d e f g h i j k l m n o p "Rotating" the data indices clockwise this becomes m i e a n j f b o k g c p l h d So the char at myMatrix[0][0] ('a') is now located at myMatrix[0][3] [0][1] ('b') moves to [1][3] [0][2] ('c') moves to [2][3] etc.... Hope that helps.
Nice video. Thanks I use the next code (it assumes different width than height which is the general case but of course no in place) void RotateMatrix() { int count = Width * Height; if (count == 0) return; int OldX, OldY, NewX, NewY; for (int t = 0; t < count; t++) { OldX = t % Width; OldY = (int)(t / Width); NewX = Height - 1 - t / Width; NewY = t % Width; ResultData[NewX, NewY] = OriginalData[OldX, OldY]; } }
Ok but I think you missed the point. She is not teaching the absolute best way to solve the problem, but she is explaining us how to deal with a prob. in an interview, that is : ask questions, show the way you think about the problem, start with an example, try to fragment it, etc...and "that" is the wole point of the video.
Good information, but from a production value point of view, not that good. A couple suggestions: - Use a lapel mic to avoid the hollow sound. - Make several takes from different points of view to keep it interesting and allow you to use only the good takes and remove the vocal missteps.
Wow! Girl's really cute :) Plus she's not so confident with the camera as also mentioned in many other comments. And Gayle, we can actually rotate non-square matrix with the condition that one of the dimensions must be positive. You are a great teacher. Cheers!
Am I the only one think that the intention is not that obvious? Why do not we just add another layer of indirection to the code? There is no specification how actual data structure looks like. We could have a consecutive chunk of data and transposing the matrix is to just change the access function.
How sad that we need to learn a *completely different skillset* for job interviews than the *actual* skillset needed to do the job. The hundreds of billions of dollars lost by engineers wasting their time on practicing crap like white board coding, which is *never* used in real life engineering! We have IDEs and compilers now, you know.
Hight Tech Companies need smart people, they prefer them because is easy for them to solve problems, learn new skills and technologies, etc. See the facts, those companies are what they are because of the people they hire.
So I learned web development all these years and realized I could not make it as one because I can't pass some of these tests. Now I am studying to do UX work instead.
@@juanperusquia7456 Yeah but there are a lot of ways to be smart and a lot of people are just studying her book and memorizing answers. Wouldn't it be better to be an expert at say..Microservices, than leetcode algo problems?
Top tech companies don't want people who can just code, they want you you to have many skills including and most importantly communication, you see if you just come and solve the problem even if you solve it really fast and really good, chances are(and the chances are really big) that you won't get accepted by big tech companies, because in big tech companies you'll spend not more than 30 to max 40% of your time coding, the rest is planning between your team or even with other teams and meetings etc... and studies shown that communication between the interviewer and interviewee is better when the interviewee is working on a white board instead of an IDE, and btw the interviewer won't have any problem if you forgot a ; or a } in your code, h doesn't care about these types of errors.
There is no such thing as a matrix inside a computer, everything in the computer is stored sequentially, even a matrix will be stored sequentially, we just abstract it to fit our human syntax of a matrix
and Im here struggling like fuck with the "easy" problems on leetcode.com and still fail interview tests cuz they feel completely out of touch from what I learned in college, lol
i would rather punch through the white board and get hired by UFC
:^)
U mean KFC?
I am pretty sure KFC will be next to whatever wall u punch.
ahahah
+bc10000 UFC is mix martial arts league, but your point it's also funny. cheers!
LOLOL
As Abhishek Somani pointed out, transposing and taking the mirror image of a matrix accomplishes the same result. However, there's no way you can guarantee that you will come up with such an elegant algorithm on the spot during an interview.
She showed us how to come up with such an algorithm by dividing and conquering the problem at hand. That's the real lesson, not that there was a simpler solution.
+Ralph Schraven It's not at all "elegant" but a good coder's nightmare for sure. Think about this - Make circular arrays out of the concentric boundaries and rotate them % n times and print them out in the required manner. No need of useless same set of rotations.
Aakash Verma good solution lol
Why doesn't she just rotate the whiteboard? That is much easier.
😀😀
because then all 8s will become infinites you silly.
haahahaha
Clockwise:
- transpose
- reverse the items in each row
Counter Clockwise:
- transpose
- reverse the rows
for a none english speaker what does transpose do?
Ben Benson
For all elements in the matrix set matrix[i][j] = matrix[j][i]
Thawsitt Naing
For counter clockwise, two steps:
- transpose
- reverse columns of the transpose
If it is a nxn matrix, then you actually don't need to rotate this. We can simply add an 'adapter' type of this on top of this object and using it we can change the incoming request as like asking from the rotated-matrix. Ex: if it request the [ 0 ][ 0 ] value, we know the value of [ 0 ][ 0 ] of the clock-wise rotated matrix is the value of [ 0 ] [ n] cell of the original matrix. Therefore from the adapter what we request and return is the original matrix's [ 0 ] [ n ] cell value. We can simply create how to map the cell between original matrix and the rotated matrix pretty easily.
Usefull mostly for per-Cell requests. Or once-read matrix (for once output into outer buffer (preview rotated image on display for example)).
Just pick up the whiteboard and turn it clockwise and set it back down on what was it's right side. Done. I can even create an "Undo" and "Redo" fairly quickly if needed. You don't need a microprocessor to solve this problem. Don't over think things people.
I thought of an easy solution....
To do inplace Matrix rotation simply
1.Transpose the matrix
2.Take the mirror image of it..
3.Loop the number of times the rotation is required!!
But the matrix has to be a Square one...( :) Enjoy)
Andy Brown Abhishek is right, actually transpose requires n*(n-1) swaps and mirror n^2/2; transpose + hmirror = clockwise rotation, transpose + vmirror = counter-clockwise rotation. straightforward elegant code, much less bug-prone (shows the employer than you are able to simplify a problem by decomposing it - much more important IMO). What she does is ugly and complicated.
Andy Brown
Sir, in my opinion the Complexity will be O((3/2)*n^2) ..As **satarimar**said the rotation just required an initial check for square matrix and if it does then simply run n*(n-1) swaps and after that n^2/2 swaps for taking mirror images..So swaps can be done by STL swap()..Hence an easy code and not much manipulation! :)
ABHISHEK SOMANI I did some timings:
transpose + hflip (mirror) on 16kx16 matrix: 1.912 sec, direct (=Gayle's solution): 1.868 sec (2.5% faster)
trans+hflip on 32kx32k matrix: 10.341 sec, direct: 10.708 sec (3.5% slower)
what a surprise :) performance is basically the same!
Andy Brown actually I was wrong, the number of swaps required to transpose a square matrix is n*(n-1)/2
Andy Brown I don't think you quite got the concept of big-O notation. The whole point is that if
f(x) = O(g(x)), then
f(x) = O(g(x))
= O(c * g(x))
= O(g(x) + g(x) + g(x) + g(x) + ... (c times))
Which proves that adding two or any other constant amount of identical O-formulas has no effect.
my code would rotate the user clockwise, because in "the matrix" it is not the spoon that bends, but your perception of it ... then I would lol, then I would go ahead and think out loud and ask questions :)
+usergroupX this is actually a pretty great solution. It is much quicker to change how you access the matrix then change the matrix. Instead have a direction variable 1-4 designating directions vertical,90o,180o,270o and then have it read the matrix differently depending on the variable setting.
That's actually a pretty genius idea
Hahahahaha Matrix Reference
as a senior java developer for 10 years.. that has been thru tons of interviews.. i honestly think these kind of questions are outdated and out of touch of reality. Better way to guage a canidate would be asking them real life business scenarios. Like you have an android phone, a tablet, and an iphone. What are some of the technologies u would use to communicate to all of them. Or discuss how you would design a MVC application for a car parts warehouse inventory tracker... this matrix interview question or asking someone to write code to do derivatives should stay in the college classroom
+Henry E It depends on what you want to test. What you have just suggested would be great if you're hiring for a more senior position (someone who already established himself as a programmer). You are emphasizing design over low detail problem solving. This interview obviously goes the other way, it is testing the algorithmic/data structure problem solving skills which is pointed towards a more junior position imo.
Yeah because if you are going to be working on image processing software (or anything having to do with data manipulation) at the company you're interviewing for, you won't be doing anything remotely similar to this example, right?
Point being, each company will ask questions that will be relevant for the position the candidate is applying for, let it be matrix rotation questions or behavioural questions.
+Gherbi Hicham I actually disagree somewhat. If you're interviewing a senior, asking architecture questions seems appropriate but what about checking that they have the knowledge of the basic building blocks of object oriented programming as well so that they can assist juniors when asked a question about frameworks. In terms of problem solving, just have them develop a solution that you'd need put into place in your day to day work and call it a day. No need to go way over the top. Interview shouldn't be a pressure test unless that's what the work environment is really like. ( which I could think of other disciplines worth pursuing that much better reward a pressure test than computer programming ).
Except real life programming and get as abstract and theoretical as this, especially for a company like google.
but this is still how people are judged
I'm sure that it's all about problems you have already seen and that you haven't. Writing code on a white board is frustrating and time consuming. So if you haven't seen the problem before, you are likely to end up spending some more time on the solution and time is limited. If you have seen the problem already you know the approach for the solution but you might not remember all the implementation details... still need time to think about it. If you remember approach and implementation you are safe, you only need to be careful to use the space on the whiteboard carefully.
So to me this is down to "how many problems (solution+implementation) can you remember?"
You might be faster than other in reasoning, maybe because you trained a lot. But I'm sure that during interviews, if you have never seen the problem, the time to get to the coded solution is never enough.
For those who think these types of questions are outdated... you are not thinking about it properly... if you learn basic mathematical operations, you apply them in real life... this is similar... when you are at a place where your code uses other peoples code and vice versa, you want it to be as fast as possible, and as clean as possible and as scalable as possible... if you are having more than a few years of experience in tech and you still think this is not important, best of luck...
My solution is to compose the 90-degree rotation out of two reflections (swaps): one through the vertical axis, and another around the matrix's diagonal. At each step, you are swapping two values and no information is lost. You only need one element-worth of extra storage.
This is way more complicated than it needs to be. First reflect over diagonal going from top left to bottom right (swap a[i][j] with a[j][i] for all j>=i. Then reflect over vertical line of symmetry (reverse each row) and you have a clockwise rotation.
1:38
thank god that if the interviewer expects you to transform the original matrix then it has to be a square matrix
The real question for the interviewee is "Can you write an app with the time wasted in technical interview and make more money than the job you are interviewing for?"
right!
"Show me a formula for curing cancer"
Exactly !
As an interviewer, you need to know whether the candidate can logically deduce the pseudo code and is cognizant of the edge cases and any possible optimization methods. After that, it is imperative to find out whether the potential candidate is detail oriented or not. This is often the key differentiator in determining overall effectiveness. But I agree with some of those who raise concerns about the effectiveness of whiteboard tests. I personally would never conduct those, but would rather find out about their attentiveness by asking backdoor questions they cannot prepare for.
Clear elegant solution and example of rotating a 2d matrix. Good job.
I'd have just reflected the array on the x-y axis through the center array[i][j] = array[j][i] and then reflect it on the side y axis to rotate once clockwise array[i][j] = array[i][n - j - 1]
transpose, reflect about y axis. Arguably better for cache locality
If an interviewer asks you something like this, then he probably doesn't want you to be hired.
Having read this problem in her book a couple of days ago, I have to say I couldn't agree more. I still couldn't figure out how she computes the coordinate of these points.
It depends. Companies like Microsoft or Google do ask these questions, because they don't just need people who can program. They want top 5%, they want people who can solve these problems in their heads in a matter of minutes. Questions like these help them distinguish between top 5% and other 95% who can just program by googling 99% problems.
However, if a company of 5 employees ask something like this during the interview on the "web developer" position (which is actually happened to me during my job seeking experience), then yes, it's pretty f-ed up.
Source?
Yes please, source?
Why, because its too easy?
Or you could map the index directly like this:
int n = res.length - 1;
for(int i = 0; i < res.length; i++) {
for(int j = 0; j < res[0].length; j++) {
// magic line
res[i][j] = a[n - j][i];
}
}
return res;
Here res is a new matrix. So we dont change the original matrix. This is not in place but has O(m*n) space complexity i.e., we duplicate the matrix. Time complexity is also O(m*n) same as the one mentioned by the author, but ease of implementation is higher in this solution. Also this solution is based on simple math(you need to figure out a function to map indices).
The point of this isn't about solving anything, but in how you would approach solving a problem. The key is to show that you can see a problem, assess it, and work it.
I have this book and I did this problem and I also have to agree that it's pretty difficult to come up with the formula to get the offset. But eventually you kind of just memorize it after you see this type of problem
Loved this video, but it might be a good idea to post an alternative solution proposed by another commenter: "flipping" the matrix horizontally and then along the y = x axis. It's much easier to code, and it has the same run time (asymptotically speaking). Again, I don't mean to take anything away from the layer approach; it is a great way of illustrating the importance of breaking up a complex problem into more manageable parts.
I slept my way through the interview process.
Q. How many people have got rejected in software engineering interviews?
A. Just count the comments stating that companies need to stop asking stupid interview questions and add the likes those comments got.
LOL! XD
I counted. It equals 149 people were asked stupid questions in software interviews, the jobs they applied for were subsequently given to people who interpret data wrong, as the interviewer was looking for like minded people to be team players. Hows that for problem solving?
How many pass this interview? count the bugs of google products and divide them by 100. Each employee has 100 bugs he made.
>>> matrix = [(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12)]
>>> list(zip(*reversed(matrix)))
[(9, 5, 1), (10, 6, 2), (11, 7, 3), (12, 8, 4)]
Problem solved...
awesome
Laughs in python
Python ftw
Now do it in C 😂
Why not use a rotation matrix? It would then allow you to rotate an arbitrary number of rads (more applicable to real-life, e.g. graphics programming) instead of 90 deg intervals. The hardest thing is just to remember the form of a rotation matrix from a basic LA class, then you just do inputMat *= rotMatrix. Done. Cleaner, and makes more sense in my opinion.
Cut to the chase would be among my first questions.
transpose matrix and reverse rows to rotate clockwise.
I feel excited about the future, I'm a senior in high school and plan to go into either computer science, computer engineering, or electrical engineering with an emphasis on technology.
Do computer engineering
Just remember that only about 1% (yes, one percent) of job recruiters verify college degrees these days, so you'll be competing with millions of people who lie about have a college degree. Bad idea. Easier just to lie about having a degree than to actually earn one.
Learn Electrical engineering... your life will be peaceful...:) as I am still repenting to choose Computer Engineering ):
Rajnish Jha Why do say that?
Joel C. Unless your job requires a professional degree, please remember: employers stopped verifying degrees a long time ago, so everybody lies about having one. It means your degree is useless, other than what you learn.
Lets visualize what happens when you go inside the layers of the square matrix:
Your left-right reduces by 1 on each side.
Your top-bottom reduces by 1 on each side.
Hence, the bounds are reducing by 2 for left-right & up-down with each deeper level into the square matrix. The whiteboard is not reflecting this (unless I'm missing something. I too am fallible and am in no way perfect).
I wrote the program depicted (I'm not going to post it here since it's an interview question). It took me more than an hour. I'm no genius. It's implementation is difficult enough, requiring a bit of debugging as what I visualized was translated line-by-line into code. I could not imagine doing it all the way on the whiteboard. Pseudo-code? Maybe. But writing code? I don't see the point.
My point- how many people write code without making a mistake or two? Literally no one. Even the author is not accounting for shifting unless I am missing something here.
+Charlie B
Did you use recursion by chance? I am a new student with less than a year of java experience and have been trying to think recursively as much as possible.
Would be nice if you were to show how you came up with the code. How did you get the expressions to go into all the marix[...] expressions.
In my view algorithm questions are overrated, but it's hard to what to replace them with. If it were possible, I would have preferred to do a demo project as it would be much more reflective of what I can do than a 30min algorithm puzzle.
danielfromca "This is for a position as a DBA. Show me a SQL query that does the following..."
"This is a position for a web developer. Create a POST request in AJAX with the following criteria..."
THAT is what technical interview questions should be. Questions relevant to the jobs that test if you can do it. The bullshit tests that they do now don't test your ability to do the job.
So the first advise is "Ask questions"? Well, once I got interviewed by a company from Washington DC and the guy would not let me ask any questions. He answered rudely: "Come on! All the informations you need are already written in the PDF!"
To tilt 90 degrees, this code also would works
int[][] input ={{1,2,3,4,13},{5,6,7,8,14},{9,10,11,12,15}};
// Assign row to column & column to row
int[][] out = new int[input[0].length][input.length];
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[i].length; j++) {
out[j][out[0].length - (i+1)] = input[i][j];
}
}
Good info Gayle..I learned something thanks for your efforts you are appreciated..
I thought this was one of the hardest problems when I first read her interview book, now it's not too bad. Guess it just takes time.
Very valuable information here! , Thanks Gayle :)
Thank you for your valuabe time and thoughts!!
Shes speaking Java according to her book its the language shes familiar and comfortable with.
I didn't understand much but enjoyed watching her
I got interviewed for a position and the interviewer only asked me one question. What's is a UDP, TCP and the difference between them? Just finishing college I don't think I even had a networking class but I still knew how to use TCP AND UDP but because I could not explain it in the way he read it from his book I was rejected. Then he recommends me to read this book. If it was really important to learn about network protocol hire me and give me time to learn that.
I actually got asked the same question. Did you have anything computer networking related on your resume because I did? TCP and UDP are both transport layer protocols. TCP has reliable data transfer which means the packets will arrive in order and will have a guarantee of delivery meanwhile UDP is the opposite and is unreliable data transfer and packets may arrive out of order or may not be sent at all. The way TCP makes sure that a packet needs to be resent is when it receives a 3 duplicate ACK packet. UDP is also very fast because its unreliable making It great for uses that can handle data loss like streaming video or video calling over internet (VoIP) while TCP is for situations that require reliable data transfer like sending email, surfing the web, etc. I did take a Computer Networking class recently so it helped me. If you didn't have anything computer networking on your resume its unfortunate they asked that.
she stares right in your soul
Thank you, I have read your book and use it for interviews.
Thanks for the suggestions Dutchboy 777. Good suggestion on the lapel mic for my flip camera. Will work with the production folks next time on editing out some of the vocal missteps.
Take care, Dawn Kawamoto, Dice Assc. Editor and video shooter.
You can just transpose the matrix and swap the column coordinates.
blonde girls... am I right?
yea... implementing this on the spot is tricky, thus the camera cut. I've been asked some fun ones, "implement auto complete", "implement infinite scroll", "implement search engine", "implement pig latin -> english translator n vice versa"... fun stuff indeed.
I've solved this problem by another approach. Firstly, I've transposed the matrix, and then swapped all the columns from right to left according to the center(middle column depending on the number of columns whether it is odd or even). On bigger number of N my approach worked faster.
Gayle's communication skills have improved vastly over the years.
That's an improvement??
thanks for sharing this, but stuttering affected the smoothness of the explanation quite a bit.
Perhaps it's a good idea to think of conditions/invariants that hold at different points in code. You clearly have an advantage if you're skilled at proving code correctness.
But she messed up her code by fixing it... the second for loop had "i < last" which means that at layer = 1 the code would've ran from 1 (which is first), then 2, but when i became 3 the code would see that it's out of bounds and exited the for-loop. Either she could've reverted to the earlier code, without the -1, because that worked, or she could've switched to i
You're incorrect. The '3' is the '1' of the other layer. In this case the top layer she circles consists of only the first (1) and second (2) element, then the right layer begins on the first layer's 1.
I saw her at CalHacks! She is amazing =]
Can someone explain me a bit more about the second FOR LOOP, it's a great video and I love it, I'm new to programming and trying to teach myself. Many thanks
Hey Michael. The second For loop goes through each element on the row. So iteration 1 rotates the top left box on all 4 sides. Then iteration 2 would rotate the second box on all four sides. We continue this for each remaining box on the row.
Excellent video and excellent book. Thank you!
Switch the array parameters from [a],[b] to array.reverse([b]),[a].
I'm going to have to watch this video multiple times to grasp that solution. This makes me feel even more terrified about my interview later. Maybe my Masters in CS was a waste of time smh.
Thank you. Very nice presentation, examples and explanations.
Great job!
This code will have an array out-of-bounds error. (Layer starts at 0. Last starts at n. Offset starts at 0. This leaves the index [last - offset] as n in the first iteration. Arrays are zero-indexed, so that's going to be an issue...
Honestly she is acting like a Genius, but the reality behind all this is, that she had to prepared all this, I am sure, if they ask her something similar or more complicated, the interviewer will tell her, sorry but your time is up. It is not so easy in real life as she is putting it, There will be cases will she will not be able to do it in the amount of time that the interview give her, complexity varies, and we don't know it all. We have to learn before we explain, unless we learn everything out there.
yet she will get ANY (and ī mean any) job SHE applies for. no interview needed. that's real life for ya.
toalopez thats absolutely false, ive solved questions like these with all edge cases included in the standard 50 mins. sometimes they even give 2 problems in that 1 hour time.
This is ridiculous, why would they put these kind of stress on candidates, when all this is useless, because all this is done years ago, and we do not need to not even think about it. They just want to analyze your brain in learning how you think to solve complex problems even when you never had done it before. But this is not new to this lady in this video, she already practice all this before making this video, but I would like to see that Microsoft, Facebook, Amazing, give her a real coding test in real life examples, that she never done in all her life previously, to see, if she can do it in the same manner that she is explaining it, it is easier said than done. In reality, this is to know, how bright and how far you can go, to know how much money they are going to save with you, because they are going to make you work like a slave with so much pressure and so many projects at the same time, making you do 2 and 3 positions for one single salary. This is some type of slavery but without the weapons they use to use to torture people, but in a physiological way. It shows them if you are worth they money they are going to invest in you and making you work for 2 or 3 employees.
This is stupid, they are making people break their head trying to find a solution, when the current expert employees, can teach you how to solve different
complex problems and if they cannot still solve any solution, then they will dismiss that person. which it is a much better solution of finding the right candidate. IF you can make them a clone of the expert, then you got the employee that you are looking for, if not , then the person does not qualify for the position. It is that simple!!! I cannot understand why people makes things more complicated in Life.
toalopez she actually did pass interviews for microsoft, not sure about other companies. Also, even if they do give more work (which is not anything extremely stressful and the big 4 companies repeatedly come in as top places to work), they pay a huge salary.
Excellent Gayle. This was really helpful. Will use these tactics on some upcoming interviews.
All the best,
A Miami Colleague
Thank you! Excellent explanation
from numpy import rot90
def rotate(m):
return rot90(m, 3).tolist() if type(m) == list else rot90(m, 3)
I
There's plenty of time to apply for a job at google. However, to get into a top company like Google, you must be willing to put in the time and effort. I recommend getting Cracking the Coding Interview book and going through it every day. Try doing the problems yourself before you look at answers.
I'm a sophomore pursuing a degree in computer science. In your freshman year, you will be taught arrays and array manipulation. A matrix can be thought of as an array of arrays or multidimensional arrays. So to manipulate or rotate a matrix would involve knowing how an array fundamentally works. Yes, you will be prepared for a job at Google or any company if you take your classes seriously and work hard to understand your field. Also, secure internships every summer working as a software developer/engineer at any company whether startups or fortune 500.
I dont like these interview questions. They belong to the academic world only or if you are interviewing an algorithm designer and not on the job. I have found Multi threading, OOP , MVC , reliable/maintainable code, documentation, commuincation, team work,networking and obviously the basic for/if constructs are much more important on the job
the answer that works on most interviews: "I will be waiting outside.. for you.."
I was actually asked this question during my onsite interview at Snaproute, March 2017. :(
How’s everything with you now? How were other interviews?
Solution:
Search for an existing library and use this instead of solving already solved problems.
Thanks giving for this... i hope.. i will crack the interviews :)
And for your next task...
I want you to write code in assembly that will land be able to land a SpaceX rocket on a launch pad in the middle of the Atlantic ocean at night.
You can use whatever color marker you like.
Why do we have to swap term by term when we can instead swap the arrays? Wouldn't it take less time
Oh, I love you
Having array.ElementLength and array.IndexLength would save hours worth of hair ripping.
My answer: study your math! This is linear algebra and there is an equasion that can be derived that can rotate a square matrix through an arbirary angle.
... she obviously never cracked a linear algebra book, and never passed a linear algebra class. You can tell by the way she is inventing her own terminology. Since when did a matrix have "cells" and "layers"? LOL
Gaussian-eliminate this chick...
***** hey man correct me if i'm wrong, as far as i can remember 2d matrices can be rotated by an angle Theta in the xy plane simply by multiplying them with the corresponding transformation matrix (would be rotation matrix in this case), can't they ??
Aritra, largely correct. Matrix rotations are only defined for square matricies. A 2D square matrix is essentially 2x2. Three dimensions is much more interesting. There are three possible rotations that you can do. In the coding example, she appears to be rotating about the z axis with a special case of 90 degrees. Here is the rotation matrix, I used google to refresh my memory.
cos(a) -sin(a) 0
sin(a) cos(a) 0
0 0 1
I suppose you could inserting cos(pi/2)=0 and sin(pi/2), perform the matrix multiplications, and get an answer, but I like reusing stuff, so I would keep everything very arbitrary and make 3 functions that takes in 3 arguments: reference to source matrix, reference to a destination matrix, and an arbitrary angle. Each of the 3 functions would be an arbitrary rotation in one of the dimensions, (x,y,z). In the documentation I would specify that the source matrix needs to be 3x3, the destination be 3x3 and the angle measured in radians.
It has to be three functions because matrix rotations depend on the order of operation.
***** yeah that's something which faintly remember... After all its been quite a long time since I completed my grad. But a 2D square matrix means any NxN matrix not necessarily a 2x2. I too was suspecting that she might be rotating it about the z axis. But the next question is how to rotate it for any NxN ??
***** Mike, while your mathematical approach is technically valid for linear algebra it is being applied in the wrong context here. The question being asked refers to moving the data items within a matrix of memory locations, not rotating an object or set of vectors through a specific physical angle in space.
Visualize the problem for a 4x4 array of characters in computer memory e.g. char myMatrix [4][4];
a b c d
e f g h
i j k l
m n o p
"Rotating" the data indices clockwise this becomes
m i e a
n j f b
o k g c
p l h d
So the char at myMatrix[0][0] ('a') is now located at myMatrix[0][3]
[0][1] ('b') moves to [1][3]
[0][2] ('c') moves to [2][3]
etc....
Hope that helps.
why do you want to rotate matrix? what is the purpose of it in real life?
It's not about the problem; it's about being able to deal with complexity.
Are there no other complex real time problems?
Come to think of it, rotating an image is very much a real-world problem. A bitmap is essentially a matrix of pixels. :)
i agree now! :)
3D Graphics Programming i guess.
Here she sounds so much better than in hacker rank videos.
Nice video. Thanks
I use the next code (it assumes different width than height which is the general case but of course no in place)
void RotateMatrix()
{
int count = Width * Height;
if (count == 0) return;
int OldX, OldY, NewX, NewY;
for (int t = 0; t < count; t++)
{
OldX = t % Width;
OldY = (int)(t / Width);
NewX = Height - 1 - t / Width;
NewY = t % Width;
ResultData[NewX, NewY] = OriginalData[OldX, OldY];
}
}
I would just go up there and rotate the board itself 90 deg clockwise and demand a TC of > tree-fiddy.
Ok but I think you missed the point. She is not teaching the absolute best way to solve the problem, but she is explaining us how to deal with a prob. in an interview, that is :
ask questions, show the way you think about the problem, start with an example, try to fragment it, etc...and "that" is the wole point of the video.
Good information, but from a production value point of view, not that good. A couple suggestions:
- Use a lapel mic to avoid the hollow sound.
- Make several takes from different points of view to keep it interesting and allow you to use only the good takes and remove the vocal missteps.
she is left handed
Wow! Girl's really cute :) Plus she's not so confident with the camera as also mentioned in many other comments.
And Gayle, we can actually rotate non-square matrix with the condition that one of the dimensions must be positive. You are a great teacher. Cheers!
Great video and great book!
How about:
def rotate(M):
return zip(*M[::-1]) # reverse the elements and pack them together with zip
Or more accurately: return [list(x) for x in zip(*M[::-1])]
Hope I never have to program something like this.
Hey Maam the video is Great!!
Am I the only one think that the intention is not that obvious? Why do not we just add another layer of indirection to the code? There is no specification how actual data structure looks like. We could have a consecutive chunk of data and transposing the matrix is to just change the access function.
offset is tricky to conjure
How sad that we need to learn a *completely different skillset* for job interviews than the *actual* skillset needed to do the job.
The hundreds of billions of dollars lost by engineers wasting their time on practicing crap like white board coding, which is *never* used in real life engineering!
We have IDEs and compilers now, you know.
We basically creat this crap as a business to make 💰
Hight Tech Companies need smart people, they prefer them because is easy for them to solve problems, learn new skills and technologies, etc. See the facts, those companies are what they are because of the people they hire.
So I learned web development all these years and realized I could not make it as one because I can't pass some of these tests. Now I am studying to do UX work instead.
@@juanperusquia7456 Yeah but there are a lot of ways to be smart and a lot of people are just studying her book and memorizing answers. Wouldn't it be better to be an expert at say..Microservices, than leetcode algo problems?
Top tech companies don't want people who can just code, they want you you to have many skills including and most importantly communication, you see if you just come and solve the problem even if you solve it really fast and really good, chances are(and the chances are really big) that you won't get accepted by big tech companies, because in big tech companies you'll spend not more than 30 to max 40% of your time coding, the rest is planning between your team or even with other teams and meetings etc... and studies shown that communication between the interviewer and interviewee is better when the interviewee is working on a white board instead of an IDE, and btw the interviewer won't have any problem if you forgot a ; or a } in your code, h doesn't care about these types of errors.
Why does the minus 1 for last make sense. The loop never reaches that number
I`m bad at algorithms and math. Algorithms on codility.com are rocket science for me.
the fact is i really learned something !
There is no such thing as a matrix inside a computer, everything in the computer is stored sequentially,
even a matrix will be stored sequentially,
we just abstract it to fit our human syntax of a matrix
We all have a calculator but we still study how to add numbers!! Don't we??
OMG its so Simple do they ask this kind of questions ??
and Im here struggling like fuck with the "easy" problems on leetcode.com and still fail interview tests cuz they feel completely out of touch from what I learned in college, lol
Thanks!
Rows don't just become columns? What am I missing?
I think we should all make things then once a week go to an open market and trade with one another. I'd make a pumpkin pie!
Government won't like that... no taxes
HOW can you get better at algorithms???
take an DS, Algo course and practice from geeksforgeeks.org
as simple as that
Or you can flip it upside down, then flip left to right