Google Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

Why BFS won't work on this?

- Vivek August 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the role of sensors? Player can only go through them, or he must avoid them?

- emb June 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have to avoid sensors..

- ankit3600 June 14, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take all sensor and create interval along the x axis and find any gaps in between to passthrough

- Anonymous June 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

remember that u can move in any direction. ur logic will not work

- ankit3600 June 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done using KD tree. Consider the path we start from a,b is the root. Then as we have to avoid the sensor coordinate as the obstacle so we have to delete the coordinate(m,n) and search for coordinate(c,d).

- Aditya June 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ankit3600 How did you manage to leave a comment to an answer?Tell us your secret, or at least browser. I thought this feature was broken for like 2 months.

- emb June 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It working now. :)
I m using safari on mac

- ankit3600 June 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve it recursively. We always want to go a straight line parallel to x axis. This basic principle. You if collision ( start, end, array of sensors) -end is straight line to the end of rect return no collision, you return c-a.
If it returnes a P that is center of a circle which collide, you call method byPass(start, P). By pass is a straight line that reaches top or bottom of circle. If collision happen during that process you by pass. If you successfully bypass P, you solve problem for point P now instead of start.

- Ahmad June 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Where is my comment

- Ahmad June 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So there is 2 way I can think of it

1> Try a version on flood fill algorithm where you have to put sensor radius as a barrier and avoid it.
2> Using graph theory. Algo may be complicated so here it goes.
For each sensor (interms of it radius), try to find the connected components. Between each two component, find the min distance between them and collect the co-ordinates in array. Along with this, you have to add, the maximum x deflection in order to avoid sensor range area. This will be easy as you know the the component, just find the max-x in that component and add that to the add co-ordinate.Now, this array will serve as a node of your new graph. Run modified dijkstra on it to find the min distance traversed from the starting point y of robot to end y.

- hprem991 June 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about a wall follower maze solver that always has a wall to it's right? Below is a simple implementation. O(x*y*N) due the lame collision detection. But it finds it's way through dead ends etc.

