从一道面试题想到的

 

最近在 javaeye 上看到一道面试题。

要求打印出：

int i = 5;

  1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

int i = 6;

1   2  3  4  5 6

20 21 22 23 24 7

19 32 33 34 25 8

18 31 36 35 26 9

17 30 29 28 27 10

16 15 14 13 12 11

从发贴人的意图来看，这应该是一道 java 面试题（ http://www.iteye.com/topic/545378?page=1 ）；

看到很多热心的网友给出各种各样的答案，其中有 java 、 c 、 ruby 的。看到很多人这么有兴趣，我也给出了自己的答案。

不过我还想到另外两个问题：

1 、什么语言的题目？

2 、考官的目的？

如果是 c 语言，那么第二个问题一定是考查面试者的算法。如果这是一道 java 面试题，那就很难说了。第一，跟考官的水平和思维很大的关系；

第二，确实考查面试者的算法能力；

第三，考查的是面向对象分析和设计的能力。

本人更倾向于第三种，为什么呢？因为主要是 java 本身是面向对象的语言；其次算法已经很成熟了，平时工作可参考资料就可以实现。

很多网友给出的答案大多都是基于面向过程的算法实现。如果这些实现放在其他面向过程的语言中可能非常适合，如果在 java 中就不合适了。 java 是一个面向对象的语言，面向对象的出现无非是为了解决面向过程中出现的一些缺点：可维护性、可扩展性、代码可复用性差等。所以在 java 语言中应该是考查我们的面向对象分析和设计的能力，而不是算法实现 !

如果我是考官，那么让我看一个人的算法实现是很痛苦的事情。首先我没有那么多脑力计算出这个算法实现是否正确，其次让我把代码一行一行敲入计算机，那肯定没有这个功夫。

所以，大家以后碰到这类题目不要一上来就冥思苦想，然后写出让人难于看懂的算法实现。当然也有例外，那就是有些考官本身水平和思维有限，就是想看到你是否有代码。

3 年前我在面试中也碰到类似的题目，我的做法仅仅是说明为了实现这个功能我有那些类和关键方法。结果很不利，所以这个跟考官的水平和思维有很大的关系。

像这道面试题，我第一次看到就联想到这个是一个贪吃蛇游戏的简化版。如果联想不到呢，那就没辙啦。那也不会。

首先，我们从上面可以看出这是一个矩阵，它的高度和宽度是一样的，矩阵中有一些格子存放数字，这个格子就是一个点。

其次，这些数字的增长是有规律的，即顺时针而且不断内旋。

所以我们可以得到两个关键的类：点（ Point ）和方向（ Direction ）。既然存在方向这个概念，那么一定存在它的主体，比如车、火箭等，这里我们就用蛇（ Snake ）吧。

既然有了类，那么他们有那些属性呢？

想到点我们必定也能想到坐标中用 x 、 y 变量来表示。另外跟我们问题域有关的是在这个点上要记录一些信息。所以点有以下定义：

class Point {

private int x ;

private int y ;

private String val ;

}

方向这个概念比较抽象，在我们要研究的问题域中方向有向左、向右、向下、向上，而且有一定的范围。所以在给定范围的方向上，类 Direction 应该知道一个点是否出界，能够计算本方向上下一个点是什么。另外从题目上看，方向的变化规律是顺时针的，所以类 Direction 应该也能够知道它下一个方向是什么。所以方向有以下定义：

abstract class Direction {

int size ;

abstract public Point nextPoint(Point p); // 下个点

abstract public Direction next(Point p); // 下一个方向

abstract public boolean isOut(Point point); // 是否在本方向上出界

}

类 Direction 有四个子类，分别是右、左、下、上。这四个子类通过 next 方法返回另一个 Direction 构成类一个顺时针。

再来看看另外一个核心类 Snake ，它有那些属性呢？这个 Snake 会在一个方向和指定范围内进行游走，碰到壁什么的会掉头，不走已经走过的点。所以它能记住自己走过的点，并且在那里做些标记。最后还会打印出自己走过的路径。

