## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

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.

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

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).

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

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

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)

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

@guilhebl. How a directed acyclic graph will be constructed?

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

dfdfdf

``dffd``

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

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.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);
String last_word = get_last_word(first_movie_name);

ArrayList<String> result_arr = new ArrayList<String>();

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{
first_movie_name = second_movie_name;
last_word = get_last_word(second_movie_name);
}
}
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();
}

}
}``````

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

Its not necessary that movie name that can concat occurs sequenceally

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.

### 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.