Strategy is as follows:
1: find a place to start by scanning the start column (y=0, a<=x<c): there must be a point that is not surveillanced otherwise it can't start
2: go downwards so there is the left wall to it's right (looking into the "robots" direction)
3: if there is nothing on the right, go into that space (doesn't happen on the left wall)
4: if there is something ahead, turn left until way is free
5: if you somehow end up at the start position, the "maze" is not solveable

PS: There is an infinite loop if it has only one "pixel" to move at the start, we should cover that special case

Improvements:
1: proper termination
2: improve that lame collision detection to something smart, any idea?
3: Think about optimizing it, e.g. when returning from a dead end, some

#include <iostream>

using namespace std;

const int sensor_r = 2;
const int sensor_rr = sensor_r * sensor_r;

struct Pt {
	int x;
	int y;
	Pt(int ay, int ax) { x = ax; y = ay; }
};

bool Collision(int a, int b, int c, int d, int y, int x, const Pt* ss, int nss)
{
	if (y < a) return true; // hit left wall, right wall we don't check, since it is "open"
	if (x < b) return true; // hit top wall
	if (x >= d) return true; // hit bottom wall	
	for (int i = 0; i < nss; ++i) // lame collision detection on sensor
	{
		int dx = ss[i].x - x;
		int dy = ss[i].y - y;
		if (dx*dx + dy*dy <= sensor_rr)
		{
			return true;
		}
	}
	return false;
}

void FindWay(int a, int b, int c, int d, const Pt* ss, int nss, char* track)
{
	if (c-a <= 0) return;
	if (d-b <= 0) return;

	int y = a;
	int x = b;
	
	for (x = b, y = a; x <= d && Collision(a, b, c, d, y, x, ss, nss); ++x);	
	if (x == d) { cout << "can't start: all starting points are checked by sensors" << endl; return; }
	
	int ox = x;
	int oy = y;
	int dx = 1; 
	int dy = 0;
	while (y < c)
	{
		track[x*(c - a + 1) + y] = 'O'; // +1: due to \n 

		if (!Collision(a,b,c,d, y - dx, x + dy, ss, nss)) // there must be something on the right to follow the "wall"
		{
			// if not, turn right ... and do a step in this direction
			int t = dx;
			dx = dy;
			dy = -t;
		}
		else if (Collision(a, b, c, d, y + dy, x + dx, ss, nss))
		{
			// collision ahead, turn left and do not move
			int t = dx;
			dx = -dy;
			dy = t;
			continue;
		}
		// turned right into an empty space or just continue into the direction 
		x += dx;
		y += dy;

		if (x == ox && y == oy) 
		{
			cout << "can't solve it, way is blocked" << endl;
			return;
		}
	}
}

char *CreateTrackBuf(int a, int b, int c, int d);

int main()
{
	int a = 0;
	int b = 0;
	int c = 15;
	int d = 10;
	
	char *track = CreateTrackBuf(a,b,c,d);
	Pt ss[] = { {6,7} , {12,7}, {12,3} /*, {12, 2} */ };
	FindWay(0, 0, 15, 10, ss, sizeof(ss) / sizeof(ss[0]), track);
	
	cout << track;
	getchar();

}


char *CreateTrackBuf(int a, int b, int c, int d)
{
	if (c - a <= 0) return nullptr;
	if (d - b <= 0) return nullptr;

	// create a char buffer to record and print the path he went
	int y2 = c - a + 1; // +1: due to '\n'
	int x2 = d - b;
	int os = y2 * x2;
	char *po = new char[os];
	for (int i = 0; i < os; ++i) po[i] = ' ';
	for (int i = 1; i <= x2; i++)
	{
		po[i*y2 - 1] = '\n';
	}
	po[os - 1] = '\0';
	return po;
}

/* output on above sample:
O          OOO
O         OO OO
O        OO   O
O        O
O    OOO OO
O   OO OO OO
O  OO   OOO
O  O     O
O  OO   OOO
OOOOOO OOOOO

with the 12,2 sensor (blocked path)

can't solve it, way is blocked
OOOOOOOOOOOO
O        OO
O        O
O        O
O    OOO OO
O   OO OO OO
O  OO   OOO
O  O     O
O  OO   OOO
OOOOOO OOOOO

*/

- Chris June 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c"

Just to clarify, you basically have to move from any point at the top of the rectangle to any point at the bottom of the rectangle?

- Samuel June 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can construct a graph with nodes as the coordinates and add edges to each neighboring node if it's not within the circular range of the sensor. Then do dijkstra's from start to end.

/*
 * Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. 
 * Also given some coordinates (m,n) of sensors inside the rectangle. 
 * All sensors can sense in a circular region of radius r about their centre (m,n).
 * Total N sensors are given. A player has to reach frolm left side of rectangle to
 * its right side (i.e. he can start his journey from any point whose y coordinate
 * is b and x coordinate is a<=x<=c. he has to end his journey to any point whose
 * y coordinate is d and x coordinate is a<=x<=c).
 * 
 * Write an algorithm to find path (possibly shortest but not necessary) from 
 * start to end as described above. 
 * NOTE: all coordinates are real numbers. 
 * You have to avoid sensors and can move in any direction any time.
 *
*/

#include <iostream>
#include <list>
#include <map>

#define MAX_INT 2147483647 // represents infinity

using namespace std; 

class Coordinate {

public: 

    Coordinate(int a, int b): x(a), y(b) {};
    int getX() { return x; }
    int getY() { return y; }
    void setX(int x) { this->x = x; }
    void setY(int y) { this->y = y; }

    operator std::string() const { return "(" + std::to_string(x) + ", " + std::to_string(y) + ")"; }
    
    
private:
int x, y;

};

typedef Coordinate Coord;

class Range {

public:
    Range(int i, int r): min(i-r), max(i+r) {}
    int getMin() { return min; }
    int getMax() { return max; }
        
private:
    int min, max;
    
};

// forward declare
class Node; 
class Sensor; 

typedef Node* NodeP;
typedef Sensor* SensorP;

class Node {

public:
    Node(int m, int n): distance(MAX_INT), n(NULL) {
        xy = new Coordinate(m,n);
        edges = list<NodeP>(); 
    };

    Node(Coordinate *c): xy(c), distance(MAX_INT), n(NULL) {
        //name = "a"; 
        edges = list<NodeP>(); 
    };

    Node(Coordinate *c, string n): xy(c), distance(MAX_INT), n(NULL) {
        //name = n; 
        edges = list<NodeP>(); 
    };
    
    // ERROR: Parameter needs a pointer!
    void addEdge(Node *a) { edges.push_back(a); }
    
    void print() {
        cout << "{x: " << std::to_string(xy->getX()) << ", y: " << std::to_string(xy->getY()) << "}\n";
    }

    //operator std::string() const 
    std::string to_string() { return  "{x: " + std::to_string(xy->getX()) + ", y: " + std::to_string(xy->getY()) + "}"; }

    std::string edges_to_string() { 
        std::string s; 
        for (list<NodeP>::iterator it=edges.begin(); it != edges.end(); it++) {
            s += " {x: " + std::to_string((*it)->xy->getX()) + ", y: " + std::to_string((*it)->xy->getY()) + "} "; 
        }
        
        return s; 
    }
    
    Coordinate *xy;
    int distance;
    list<NodeP> edges;
    
    void addNext(NodeP n) { this->n = n; }
    NodeP next() { return n; }

protected:
    std::string name;
    NodeP n; 
};


class Sensor : public Node {

public:
    Sensor(Coordinate *c, int r) : Node(c), radius(r), x_range(new Range(c->getX(),r)), y_range(new Range(c->getY(), r)) {}

    bool isWithinRange(int x, int y) {
        
        if ((x >= x_range->getMin()) && (x <= x_range->getMax())
            && ((y >= y_range->getMin()) && (y <= y_range->getMax()))
        ) {
            if (x == x_range->getMin() && y != xy->getY()) return false; 
            if (x == x_range->getMax() && y != xy->getY()) return false; 
            if (y == y_range->getMin() && x != xy->getX()) return false; 
            if (y == y_range->getMax() && x != xy->getX()) return false; 
            return true;
        }
        
        return false; 
    }

    bool isWithinRange(Coordinate *c) {
        
        if ((c->getX() >= x_range->getMin()) && (c->getX() <= x_range->getMax())
            && ((c->getY() >= y_range->getMin()) && (c->getY() <= y_range->getMax()))
        ) {
            if (c->getX() == x_range->getMin() && c->getY() != xy->getY()) return false; 
            if (c->getX() == x_range->getMax() && c->getY() != xy->getY()) return false; 
            if (c->getY() == y_range->getMin() && c->getX() != xy->getX()) return false; 
            if (c->getY() == y_range->getMax() && c->getX() != xy->getX()) return false; 
            return true;
        }
        
        return false; 
    }
    
    void print() {
        cout << "{x: " << xy->getX() << ", y: " << xy->getY() << ", r: " << radius << "}\n";
    }
protected:
    int radius; 
    Range *x_range; 
    Range *y_range; 
};

list<NodeP>* dijkstra(NodeP start, NodeP end) {

    list<NodeP> todo = list<NodeP>(); 
    list<NodeP> path = list<NodeP>(); 
    NodeP tmp;
    todo.push_back(start);
    
    // Start with distance 0
    start->distance = 0; 
    
    while (!todo.empty()) {
    
        tmp = todo.back(); 
        todo.pop_back();
        cout << "Searching " << tmp->to_string() << " with edges: " << tmp->edges_to_string() << "\n"; 
        for (list<NodeP>::iterator it = tmp->edges.begin(); it != tmp->edges.end(); it++) {

            cout << "Distance " << std::to_string(tmp->distance + 1) << " < " << std::to_string((*it)->distance) << "?\n";
            if ((tmp->distance + 1) < (*it)->distance) {
                cout << "Updating distance of " << (*it)->to_string() << "\n";
                (*it)->distance = tmp->distance + 1;
                todo.push_back(*it); 
                tmp->addNext((*it));
            }
            
            if (((*it)->xy->getX() == end->xy->getX()) && 
            ((*it)->xy->getY() == end->xy->getY())) {
                cout << "Found!\n";
                break;
            }
        }
    }
    
    tmp = start; 
    path.push_back(tmp); 
    
    while ((tmp = tmp->next())) {
    
        cout << "Path " << tmp->to_string() << "\n"; 
        path.push_back(tmp); 
    }
    return &path; 
} 

int main() {

    int a = 0, b = 0, c = 4, d = 4;
    map<std::string, NodeP> graph;
    map<std::string,NodeP>::iterator it;
    list<SensorP> sensors = list<SensorP>();
    
    Sensor *s = new Sensor(new Coordinate(1,2),1);
    s->print();
    sensors.push_back(s);

    Sensor *s1 = new Sensor(new Coordinate(3,0),1);
    s1->print();
    sensors.push_back(s1);

    
    bool bad = s->isWithinRange(3,6); 
    cout << "bad: " << bad << "\n"; 
    
    bad = s->isWithinRange(4,3); 
    cout << "bad: " << bad << "\n"; 
    
    Node *end = new Node(c, d); 
    
    bool safe = false; 
    
    // Construct graph
    for (int i=0; i<c; i++) {
    
        for (int j=0; j<d; j++) {
        
            Coord *c = new Coord(i,j);
            safe = true;
            // Check if we're safe from all sensors
            for (list<SensorP>::iterator sen=sensors.begin(); sen != sensors.end(); sen++) {
                if ((*sen)->isWithinRange(c)) {
                    safe = false;
                    break;
                }            
            }

            if (safe) {

                Node *next = new Node(c); 
                std::string s = std::to_string(i) + std::to_string(j); 

                // add neighboring nodes
                std::string top = std::to_string(i) + std::to_string(j-1); 
                std::string left = std::to_string(i-1) + std::to_string(j); 
                std::string topleft = std::to_string(i-1) + std::to_string(j-1); 

                it = graph.find(top); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                it = graph.find(left); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                it = graph.find(topleft); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                graph.insert(pair<std::string,Node*>(s, next));
               } 

        }
    }
    
    for (auto& x: graph) {
        cout << x.first << ": " << x.second->to_string() << " edges: " << x.second->edges_to_string() << '\n';
    }
    
    // Do dijkstra's 
    // Get start node
    list<NodeP> *path;
    std::string start_str = std::to_string(0) + std::to_string(0); 
    it = graph.find(start_str);
    if (it != graph.end()) {
        path = dijkstra((it->second), end);
    }

    
    cout << "path: ";
    for (list<NodeP>::iterator it=path->begin(); it != path->end(); it++) {
        cout << (*it)->to_string() << " ";
    }
    cout << "\n";
    
    return 0;
};

- Kim June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can create a graph with nodes as coordinates and an edges to each neighboring node if the node is not within range of the all the sensors. Then do dijkstra's from start to end given a list of possible starting positions and a list of possible ending positions.

So something like this:

/*
 * Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. 
 * Also given some coordinates (m,n) of sensors inside the rectangle. 
 * All sensors can sense in a circular region of radius r about their centre (m,n).
 * Total N sensors are given. A player has to reach frolm left side of rectangle to
 * its right side (i.e. he can start his journey from any point whose y coordinate
 * is b and x coordinate is a<=x<=c. he has to end his journey to any point whose
 * y coordinate is d and x coordinate is a<=x<=c).
 * 
 * Write an algorithm to find path (possibly shortest but not necessary) from 
 * start to end as described above. 
 * NOTE: all coordinates are real numbers. 
 * You have to avoid sensors and can move in any direction any time.
 *
*/

#include <iostream>
#include <list>
#include <map>

#define MAX_INT 2147483647 // represents infinity

using namespace std; 

class Coordinate {

public: 

    Coordinate(int a, int b): x(a), y(b) {};
    int getX() { return x; }
    int getY() { return y; }
    void setX(int x) { this->x = x; }
    void setY(int y) { this->y = y; }

    operator std::string() const { return "(" + std::to_string(x) + ", " + std::to_string(y) + ")"; }
    
    
private:
int x, y;

};

typedef Coordinate Coord;

class Range {

public:
    Range(int i, int r): min(i-r), max(i+r) {}
    int getMin() { return min; }
    int getMax() { return max; }
        
private:
    int min, max;
    
};

// forward declare
class Node; 
class Sensor; 

typedef Node* NodeP;
typedef Sensor* SensorP;

class Node {

public:
    Node(int m, int n): distance(MAX_INT), n(NULL) {
        xy = new Coordinate(m,n);
        edges = list<NodeP>(); 
    };

    Node(Coordinate *c): xy(c), distance(MAX_INT), n(NULL) {
        //name = "a"; 
        edges = list<NodeP>(); 
    };

    Node(Coordinate *c, string n): xy(c), distance(MAX_INT), n(NULL) {
        //name = n; 
        edges = list<NodeP>(); 
    };
    
    // ERROR: Parameter needs a pointer!
    void addEdge(Node *a) { edges.push_back(a); }
    
    void print() {
        cout << "{x: " << std::to_string(xy->getX()) << ", y: " << std::to_string(xy->getY()) << "}\n";
    }

    //operator std::string() const 
    std::string to_string() { return  "{x: " + std::to_string(xy->getX()) + ", y: " + std::to_string(xy->getY()) + "}"; }

    std::string edges_to_string() { 
        std::string s; 
        for (list<NodeP>::iterator it=edges.begin(); it != edges.end(); it++) {
            s += " {x: " + std::to_string((*it)->xy->getX()) + ", y: " + std::to_string((*it)->xy->getY()) + "} "; 
        }
        
        return s; 
    }
    
    Coordinate *xy;
    int distance;
    list<NodeP> edges;
    
    void addNext(NodeP n) { this->n = n; }
    NodeP next() { return n; }

protected:
    std::string name;
    NodeP n; 
};


class Sensor : public Node {

public:
    Sensor(Coordinate *c, int r) : Node(c), radius(r), x_range(new Range(c->getX(),r)), y_range(new Range(c->getY(), r)) {}

    bool isWithinRange(int x, int y) {
        
        if ((x >= x_range->getMin()) && (x <= x_range->getMax())
            && ((y >= y_range->getMin()) && (y <= y_range->getMax()))
        ) {
            if (x == x_range->getMin() && y != xy->getY()) return false; 
            if (x == x_range->getMax() && y != xy->getY()) return false; 
            if (y == y_range->getMin() && x != xy->getX()) return false; 
            if (y == y_range->getMax() && x != xy->getX()) return false; 
            return true;
        }
        
        return false; 
    }

    bool isWithinRange(Coordinate *c) {
        
        if ((c->getX() >= x_range->getMin()) && (c->getX() <= x_range->getMax())
            && ((c->getY() >= y_range->getMin()) && (c->getY() <= y_range->getMax()))
        ) {
            if (c->getX() == x_range->getMin() && c->getY() != xy->getY()) return false; 
            if (c->getX() == x_range->getMax() && c->getY() != xy->getY()) return false; 
            if (c->getY() == y_range->getMin() && c->getX() != xy->getX()) return false; 
            if (c->getY() == y_range->getMax() && c->getX() != xy->getX()) return false; 
            return true;
        }
        
        return false; 
    }
    
    void print() {
        cout << "{x: " << xy->getX() << ", y: " << xy->getY() << ", r: " << radius << "}\n";
    }
protected:
    int radius; 
    Range *x_range; 
    Range *y_range; 
};

list<NodeP>* dijkstra(NodeP start, NodeP end) {

    list<NodeP> todo = list<NodeP>(); 
    list<NodeP> path = list<NodeP>(); 
    NodeP tmp;
    todo.push_back(start);
    
    // Start with distance 0
    start->distance = 0; 
    
    while (!todo.empty()) {
    
        tmp = todo.back(); 
        todo.pop_back();
        cout << "Searching " << tmp->to_string() << " with edges: " << tmp->edges_to_string() << "\n"; 
        for (list<NodeP>::iterator it = tmp->edges.begin(); it != tmp->edges.end(); it++) {

            cout << "Distance " << std::to_string(tmp->distance + 1) << " < " << std::to_string((*it)->distance) << "?\n";
            if ((tmp->distance + 1) < (*it)->distance) {
                cout << "Updating distance of " << (*it)->to_string() << "\n";
                (*it)->distance = tmp->distance + 1;
                todo.push_back(*it); 
                tmp->addNext((*it));
            }
            
            if (((*it)->xy->getX() == end->xy->getX()) && 
            ((*it)->xy->getY() == end->xy->getY())) {
                cout << "Found!\n";
                break;
            }
        }
    }
    
    tmp = start; 
    path.push_back(tmp); 
    
    while ((tmp = tmp->next())) {
    
        cout << "Path " << tmp->to_string() << "\n"; 
        path.push_back(tmp); 
    }
    return &path; 
} 

int main() {

    int a = 0, b = 0, c = 4, d = 4;
    map<std::string, NodeP> graph;
    map<std::string,NodeP>::iterator it;
    list<SensorP> sensors = list<SensorP>();
    
    Sensor *s = new Sensor(new Coordinate(1,2),1);
    s->print();
    sensors.push_back(s);

    Sensor *s1 = new Sensor(new Coordinate(3,0),1);
    s1->print();
    sensors.push_back(s1);

    
    bool bad = s->isWithinRange(3,6); 
    cout << "bad: " << bad << "\n"; 
    
    bad = s->isWithinRange(4,3); 
    cout << "bad: " << bad << "\n"; 
    
    Node *end = new Node(c, d); 
    
    bool safe = false; 
    
    // Construct graph
    for (int i=0; i<c; i++) {
    
        for (int j=0; j<d; j++) {
        
            Coord *c = new Coord(i,j);
            safe = true;
            // Check if we're safe from all sensors
            for (list<SensorP>::iterator sen=sensors.begin(); sen != sensors.end(); sen++) {
                if ((*sen)->isWithinRange(c)) {
                    safe = false;
                    break;
                }            
            }

            if (safe) {

                Node *next = new Node(c); 
                std::string s = std::to_string(i) + std::to_string(j); 

                // add neighboring nodes
                std::string top = std::to_string(i) + std::to_string(j-1); 
                std::string left = std::to_string(i-1) + std::to_string(j); 
                std::string topleft = std::to_string(i-1) + std::to_string(j-1); 

                it = graph.find(top); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                it = graph.find(left); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                it = graph.find(topleft); 
                if (it != graph.end()) {
                    it->second->addEdge(next);
                }

                graph.insert(pair<std::string,Node*>(s, next));
               } 

        }
    }
    
    for (auto& x: graph) {
        cout << x.first << ": " << x.second->to_string() << " edges: " << x.second->edges_to_string() << '\n';
    }
    
    // Do dijkstra's 
    // Get start node
    list<NodeP> *path;
    std::string start_str = std::to_string(0) + std::to_string(0); 
    it = graph.find(start_str);
    if (it != graph.end()) {
        path = dijkstra((it->second), end);
    }

    
    cout << "path: ";
    for (list<NodeP>::iterator it=path->begin(); it != path->end(); it++) {
        cout << (*it)->to_string() << " ";
    }
    cout << "\n";
    
    return 0;
};

- Kim June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import deque
from math import pi, cos, sin

def draw_circle(grid, x_o, y_o, R):
    h = len(grid)
    w = len(grid[0])
    for theta in range(0, 361, 10):
        x = int(x_o + R * cos (theta * pi / 180))
        y = int(y_o + R * sin (theta * pi / 180))
        if x >= 0 and x < w and y >= 0 and y < h:
            grid[x][y] = '0'

def dfs(grid, source, possible_start, c, d):
    visited = set()
    parents = {source: None}
    stack = [source]

    while stack:
        x, y = stack.pop()
        visited.add((x,y))
        if y == d:
            # reached other side, return path (build in reverse)
            path = deque(tuple((x,y)))
            while parents[(x,y)]:
                x, y = parents[(x,y)]
                path.appendleft((x,y))
                if y == 0: # the start of the path can be which ever (row, 0) position we encounter first
                    break
            return path
        if (x,y) in possible_start: #if a possible start can be reached from this connected component, remove it
            possible_start.remove((x,y))
        for x_adj, y_adj in [(x-1, y), (x+1,y), (x, y-1), (x, y+1)]:
            if x_adj >= 0 and x_adj <= d and y_adj >= 0 and y_adj <= c\
                    and grid[x_adj][y_adj] == ' ' and (x_adj, y_adj) not in visited:
                parents[(x_adj, y_adj)] = (x,y)
                stack.append((x_adj, y_adj))
    return None


def cross_grid(c, d, sensors, R):
    grid = [ [' ' for i in range(d + 1)] for i in range(c + 1) ]

    for x_s, x_y in sensors:
        draw_circle(grid, x_s, x_y, R)

    starts = set()
    for i in range(d+1):
        if grid[i][0] == ' ':
            starts.add((i,0))

    path = None
    while starts: # dfs on all unconnected components
        if path:
            break
        source = starts.pop()
        path = dfs(grid, source, starts, c, d)

    for r in grid: to print grid
         print(r)

    return path

- meowmeow June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import deque
from math import pi, cos, sin

def draw_circle(grid, x_o, y_o, R):
    h = len(grid)
    w = len(grid[0])
    for theta in range(0, 361, 10):
        x = int(x_o + R * cos (theta * pi / 180))
        y = int(y_o + R * sin (theta * pi / 180))
        if x >= 0 and x < w and y >= 0 and y < h:
            grid[x][y] = '0'

def dfs(grid, source, possible_start, c, d):
    visited = set()
    parents = {source: None}
    stack = [source]

    while stack:
        x, y = stack.pop()
        visited.add((x,y))
        if y == d:
            # reached other side, return path (build in reverse)
            path = deque(tuple((x,y)))
            while parents[(x,y)]:
                x, y = parents[(x,y)]
                path.appendleft((x,y))
                if y == 0: # the start of the path can be which ever (row, 0) position we encounter first
                    break
            return path
        if (x,y) in possible_start: #if a possible start can be reached from this connected component, remove it
            possible_start.remove((x,y))
        for x_adj, y_adj in [(x-1, y), (x+1,y), (x, y-1), (x, y+1)]:
            if x_adj >= 0 and x_adj <= d and y_adj >= 0 and y_adj <= c\
                    and grid[x_adj][y_adj] == ' ' and (x_adj, y_adj) not in visited:
                parents[(x_adj, y_adj)] = (x,y)
                stack.append((x_adj, y_adj))
    return None


def cross_grid(c, d, sensors, R):
    grid = [ [' ' for i in range(d + 1)] for i in range(c + 1) ]

    for x_s, x_y in sensors:
        draw_circle(grid, x_s, x_y, R)

    starts = set()
    for i in range(d+1):
        if grid[i][0] == ' ':
            starts.add((i,0))

    path = None
    while starts: # dfs on all unconnected components
        if path:
            break
        source = starts.pop()
        path = dfs(grid, source, starts, c, d)

    for r in grid: to print grid
         print(r)

    return path

- meowmeow June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// travel.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <queue>
enum BitType{
    eEmpty,
    ePath,
    eSensor,
    eVisited,
    eInvalid
};

class Sensor{
public:
    Sensor(int x, int y, int radius) : _x(x), _y(y), _radius(radius) {
    }
    bool hitTest(int x, int y) {
        int h = _x - x;
        int v = _y - y;
        if(v*v + h*h <= _radius* _radius){
            return true;
        }
        return false;
    }
private:
    int _x, _y;
    int _radius;
};

class Bitmap{
public :
    Bitmap(int width, int height) : _width(width), _height(height) {
        _buffer = new char [_width * _height];
        if(_buffer != NULL) {
            memset(_buffer, eEmpty, _width *_height);
        }
    }
    void setBit(int x, int y, BitType bitType) {
        if(_buffer == NULL || x<0||y<0 || x>=_width || y>=_height)
            return;
        _buffer [y * _width + x] = bitType;
    }
    BitType getBit(int x, int y) {
        if(_buffer == NULL || x >= _width || x < 0|| y >= _height || y < 0) {
            return eInvalid;
        } else {
            return (BitType)_buffer[y * _width + x];
        }
    }
    void printBitmap() {
        for(int y = 0;  y < _height; ++y){
            printf("|");
            for (int x =0; x < _width; ++x) {
                if(_buffer[x + y * _width] == eEmpty){
                    printf(" ");
                } else if(_buffer[x + y * _width] == ePath) {
                    printf("-");
                } else if(_buffer[x + y * _width] == eSensor) {
                    printf("S");
                } else if(_buffer[x + y * _width] == eVisited) {
                    printf(" ");
                }
            }
            printf("|\n");
        }
    }
    int getWidth() {
        return _width;
    }
    int getHeight() {
        return _height;
    }
private :
    int _height;
    int _width;
    char * _buffer;
};

class Node {
public :
    Node(int x, int y, Node * parent) : _x(x), _y(y), _parent(parent) {
    }
    int getX(){
        return _x;
    }
    int getY() {
        return _y;
    }
    Node * getParent() {
        return _parent;
    }
    void addChild(Node * child) {
        _childs.push_back(child);
    }
    void addChildsInQueue(std::queue<Node *> &queue) {
        std::vector<Node *>::iterator itr = _childs.begin();
        while(itr != _childs.end()){
            queue.push(*itr);
            ++itr;
        }
    }
private:
    int _x;
    int _y;
    Node * _parent;
    std::vector<Node *> _childs;
};

class Terrain {
public:
    Terrain(Bitmap *bitmap, std::vector<Sensor *> & sensors) :_bitmap(bitmap), _sensors(sensors) {
    }
    ~Terrain(){
        std::vector<Sensor *>::iterator itr = _sensors.begin();
        while(itr != _sensors.end()) {
            delete (*itr);
        }
        _sensors.erase(_sensors.begin(), _sensors.end());
        delete _bitmap;
    }
    void traversePath() {
        if(_bitmap == NULL) {
            return;
        }
        for(int y = 0;  y < _bitmap->getHeight(); ++y){
            for (int x =0; x < _bitmap->getWidth(); ++x) {
                std::vector<Sensor *>::iterator itr = _sensors.begin();
                while(itr != _sensors.end()) {
                    if((*itr)->hitTest(x,y)) {
                        _bitmap->setBit(x,y, eSensor);
                    }
                    ++itr;
                }
            }
        }
        std::queue<Node *> queue;
        Node * root = new Node(-1,-1,NULL);
        for(int y = 0; y < _bitmap->getHeight(); ++y) {
            if(_bitmap->getBit(0, y) == eEmpty) {
                Node * node = new Node(0,y,root);
                _bitmap->setBit(0,y, eVisited);
                queue.push(node);
                root->addChild(node);
            }
        }
        Node * destination = NULL;
        while(!queue.empty()){
            Node * node = queue.front();
            if(_bitmap->getBit(node->getX() + 1, node->getY()) == eEmpty){
                Node *child = new Node (node->getX() + 1, node->getY(), node);
                _bitmap->setBit(node->getX() + 1, node->getY(), eVisited);
                queue.push(child);
                node->addChild(child);
                if(node->getX() +1 == _bitmap->getWidth() -1) {
                    destination = child; //We reached the right side. So break
                    break;
                }
            }
            if(_bitmap->getBit(node->getX(), node->getY() + 1) == eEmpty){
                Node *child = new Node (node->getX(), node->getY() + 1, node);
                _bitmap->setBit(node->getX(), node->getY() + 1, eVisited);
                queue.push(child);
                node->addChild(child);
            }
            if(_bitmap->getBit(node->getX(), node->getY() - 1) == eEmpty){
                Node *child = new Node (node->getX(), node->getY() - 1, node);
                _bitmap->setBit(node->getX(), node->getY() - 1, eVisited);
                queue.push(child);
                node->addChild(child);
            }
            queue.pop();
        }
        while(destination != NULL) {
            _bitmap->setBit(destination->getX(), destination->getY(), ePath);
            destination = destination->getParent();
        }
        while(!queue.empty()) {
            queue.pop();
        }
        _bitmap->printBitmap();

        //Delete the tree
        queue.push(root);
        while(!queue.empty()){
            Node * node = queue.front();
            node->addChildsInQueue(queue);
            delete node;
            queue.pop();
        }
        
    }
private:
    Bitmap * _bitmap;
    std::vector<Sensor *> _sensors;
};


int _tmain(int argc, _TCHAR* argv[])
{
    Bitmap * bitmap = new Bitmap(20, 20);
    std::vector<Sensor *> sensors;
    sensors.push_back(new Sensor(4, 4, 4)); 
    sensors.push_back(new Sensor(11, 11, 4)); 
    sensors.push_back(new Sensor(15, 15, 4)); 
    sensors.push_back(new Sensor(14, 5, 4)); 
    Terrain terrain(bitmap, sensors);
    terrain.traversePath();
    getchar();
	return 0;
}

- Sunil June 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I beleieve this should be a dynamic obstacle resolving problem.
The player must start from top of Rectangle to bottom at shortest distance. The shortest distance will be a vertical line from top to bottom. But there are obstacles in shape of circles which may be intersecting. The player must avoid them.
I think the logic to solve should be as below:
a) The player start from top and tries to move bottom in straight vertical line.
b) If he encounters an obstacle the program will call method goLeftOrRight(). This method will determine how many intersecting circle are to right and how many are to left. The direction with least X-direction movement will be taken up.
NOTE: Above is a workable but still a bit naive implementation. It may happen that suppose right direction has two obstacles and left have four. But right also have an intersecting obstacle just below the obstacle at its rightmost corner which further has 4 more intersecting obstacles on its right. In that case Right one will be more costly. Therefore the best solution will be we determine the total X-direction movement with all intersections horizontal or vertical and take that direction.

