Question

Queue with two stacks

Implement queue with two stacks

Image uploaded from iOS (7).jpg


template<class T> 
class StackNode {
public:
    StackNode(T initVal) {
        value = initVal;
        next = NULL;
    }

    T value;
    StackNode* next;
};

template<class T>
class Stack {
public:
    Stack() { top = NULL; }
    ~Stack() {
        StackNode<T> *node = top;
        while (node) {
            StackNode<T> *next = node->next;
            delete node;
            node = next;
        }

    }
    bool isEmpty() { return (top == NULL); }
    void push(T value) {
        StackNode<T> *node = new StackNode<T>(value);
        
        if (top) {
            node->next = top;
        }
        top = node;
    }
    T pop() {
        assert(top);
        
        T val = top->value;
        StackNode<T> *next = top->next;
        delete top;
        top = next;
        return val;
    }
    StackNode<T> *top;
};

template<class T>
class Queue {
public:
    Queue() {}
    ~Queue() {}

    void add(T value) {
        inStack.push(value);
    }

    T remove() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
        
    }

    Stack<T> inStack;
    Stack<T> outStack;
};

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));
    }
}