Image erosion

The image is represented in a two-dimension array. Every pixel of the image can only to assigned to either 0 or 1. If a pixel is 0, just leave it there. If a pixel is 1, we check its four neighbors. If all its four neighbors are 1, leave it there. Otherwise, erode it to 0.

Example:

0 1 1 1 0        0 0 1 0 0

1 1 1 0 0  --> 0 1 0 0 0 

0 1 0 1 1        0 0 0 0 0

Solution:

The difficult part is that every pixel can only be assigned to either 0 or 1. Otherwise, we can assign the 1s which need erosion first to some other value in the first scan. In the second scan, we can change this value to 0.

So here we use to arrays to store the row index and column index for the pixel need erosion.
The problem with this method is that we use to much memory to store the row index and column index. One way to optimize is that we only store the index for two rows. Because the erosion of row 0 will not affect the check for row 2.

bool check (int x, int y, int image[H][M]) {
    if (x>0 && image[x-1][y]==0)
        return true;
    if (x<H-1 && image[x+1][y]==0)
        return true;
    if (y>0 && image[x][y-1]==0)
        return true;
    if (y<W-1 && image[x][y+1]==0)
        return true;
    return false;
}

void erosion_part (vector<int> &row, vector<int> &col, int image[H][M]) {
    for (int i = 0; i < row.size(); i++)
        image[row[i]][col[i]] = 0;
}

void erosion (int image[H][W]) {
    vector<int> row, col;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (check(i, j, image)) {
                row.push_back(i);
                col.push_back(j);
            }
        }
    }
    erosion_part (row, col, image);
}

The problem with this method is that we use to much memory to store the row index and column index. One way to optimize is that we only store the index for two rows. Because the erosion of row 0 will not affect the check for row 2.

void erosion_part (vector<int> &row, vector<int> &col, int image[H][M], int end) {
    while (!row.empty()) {
        if (row.front() > end)
            break;
        image[row.front()][col.front()] = 0;
        row.pop_front();
        col.pop_front();
    }
}

void erosion (int image[H][W]) {
    list<int> row, col;
    int start = 0;
    for (int i = 0; i < H; i++) {
        if (i-start >= 2) {
            erosion_part (row, col, image, start);
            row.clear();
            col.clear();
            start++;
        }
        for (int j = 0; j < W; j++) {
            if (check(i, j, image)) {
                row.push_back(i);
                col.push_back(j);
            }
        }
    }
    erosion_part (row, col, H-1);
}

Longest common prefix

Given an array of strings, find the longest common prefix.
Example:
["abc", "a", "ab"] --> "a"
["abcd", "ab", "abc] --> "ab"

Solution:

string lcs (vector<string> array) {
    if (array.empty())
        return "";
    int pos = 0;
    string result = "";
    for (int i = 0; i < array[0].size(); i++) {
        char target = array[0][i];
        for (int j = 1; j < array.size(); j++) {
            if (i >= array[j].size() || array[j][i] != target)
            //a small trick here is that the length of the first string may be longer that some of other 
            //strings in the array. We need to test whether we have reached the end of other strings
                return result;
            else
                result += array[0][i];
        }
    }
    return result;
}

Build a tree from a xml file

Give a xml file like this,
<a>
   <b>Text<\b>
   <c>
      <d>Computer Science<\d>
      <d>Linear Algebra<\d>
   <\c>
   <e> Hello world <\e>
<\a>
Convert the file into a tree
                     <a>
                    /     \       \
                 <b>  <c>   <e>
                          /    \
                       <d>  <d>
Note the result don't have to be a binary tree. To functions are given.
1. getToke(): It returns two values Type and Text. Type includes BEGIN, TEXT, END. Text is the actual content of the token.
2. hasNext(): It will return true until the scan hit the end of the file.

Solution:
You have to first decide how to store the tree structure. Then another problem is how to differentiate between parent and children. We use a stack to store the current parent.

One thing to be careful about is that the xml file may be not in the correct format, i.e. <a>text<\c>. Return NULL in this case.

class Node {
public:
    string name;
    string content;
    vector<Node *> children;
    Node (string n, string c = "");
};

struct Token {
    Type type;
    String content;
};

Node * buildTree (){
    Token t = getToken();
    Node * root = new Node (root.content);
    stack<Node *> s;
    s.push (root);
    
    while (hasNext()) {
        t = getToken();
        if (t.type == BEGIN) {
            Node * tmp = new Node (t.content);
            s.top->children.push_back (tmp);
            s.push (tmp);
            continue;
        }
        if (t.type == TEXT) {
            tmp->content += t.content;
            continue;
        }
        if (t.type == END) {
            //Here you need to check whether the format of xml file is correct
            //If the type of token doesn't match, return NULL
            if (t.content == s.top())
                s.pop();
            else
                return NULL;
        }
    }
    //if the stack is not empty at the end, xml is not correct formatted, return NULL
    if (!s.empty())
        return NULL;
    else
        return root;
}