- Tejinder Singh June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I beleieve this should be a dynamic obstacle resolving problem.
The player must start from top of Rectangle to bottom at shortest distance. The shortest distance will be a vertical line from top to bottom. But there are obstacles in shape of circles which may be intersecting. The player must avoid them.
I think the logic to solve should be as below:
a) The player start from top and tries to move bottom in straight vertical line.
b) If he encounters an obstacle the program will call method goLeftOrRight(). This method will determine how many intersecting circle are to right and how many are to left. The direction with least X-direction movement will be taken up.
NOTE: Above is a workable but still a bit naive implementaion. It may happen that suppose right direction has two obstacles and left have four. But right also have an intersecting obstacle just below the obstacle at its rightmost corner which further has 4 more intersecting obstacles on its right. In that case Right one will be more costly. Therefore the best solution will be we determine the total X-direction movement with all intersections horizontal or vertical and take that direction.

- teji.catia June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Maze {

    private final Point upperCorner;
    private final Point lowerCorner;

    private final int radius;

    private final Point [] sensors;

    public Maze(Point upperCorner, Point lowerCorner, int radius, Point[] sensors) {
        this.upperCorner = upperCorner;
        this.lowerCorner = lowerCorner;
        this.radius = radius;
        this.sensors = sensors;
    }

    public List<Point> getPath() {

        boolean [][] map = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];

        for (Point sensor : sensors) {
            for (int i = sensor.y - radius; i <= sensor.y + radius; i++) {
                for (int j = sensor.x - radius; j <= sensor.x + radius; j++) {
                    if (i >= lowerCorner.y && i <= upperCorner.y && j >= upperCorner.x && j <= lowerCorner.x) {
                        map[i][j] = true;
                    }
                }
            }
        }

        for (int i = lowerCorner.y; i <= upperCorner.y; i++ ) {
            if (map[i][upperCorner.x] == false) {
                // DFT search for solution

                Stack<Point> stack = new Stack<>();
                stack.add(new Point(i, upperCorner.x));
                boolean [][] visited = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];

                while (!stack.isEmpty()) {
                    Point p = stack.pop();

                    if (visited[p.y][p.x]) {
                        continue;
                    }

                    visited[p.y][p.x] = true;

                    if (p.x == lowerCorner.x) {
                        // we found solution
                        // TODO: get the path
                    }

                    // add all child to stack if they are not visited
                    if (p.y+1 <= upperCorner.y && map[p.y+1][p.x] == false) {
                        stack.add(new Point(p.y+1, p.x));
                    }

                    if (p.y-1 >= lowerCorner.y && map[p.y-1][p.x] == false) {
                        stack.add(new Point(p.y-1, p.x));
                    }

                    if (p.x+1 >= lowerCorner.x && map[p.y][p.x+1] == false) {
                        stack.add(new Point(p.y, p.x+1));
                    }

                    if (p.x-1 >= upperCorner.x && map[p.y][p.x-1] == false) {
                        stack.add(new Point(p.y, p.x-1));
                    }
                }
            }
        }

        // no solution
        return null;
    }
}

