Rotating a Matrix (with Gifs!)

This post is a bit more technical than usual, but don’t worry, there are pictures.

I was having a lovely time working through the Arrays and Strings section of Cracking the Coding Interview until I reached this problem:

Rotate Matrix: Given an image represented by an NxN matrix** … write a method to rotate the image by 90 degrees. Can you do this in place?

This is a deceptively tricky problem, and I had to draw quite a few diagrams in order to understand it. Let’s walk through it.

First, for our purposes, a matrix is a two-dimensional array. While the problem suggests that we should be able to apply this solution to a very large matrix (like an image), I have found that a 4×4 array is the easiest way to visualize this problem. Here  is the basic example that I will be referencing throughout the post:

[
[1,    2,   3,   4],
[5,    6,   7,   8],
[9,   10, 11, 12],
[13, 14, 15, 16]
]

Our function to rotate it by 90 degrees should return:

[
[13,  9,  5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]
]

Note: The first element of a JavaScript array has an index of 0, the last element has an index of array.length -1. Each element of the matrix can be referenced by its position in the outer array followed by its position in the inner array, so matrix[0][2] = 3.

The Approach: We will tackle this matrix layer by layer, starting from the outermost layer and working inwards. Since the problem is to rotate the matrix “in place” instead of making a copy of the matrix, we will swap each element individually, moving it from its current position to the position 90 degrees from it.

This requires that, for any element, we can find the coordinates of its position when rotated 90 degrees. We can then loop through each element and rotate it by swapping it with the element that is a 90 degree rotation from it. 

flipmatrix

It took a while to come up with a methodical system to find these coordinates, but with a little help from my friends and the internet, here’s what I’ve got:

The Coordinates: In order to find each set of coordinates, we need three variables:

  1. The width of the matrix, N.
  2. The Layer of the matrix that we are inspecting, starting with 0 (the outermost layer)
  3. The Position of the element that we are inspecting within its row. This can also be thought of as the element’s offset from the end of the row.

Using these three variables, We can establish that for any layer and position, the four corresponding elements that need to be swapped are:

matrix[Layer][Pos]
matrix[Pos][N-Layer-1]
matrix[N-Layer-1][N-Pos-1]
matrix[N-Pos-1][Layer]

To help visualize this, I have created a diagram of these coordinates on our 4×4 matrix

screen-shot-2016-11-18-at-10-15-48-amscreen-shot-2016-11-18-at-10-16-15-amscreen-shot-2016-11-18-at-10-16-27-amscreen-shot-2016-11-18-at-10-16-37-am

You can view and test my final solution to the problem here.

** I have eliminated the portion of the question concerned with memory, since I am working in JavaScript and memory is magically taken care of.

The Beginning (kinda)

For the past week and a half I have been working as a teaching fellow at Grace Hopper. The transition from being a student to an employee has been pretty smooth. Maybe it’s my teaching background, but it seems perfectly natural that, after devoting three intensive months to learning to code, I should spend another three months helping a new group of students do the same (while continuing to learn myself).

As a teaching fellow, I spend about two to three hours per day helping students with their workshops. This is a very engaging mixture of fun and stressful, since the current group of students is extremely talented. Several of them have studied computer science, and others have work experience in related fields. There are also a number of students who, like myself, have no formal background before Grace Hopper, but on the whole this group is very capable. So far, I haven’t felt like there were questions that I couldn’t answer, but as it definitely keeps me on my toes.

I also spend a good chunk of time each day going over the next workshop that I will be covering. This is something that I always wished that my own TAs had done when I was a student, since it’s difficult to jump in and debug code when you don’t know the context. There isn’t explicitly time allotted to this, but I think it’s essential to doing my job well and helping the students as much as possible.

Another aspect of my job is engineering for Learndot, the website that students and instructors at Grace Hopper and Fullstack use. My first task was writing tests for some methods that had already been written. This was pretty challenging, because the methods were for MongoDB and JSData, neither of which I have any prior experience with. I needed quite a bit of help to get started, but yesterday I finally got my work merged into the master branch, which felt amazing. My second task has been entirely Angular, which, as readers of this blog know, I love. It’s been going much more smoothly.

The final aspect of my job is interviewing candidates to be future students. I am currently still in training for that, and probably can’t talk much about it, but it is something that really excites me.

That’s all for now! Happy election day (let’s hope) and thanks for reading!!

Week 13 – THE END (kinda)

So, yesterday was my official graduation from Grace Hopper. However, since I am staying for an additional three months as a fellow, it didn’t feel like much of an ending. I have already started learning React so that I will be able to help the new students with it (future cohorts are learning React instead of Angular), and it feels very much like, even though I have learned so much, there is still a great deal of new information ahead of me. I am excited that I will get to hear some old material described by new instructors, and particularly excited that I will be a part of the engineering team for the online learning platform that we use at Grace Hopper and Fullstack. I will continue to document my adventures here, possibly adding some new structure to the site.

