Tuesday, May 14, 2013

Questions/Thoughts for interviews

shortest path in a 2d matrix
int shortestPath(vector<vector<bool> > matrix, int target_row, int target_col) {
    vector<vector<bool> > visit(matrix.size(),vector<bool>(matrix[0).size(),true);
    queue<pair(int,int)> que;
    queue<int> count;
    que.push(make_pair(0,0));
    count.push(0);
    
    while (!que.empty()) {
        int row = que.front().first;
        int col = que.front().second;
        que.pop();
        int curCount = count.front();
        count.pop();
        
        if (row == target_row && col == target_col) {
            return count;
        }
        if (row + 1 < matrix.size() && matrix[row + 1][col] && visit[row + 1][col]) {
            visit[row + 1][col] = false;
            que.push(make_pair(row + 1, col));
            count.push(curCount + 1);
        }
        if (row - 1 >= 0 && matrix[row - 1][col] && visit[row - 1][col]) {
            visit[row - 1][col] = false;
            que.push(make_pair(row - 1, col));
            count.push(curCount + 1);
        }
        if (col + 1 < matrix[0].size() && matrix[row][col + 1] && visit[row][col + 1]) {
            visit[row][col + 1] = false;
            que.push(make_pair(row, col + 1));
            count.push(curCount + 1);
        }
        if (col- 1 >= 0 && matrix[row][col - 1] && visit[row][col - 1]) {
            visit[row][col - 1] = false;
            que.push(make_pair(row, col - 1));
            count.push(curCount + 1);
        }
    }
    
    return -1;
}
Q: How to std::cout some sentences before main() function.
A : constructor of a global object will be called before main()
 class Object {
public:
  Object();
};

Object::Object() {
  cout << "my message\n";
}

// define a global object somewhere in .cc or .cxx or .cpp
Object obj;

int main()
{
}

No comments:

Post a Comment