> It turns out optimally computing the LZ Distance Metric requires efficiently solving the Longest Common Substring problem, which can be solved with a generali

> It turns out optimally computing the LZ Distance Metric requires efficiently solving the Longest Common Substring problem, which can be solved with a generalized suffix tree in O(N + M) time. Imagine you walked in to your Google interview, with all of the experience from improving the size of GWT output fresh in your mind, but before you "ran into the 'LZ Distance Metric'". They sit you down and say "LZ Distance Metric is related to your past projects, we want you to solve the LCS problem. Use this whiteboard, markers are to your left, you have 45 minutes." You don't have time to read some papers, research, prototype things or sleep on it. No doubt it takes experience, curiousity and exposure to algorithms to solve but in order to solve it under Google interview like conditions it mostly requires that you've done it before and memorized it.