- ugurdonmez87 July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why BFS won't solve the problem?

- Viku August 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.

Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.

With this setup, the problem becomes a standard A* search.

- kefeilei87 September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.

Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.

With this setup, the problem becomes a standard A* search.

- kefeilei87 September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to merge sensors crossed with other into sensor ranges. Keep track of the crosses with rectangle boundaries of sensor rangers. If there does not exist any sensor range with valid left and right cross, then there is a horizontal path. Otherwise not path. For vertical path, checking the top and bottom cross.
If the path exists, then work out the first pair of complement range of sensors range's cross with rectangle boundaries. Return the mid point of the very first ranges of left and right ranges for horizontal path. Return the mid point of the very first ranges of top and bottom ranges for a vertical path.

Details please see: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-find-path.html
Both Python and C++ implementations are provided.

- peter tang September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use optimal seam carving Algo.

- sumit December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use seam carving algo to get optimal path. sensor will work like high weight region which seam has to avoid.

- sumit December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//Assumption:When finding a path from start to end you can only move to the right or down.
//Time complexity: O(mn + m+n).Space: O(mn)
public class Point
{
	double x;
	double y;
	public class Point(double r, double c)
	{
		x=r;
		y=c;
	}
	
	
	public int hashCode()
	{
		return Objects.hash(new Double(x),new Double(y));
	}
	
