Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
You can create the DAG from the graph using DFS which is O(V+E):
1. compute DFS on the graph which gives a start and finish times for each node
2. Insert each finished vertex into the front of a linked list, going from the last finished to the first (backwards in the finishing times).
3. Return the linked list
Calculate the Longest path of each node to all other nodes and pick the max among all.
1. Calculate longest path for a single node to all other nodes: O(n) for DAGs using Topological Sort.
2. Calculate for each node its longest path to all others in graph: O(N)^2
3. start a variable max = 0; loop through all the results and pick the max found.
Time: O(n^2)
Assumption:
movie names are more than 1 word long.
each word separated with space
PS: we can update the code if assumptions are not correct.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
public class practice{
String get_last_word(String movie_name){
String[] movie = movie_name.split(" ");
return movie[movie.length-1];
}
String get_first_word(String movie_name){
String[] movie = movie_name.split(" ");
return movie[0];
}
String get_word_except_first(String movie_name){
int i=0;
while(movie_name.charAt(i)!=' '){
i++;
}
return movie_name.substring(i+1,movie_name.length());
}
String movie_name_concat(String filename) throws Exception{
File f = new File(filename);
BufferedReader br = new BufferedReader(new FileReader(f));
String first_movie_name = br.readLine();
String last_word = get_last_word(first_movie_name);
ArrayList<String> result_arr = new ArrayList<String>();
String second_movie_name = br.readLine();
System.out.println("1st= "+first_movie_name+" 2nd= "+second_movie_name);
while(second_movie_name!=null){
String first_word = get_first_word(second_movie_name);
if(last_word.equals(first_word)){
first_movie_name = first_movie_name + " "+get_word_except_first(second_movie_name);
last_word = get_last_word(second_movie_name);
}
else{
result_arr.add(first_movie_name);
first_movie_name = second_movie_name;
last_word = get_last_word(second_movie_name);
}
second_movie_name = br.readLine();
}
result_arr.add(first_movie_name); //may have duplicate for last movie name
//if last_word of previous was != first word of last movie name.
//i.e: if the process went through else block
br.close();
int max_val = Integer.MIN_VALUE;
int max_index=0;
for(int i=0;i<result_arr.size();i++){
if(result_arr.get(i).length()>max_val){
max_val = result_arr.get(i).length();
max_index =i;
}
}
return result_arr.get(max_index);
}
public static void main(String[] args){
practice obj = new practice();
String filename = "E:\\eclipse-workspace\\interview\\src\\external_files\\names.txt";
try {
System.out.println(obj.movie_name_concat(filename));
}
catch(Exception e) {
e.printStackTrace();
}
}
}
Longest path in a DAG. Assuming there are no cycles in the directed graph formed by treating each title as a node , and each adjacency defined by the connectivity property described in the problem.
- random May 01, 2018