Bloomberg Interview Questions/Q 1

From Software Engineers Wiki
Jump to: navigation, search

Image an airport with the control tower having a constantly rotating radar scanning for airplanes. The radar's coordinates in the 2-d plane are (0,0). The radar has an API: void scan(const Plane &P) that is called periodically whenever the radar detects a plane. You can imagine that the Plane structure has x,y coordinates for that plane. You should fill in the function Scan, such that at any given time you are able to return the 10 closest planes to the tower (0,0).

Answer

The key is to use max heap to maintain closest 10 planes. Every time it detects a plane, calculate how far the plane is. Put first 10 planes into the max heap. After that, if the distance of new plane is shorter than the farthest plane in the max heap (max heap keep the largest one at the top), pop the top plane out of the max heap, then push the new plane into the max heap.

Only drawback of this mechanism is, since the max heap keeps only the farthest in the top, and it is not easy to find what is closest one.

/* Coordination */
class CCoord {
private:
        int m_x, m_y;
public:
        CCoord() {}
        CCoord(int x, int y) : m_x { x }, m_y { y } {}
        CCoord &operator = (CCoord &opnd) { m_x = opnd.m_x; m_y = opnd.m_y; return *this; }

        unsigned int getDistanceSquared(void) { return m_x * m_x + m_y * m_y; }
        void move(int x, int y) { m_x += x; m_y += y; }
        int getX(void) { return m_x; }
        int getY(void) { return m_y; }
};

/* Plane */
class CPlane {
public:
        std::string m_name;
        CCoord m_cur;
        int m_deltaX, m_deltaY;
public:
        CPlane(const char *name, int curX, int curY, int deltaX, int deltaY) :
                m_name { name }, m_cur { curX, curY }, m_deltaX { deltaX }, m_deltaY { deltaY } {}

        unsigned int getDistanceSquared(void) { return m_cur.getDistanceSquared(); }
        void moveToNextPos(void) { m_cur.move(m_deltaX, m_deltaY); }
};

/* Airport Control Tower */
class CTower {
private:
        std::mutex m_mutex;
        /* number of nearest airplanes that it will keep track of */
        int m_nearCount;
        /* list of all planes */
        std::list<CPlane *> m_planes;
        /* max heap */
        std::priority_queue<CPlane *, std::vector<CPlane *>, CPlaneCompare> m_maxHeap;
public:
        CTower(int nearCount) : m_nearCount { nearCount } {}
        ~CTower() { for (auto ir : m_planes) delete ir; }

        void registerPlane(CPlane *plane) { m_planes.push_back(plane); };
        void scan(void);
        void movePlanes(void);
        void printAll(void);
        void printNear(void);
};

void CTower::scan(void)
{
        int count;
        unsigned int distance, maxDistance;

        /* remove all */
        while (!m_maxHeap.empty())
                m_maxHeap.pop();

        /* scan, and rebuild heap */
        count = 0;
        maxDistance = 0;

        for (auto x : m_planes) {
                distance = x->getDistanceSquared();
                if (count < m_nearCount) {
                        if (maxDistance < distance)
                                maxDistance = distance;
                        m_maxHeap.push(x);
                        ++count;
                } else {
                        if (distance < maxDistance) {
                                m_maxHeap.pop();
                                m_maxHeap.push(x);
                        }
                }
        }
}

void CTower::movePlanes(void)
{
        for (auto ir : m_planes)
                ir->moveToNextPos();
}

void CTower::printAll(void)
{
        for (auto ir : m_planes)
                std::cout << ir->m_name << " : " << ir->getDistanceSquared() << std::endl;
}

void CTower::printNear(void)
{
        CPlane *plane;

        while (!m_maxHeap.empty()) {
                plane = m_maxHeap.top();
                m_maxHeap.pop();
                std::cout << plane->m_name << " : " << plane->getDistanceSquared() << std::endl;
        }
}

Test program:

int main(void)
{
        int i;
        char name[16];
        CPlane *plane;
        CTower tower(10);

        for (i = 0; i < 100; ++i) {
                sprintf(name, "Plane%3d", i);
                plane = new CPlane(name,
                        (random() & 0xff) - 0x80,
                        (random() & 0xff) - 0x80,
                        (random() & 0x07) - 0x04,
                        (random() & 0x07) - 0x04);
                tower.registerPlane(plane);
        }

        for (i = 0; i < 20; ++i) {
                std::cout << "Iteration " << i << std::endl;
                tower.scan();
                tower.printNear();
                tower.movePlanes();
        }

        return 0;
}

Test result:

