Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

"Parallel" is ambiguous and a decent algorithm completely depends on the what underlying "parallel machine" you have. The mention of C & OpenMP narrows it down a bit, though, I suppose.

- Anonymous October 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, I believe everyone knows how to implement BFS, DFS or shortest path. But the point is how can we optimize it by performing mutually exclusive parallel computations on different nodes and yet get the right results at the end.

May be to split the graph and work on them parallely.

- mudit.f2004912 October 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

While implementing BFS, we enque the neighbours of the present node into the queue. Then we deque each of them and again run a BFS on them sequentially. Because we have a parallel processing available, we can execute them in parallel instead of sequential. But we need to keep the common information like visited nodes etc with each of the process.

- jackass October 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry... since it's a weighted directed graph this won't work...

- jackass October 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Even if it is unweighted, you cant process them parallely.

- viiids November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

If the graph is unweighted we can use BFS to find the shortest path between the source node and anyother node with the following code. I am using distributed computation to process every node's neighbours. However, we have to make sure that we move to next level only once all the nodes at previous level are done.

BFS(G)
{
     For v in Vertices
          v.d = 0; 
          v.prev = null;
          v.discovered = 0; 
// 0 for not yet discovered, 1 for discovered, 2 for completed processing neighbours 
          v.level = 0;

     s.prev = 0;
     s.discovered = 1;
     s.d = 0;
     s.level = 0;
     Q.enque(s);
     level = 0;
     while(!IsEmpty(Q))
           if(Q(NextNode).level == level)
                v = deque(Q);
           else
                wait(); //This waits untill all the child threads are exited.
           Process_Parallel(v);  
}

Process_Parallel(Node v)
{
     for every neighbour u of v:
           if(u.discovered == 0)
                   u.d = v.d+1;
                   u.discovered = 1;
                   u.prev = v;
                   u.level = v.level+1;
}

- divya October 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Divya,

Well a good implementation. However, how do we do it for weighted graph. I have an idea, why not do a topological sorting on nodes and then apply BFS as to the trick is, only add a node to the queue when it has exhausted all it's incoming edges, that means all the parents have already been calculated for the minimum distance.

- mudit.f2004912 October 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The same code with small change will work for weighted directed graph as long as there is no cycle in the graph.

Process_Parallel(Node v){     
for every neighbour u of v:   
        if(u.discovered == 0 || u.d > v.d+weight(uv))
                   u.d = v.d+weight(uv);
                   u.discovered = 1;                   
                   u.prev = v;              
                   u.level = v.level+1;
}

- Divya October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Divya,

I am afraid that it will not work.

Just consider this example..

n1-->n2 (5)
n1-->n3 (1)
n2-->n5 (2)
n3-->n4 (1)
n4-->n2 (1)

now according to your node, you will calculate the minimum length of n2 as 5 and put it on level two (or 1 depending on whether you start the leveling from 0 or 1). From there you would move on and calculate the optimum length of n5 as 5+2=7. However, on level three you see that n4 has a link to n2 and this is the optimum path to n2 with cost 3(1+1+1). You change this value, however all the nodes that were the child of n2 were calculated with the previous optimum value of n2 (5) which will give incorrect results.

So we have to consider the topology here in a way that we only add a node to queue when all the parents have calculated their optimum path. This will assurance to a node that it will have the optimum value and it can safely proceed with the child nodes.

So, in our example N2 should only be added to queue after N4. That's nothing but the topological sort mixed with BFS. (only if their are no cycles)

Thanks

- mudit October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For weighted graphs, we need to use the priority queue instead of queue with the top element being the least cost

- Venkatesh April 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra's algorithm for finding shortest path is based on BFS. So I guess we can use this algorithm. what remains is making it work parallel.

- Anonymous October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess for bfs, we do not put the node into queue, for each node, create a new thread to continue the processing, the parameter contains the cost to the current node so far

- lclc October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

multiple threads -----parallel

- lclc October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think you can use traditional BFS for weighted graph. The difference in weighted graphs is that a longer path can still end up incurring less cost(distance). Distance should be only updated if it's less than the current distance. If the graph doesn't have cycles then you can still use while(!Empty(Q)) to check for completion.

- kill October 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about parallelizing the Warshall's algorithm ? Since it has three loops, we should be able to easily make it parallel using openMP

- liquid February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about parallelizing the Warshall's algorithm ? Since it has three loops, we should be able to easily make it parallel using openMP

- liquid February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Single source shortest path problem - Bellman Ford's algorithm, which is in essense a BFS.

for each u in V(G), d[u]=infinity;
d[s] = 0;
for(i=0; i<|E(G)|-1; i++) {
   /* parallelize the following loop */
   for(each edge (u, v) in E(G)) {
/* critical section */      
mutex_lock();
      if(d[v]>d[u] + w(u,v)) {
         d[v] = d[u] + w(u,v);
      }
mutext_unlock();
   }
}

Optimization should be done as to the use of lock, so that it does not become a performance choke point. For large graph, one lock is obviously not enough, but one lock for each vertex seems too much. We can use one lock to guard a given amount of vertices, for example 16.

- jzhu May 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in place of lock... be can reduce it on all machine with keeping minimum only...

- Anonymous September 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

on a single machine:
1. I would say use Dijkstra to find shortest path (based on BFS)
2. we need to mark on each note when we pass it
when moving to make it parallel
Assumption: parallel here would mean that few searches on the same graph can be done simultaneously , meaning, each search can touch the same node (altough coming from different path)

This mean that instead of making when touching it on the node itself, each thread/process, - should hold a hash table if this node is visited.

How would you start the "parallelism" - let's say we have N threads/machines. and the first node in the graph has C children, we would give N%C for each process to work on, although working on the same graph

- Anonymous May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use stack for breadth first query, mark nodes touched

- Anonymous October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The keyword in this problem is PARALLEL. Every student knows how to implement simple DFS in a graph.

- gevorgk October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use Breadth first search to find the shortest path between two nodes if the graph is unweighted graph. However, if the graph is weighted will the BFS still work? I think we can't use BFS for weighted graphs. Can someone correct me if I am wrong here.

- divya October 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If it is a directed acuclic graph, then you can sure use modified BFS (as long as you re-visit an already visited node). If not, BFS cannot be used.

- Anonymous April 04, 2012 | 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