My Google Tech Interviewing Decoded Experience

Maybe the OP /u/madnessman can correct me if I'm wrong (since I haven't slept in 24 hours due to cramming for finals), but from what I understand, isn't this simply a graph problem involving DFS where you traverse all the neighbours for each cell, and build the set of all paths as you go along (while doing some sort of memoization to store the recursive results for each cell index in an externaln * n array)? You'd store the parent -> child relation for all possible paths in some map/hashmap implementation as you visit each new cell. In other words, either the value for a given cell is 1, or max(1, largestneighbour + 1), where the value of that cell is the length of the longest path starting from that cell.

This will approximately traverse through the entire array in linear time (more accurately O(|V| + |E|) where |V| is the cardinality of the set of all vertices, n, and |E| is the cardinality of the set of all edges), if the number of edges is fairly small relative to n. In the worst case, you'd have a k-complete graph, which would be n(n - 1)/2 edges, so you'd end up with O(n + n(n-1)/2) = O(n^2) runtime. I guess we're assuming that the number of edges is fairly small compared to the number of vertices.

Then when you've visited every node, you traverse through the n * n array and find the longest possible path, which is linear in terms of the nodes. I think you should be able to do this while you're recursively computing the paths, but it doesn't really matter too much in terms of Big O.

Then you just walk up the path hashmap structure, until you reach the end of the path (which is just the parent -> child path starting at the maximal index that you just found).

So if you define n as the the number of elements in the array, then you'd have O(n + E) to build the set of all paths, O(n) to find the largest element, and O(n) to traverse the longest path in the worst case (assuming O(1) lookup) resulting in O(n + E) + O(n) + O(n) = O(n) runtime, assuming that E is not ridiculously large. You'd use O(n) memory, plus however much stack memory is needed for the recursive function.

/r/cscareerquestions Thread Parent