Google | Phone | Print ranks of "A"

Anonymous User

684

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

Comments (2)