2
\$\begingroup\$

I'm posting my code for a LeetCode problem copied here. If you have time and would like to review, please do so. Thank you!

Problem

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.

A student attendance record is a string that only contains the following three characters:

  • 'A' : Absent.
  • 'L' : Late.
  • 'P' : Present.

A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

Example 1:

  • Input: n = 2
  • Output: 8

Explanation:

There are 8 records with length 2 will be regarded as rewardable:

  • "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"

  • Only "AA" won't be regarded as rewardable owing to more than one absent times.

  • Note: The value of n won't exceed 100,000.

Accepted Code

class Solution {
public:
    static int checkRecord(int edges) {
        if (edges == 0) {
            return 1;
        }

        // possible candidates
        uint32_t adj_matrix[MATRIX_WIDTH_SQUARED] = {
            1, 1, 1, 0, 0, 0,
            1, 0, 0, 0, 0, 0,
            0, 1, 0, 0, 0, 0,
            1, 1, 1, 1, 1, 1,
            0, 0, 0, 1, 0, 0,
            0, 0, 0, 0, 1, 0,
        };

        uint32_t a[MATRIX_WIDTH_SQUARED];
        uint32_t b[MATRIX_WIDTH_SQUARED];
        uint32_t* accumulated = a;
        uint32_t* temp = b;
        uint32_t* adj_matrix_pointer = adj_matrix;

        std::memset(a, 0, sizeof(a));

        for (unsigned int node_x = 0; node_x < MATRIX_WIDTH_SQUARED; node_x += MATRIX_WIDTH + 1) {
            a[node_x] = 1;
        }

        // Square 
        while (edges > 1) {
            if (edges & 1) {
                matrix_multiply(accumulated, adj_matrix_pointer, temp);
                std::swap(temp, accumulated);
            }

            matrix_multiply(adj_matrix_pointer, adj_matrix_pointer, temp);
            std::swap(temp, adj_matrix_pointer);
            edges >>= 1;
        }

        matrix_multiply(adj_matrix_pointer, accumulated, temp);
        uint64_t first_col_sum = 0;

        // Sum up
        for (int node_y = 0; node_y < MATRIX_WIDTH_SQUARED; node_y += MATRIX_WIDTH) {
            first_col_sum += temp[node_y];
        }

        return (uint32_t) (first_col_sum % MODE);
    }

private:
    static constexpr int MATRIX_WIDTH = 6;
    static constexpr int MATRIX_WIDTH_SQUARED = MATRIX_WIDTH * MATRIX_WIDTH;
    static constexpr uint64_t MODE = 1000000007UL;

    static void matrix_multiply(uint32_t* a, uint32_t* b, uint32_t* c) {
        for (unsigned int node_y = 0; node_y < MATRIX_WIDTH; node_y++) {
            for (unsigned int node_x = 0; node_x < MATRIX_WIDTH; node_x++) {
                uint64_t matrix_multi = 0;

                for (unsigned int k = 0; k < MATRIX_WIDTH; k++) {
                    matrix_multi += (uint64_t) (a[node_y * MATRIX_WIDTH + k]) * (uint64_t) (b[k * MATRIX_WIDTH + node_x]);
                    matrix_multi %= MODE;
                }

                c[node_y * MATRIX_WIDTH + node_x] = matrix_multi;
            }
        }
    }
};

Reference

In LeetCode's answer template, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I suggest you try some of the problems on hackerrank.com to get a little more attention to your questions. \$\endgroup\$ – pacmaninbw Jun 24 '20 at 4:07
2
\$\begingroup\$

Use C++ Container Classes
This code looks too much like C code and not enough like C++ Code.

In the modern day C++, the use of raw pointers such as uint32_t* accumulated = a; are frowned upon, and container classes such as std::array and iterators were developed to reduce the use of raw pointers.

The C style array b is never initialized, and the C style array a is initialized twice.

        std::memset(a, 0, sizeof(a));

        for (unsigned int node_x = 0; node_x < MATRIX_WIDTH_SQUARED; node_x += MATRIX_WIDTH + 1) {
            a[node_x] = 1;
        }

The first initialization can be accomplished by:

        uint32_t a[MATRIX_WIDTH_SQUARED] = {0};

and I would prefer to see an iterator used in the second initialization.

Use Proper Casting
Currently the code is implementing C style casting ((uint32_t) (first_col_sum % MODE)) which is not as type safe as either static_cast(VALUE_TO_BE_CAST) or dynamic_cast<NEW_TYPE>(EXPRESSION). In this case I recommend static_cast.

Static Functions
It is not clear why the checkRecord() function was changed to a static member function since the original prototype was int checkRecord(int n) in the question. There really is no need for it to be static.

By declaring a function member as static, you make it independent of any particular object of the class. A static member function can be called even if no objects of the class exist and the static functions are accessed using only the class name and the scope resolution operator.

Variable Names
The symbolic constant names are clear as are the variable names adj_matrix (adjacency would be clearer), accumulated and adj_matrix_pointer, but the variable names a, b and temp are not clear and leave someone who has to read or maintain the code guessing.

Complexity
The function checkRecord() is too complex (does too much). After the if statement there should be a call to a function to execute the rest of the code, and that function might cal sub functions. Remember that it is much easier to write correct code when you limit what a function is responsible for.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

\$\endgroup\$
0

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.