public class Snake {

int size ;

Direction direct ;

Point next ;

Map<String, Point> map = new HashMap<String, Point>(); // 记录走过的点

public Snake( int size, Direction direct, Point point) {

this . size = size;

this . direct = direct;

next = point;

map .put(key( next ), next );

}

// 游走

public void run() {

for ( int i = 2; i < size * size + 1; i++) {

Point tempNext = direct .nextPoint( next );

// 如果在一个方向上出界或者已经走过的点要掉头

if ( direct .isOut(tempNext) || containsPoint(tempNext)) {

direct = direct .next(tempNext);

next = direct .nextPoint( next );

} else {

next = tempNext;

}

next .setVal(String. valueOf (i));

map .put(key( next ), next ); // 记录走过的点

}

}

// 打印走过的点

public void print() {

for ( int y = 1; y < size + 1; y++) {

for ( int x = 1; x < size + 1; x++) {

String temp = " "

+ (containsPoint( new Point(x, y)) ? map .get(key(x, y))

.getVal() : " " );

System. out .print(temp.substring(temp.length() - 5));

}

System. out .println( "" );

}

}

private String key(Point point) {

return key(point.getX(), point.getY());

}

private String key( int x, int y) {

String xVal = "00000" + x;

String yVal = "00000" + y;

return xVal.substring(xVal.length() - 3)

+ yVal.substring(yVal.length() - 3);

}

private boolean containsPoint(Point point) {

return map .containsKey(key(point));

}

public static void main(String[] args) {

// 指定范围、起始点、起始方向

Snake snake = new Snake(6, new Right(6), new Point(1, 1, "1" ));

snake.run();

snake.print();

}

}

到此，如果只给出 Snake 的属性和关键方法（ run,print ）的实现就可以表达你的设计意图了，其他的只不过是实现细节而已。

为什么这么实现，首先我觉得是自然，至于有什么好处当时还没有想过。看看这句就非常达意：

Snake snake = new Snake(6, new Right(6), new Point(1, 1, "1" ));

对蛇指定范围、起始方向、起始点才能让蛇开始游走。从这里我们也可以知道，对于蛇来讲只要你告诉它这几个输入，它就知道怎么做了，其他的你不用管。

这样设计有什么好处呢？从题目来看，用户只不过想在一个矩阵上打印一些数字序列。我们知道用户的想法最不可靠了。更多的想法如下：

1 、还可以从四个角开始顺时针内旋；

2 、分别可以从四个角逆时针内旋；

3 、还可以这样：

   1  2  3  4  5  6

12 11 10  9  8  7

13 14 15 16 17 18

24 23 22 21 20 19

25 26 27 28 29 30

36 35 34 33 32 31

4 、在单数的序列上用红色字体：

   1  2  3  4  5 6

20 21 22 23 24 7

19 32 33 34 25 8

18 31 36 35 26 9

17 30 29 28 27 10

16 15 14 13 12 11 ；

5 、 ...........

其中：

关于第一个想法，我们一开始就认为是顺时针内旋的，只要正确的初始化起始点和起始方向就可以轻松满足用户需求：

Snake snake = new Snake(6, new Down(6), new Point(6,1, "1" ));

Snake snake = new Snake(6, new Left(6), new Point(6,6, "1" ));

Snake snake = new Snake(6, new Up(6), new Point(1, 6, "1" ));

关于第二、三个想法，因为我们有 Direction 为抽象类，根据需要重写子类即可。

关于第四个想法，我想这个工作应该由蛇来做，你（蛇）到那个点上爱干嘛就干嘛，不关方向什么事。

所以好处是：

1 、第一、二、三个需求的变化是通过继承和扩展而不是修改来达到增加功能的目的，最大限度地保护 Snake 类的代码不受冲击。

