5
\$\begingroup\$

I want to compare two solutions to the following question from Cracking The Coding Interview by Gayle Laakman McDowell :

1.7 Rotate Matrix - Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

We will be assuming we have a square matrix to rotate by 90 degrees clockwise like so:

input: 
1 2 3
4 5 6 
7 8 9 
result: 
7 4 1 
8 5 2 
9 6 3

The book suggests an unusual "layer" method that works its way from the outer edge of the matrix towards the inside

A much more intuitive way to solve this seems to be a matrix transpose, followed by a mirror about the vertical axis. This solution is more intuitive because it uses known mathematical matrix operations - the transposition and the reflection. Aside from this being more obvious and easier to read for who have dealt with matrices in the past, it is also more useful because these individual mathematical operations could be saved for other purposes.

Is there any issue with the following code ? More specifically, what are the pros and cons versus the original McDowell solution ?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<vector<int>> matrixT; 
class Solution {
    public:
    bool static rotateMatrix(matrixT &mtx){
        if (mtx.size() != mtx[0].size() || mtx.size() == 0) return false;
        int N = mtx.size();

        //transpose matrix
        for (int n = 0 ; n<= N-2; n++)
            for(int m= n+1 ; m<= N-1; m++)
                swap(mtx[n][m], mtx[m][n]); 

        //vertical mirror
        for (int n = 0; n < N; n ++)
            for (int m=0; m<N/2 ;m++) 
                swap(mtx[n][m], mtx[n][N-1-m]);  

        return true;    
    }

    void static printMatrix(matrixT mtx){
        for(int m = 0; m < mtx.size(); m++) {
            for(int n = 0; n < mtx.size(); n++)
                cout << mtx[m][n] << " ";
            cout << endl;
        }    
    } 
}; 

int main() {
    cout << "input: " << endl;
    matrixT mtx = {{1,2,3},
                   {4,5,6},
                   {7,8,9}};

    Solution::printMatrix (mtx);
    Solution::rotateMatrix (mtx); 
    cout << "result: " << endl;
    Solution::printMatrix (mtx); 
    return 0;
}
\$\endgroup\$
5
  • \$\begingroup\$ I've removed comparative-review as you only provide one program (the one you've linked to is out of scope, as it's not your code to post). \$\endgroup\$ Oct 29, 2019 at 14:27
  • \$\begingroup\$ @TobySpeight I've seen your comment and added the other solution to the question. \$\endgroup\$ Oct 29, 2019 at 14:40
  • \$\begingroup\$ I don't think you're entitled to post that code - did you write it yourself? \$\endgroup\$ Oct 29, 2019 at 14:42
  • 1
    \$\begingroup\$ Please be aware that editing questions after they have been answered is discouraged by the community. Please see this help topic codereview.stackexchange.com/help/someone-answers. \$\endgroup\$
    – pacmaninbw
    Oct 29, 2019 at 14:46
  • 1
    \$\begingroup\$ Why would you even move the elements in the matrix? That seems like a very inefficient way of implementing this. I would rather define an interface the converts input coordinates into actual coordinates of the underlying data structure. That way you don't move anything. Then you can have several deferent translations applied to the data and only actually move the data if you want to save it at some point into the new position. \$\endgroup\$ Oct 29, 2019 at 18:16

2 Answers 2

2
\$\begingroup\$

I would use a virtual view onto the underlying data.

A view simply converts the coordinates from the user specified value into actual data coordinates. No need to actually move any data.

typedef vector<vector<int>> matrixT; 
class View
{
    public:
        virtual ~View();
        virtual int& get(int x, int y) = 0
};

class IdentityView: public View
{
    matrixT&    data;
    public:
        IdentityView(matrixT& data): data(data) {}
        virtual int& get(int x, int y) override {return data[x][y];}
};
class Rotation90ClockWise: public View
{
    View&     parent;
    public:
        IdentityView(View& data): data(data) {}
        virtual int& get(int x, int y) override
        {
            int actualY = x;
            int actualX = maxX - y - 1;
            return view.get(actualX, actualY);
        }
};
// etc lots of transpositions like mirroring rotations can be defined.
// Apply multiple transitions without doing any moving. Once you have
// the correct transformation then copy to a destination
\$\endgroup\$
2
\$\begingroup\$

Keep in mind that the primary focus of this web site is to review your working code and provide suggestions on how to improve the code. Questions about which way is better or worse may be based on opinion and that is off-topic for most of the stack exchange websites.

In answer to your question, it could be a possible optimization that reduces the number of steps, but that isn't clear. You may be missing the point of the interview, which is that you should explain as clearly as possible to the interviewer(s) what you are doing at each step so they understand your problem solving techniques. Please note that the video code looked more like C rather than C++, but could have also been other languages.

Avoid Using Namespace std

If you are coding professionally you should get out of the habit of using the using namespace std; statement. In an interview you definitely don't want to use this statement because it is unprofessional. The concept of Name Spaces was invented to specifically solve certain problems such as collision of duplicate function names from core code and library code. This stack overflow question discusses this in more detail.

Use Code Blocks in Flow Control Rather Than Single Statements

Professional coders generally put code blocks or complex statements into if statements, else clauses or loop bodies. The reason for this is to enhance the maintainability of the code. To many bugs have been introduced into code by trying to add one statement to an if statement, else clause or loop. A code maintainer may forget to add the necessary braces so putting them in from the beginning is better. It also makes the code more readable and easier to understand to begin with.

So code like

        int N = mtx.size();
        for (int n = 0 ; n<= N-2; n++)
            for(int m= n+1 ; m<= N-1; m++)
                swap(mtx[n][m], mtx[m][n]);

is better written as

        size_t N = mtx.size();
        for (size_t n = 0 ; n <= N-2; n++)
        {
            for(size_t m= n + 1 ; m <= N-1; m++)
            {
                std::swap(mtx[n][m], mtx[m][n]);
            }
        }

Obviously a maintainer of the code can figure out where to add a statement here.

Horizontal Spacing

It is common to leave spaces between operator and variable. The horizontal spacing in this code is inconsistent.

Prefer std::size_t Over int For Loop Control Variables That Index through C++ Container Classes

While the code in the example from this question will compile and run properly there may be warning messages if the strictest level of compiler switch is used. std::vector.size() returns std::size_t which is unsigned, rather than signed. If the strictest level of switches are used a the following loop might yield the warning message type mismatch.

        for (int n = 0 ; n <= mtx.size() - 2; n++)
        {
            for(int m= n + 1 ; m <= mtx.size() - 1; m++)
            {
                std::swap(mtx[n][m], mtx[m][n]);
            }
        }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ As for your first paragraph: we have comparative-review. \$\endgroup\$
    – Mast
    Oct 29, 2019 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.