	public boolean equals(Object obj)
	{
		if(obj==null|| !obj instanceOf(Point))
		{
			return false;
		}
		Point p=(Point)obj;
		return p.hashCode()==hashCode();
	}
}

public ArrayList<Point> findPath(Point top,Point bott,Point[] sensors,double r)
{
	if(top==null||bott==null||sensors==null)
	{
		return null;
	}
	
	ArrayList<Point> path=new ArrayList<Point>();
	HashMap<Point,Boolean> mp=getBlockedZones(sensors,top,bott,r);
	for(doube startX=top.x; startX<=bott.x;startX++)
	{
		if(dfs(startX,top,bott,mp,path))
		{
			break;
		}
	}
	return path;
}

private boolean dfs(Point start, Point top,Point bott, HashMap<Point,Boolean> blocked, ArrayList<Point> pth)
{
	if(start.y==bott.y)
	{
		pth.add(start);
		return true;
	}
	if(blocked.containsKey(start) || (start.x<top.x) || (start.x>bott.x) || (start.y>top.y) || (start.y<bott.y))
	{
		return false;
	}
	
	Point next=new Point(start.x+1.0,start.y);
	if(dfs(next,top,bott,blocked,pth))
	{
		pth.add(0,next);
		return true;
	}
	
	next=new Point(start.x,start.y+1.0);
	if(dfs(next,top,bott,blocked,pth))
	{
		pth.add(0,next);
		return true;
	}
	blocked.put(start,false);
	return false;
}