2 、现在我们有很多各种各样“走法”的功能了，现在有点点变化就是想给数字加上颜色。我们不可能针对每种走法都进行修改吧。因为这个职责很自然地分配给了 Snake ，所以我们就只要修改 Snake 即可，同样其他代码得到保护。

下面是 Direction 子类实现示例：

class Right extends Direction {

public Right( int size) {

this . size = size;

}

public Direction next(Point point) {

return new Down( size );

}

public Point nextPoint(Point p) {

return new Point(p.getX() + 1, p.getY());

}

public boolean isOut(Point point) {

return point.getX() > size ;

}

}

class Down extends Direction {

public Down( int size) {

this . size = size;

}

public Direction next(Point point) {

return new Left( size );

}

public Point nextPoint(Point p) {

return new Point(p.getX(), p.getY() + 1);

}

public boolean isOut(Point point) {

return point.getY() > size ;

}

}

class Left extends Direction {

public Left( int size) {

this . size = size;

}

public Direction next(Point point) {

return new Up( size );

}

public Point nextPoint(Point p) {

return new Point(p.getX() - 1, p.getY());

}

public boolean </spa

评论

55 楼 sav2005 2010-10-08  

确实很强啊~~佩服

54 楼 bill600 2010-10-06  

看看同道的讨论 觉着很有意思 我也弄一个试试

思路很简单
把数据按照螺旋矩阵的路线装进数组
然后再打印出来

public class PrintSquare {
	private int[][] getArray(int n){
		if(n>0){
			int[][] array=new int[n][n];
			int x=0;
			int y=0;
			int xStart=0;
			int xEnd=n-1;
			int yStart=0;
			int yEnd=n-1;
			for(int i=1;i<=n*n;i++){
				array[y][x]=i;
				if(y==yStart&&x<xEnd){//横向前进
					x++;
					if(x==xEnd){
						yStart++;
					}
				}
				else if(y<yEnd&&x==xEnd){//纵向前进
					y++;
					if(y==yEnd){
						xEnd--;
					}
				}
				else if(y==yEnd&&x>xStart){//横向倒退
					x--;
					if(x==xStart){
						yEnd--;
					}
				}
				else if(y>yStart&&x==xStart){//纵向倒退
					y--;
					if(y==yStart){
						xStart++;
					}
				}
			}
			return array;
		}
		return null;
	}
	
	public void printSquare(int n){
		if(n>0){
			int[][] arr=getArray(n);
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					System.out.print(arr[i][j]+"\t");
				}
				System.out.println();
			}
		}
	}
	
	public static void main(String[] args) {
		PrintSquare test=new PrintSquare();
		test.printSquare(5);
		System.out.println();
		test.printSquare(6);
	}

}

53 楼 cat 2010-10-05  

我猜这种题目，不会是用这个来考OO的吧。而只是看能否用简洁的代码把这件事情写对写出来。主要是逻辑思维和心算。

52 楼 kukumayas 2010-10-05  

个人觉得,如果一样东西拿来当花瓶,可以考虑面向对象的思路,可以考虑包装,可以考虑美化.
但如果像数据库里的select,每天都要进行不计其数的操作,这些东西可以抛开了. 最高效,最有效的办法,才是上策. 而最高效,往往和巧妙的算法相关.
虽然这个题,偏第一种--花瓶,但我不支持楼主对算法的一些褒贬.
藐予小子,仅抒己见.

51 楼 yangyi 2009-12-30  

供参考

public class Calc {
	public static void main(String[] args){
		for(int i=1;i<8;i++){
			calc(i);
			System.out.println("---------------------------" +
					"---------------------------");
		}
	}
	
