Google Interview Question for Software Developers


Country: India




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

Small modification to BFS to measure distance between two graph nodes. The issue is they should be the same node so you are confident you find the shortest cycle.

from collections import deque

def bfs(adj, u):
    dist = [-1]*len(adj)
    prev = [None]*len(adj)
    thenode = u
    dist[u] = 0
    queue = deque()
    queue.appendleft(u)
    while len(queue) > 0:
        u = queue.pop()
        for v in adj[u]:
            if dist[v] == -1 or dist[v] == 0:
                dist[v] = dist[u] + 1
                prev[v] = u
                if v == thenode:
                    return dist[v], prev
                queue.appendleft(v)
    return -1, []

def print_cycle(path, u):
    v = path[u]
    result = str(u)
    while v != u:
        result += ' <- {}'.format(v)
        v = path[v]
    result += ' <- {}'.format(v)
    print(result)

def find_shortest_cycle(adj, u):
    dist, path = bfs(adj, u)
    if dist != -1:
        print('cycle size:', dist)
        print_cycle(path, u)
    else:
        print('no cycle')

adj = [
[1],
[2,3],
[4,5,6],
[0],
[],
[],
[0]
]

find_shortest_cycle(adj, 0) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 1) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 3) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 2) # return 2 <- 1 <- 0 <- 6 <- 2
find_shortest_cycle(adj, 6) # return 6 <- 2 <- 1 <- 0 <- 6
find_shortest_cycle(adj, 4) # return "no cycle"

- baites January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//BFS time complexity: O(V + E), space: O(V)

class Solution {
  public static void main(String[] args) {
    
    List<List<Integer>> adj = new ArrayList<List<Integer>>(9);
    
    for (int i = 0; i < 9; i++) {
      adj.add(new ArrayList<Integer>());
    }
    

    adj.get(4).add(5);
    
    adj.get(5).add(6);
    adj.get(5).add(7);
    
    adj.get(7).add(6);
    adj.get(7).add(8);
    

    
    System.out.println(longestCycle(adj,4));
}


public static int longestCycle(List<List<Integer>> adj, int node) {

  Deque<Integer> q = new LinkedList<Integer>();
  
  boolean[] visited = new boolean[adj.size()];
  int[] levels = new int[adj.size()];
  levels[node] = 1;
  
  q.addLast(node);
  visited[node] = true;
  
  while (!q.isEmpty()) {
    int top = q.pollFirst();
    
    for (Integer x: adj.get(top)) {
      if (visited[x]) {
         if (x == node) {
          return levels[top];
         }
      } else {
      
        levels[x] = levels[top] + 1;
        q.addLast(x);
      }
    }
  
  }
  
  return -1;
}


}

