从一道面试题想到的

 

最近在 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

评论

35 楼 lyy3323 2009-12-29  

哎。。
不知道该说什么。
有人说有意义，有人说没意义。
如果是应聘，这样的代码可能在有效时间里无法实现。
但是对于学习JAVA的人来说，确实应该重视起来。
OO思想。
对于某些人的简单问题复杂化？？？真的不想说什么了！

34 楼 达达乐队 2009-12-29  

发个我的。思路就是，先初始化一个二维数组，然后通过行和列的index变化的往里添数据。

public class PrintSquare {
    private int sideLength = 1;
    private String[][] elementList;
    private static final String GO_RIGHT = "right";
    private static final String GO_DOWN = "down";
    private static final String GO_LEFT = "left";
    private static final String GO_UP = "up";

    PrintSquare() {
    }

    PrintSquare(int sideLength) {
        this.sideLength = sideLength;
        elementList = new String[sideLength][sideLength];
    }

    public void printSquareToConsole() {
        int num;
        int column = 0;
        int row = 0;
        String mark1 = GO_RIGHT;
        for (num = 0;num < sideLength * sideLength;num++) {
            elementList[row][column] = String.valueOf(num);
            if ((mark1) == GO_RIGHT) {
                column++;
                if (column == sideLength || elementList[row][column] != null) {
                    column--;
                    row++;
                    mark1 = GO_DOWN;
                }
            } else if ((mark1) == GO_DOWN) {
                row++;
                if (row == sideLength || elementList[row][column] != null) {
                    column--;
                    row--;
                    mark1 = GO_LEFT;
                }
            } else if ((mark1) == GO_LEFT) {
                column--;
                if (column == -1 || elementList[row][column] != null) {
                    column++;
                    row--;
                    mark1 = GO_UP;
                }
            } else if ((mark1) == GO_UP) {
                row--;
                if (row == -1 || elementList[row][column] != null) {
                    column++;
                    row++;
                    mark1 = GO_RIGHT;
                }
            }
        }

        for (int i = 0;i < this.sideLength;i++) {
            for (int j = 0;j < this.sideLength;j++) {
                System.out.print(elementList[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        PrintSquare ps = new PrintSquare(3);
        ps.printSquareToConsole();
    }
}

33 楼 zzy9zzy 2009-12-29  

学C语言的时候做过这个题，应该是谭浩强那本《C语言程序设计》里面的，代码比较简短

32 楼 抛出异常的爱 2009-12-29  

lwyx2000 写道

不想为了oo 而 oo

locked 写道

数组行列互换 + 递归

static void populateArray(int minValue, int rowNum, int colNum, int[][] toBePopulatedArray) {
		for (int colIdx = 0; colIdx < colNum; colIdx++) {
			toBePopulatedArray[0][colIdx] = minValue++;
		}
		
		//Recursive population
		if (rowNum > 1 || colNum > 1) {
			
			int newRowNum = colNum;
			int newcolNum = rowNum - 1;
			int[][] subArray = new int[newRowNum][newcolNum];
			
			populateArray(minValue, newRowNum, newcolNum, subArray);
			
			for (int colIdx = colNum - 1; colIdx > -1; colIdx--) {
				for (int rowIdx = 1; rowIdx < rowNum; rowIdx++) {
					toBePopulatedArray[rowIdx][colIdx] = subArray[newRowNum	- colIdx - 1][rowIdx - 1];
				}
			}
		}
	}

这个是我见过最OO的算法了
OO不是要多建类.
而是要有一个现实中可以对应的例子
以帮助理解.
这个算法就是对原题的描述.
削土豆可以用来形容这个算法
把已经削下去的部分就不放在数组中了.

31 楼 lwyx2000 2009-12-29  

不想为了oo 而 oo

30 楼 lydiap 2009-12-29  

贴贴我的实现，呵呵，虽然没有楼主的精辟，但是欢迎大家一块参考一下

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TestArray {
private int index=0;
private Integer[][] array;
public TestArray(){

}
public void doGenerateArray(int  ind){
this.index=ind;
int content=1;
array=new Integer[index][index];
if(index>=1){
for(int i=0;i<index;i++){
array[0][i]=content++;
}
int rowIndex=1;
int colIndex=index-1;
for(int i=index-1;i>0;i--){
for(int cir=0;cir<i;rowIndex++,cir++){
array[rowIndex][colIndex]=content++;
}
rowIndex--;
colIndex--;
for(int cir=0;cir<i;colIndex--,cir++){
array[rowIndex][colIndex]=content++;
}
rowIndex--;
colIndex++;
i--;
for(int cir=0;cir<i;rowIndex--,cir++){
array[rowIndex][colIndex]=content++;
}
rowIndex++;
colIndex++;
for(int cir=0;cir<i;colIndex++,cir++){
array[rowIndex][colIndex]=content++;
}
rowIndex++;
colIndex--;
}
}
}
public void doPrintArray(){
StringBuffer s;
Integer outputStr;
if(index>=1){
for(int i=0;i<index;i++){
for(int j=0;j<index;j++){
outputStr=array[i][j];
s=new StringBuffer(5);
s.append(outputStr);
if(outputStr>99&&outputStr<=999){
s.append(" ");
}
if(outputStr>9&&outputStr<=99){
s.append("  ");
}else if(outputStr<=9){
s.append("   ");
}
System.out.print(s.toString());
}
System.out.println("");
}
}else{
System.out.println("这是一个空数组!");
}
}

public boolean isNumeric(String str)
{
Pattern pattern=Pattern.compile("[0-9]*");
Matcher isNum=pattern.matcher(str);
if(!isNum.matches()){
return false;
}
return true;
}

public static void main(String[] args){
TestArray testArray=new TestArray();
String str=null;
InputStreamReader reader=new InputStreamReader(System.in);
BufferedReader bufferReader=new BufferedReader(reader);
System.out.println("请输入矩阵长度，例如5：");
try{
str=bufferReader.readLine();
if(testArray.isNumeric(str)){
testArray.doGenerateArray(Integer.parseInt(str));
testArray.doPrintArray();
}
}catch(Exception e){
e.printStackTrace();
}
}
}

29 楼 kingapex 2009-12-29  

<div class="quote_title">kingdu_12 写道</div>
<div class="quote_div">
<div class="quote_title">kingapex 写道</div>
<div class="quote_div">
<p>内螺旋矩阵算法分析<br><a href="http://shuishou119800.iteye.com/blog/549592" target="_blank"><br>http://shuishou119800.iteye.com/blog/549592</a></p>
<p> </p>
</div>
<p> </p>
<p>您访问的地址不存在，请确认您输入的URL地址</p>
</div>
<p> </p>
<p> </p>
<p>连接加错了，不好意思</p>
<p>已纠正</p>

28 楼 kingdu_12 2009-12-29  

<div class="quote_title">kingapex 写道</div>
<div class="quote_div">
<p>内螺旋矩阵算法分析<br><a href="%E5%86%85%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90%20%20http://shuishou119800.iteye.com/blog/549592" target="_blank"><br>http://shuishou119800.iteye.com/blog/549592</a></p>
<p> </p>
</div>
<p> </p>
<p>您访问的地址不存在，请确认您输入的URL地址</p>

27 楼 kingapex 2009-12-29  

<p>内螺旋矩阵算法分析<br><a href="http://shuishou119800.iteye.com/blog/549592" target="_blank"><br>http://shuishou119800.iteye.com/blog/549592</a></p>
<p> </p>

26 楼 biyao500 2009-12-29  

仍需努力，继续学习

25 楼 达达乐队 2009-12-29  

2wei shu zu

24 楼 patrickyao1988 2009-12-28  

支持楼主，学习了。看到有朋友说“简单问题复杂化”，我觉得这只是楼主做了个一个头脑风暴，拓宽了一下大家的思维。说道实际生产中的问题，我想自然会权衡，不会为了OO而OO

23 楼 chanball 2009-12-28  

楼主，顺便分享一下你的oo历程吧，让菜鸟学习学习！

22 楼 tntxia 2009-12-28  

楼主的思想很值得我们思考，不错

21 楼 yilong511 2009-12-28  

我要努力了，看了这道题目，我都无从下手。

20 楼 pipilu 2009-12-28  

luncaixia 写道

对oop的理解很深，对比起来我很汗颜，如果给我我就只会考虑算法的实现而没有考虑到面向对象的分析

一个对象就看出对oop理解很深了，那我只能说你理解的够浅的了!!-_-

19 楼 condeywadl 2009-12-28  

从OO角度来说 确实很值得学习

18 楼 luncaixia 2009-12-28  

对oop的理解很深，对比起来我很汗颜，如果给我我就只会考虑算法的实现而没有考虑到面向对象的分析

17 楼 mali0330 2009-12-28  

Eastsun 写道

简单问题复杂化？

恩，我赞同你的说法，简单问题复杂化。精辟的发表了对文章的看法

16 楼 flootball 2009-12-28  

这个是C语言的课后练习题。