	public static void calc(int border){
		//setup border here
		int end = border;
		int start = 1;
		int seq = 1;
		int[] c;
		int[] n = {start, start};
		int[][] data = new int[end][end];
		data[0][0] = seq++;
		
		do{
			c = n;
			n = next(c, start, end);
			
			if(n[0] == start && n[1] == start){
				start++;
				end--;
				n[0] = start;
				n[1] = start;
				if(start == end){
					data[n[0]-1][n[1]-1] = seq++;
					break;
				}else if(start>end){
					break;
				}
			}
			
			data[n[0]-1][n[1]-1] = seq++;
		}while(true);
		
		for(int i=0;i<data.length;i++){
			for(int j=0;j<data[i].length;j++){
				System.out.print(data[j][i] + "\t");
			}
			System.out.print("\n");
		}
	}
	
	private static int[] next(int[] current, int start, int end){
		int x = current[0];
		int y = current[1];
		
		if(x == end && y != end){
			y++;
		}else if(x > start && y == end){
			x--;
		}else if(x == start && y > start){
			y--;
		}else if(x < end && y == start){
			x++;
		}else{
			x = start;
			y = end;
		}
		
		return new int[]{x, y};
	}
}

50 楼 ilove2009 2009-12-30  

第一次发帖，竟然这样！！！！！！！！！！！！！！！！！！天理啊。而且还让我做《JavaEye论坛使用规则 》题。

49 楼 ilove2009 2009-12-30  

4 小时前 JavaEye管理员 发给 我 的消息
标题: 您的帖子被JavaEye会员集体投票评为新手帖
正文:
您的帖子：从一道面试题想到的 被JavaEye用户投票评为新手帖帖，积分-10分。
发贴前请仔细阅读 JavaEye版规和提问的智慧，如有异议，可以到JavaEye站务圈子申诉。

如果您只是急切的想找人解答你的问题，而不是为了讨论技术的话，请移步到JavaEye问答频道，在问答频道您可以用积分悬赏解答，并且不受论坛发贴规则的制约，谢谢！

这是系统的自动通知，无需回复

48 楼 cjx186 2009-12-30  

楼主很强悍。思考很周道。呵呵。楼上很多说简单的东西复杂化了，问题并不是简单的东西复杂化，要考虑周道不简单啊。现在开发中改得多，很多就是程序太懒太简单自认为就可以了。太少考虑设计了。

47 楼 ora92 2009-12-29  

运行不了，有运行起来的吗

46 楼 jiangduxi 2009-12-29  

楼主的思考，真的很有道理，并且思路很清晰！

45 楼 JArcher 2009-12-29  

我觉得这个贴该发在jdon上，呵呵。。

44 楼 michaellou 2009-12-29  

面向对象的思维呀，哈哈！

43 楼 andysxf0 2009-12-29  

package first;


/**
* Created on 2009-12-29
* <p>Description: [描述该类概要功能介绍]</p>
*/
public class Game
{
private static final String BLANK = " ";

public static void main(String[] args)
{
// 打印的结果可以理解为一个正方形，参数相当于正方形的边长
int[][] target = createArray(6);

printArray(target);
}
/**
* <p>Discription:[参数相当于正方形的边长]</p>
* @param iLength
* @return
*/
private static int[][] createArray(int iLength)
{
int[][] target = new int[iLength][iLength];
int iCircle = (iLength % 2 == 0) ? iLength/2 : iLength/2 + 1;
int a1 = 1;
for (int k = 0; k < iCircle; k++)
{
int a2 = a1 + iLength-1;
int a3 = a2 + iLength-1;
int a4 = a3 + iLength-1;
int a4End = a4 + iLength-2;

int iColumn = k + iLength;
// 向右移动
for (int m = k, n = k; n < iColumn; n++)
{
if (n == k) {
target[m][n] = a1;
} else {
target[m][n] = target[m][n - 1] + 1;
}
}
// 向下移动
for (int m = k, n = iColumn -1; m < iColumn; m++)
{
if (m == k) {
target[m][n] = a2;
} else {
target[m][n] = target[m - 1][n] + 1;
}
}
// 向左移动
for (int m = iColumn -1, n = iColumn -1; n >= k; n--)
{
if (n == iColumn - 1) {
target[m][n] = a3;
} else {
target[m][n] = target[m][n + 1] + 1;
}
}
// 向上移动，移动到起始位置的下方的点
for (int m = iColumn -1, n = k; m > k; m--)
{
if (m == iColumn - 1) {
target[m][n] = a4;
} else {
target[m][n] = target[m + 1][n] + 1;
}
}
a1 = a4End + 1;
iLength -= 2;
}
return target;
}
private static void printArray(int[][] target)
{
int iLength = target.length;
for (int i = 0; i < iLength; i++)
{
for (int j = 0; j < target[i].length; j++)
{
String str = String.valueOf(target[i][j]);
if (str.length() == 1) str = BLANK + str;
System.out.print(str + BLANK);
if ((j+1)%iLength == 0) System.out.println();
}
}
}
}

