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


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