Google Interview Question for Jr. Software Engineers


Country: United States
Interview Type: Phone Interview




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

#include <iostream>
#include <list>
#include <stack>

class Graph {
private:
    int vertices;
    std::list<int> * adjacencies;
    
private:
    void runTopologicalSortUtility(int vertex, bool * visitedVertices, std::stack<int> & stack);
    
public:
    Graph(int vertices);
    ~Graph();
    
    void addEdge(int from, int to);
    void runTopologicalSort();
};

Graph::Graph(int vertices) {
    this->vertices      = vertices;
    this->adjacencies   = new std::list<int>[vertices];
}

Graph::~Graph() {
    delete [] adjacencies;
}

void Graph::addEdge(int from, int to) {
    adjacencies[from].push_back(to);
}

void Graph::runTopologicalSortUtility(int vertex, bool * visitedVertices, std::stack<int> & stack) {
    std::reverse_iterator<std::list<int>::iterator> reverseListIterator;
    
    visitedVertices[vertex] = true;
    
    for (reverseListIterator = adjacencies[vertex].rbegin(); reverseListIterator != adjacencies[vertex].rend(); reverseListIterator++) {
        if (visitedVertices[*reverseListIterator] == false) {
            runTopologicalSortUtility(*reverseListIterator, visitedVertices, stack);
        }
    }
    
    stack.push(vertex);
}

void Graph::runTopologicalSort() {
    bool * visitedVertices;
    std::stack<int> stack;
    
    visitedVertices = new bool[vertices];
    for (int i = 0; i < vertices; i++) {
        visitedVertices[i] = false;
    }
    
    
    for (int vertex = 1; vertex < vertices; vertex++) {
        if (visitedVertices[vertex] == false) {
            runTopologicalSortUtility(vertex, visitedVertices, stack);
        }
    }
    
    while (stack.empty() == false) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;
}

int main(int argc, const char * argv[]) {
    Graph graph(6);
    
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(3, 5);
    graph.addEdge(2, 5);
    graph.addEdge(4, 5);
    
    std::cout << "Following is a Topological Sort of the given graph" << std::endl;
    graph.runTopologicalSort();
    
    return 0;
}

- Hsien Chang Peng November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good one :) but I think (IMHO) you should put the :
stack.push(vertex); inside the if:

if (visitedVertices[*reverseListIterator] == false) {
            runTopologicalSortUtility(*reverseListIterator, visitedVertices, stack);
	    stack.push(vertex);
}

Otherwise your keep pushing the 5 vertex (from the example)...

- Natty December 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry ... you are most correct... the check for not visited is done when running on the graph vertexes (before calling to the utility)... and pushing to the stack should be done (as you've done most correctly) after finishing with the current vertex... my bad :)

- Natty.Kohn December 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Java implementation of Tarjan's algorithm:

public static <T> List<Node<T>> sortTopological(Set<Node<T>> nodes) {
    List<Node<T>> result = new ArrayList<>(); // Sorted list of Nodes
    Set<Node<T>> visited = new HashSet<>(); // Used in lieu of a boolean flag on Node
    Set<Node<T>> visitedTemp = new HashSet<>(); // Used in lieu of a boolean flag on Node
    for (Node<T> node : nodes) {
        if (!visited.contains(node)) visit(node, result, visited, visitedTemp);
    }
    return result;
}

private static <T> void visit(Node<T> node, List<Node<T>> sorted, Set<Node<T>> visited, Set<Node<T>> visitedTemp) {
    if (visitedTemp.contains(node)) throw new RuntimeException("Graph is not acyclic");
    visitedTemp.add(node);
    for (int i = 0; i < node.adjacent.size(); i++) {
        Node<T> adjacentNode = node.adjacent.get(i);
        if (!visited.contains(adjacentNode)) {
            visit(adjacentNode, sorted, visited, visitedTemp);
        }
    }
    visited.add(node);
    visitedTemp.remove(node);
    sorted.add(0, node);
}

- damien5314 December 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what do you mean by "partial topological sort"?

- lepeisi November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry fixed.

- J@sper November 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is expected in case graph is cyclic?

- EPavlova November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not specified

- J@sper November 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do bfs from vertex with zero in-degree.

Delete vertex of in-degree 0 and all its outgoing edges from the graph.

Continue doing so until no more in-degree 0 vertex.

If the graph still have vertexes, then it has cycle. Return what ever the reviewer want (could be null or the vertexes deleted)

If the graph do not have vertexes then the deleted vertexes is in topological order.

We could keep a stack for the deleted vertexes and return it as the answer.

- lepeisi November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];