42 楼 wuhoufeng 2009-12-29  

金蝶确实考很多算法，我栽了

41 楼 akunspy 2009-12-29  

berlou 写道

akunspy 写道

总有蠢材要把简单问题复杂化,这样的程序员我碰到直接就不要
考设计会出这样的题?真不知道是谁脑子坏了

简单问题复杂化确实是不好的习惯， 不过也因情况而异。
这种问题确实需要做些设计的， 也许客户需求变化了呢？不是螺旋矩阵而是贪吃蛇呢？
如果是一个网络游戏， 物体行走路线算法呢？Point, Direction这种封装还是有必要的。
当然这种问题在面试时回答要看对方是什么样的公司， 考察什么内容， 如果C程序员职位， 做底层开发的， 自然不用这么封装， 如果是Java程序员， 做游戏或者产品的， 不封装一下才是找抽呢。

    说得好,需求变化了怎么办.需求变成不是螺旋矩阵也不是贪吃蛇,而是三维空间多方向同时的旋转,且几个旋转方向互相影响,我倒想看看这段所谓OO的代码要改成啥子样子.
    你举的网络游戏例子更不合适,我就是做网络游戏服务端的,那种效率优先的地方最直接的行走路线算法都嫌慢(防外挂,路点必须都做检查),要是到处都"封装"一下,多"完美"啊,只是一台服务器只上得到100人,这可不怪我了.
    OO不是银弹更不是一切,KISS才是程序员应该树立的正确的世界观.感觉JAVA程序员很多走进了OO的怪圈.为了OO而OO,真正重要的是什么?是设计,是了解你要做的东西的业务逻辑而做出合理的能适应修改的设计.
    别天真的以为封了几个类就灵活了

40 楼 berlou 2009-12-29  

akunspy 写道

总有蠢材要把简单问题复杂化,这样的程序员我碰到直接就不要
考设计会出这样的题?真不知道是谁脑子坏了

简单问题复杂化确实是不好的习惯， 不过也因情况而异。
这种问题确实需要做些设计的， 也许客户需求变化了呢？不是螺旋矩阵而是贪吃蛇呢？
如果是一个网络游戏， 物体行走路线算法呢？Point, Direction这种封装还是有必要的。
当然这种问题在面试时回答要看对方是什么样的公司， 考察什么内容， 如果C程序员职位， 做底层开发的， 自然不用这么封装， 如果是Java程序员， 做游戏或者产品的， 不封装一下才是找抽呢。

39 楼 libo_591 2009-12-29  

看到楼主对问题的分析，让我对JAVA的理解和认识，有了眼前一亮的感觉。感谢楼主，订阅了。。

38 楼 wander312 2009-12-29  

OO很到位, 学习了!

37 楼 kyo19 2009-12-29  

难道用Java做这个题目就是考你的OOP？ 不一定吧，写程序最重要是的逻辑思维能力，如果什么都像你这样用OOP那么，如果让你写一个1—1=0 是不是要用到OOP来个封装，继承，多态呢？

不过你也提供了对这人问题的另一种解法，也不错，不过这样很容易让面试的人认为你过于学术派。有点生搬硬套，过份OOP的样子

36 楼 sky.zha 2009-12-29  

人的思维=效率低+复杂