Longest Common Subpath

Longest Common Subpath

What is this problem about?

The Longest Common Subpath interview question asks you to find the longest contiguous sequence of integers (representing a subpath) that is present in every single array within a given list of arrays. Think of it as finding the longest exact matching route that multiple different users took on a map, where each user's path is represented as an array of city IDs.

Why is this asked in interviews?

This is a notoriously difficult, high-level algorithm question. Tech giants ask it to identify candidates who possess a deep understanding of advanced string-searching algorithms applied to integer arrays. It tests your ability to handle massive inputs efficiently, as naive solutions will immediately fail due to Time Limit Exceeded errors. It is a true test of algorithmic optimization and hash collision management.

Algorithmic pattern used

To solve this optimally, you must use Binary Search on the Answer combined with a Rolling Hash (Rabin-Karp). Instead of searching blindly, you use binary search to guess the length of the common subpath. For a guessed length L, you compute the rolling hashes of all subpaths of length L in the first array, then check if at least one of those hashes exists in all subsequent arrays.

Example explanation

Suppose we have paths: [1, 2, 3, 4] [4, 1, 2, 3] [1, 2, 3, 5] We binary search for the longest length. The shortest path length is 4.

• Guess length L = 3.
• Array 1 subpaths of length 3: [1, 2, 3], [2, 3, 4]. We hash these.
• Array 2 subpaths of length 3: [4, 1, 2], [1, 2, 3]. We see the hash for [1, 2, 3] matches.
• Array 3 subpaths of length 3: [1, 2, 3], [2, 3, 5]. Hash for [1, 2, 3] matches here too! Since [1, 2, 3] is in all arrays, length 3 is possible. We would then try to guess a larger length (like 4). Since [1, 2, 3, 4] isn't in array 3, 4 fails. The maximum length is 3.

Common mistakes candidates make

The biggest obstacle is hash collisions. Because the arrays can be very long and the values very large, using a single rolling hash with a standard modulus will inevitably result in two different subpaths producing the same hash, leading to false positives. Candidates often fail because they don't implement a Double Hash (hashing with two different prime moduli) or fail to double-check collisions when a hash match is found.

Interview preparation tip

If you encounter the Longest Common Subpath interview pattern, you need to be extremely confident with the Rabin-Karp algorithm. Practice writing a clean Rolling Hash function that updates in $O(1)$ time as a window slides across an array. Understand how to manage large prime numbers to minimize collisions, as this is the crux of making the binary search approach viable.