【Google面经】Print ranks of "A"| Phone Interview Google 电面 开发岗

胖蛋 2020-5-25 615


The task was to print out the rank n of the character "A". The rank 0 of "A" is defined as "A" itself. The rank 1 is defined as follow

A

A A

AAA

A A

A A

At this point I was given another example of a rank but it took me a long time to infer the recursive relation from the examples. I think we agreed that the rank of n is formed by replacing every "A" in rank 1 with the whole rank n-1. Originally I was just given the examples and no explanation which made it difficult.

He asked me about O(n) and I said 15^n. Let me know if you know/think of a better approach.

This is my solution:

void printA(int n) {

if (n == 0) {

System.out.println(“A”);

return;

}

String p1 = “ A

A A

AAA

A A

A A”;

final int p1Width = 3, p1Height=5;

char[][] prev_ans = new char[p1Height][p1Width];

for (int i = 0, c=0; i < p1Height; ++i) {

for (int j = 0; j < p1Width; ++j) {

prev_ans[i][j] = p1.charAt(c++);

}

++c; // skip newline

}

char[][] p1Ans = prev_ans; // representation of p1 as matrix

for int (rank = 2; rank < n; ++rank) {

final int pnHeight = prev_ans.length * p1Height;

final int pnWidth = prev_ans[0].length * p1Width;

char[][] ans = new char[pnHeight][pnWidth];

for (int i = 0; i < p1Height; ++i) {

for (int j = 0; j < p1Width; ++j) {

for (int y = 0; y < prev_ans.length; ++y) {

for (int x = 0; x < prev_ans[0].length; ++x) {

ans[i*prev_ans.length + y][j*prev_ans[0].length + x] =

p1Ans[i][j] == ‘ ‘ ? ‘ ‘ : prev_ans[y][x];

}

}

}

}

prev_ans = ans;

}

for (int i = 0; i < prev_ans.length; ++i) {

for (int j = 0; j < prev_ans[0].length; ++j)

System.out.println(ans[i][j]);

System.out. println();

}

}

最后于 2020-6-1 被maomoke编辑 ,原因:
最新回复 (0)
返回