每周一题 -- Nov 17 (发表于17年前)

杜鲁门 · 时间: *2008-11-17 15:46*

一道面试题，题目有点长

===[ Introduction ]============================================================

The enclosed code is some basic code for managing path-node and Power-Up
objects in a 3D Map. A very simple power-up heirarchy is in place but is
far from complete.

As I'm sure you know, path-nodes are used by AI agents to navigate through a
map. A typical "real" map would contain upwards of a thousand PathNodes, but
we've included a simple graph of 8 nodes. A pictoral representation of the
graph is shown in Graph.png and the data has been entered in Main.cpp.

The test has been broken up into three small parts. The entire thing should
take no-more than a few hours (an evening, tops), but take your time. Please
keep a rough idea of how long you spent at it, though -- if you spent more
time and did cooler stuff, that's all good.

===[ Part 1 ]==================================================================

Find as many bugs with the existing code as you can. There are several subtle
but common errors throughout the code. It compiles, and runs, but would not
stand up to production use.

For bonus marks, add a few statements here-and-there to make the code more
quick to detect errors.

You can impose any reasonable restrictions on how the functions can be used
and abused. Halting the program on error illegal input is acceptable in most
cases, but use your judgement for deciding when it isn't appropriate.

===[ Part 2 ]==================================================================

Implement the "findPowerUp" function sketched out in Main.cpp. It is to find a
path through the graph of PathNodes to the nearest PowerUp of the given mType.
Return NULL for no-path, or return an allocated array containing the path as
shown in the function skeleton.

Please briefly describe the algorithm you chose and why you chose it in a
comment block at the top of the function.

===[ Part 3 ]==================================================================

Fill in the Armor and Weapon classes. Add members and methods that you think
would be useful for these kinds of objects. What you add is totally up to you;
it's more meant to show your personal coding style and how you think about
what kind of functionality you'd want to add to the game.

This part is very subjective, so don't worry about it -- there is no wrong
answer.

Vertex.h

PHP源代码:



#ifndef VERTEX_H
#define VERTEX_H

struct Vertex
{
    Vertex()
    {
    }

    Vertex(float iX, float iY, float iZ) :
        x(iX),
        y(iY),
        z(iZ)
    {
    }

    float x, y, z;
};

#endif // VERTEX_H

PowerUp.h

PHP源代码:



#ifndef POWER_UP_H
#define POWER_UP_H

#include "Vertex.h"
#include <string.h>

class PowerUp
{
public:
    PowerUp(const char* name, Vertex position)
    {
        mPosition = position;
        mName = new char [strlen(name)];
        strcpy(mName, name);
    }

    ~PowerUp()
    {
        delete mName;
    }

    enum PowerUpType
    {
        WEAPON,
        ARMOUR, 
        HEALTH
    };

    PowerUpType getPowerUpType() const
    {
        return(mType);
    };

    const Vertex& GetPosition() const
    {
        return(mPosition);
    }

protected:
    Vertex      mPosition;
    PowerUpType mType;
    char*       mName;
};

#endif // POWER_UP_H

PathNode.h

PHP源代码:

Weapon.h

PHP源代码:



#ifndef WEAPON_H
#define WEAPON_H

#include "PowerUp.h"

class Weapon : public PowerUp
{
public:
    Weapon(const char* name, Vertex position) :
        PowerUp(name, position)
    {
        mType = WEAPON;
    }
};

#endif // WEAPON_H

Health.h

PHP源代码:



#ifndef HEALTH_H
#define HEALTH_H

#include "PowerUp.h"

class Health : public PowerUp
{
public:
    Health(const char* name, Vertex position) :
        PowerUp(name, position)
    {
        mType = HEALTH;
    }
    
protected:
    float healing;
};

#endif // HEALTH_H

Armor.h

PHP源代码:



#ifndef ARMOUR_H
#define ARMOUR_H

#include "PowerUp.h"

#include <stddef.h>
#include <string.h>

class Armour : public PowerUp
{
public:
    Armour(const char* name, const Vertex& position) :
        PowerUp(name, position)
    {
        mType = ARMOUR;
        mClanTag = NULL;
    }

    ~Armour()
    {
        delete mClanTag;
    }

    const char* getClanTag() const
    {
        return(mClanTag);
    }

    void setClanTag(char* n)
    {
        delete mClanTag;
        mClanTag = new char[strlen(n)];
        strcpy(mClanTag, n);
    }

protected:
    char* mClanTag;
};

#endif // ARMOUR_H

Main.cpp

PHP源代码:

webdriver · 时间: *2008-11-17 15:52*

像是某家游戏公司的面试题

webdriver · 时间: *2008-11-17 16:16*

而且比较复杂，如果不让上机操作的话，要在半个小时内搞清楚关系，算是高手了。

杜鲁门 · 时间: *2008-11-17 16:20*

课外作业几个小时之内完成都可以答卷应是可编译运行的

7thGuest · 时间: *2008-11-17 16:23*

they allow you to use a compiler in interview? they are quite kind

webdriver · 时间: *2008-11-17 16:28*

杜鲁门写道:

课外作业几个小时之内完成都可以答卷应是可编译运行的

这样简单多了

1）主要问题是constructor，destructor的问题，尤其是stl vector，用push back的对象一定要实现copy constructor
2）头文件包含问题，如果没有采用pre-compile header选项，其中几个文件无法编译
3）直接引用下标而不做下标检查，太容易出错了（core dump）
4）有些变量未初始化就用，dotNet检查严格多了
5）数组越界问题

SARS · 时间: *2008-11-17 16:30*

看题都要看半小时

先挑几个显而易见的错误：

1、所有 new char [strlen(name)]语句的中括号内应该再+1

2、main中一开始在堆上创建的那一大堆对象，后来又放到两个vector中去了。但退出的时候没见着删除（或许是俺老眼昏花看漏了？

）

3、PowerUp::~PowerUp()应该是虚函数，否则即便改正了错误2，它的那些乱七八糟的子类对象也无法删除（搞不好还会crash）

4、delete字符串指针之前都检查一下空指针系不系更安全一些？

有空再继续找......

7thGuest · 时间: *2008-11-17 16:30*

here is what I come up with with first sight

1. strlen doesn't include the tail 0. +1 please
2. anytime use new[], use delete[]
3. destructor of PathNode is not implemented, I don't know how it can compile
4. pathnode and powerup and its inheritance, non of them implement copy construct, when they are put into stl container, memory leak/stomping everywhere.
5. one of the Vector construtor doesn't initialize its member, looking for trouble of determinism
6. if you want, you can always asset(name), but not a big deal
7. not quite sure if erase(vector.end()) is legal or not, personally, I am not a big fan of stl.

7thGuest · 时间: *2008-11-17 16:31*

delete null is 100% legal.

no need to check

7thGuest · 时间: *2008-11-17 16:42*

SARS 写道:

3、PowerUp::~PowerUp()应该是虚函数，否则即便改正了错误2，它的那些乱七八糟的子类对象也无法删除（搞不好还会crash）

right, forgot about this, together with the other 2 member functions