Google Interview Question for Developer Program Engineers






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

I took some time to understand the game also played 2 minute and in last 15 minute I wrote this way exactly so there could be some bug

class Point{
   int id;
   Point left;
   Point right;
   Point top;
   Point bottom;
   boolean visit;
}

public boolean dfsVisit(Point start,Point end ,String path){
        start.visit = true;   
        if(start.id==end.id)
        {
             System.out.println("Path:"+path);
             return true;
        }
  
        if(isValid(start.left) && dfsVisit(start.left,end,start.id+path)
            return true;
        if(isValid(start.right) && dfsVisit(start.right,end,start.id+path)
            return true;
        if(isValid(start.top) && dfsVisit(start.top,end,start.id+path)
            return true;
        if(isValid(start.bottom) && dfsVisit(start.bottom,end,start.id+path)
            return true;
    return false;
}

public boolean isValid(Point p)
{
  if(p==null) return false;
  if(p.visit) return false;
  return true; 
}

- MaYanK July 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This data structure does not look right. A point is (x,y). Left = x+1, ...
That error might cost you the job.

- QHu September 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks for the clearly written google interview report!

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

1. Connected components will let you know if there is a path between two nodes, but I am not sure if it could be used to find the actual path.

2. Flood fill algo can give us the path as well, but it is expensive.

- gaurav August 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BUt if in game there point for finding minimum path then BFS shuld be used

- coder August 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

policyalmanac.org/games/aStarTutorial.htm
A* pathfinding

- swk September 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think A* needs an additional parameter for every tile. How could you do A* in this case?

- CorrectMe October 08, 2010 | 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