- divm01986 January 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DetectSmallestCycleInGraph {
    private int shortestCycleSize = Integer.MAX_VALUE;
    private Graph.Vertex[] shortestCycle;

    Graph.Vertex[] findSmallestCycleDirectedGraph(Graph g) {
       for(Graph.Vertex v :g.getVertices()) {//O(V)
           Stack<Graph.Vertex> vertexStack = new Stack<>();
           v.setVisited(false);//marking it unvisited so it can be traversed
           boolean hasCycle = hasCycleDirectedGraph(v, vertexStack);
           if(hasCycle) {
               if(vertexStack.size() < shortestCycleSize){
                   shortestCycleSize = vertexStack.size();
                   shortestCycle = new Graph.Vertex[shortestCycleSize];
                   vertexStack.toArray(shortestCycle);
               }
           }
       }
       return shortestCycle;
    }

    
    boolean hasCycleDirectedGraph(Graph.Vertex source,  Stack<Graph.Vertex> adjVertex) {
        if(source.isVisited()) return false;
        source.setVisited(true);
        adjVertex.push(source);
        for(Graph.Edge adj : source.getEdges()) {//O(A) , where A is adjacent edges to source
            if(adj.getTo().isVisited() && adjVertex.contains(adj.getTo())) {//contains causes O(M) where M is the number of vertices on a path from the source node
                return true;
            } else if(!adj.getTo().isVisited() && hasCycleDirectedGraph(adj.getTo(), adjVertex)) {
                return true;
            }
        }
        adjVertex.pop();
        return false;
    }


    public static void main(String[] args) {
        int[][] edges =  {
                {0,      1},
                {0,      2},
                {2,      1},
                {3,      0},
                {1,      3},//shortest cycle
                {1,      4},
                {4,      5},
                {5,      6},
                {6,      7},
                {7,      1}//cycle

        };
        Graph g = new Graph(edges);
        DetectSmallestCycleInGraph da = new DetectSmallestCycleInGraph();
        Graph.Vertex[] cycle = da.findSmallestCycleDirectedGraph(g);
        System.out.println("\n Shortest cycle : ");
        for (Graph.Vertex v : cycle) {
            System.out.print(v.getId() + " -> ");
        }
    }

- azrarabbani February 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct PathNode
{
	shared_ptr<PathNode> prev;
	int dist;
	const GraphNode* node;
	PathNode(const GraphNode* n, shared_ptr<PathNode>* p=NULL)
	{
		node = n;
		if (p)
		{
			prev = *p;
			dist = p->get()->dist + 1;
		}
		else
			dist = 0;
	}

	bool has(const GraphNode* f)
	{
		PathNode* cur = this;
		do {
			if (cur->node == f)
				return true;
			cur = cur->prev.get();
		} while (cur);
		return false;
	}

	void getAllPath(list<const GraphNode*>& ret)
	{
		PathNode* cur = this;
		do {
			ret.push_front(cur->node);
			cur = cur->prev.get();
		} while (cur);
	}
};

void findShortestCycle(const GraphNode& node, list<const GraphNode*>& ret)
{
	queue<shared_ptr<PathNode>> to_visit;
	to_visit.push(shared_ptr<PathNode>(new PathNode(&node)));
	unordered_map<const GraphNode*, int> dist_map;
	while (!to_visit.empty())
	{
		shared_ptr<PathNode> path = to_visit.front(); to_visit.pop();
		cout << to_visit.size() << ":" << path->node->getValue() << " -> ";
		for (const GraphNode* linked : path->node->links())
		{
			cout << linked->getValue();
			if (path->has(linked))	// cycle
			{
				cout << endl;
				path->getAllPath(ret);
				return;
			}
			unordered_map<const GraphNode*, int>::iterator dist_it = dist_map.find(linked);
			if (dist_it != dist_map.end() && dist_it->second < path->dist + 1)
			{
				cout << "-skip";
				continue;
			}
			cout << " ";

			shared_ptr<PathNode> new_path(new PathNode(linked, &path));
			to_visit.push(new_path);
			dist_map.insert({ linked, new_path->dist });
		}
		cout << endl;
	}
}

void TestShortCycle()
{
	/*
		    b --+ d
		   +      |  \
		  /       |     \
		 /        +       +
		a ------+ c +----- f
		           \      +
		            \    /
				     +  /
				      e

	cycle1 : a -> b -> d -> c -> e -> f -> c
	cycle2 : a -> c -> e -> f -> c

	the lengths of two path are same until 'f' node : a -> b -> d -> f, a -> c -> e -> f
	so, we can't use dijkstra's algorithm to calcuate shortest cycle.
	we can't use visited hash table neither.
	If you use it, second path(a -> c -> e -> f) will vanish.

	But, I really want the faster way of checking cycle
	*/
	GraphNode a("a"), b("b"), c("c"), d("d"), e("e"), f("f");
	a.addFriend(&b);
	a.addFriend(&c);
	b.addFriend(&d);
	c.addFriend(&e);

	d.addFriend(&f);
	d.addFriend(&c);
	e.addFriend(&f);
	f.addFriend(&c);

	list<const GraphNode*> ret;
	findShortestCycle(a, ret);

	cout << "path : ";
	for(const GraphNode* node : ret)
		cout << node->getValue() << " ";
	cout << endl;
}

- lesit.jae February 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution with BFS, extended to track back nodes and the parent (to reconstruct the path):

class Graph
{
private:
    int V;
    vector<int>* adj;

public:
    Graph(int V) :
        V(V),
        parents(V, -1)
    {
        adj = new vector<int>[V];
    }

    ~Graph()
    {
        delete[] adj;
    }

    void addEdge(int src, int dest)
    {
        adj[src].push_back(dest);
    }
    
    bool findShortestCycle(int root)
    {
        vector<bool> visited(V, false);
        vector<bool> backNode(V, false);
        
        queue<int> q;
        q.push(root);
        visited[root] = true;
            
        while(!q.empty())
        {
            int t = q.front();
            q.pop();
            
            for (int &a: adj[t])
            {
                if (backNode[a])
                {
                    if (a == root)
                    {
                        parents[a] = t;
                        return true;
                    }
                    continue;
                }
                
                if (!visited[a])
                {
                    visited[a] = true;
                    parents[a] = t;
                    q.push(a);
                }
            }
            
            backNode[t] = true;
        }
        
        return false;
    }
    
    vector<int> parents;
};

int main() {
    Graph g(6);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 1);
    g.addEdge(3, 2);
    g.addEdge(3, 4);
    g.addEdge(4, 3);
    g.addEdge(4, 5);
    g.addEdge(5, 2);

    cout << "Cycle found: " << g.findShortestCycle(3) << endl;
    
    string path = "3 <- ";
    int v = 3;
        
    while (g.parents[v] != 3)
    {
        path += std::to_string(g.parents[v]) + " <- ";
        v = g.parents[v];
    }
    
    cout << path  << "3 <- " << endl;
    
	return 0;
}

- bertelli.lorenzo April 14, 2019 | 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