The entire last week was taken up by rehearsing our presentations for hiring day. We made screencasts that walked through our final projects, and we practiced delivering out demos in front of each other 5 or 6 times. This was a bit painful but I thought that everyone’s presentation ended up being extremely polished as a result, and in general it helped us build the good habits of practicing presentations.

Speaking of presentations, here is a link to my tech talk from week 11!

 

Weeks 11 and 12


My only excuse for not posting in two weeks is that these weeks have been by far the toughest, busiest, and most stressful weeks in Grace Hopper. I feel like I have been working nonstop and only now have time to take a breath. Here are some things that happened since I last wrote:

  • We made Dish’d! In two short weeks, we converted this app from a wobbly lump of code that broke every time we touched it to a robust and usable application. If you tend to have trouble planning out your meals for the week, I suggest you try it out! It’s live at dishd.us (and if it seems to be down for a sec, try again later. I swear it’s worth it!!)
  • My team also worked on and presented our application at the Angelhack “Lady Problems” hackathon. Even though we didn’t take home any prizes, it was a really great place to work and meet people all week. It’s very inspiring to work in a room full of mostly other female developers, and the venue at the AWS popup loft was beautiful! Plus, there was free food and several free t-shirts.
  • I made a stop by Code Camp NYC, a conference at the Microsoft center where I saw a very helpful lecture on Angular 2.
  • We also presented Dish’d at family and friends demo day. Thanks, mom, for coming to New York to see our presentation!!
  • If that wasn’t enough, I also gave a tech talk on components in angular 1. This was for a 10 minute presentation that all Grace Hopper seniors are required to put together. I will post a video of it soon, for anyone who is interested in my take on that topic (anyone?).
  • I applied for, and was accepted to, the Grace Hopper fellowship program! This means I will be staying on for the next three months as a teaching assistant, while also doing work on the website used by students at Grace Hopper and Fullstack Academy. I’m very excited for this opportunity to keep learning (and get paid for it this time). The adventure continues!!

It’s now the last week as a student in the program, and I can’t believe it! let’s do this!!

Week 9 (whoops)

I accidentally published this on my other blog! Whoops. Here’s a recap of last week:

This week felt very different from the others, perhaps best characterized by the phrase “hurry up and wait.” There was a huge rush to get Grace shopper deployed by Wednesday morning, followed by a lull for the rest of the day while we waited for others to finish presenting and then took our final quiz of grace hopper (which, at this point, didn’t feel like a huge deal since we have been practicing all of our tools very intensely).

On Thursday, we started ‘stackathon’, which is a two-day hackathon where you can work independently or in pairs on whatever you want. I had been planning to try something very ambitious for it, but at the last minute I decided to do something fun instead. I have been working (Thursday, Friday, and through the weekend) on an iPhone app that helps you learn different languages. The app lets you take a picture, and then it suggests tags for that picture in the foreign language of your choosing using image recognition software. It then generates flash cards based on the image, so that you can carry around a deck of clash cards based on what you have seen that day. The app runs on ionic, which allows you to write apps in JavaScript (very cool but hard to debug)! I will try to share some version of it on here soon.

Week 10

Wow, a double-digit week number feels pretty surreal. This week has been, I can’t lie, very stressful. All those earlier weeks where I thought “wow, this isn’t so difficult” are coming back to bite me.

This was the first week of our capstone projects. We were assigned teams of 3 and 4, and we spent Monday and Tuesday brainstorming projects. My group, and every group I think, struggled with this. It is hard to come up with something interesting yet doable, something that feels fresh and exciting but that is also, at its core, just a website. I think my group got bogged down by trying to come up with something that absolutely no one had ever done before. Ultimately we decided to build a meal planner application that will suggest recipe pairings  to the user and generate a weekly shopping list. It’s been done, but we’re going to do it again, hopefully with our own personal twists.

Once we had an idea, we had the additional roadblock of trying to use a new framework. React is becoming an extremely common alternative to Angular, and we initially planned to use it for our project. This resulted in us losing all of Wednesday to powering through React tutorials, trying to get the barebones of our application set up, realizing the instructors and TAs couldn’t really help us with our React problems, and ultimately deciding to stick with Angular. That was frustrating.

Anyway, now we are up and running, and moving right along. The site, in its early stages, is deployed at dishd.us, and will be updated continuously as we work on it (as of publication I think it is just the boilerplate Fullstack website that we are all allowed to use to start off).