Google Phone Screening Round - L5
Summary
I experienced a phone screening round with Google for an L5 position and was presented with a sequence merging problem, which I solved using topological sort.
Full Experience
You have sequence array, each sequence has some value in order. You have to create a result where order of sequence stays as it is. Ex - [ [1,2,15,8], [2,4,7,8], [2,3,7,15] ] Output - 1,2,3,4,7,15,8 or 1,2,4,3,7,15,8 False case - [[1,6,4], [4,1]] -
Solved this using toposort. Created an adjList and indegree matrix and traversed the list to get the result array. For false case, checked if the cycle exists
Interview Questions (1)
You have sequence array, each sequence has some value in order. You have to create a result where order of sequence stays as it is. Ex - [ [1,2,15,8], [2,4,7,8], [2,3,7,15] ] Output - 1,2,3,4,7,15,8 or 1,2,4,3,7,15,8 False case - [[1,6,4], [4,1]] -