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


 

Uncategorized

Steps to answer

  1. Listen carefully.
    • Pay very close attention to any information.
  2. Draw an example.
    1. Specific. Sufficiently large. Not a special case.
  3. State a brute force
    1. The initial solution may be terrible. Explain the space/time complexity.
  4. Optimize
    1. Look for any unused information
    2. Use a fresh example
    3. Solve it incorrectly.
    4. Make time vs. space tradeoff
    5. Precompute
    6. Use a hash table
    7. Think about the best conceivable runtime
    8. Walk through with Bottleneck, Unnecessary work and Duplicated work
  5. Implement
  6. Test

 

Techniques

  1. BUD
  2. DIY
  3. Simplify and generalize
  4. Base case and build
  5. Data structure brainstorm
  6. BCR

 

Uncategorized

quicksort


void quicksort(char* str, int strlen) {
    if (strlen < 2) return;

    int p_idx = strlen / 2;
    char p = str[p_idx];
    int i = 0;
    int j = strlen - 1;

    while (i < j) {
        while (str[i] <= p && i < j) {
            p_idx = i;
            i++;
        }

        while (str[j] > p && i < j) {
            j--;
        }

        if (str[i] > p && str[j] <= p) {
            char ch = str[i];
            str[i] = str[j];
            str[j] = ch;
        }

    }

    quicksort(str, p_idx); // [0 ... (p_idx-1)]
    quicksort(&str[p_idx+1], strlen - p_idx - 1); //[(p_idx+1) ... (strlen-1)]
}