Iteration 0
Plane 99 : 6425
Plane 82 : 2929
Plane 98 : 2788
Plane 53 : 2650
Plane 30 : 2225
Plane 92 : 2041
Plane 56 : 1972
Plane  6 : 1544
Plane 72 : 1241
Plane 90 : 488
Iteration 1
Plane 99 : 6109
Plane 82 : 2977
Plane 98 : 2756
Plane 53 : 2637
Plane 30 : 2525
Plane 92 : 2029
Plane 56 : 1706
Plane  6 : 1585
Plane 72 : 1469
Plane 90 : 484
Iteration 2
Plane 99 : 5801
Plane 13 : 2845
Plane 30 : 2845
Plane 98 : 2740
Plane 53 : 2626
Plane 92 : 2025
Plane 72 : 1717
Plane  6 : 1636
Plane 56 : 1460
Plane 90 : 488
Iteration 3
Plane 99 : 5501
Plane 98 : 2740
Plane 68 : 2642
Plane 53 : 2617
Plane 13 : 2578
Plane 92 : 2029
Plane 72 : 1985
Plane  6 : 1697
Plane 56 : 1234
Plane 90 : 500
Iteration 4
Plane 99 : 5209
Plane 53 : 2610
Plane  4 : 2516
Plane 68 : 2441
Plane 13 : 2329
Plane 72 : 2273
Plane 92 : 2041
Plane  6 : 1768
Plane 56 : 1028
Plane 90 : 520
Iteration 5
Plane 99 : 4925
Plane 53 : 2605
Plane 72 : 2581
Plane 68 : 2250
Plane  4 : 2132
Plane 13 : 2098
Plane 92 : 2061
Plane  6 : 1849
Plane 56 : 842
Plane 90 : 548
Iteration 6
Plane 99 : 4649
Plane 88 : 2690
Plane 53 : 2602
Plane 92 : 2089
Plane 68 : 2069
Plane  6 : 1940
Plane 13 : 1885
Plane  4 : 1780
Plane 56 : 676
Plane 90 : 584
Iteration 7
Plane 99 : 4381
Plane 53 : 2601
Plane 88 : 2581
Plane 92 : 2125
Plane  6 : 2041
Plane 68 : 1898
Plane 13 : 1690
Plane  4 : 1460
Plane 90 : 628
Plane 56 : 530
Iteration 8
Plane 99 : 4121
Plane 53 : 2602
Plane 88 : 2482
Plane 92 : 2169
Plane  6 : 2152
Plane 68 : 1737
Plane 13 : 1513
Plane  4 : 1172
Plane 90 : 680
Plane 56 : 404
Iteration 9
Plane 99 : 3869
Plane 53 : 2605
Plane 88 : 2393
Plane  6 : 2273
Plane 92 : 2221
Plane 68 : 1586
Plane 13 : 1354
Plane  4 : 916
Plane 90 : 740
Plane 56 : 298
Iteration 10
Plane 99 : 3625
Plane  8 : 2560
Plane  6 : 2404
Plane 88 : 2314
Plane 92 : 2281
Plane 68 : 1445
Plane 13 : 1213
Plane 90 : 808
Plane  4 : 692
Plane 56 : 212
Iteration 11
Plane 99 : 3389
Plane  6 : 2545
Plane 92 : 2349
Plane  8 : 2250
Plane 88 : 2245
Plane 68 : 1314
Plane 13 : 1090
Plane 90 : 884
Plane  4 : 500
Plane 56 : 146
Iteration 12
Plane 99 : 3161
Plane 53 : 2626
Plane 92 : 2425
Plane 88 : 2186
Plane  8 : 1960
Plane 68 : 1193
Plane 13 : 985
Plane 90 : 968
Plane  4 : 340
Plane 56 : 100
Iteration 13
Plane 99 : 2941
Plane 28 : 2626
Plane 92 : 2509
Plane 88 : 2137
Plane  8 : 1690
Plane 68 : 1082
Plane 90 : 1060
Plane 13 : 898
Plane  4 : 212
Plane 56 : 74
Iteration 14
Plane 99 : 2729
Plane 92 : 2601
Plane 28 : 2405
Plane 88 : 2098
Plane  8 : 1440
Plane 90 : 1160
Plane 68 : 981
Plane 13 : 829
Plane  4 : 116
Plane 56 : 68
Iteration 15
Plane 53 : 2665
Plane 99 : 2525
Plane 28 : 2210
Plane 88 : 2069
Plane 90 : 1268
Plane  8 : 1210
Plane 68 : 890
Plane 13 : 778
Plane 56 : 82
Plane  4 : 52
Iteration 16
Plane 53 : 2682
Plane 99 : 2329
Plane 88 : 2050
Plane 28 : 2041
Plane 90 : 1384
Plane  8 : 1000
Plane 68 : 809
Plane 13 : 745
Plane 56 : 116
Plane  4 : 20
Iteration 17
Plane 53 : 2701
Plane 99 : 2141
Plane 88 : 2041
Plane 28 : 1898
Plane 90 : 1508
Plane  8 : 810
Plane 68 : 738
Plane 13 : 730
Plane 56 : 170
Plane  4 : 20
Iteration 18
Plane 53 : 2722
Plane 88 : 2042
Plane 99 : 1961
Plane 28 : 1781
Plane 90 : 1640
Plane 13 : 733
Plane 68 : 677
Plane  8 : 640
Plane 56 : 244
Plane  4 : 52
Iteration 19
Plane 53 : 2745
Plane 88 : 2053
Plane 99 : 1789
Plane 90 : 1780
Plane 28 : 1690
Plane 13 : 754
Plane 68 : 626
Plane  8 : 490
Plane 56 : 338
Plane  4 : 116

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox