Mem
BAN USER- 11of 11 votes
AnswersGive a N*N matrix, print it out diagonally.
- Mem in United States
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
This is the question in the phone interview.
Please share more questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
Below is my code, I did some test.
-2 for block, -1 for gurad.
void dfs(vector<vector<int>>& matrix, int x, int y, int step){
if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()) return;
if (matrix[x][y] < 0) return;
if (matrix[x][y]>step + 1 || matrix[x][y] == 0)
matrix[x][y] = step + 1;
else return;
dfs(matrix, x + 1, y, step + 1);
dfs(matrix, x, y + 1, step + 1);
dfs(matrix, x - 1, y, step + 1);
dfs(matrix, x, y - 1, step + 1);
}
void RoomGuard(vector<vector<int>>&matrix){
for (int i = 0; i < matrix.size(); i++){
for (int j = 0; j < matrix[0].size(); j++){
if (matrix[i][j] == -1){
dfs(matrix, i-1, j, 0);
dfs(matrix, i, j-1, 0);
dfs(matrix, i +1, j, 0);
dfs(matrix, i , j+1, 0);
}
}
}
}
This is what I thought, start from every G, go 4 direction, if we find current cell is B or another G we return, or if it is a number that smaller than the step we have from Current G, we also return other wise add 1 to current step and put it into current cell. Do the same recursion for current cell until no move can made. Do the same process for all G.
- Mem March 10, 2014Here is the brute method:
int PopACard(vector<int>& cards){
if (cards.empty()) return -1;
int card = cards[0];
cards.erase(cards.begin());
if (!cards.empty()){
int top = cards[0];
cards.erase(cards.begin());
cards.push_back(top);
}
return card;
}
int iter(vector<int>& cards){
vector<int> cur = cards;
vector<int> next;
int step = 0;
bool same = false;
while (!same){
step++;
while (!cur.empty()){
next.push_back(PopACard(cur));
}
swap(cur, next);
reverse(cur.begin(), cur.end());
if (cards==cur)
same = true;
}
return step;
}
For <<, >>, it works like the following:
<<X
1.Reverse the whole string first.
2.Reverse the first X substr.
3.Reverse the last length-X substr.
For example:
Microsoft << 2:
1. tfosorciM
2. First 2 chars, ftosorciM
3. Rest substr, ftMicroso;
The >>X operation works the same way except the reverse the Length-X chars first and than X chars.
If you consider the duplicate chars in string, there is something missed here.
- Mem March 24, 2014