Question

Rotate matrix

Rotate N x N matrix in 90 degrees, in place.

Image uploaded from iOS (3).jpg


 void rotate90(int** Mat, int N) {
    bool* visited = new bool[N*N];
    memset(visited, 0, sizeof(bool) * N * N);
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            //Mat[row][col]         -> Mat[col][N-1-row]
            //Mat[col][N-1-row]     -> Mat[N-1-row][N-1-col]
            //Mat[N-1-row][N-1-col] -> Mat[N-1-col][row]
            //Mat[N-1-col][row]     -> Mat[row][col]
            if (visited[row*N + col]) continue;

            int temp = Mat[row][col];
            Mat[row][col] = Mat[N - 1 - col][row];
            Mat[N - 1 - col][row] = Mat[N - 1 - row][N - 1 - col];
            Mat[N - 1 - row][N - 1 - col] = Mat[col][N - 1 - row];
            Mat[col][N - 1 - row] = temp;
            visited[row*N + col] = true;
            visited[(N - 1 - col)*N +row] = true;
            visited[(N - 1 - row)*N + N - 1 - col] = true;
            visited[(col)*N + N - 1 - row] = true;
        }
    }
}

Question

String compression

Using the counts of repeated characters

aabcccccaaa -> a2b1c5a3

Image uploaded from iOS (2).jpg


char* compression(const char* input, char *output) {
    int len = strlen(input);
    char prev = '\0';
    int read = 0;
    int write = 0;
    int count = 0;
    while (read < len && write < (len - 1)) {
         if (input[read] != prev) {
             if (count > 0) {
                output[write++] = '0' + count;
            }
            output[write++] = input[read];
            prev = input[read];
            count = 1;
        }
        else {
            count++;
        }
        read++;
    }

    if (write < (len - 1)) {
        output[write++] = '0' + count;
        output[write] = 0;
    }
    else {
        memcpy(output, input, strlen(input) + 1);
    }
    return output;
}

Question

One edit away

Check if two strings are one edit away

pale, ple -> true
pale, bake -> false

image-uploaded-from-ios-1

Can be solved by induction and optimized by dynamic programming


int HowManyEdits_recursion(const char* A, const char* B, int i, int j) {
    if (i < 0 || j < 0) return 0;

    if (A[i] == B[j]) {
        return HowManyEdits_recursion(A, B, i - 1, j - 1);
    }
    else {
        return MIN3(HowManyEdits_recursion(A, B, i, j - 1), HowManyEdits_recursion(A, B, i - 1, j), HowManyEdits_recursion(A, B, i - 1, j - 1)) + 1;
    }
}

class SUBSOL {
public:
    SUBSOL(int a_len, int b_len) {
        this->a_len = a_len;
        this->b_len = b_len;
        solutions = new int[a_len * b_len];
        memset(solutions, 0, sizeof(int) * a_len * b_len);

    }
    virtual ~SUBSOL() {
        delete[] solutions;
    }

    int getVal(int i, int j) {
        if (i < 0 || j < 0) return 0;
        return solutions[i * b_len + j];
    }
    void setVal(int i, int j, int val) {
        solutions[i * b_len + j] = val;
    }

private:
    int* solutions;
    int a_len;
    int b_len;
};
int HowManyEdits(const char* A, const char* B, int A_len, int B_len) {
    SUBSOL sub(A_len, B_len);

    for (int i = 0; i < A_len; i++) {
        for (int j = 0; j < B_len; j++) {
            if (A[i] == B[j]) {
                sub.setVal(i, j, sub.getVal(i - 1, j - 1));
            }
            else {
                sub.setVal(i, j, MIN3(sub.getVal(i, j - 1), sub.getVal(i - 1, j), sub.getVal(i - 1, j - 1)) + 1);
            }
        }
    }

    return sub.getVal(A_len - 1, B_len - 1);
}

int HowManyEdits(const char* A, const char* B) {
    bool recursion = false;
    if (recursion) {
        return HowManyEdits_recursion(A, B, strlen(A) - 1, strlen(B) - 1);
    }
    else {
        return HowManyEdits(A, B, strlen(A), strlen(B));
    }
}
Question

URLify

Replace all spaces with %20.


 int getNumSpaces(char* string, int length) {
    int n = 0;
    for (int i = 0; i < length; i++) {
        if (string[i] == ' ') {
            n++;
        }
    }
    return n;
}

void URLify(char* string, int actual_length) {
    const int num_spaces = getNumSpaces(string, actual_length);
    const int additional_spaces = num_spaces * 2;
    int readidx = actual_length - 1; // backward
    int writeidx = readidx + additional_spaces;
    while (readidx >= 0)
    {
        assert(writeidx >= readidx);
        if (string[readidx] != ' ') {
            string[writeidx--] = string[readidx];
        }
        else if (string[readidx] == ' ') {
            string[writeidx--] = '0';
            string[writeidx--] = '2';
            string[writeidx--] = '%';
        }

        readidx--;
    }
}