private HashMap<Point,Boolean> getBlockedZones(Point[] sensors,Point t,Point b, double rad)
{
HashMap<Point,Boolean> blocked=new HashMap<Point,Boolean>();
	for(Point s:sensors)
	{
		updateBlocked(blocked,s,t,b,rad);
	}
	return blocked;
}

private void updateBlocked(HashMap<Point,Boolean> mp, Point sensor,Point top,Point bott, double rad)
{
	Deque<Point>q=new LinkedList<Point>();
	q.addFirst(sensor);
	mp.put(sensor,true);
	while(!q.isEmpty())
	{
		Point top=q.removeFirst();
		for(double i=top.x-1.0;i<=top.x+1.0;i++)
		{
			for(double j=top.y-1.0;j<=top.y+1.0;j++)
			{
				Point p=new Point(i,j);
				if(inBounds(p,sensor,rad,top,bott) && !mp.containsKey(p))
				{
					mp.put(p,true);
					q.addLast(p);
				}
			}
		}
	}
}

private boolean inBounds(Point p,Point s, double r, Point top,Point bott){
	return(p.x>=top.x && p.x<=bott.x) && (p.y>=top.y && p.y<=bott.y) && dist(p,s)<=r);
}

private double dist(Point f,Point g)
{
	double xDist=Math.abs(f.x-g.x);
	double yDist=Math.abs(f.y-g.y);
	return Math.sqrt(Math.pow(xDist,2) + Math.pow(yDist,2));
}

- divm01986 June 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have to move in all directions. So pls solve the generic question.

- ankit3600 June 16, 2016 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More