Google Interview Question for SDE1s


Country: United States




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

Assumptions:
- "unique path" means a path given by label is non-ambiguous
- longest path means the path that includes most labels / visits most vertices, without visiting vertices twice (hamiltonian path if exists is the best solution)
- as the name sais it's an un-directed graph, I assume, the given adjacency list rep. of
the graph ensures all eges (u,v) originating at u have an edge (v,u) originating
at v in it's "neighbors" list
- If I encounter a cycle, I do not consider infinte paths as a solution and try to find
the longest path that is not going through a cycle (I ignore the cycle)
- I rename "neighbors" to adjacents

The problem is NP hard. So, an exponential solution is okay. I am not sure, if there are approximation algorithms and how they look like.

Therefore, I'd completely forget about graph algorithms and do some sort of counting
using the adjacency list repr. of the graph:
- try all node's as first nodes
- now for the second node, try all adjacents of the first node, that aren't already used
- repeat until no more options are available, do this recursively, so all options are
evaluated. Stop if a hamiltonian path (all vertecis visted once) was accidentaly found.

#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

class Node;

int max_path_rec(const vector<Node*>& graph, Node* previous, unordered_set<Node*>& usedNodes)
{	
	int max_sub_path = 0;
	for (Node* next : previous->getAdjacents()) {
		if (usedNodes.count(next) == 0) {
			usedNodes.insert(next);
			max_sub_path = max(max_sub_path, 1 + max_path_rec(graph, next, usedNodes));
			usedNodes.erase(next);
			if (max_sub_path == usedNodes.size() + 1) break;
		}
	}
	return max_sub_path;
}

int max_path(const vector<Node*>& graph) 
{
	int max_graph = 0;
	for (Node* first : graph) {
		unordered_set<Node*> usedNodes{ first };
		max_graph = max(max_graph, 1 + max_path_rec(graph, first, usedNodes));
		if (max_graph == graph.size()) break;
	}
	return max_graph;
}

class Node
{
private:
	int value_;
	unordered_set<Node*> adjacents_;

public:
	const unordered_set<Node*>& getAdjacents() const { return adjacents_; }
	void link(Node* other) {
		other->adjacents_.insert(this);
		adjacents_.insert(other);
	}
};

- Chris November 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@studip.innovates: "neighbors are one direction mapped" this is a minimal change in wording, but a complete different problem: in a DAG (directed a-cyclic graph) the problem of longest path is in P, the original problem is NP hard tough.
[en.wikipedia.org/wiki/Longest_path_problem]

- Chris November 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for some *intuition* on why longest path is np-hard on a un-directed, general graph:
1. It's not a decision problem: if somebody would give you a longest path, you can't verify it in polynomial time, because in order to do so, you would need to know if there isn't an other, longer path. A strong argument it's not an NP-complete problem.
2. Why can't BFS / DFS solve the problem: Because the order in which you traverse the graph matters, by example:

(b)
  /  \
(a)--(c)--(e)
 \   /
  (d)

let's assume some DFS traversals:
i) it did d->a->b->c->e it had it: is obviously a longest path
ii) d->a->c->e, a->b: isn't but one can argue, similar like the longest path in a DAG
works, one just needs to extend the existing DFS-tree when detecting a forward node,
so let's consider:
iii) d->c->b->a, c->e: maybe if we start from each node a dfs? e.g. from e) we must find
the longest path?
iv) e->c->d->a->b: cool, how about
v) e->c->a->d, a->b: hmm... maybe it aint that easy

3) you can derive the problem from the hamiltonian path, because if a hamiltonian path exists, that's the longest one. Deciding if a hamiltonian path exists in a graph is a well-known NP hard problem.

- Chris November 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A simple BFS approach, considering with only 1 node. We can extend this to multiple nodes to check the longest paths. The neighbors are one direction mapped for simplicity-

public static void main(String[] args){
  	UndirectedGraphNode u0 = new UndirectedGraphNode(0);
    UndirectedGraphNode u1 = new UndirectedGraphNode(1);
    UndirectedGraphNode u2 = new UndirectedGraphNode(2);
    UndirectedGraphNode u3 = new UndirectedGraphNode(3);
    UndirectedGraphNode u4 = new UndirectedGraphNode(4);
    UndirectedGraphNode u5 = new UndirectedGraphNode(5);
    UndirectedGraphNode u6 = new UndirectedGraphNode(6);
    UndirectedGraphNode u7 = new UndirectedGraphNode(7);
    
    u0.neighbors.add(u6);
    u0.neighbors.add(u4);
    u0.neighbors.add(u5);
    u0.neighbors.add(u1);
    
    u1.neighbors.add(u3);
    u3.neighbors.add(u2);
    u2.neighbors.add(u7);
    
    int max = Integer.MIN_VALUE;
    int n = maxpath(u0, new ArrayList<>(), "", 0, max);
    System.out.println(n);
  }
  
  public static int maxpath(UndirectedGraphNode graph, List<String> paths, String path, int len, int max){
  	
    if(graph == null)
      return max;
    
    List<UndirectedGraphNode> neighbors = graph.neighbors;
    if(neighbors.size() > 0){
      for(UndirectedGraphNode node: neighbors){
        if(!paths.contains(path+node.label)){
          if(node != null){
          	max = maxpath(node, paths, path+node.label, len+1, max);
          }
      	}
      }
    }else{
      	paths.add(path);
    	max = Math.max(max, len);
      	return max;
    }
    return max;
  }
  
  
  static class UndirectedGraphNode { 
  	int label; 
  	List<UndirectedGraphNode> neighbors; 
    
    public UndirectedGraphNode(int x){
    	label = x;
    	neighbors = new ArrayList<UndirectedGraphNode>(); 
    } 
  }

- sudip.innovates November 07, 2017 | 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