void top(int u)
{
vis[u]=1;
//s.pb(u);
for(int el: g[u]){
if(!vis[el]){
top(el);
}
}
s.pb(u);
}

int main()
{
int m=6;
int u,v;
for(int i=0;i<m;i++){
cin>>u>>v;
g[u].push_back(v);
vis[v]=1;
//g[v].push_back(u);
}
int st;
for(int i=1;i<=5;i++){
if(!vis[i]){
st=i; break;
}
}
memset(vis,0,sizeof(vis));
top(st);
reverse(s.begin(),s.end());
for(int el: s){
cout<<el<<" ";
}
return 0;
}

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

#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];

void top(int u)
{
	vis[u]=1;	
	//s.pb(u);
	for(int el: g[u]){
		if(!vis[el]){
			top(el);
		}
	}
	s.pb(u);
}

int main() 
{
	int m=6;
	int u,v;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		vis[v]=1;
		//g[v].push_back(u);
	}
	int st;
	for(int i=1;i<=5;i++){
		if(!vis[i]){
			st=i; break;
		}
	}
	memset(vis,0,sizeof(vis));
	top(st);
	reverse(s.begin(),s.end());
	for(int el: s){
		cout<<el<<" ";
	}
	return 0;

}

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

top

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

#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];

void top(int u)
{
	vis[u]=1;	
	//s.pb(u);
	for(int el: g[u]){
		if(!vis[el]){
			top(el);
		}
	}
	s.pb(u);
}

int main() 
{
	int m=6;
	int u,v;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		vis[v]=1;
		//g[v].push_back(u);
	}
	int st;
	for(int i=1;i<=5;i++){
		if(!vis[i]){
			st=i; break;
		}
	}
	memset(vis,0,sizeof(vis));
	top(st);
	reverse(s.begin(),s.end());
	for(int el: s){
		cout<<el<<" ";
	}
	return 0;
}

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

from copy import copy

class Queue:

    def __init__(self):
      self.items = []

    def isEmpty(self):
       
      if len(self.items) == 0 :
          return True
      else:
          return False
    
    def enqueue(self, v):
        self.items.insert(0, v)
   
    def dequeue(self):
       return self.items.pop()    

class Node:
    
    
    def __init__(self, v):
        self.v = v
        self.adjNodes = []

    def adjacentTo(self, vs):
        self.adjNodes = copy(vs)

class Graph:

   def __init__(self, nodes):
      self.nodes = nodes 
      self.inDegree = self.getinDegree()
      self.printinDegree()


   def printinDegree(self) :

       for n in self.nodes:
           print('n:= ', n.v,' >> inDegree:= ' ,self.inDegree[n])
           

      
   def getinDegree(self):

       inDegree = dict()
       
       for n in self.nodes:
           if n not in inDegree:
              inDegree[n] = 0
           js = n.adjNodes
           for j in js:
               if j not in inDegree:
                  inDegree[j] = 1
               else:
                  inDegree[j] += 1
       return inDegree   

   def topologicalSort(self):

        sortedList = []
        q = Queue()
         
        for n in self.nodes:
            if self.inDegree[n] == 0:
                q.enqueue(n)
                for t in n.adjNodes:
                    self.inDegree[t] -= 1
                    if self.inDegree[t] == 0:
                       q.enqueue(t) 

        while(not q.isEmpty()):

          p = q.dequeue()
          sortedList.append(p)
          for t in p.adjNodes:
              self.inDegree[t] -=1
              if self.inDegree[t] == 0:
                q.enqueue(t)

        for s in sortedList:
           print(s.v) 

a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)
f = Node(6)
a.adjacentTo([b,c])
b.adjacentTo([c,d,e])
c.adjacentTo([d,a])
f.adjacentTo([a])
g = Graph([a,b,c,e,d,f])
g.topologicalSort()

- Fahmida January 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
public:
    int key;
    Node(int k) : key(k) {}
};
class Graph {
public:
   std::stack<int> topSort()
    {
        std::stack<int> ret;
        std::vector<int>    st (nodes.size(), 0);
        for (int i = 0; i < heads.size(); i++)
            dfs(heads[i], ret, st);
        return ret;
    }
   
private:
    void dfs(int root, std::stack<int>& ret, std::vector<int>& st)
    {
        st[root] = 1;
        for (int j = 0; j < adjacency[root].size(); j++)
            if (st[adjacency[root][j]] == 0)
                dfs(adjacency[root][j], ret, st);
        st[root] = 2;
        ret.push(root);
    }
   
    std::vector<Node>   nodes;
    std::vector<int>    heads;
    std::vector<std::vector<int>>   adjacency;
};

- Sean Locke March 20, 2016 | Flag Reply


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