Find the Length of the Longest Common Prefix

Find the Length of the Longest Common Prefix

What is this problem about?

The Find the Length of the Longest Common Prefix interview question involves two arrays of positive integers, arr1 and arr2. You need to find the longest common prefix shared between any number from arr1 and any number from arr2. A prefix is the leading part of a number (e.g., the prefixes of 123 are 1, 12, and 123). You want to return the length of the longest such prefix.

Why is this asked in interviews?

This "Medium" difficulty problem is popular at companies like Uber, Databricks, and Meta. it's a test of your ability to perform efficient string or number matching. While you could compare every pair ($O(n^2)$), the problem challenges you to find an $O(n)$ or $O(n \log n)$ solution using a Trie interview pattern or a Hash Set of all possible prefixes.

Algorithmic pattern used

There are two effective patterns:

1. Hash Set of Prefixes:
   • Iterate through arr1. For each number, generate all its prefixes (e.g., 123 $o$ 1, 12, 123) and add them to a HashSet.
   • Iterate through arr2. For each number, check its prefixes from longest to shortest.
   • The first prefix found in the HashSet is a candidate for the longest common prefix.
2. Trie (Prefix Tree):
   • Insert every number from arr1 into a Trie (treating them as strings).
   • For each number in arr2, traverse the Trie to see how deep you can go. The depth reached is the length of the common prefix.

Example explanation

arr1 = [123, 456], arr2 = [12, 45]

1. arr1 prefixes: {1, 12, 123, 4, 45, 456}.
2. Check 12 from arr2:
   • Prefixes: 12 (exists), 1. Max length so far = 2.
3. Check 45 from arr2:
   • Prefixes: 45 (exists), 4. Max length so far = 2. Result: 2.

Common mistakes candidates make

• Brute Force: Comparing every $x$ in arr1 with every $y$ in arr2, resulting in $O(N imes M imes ext{digits})$, which will time out.
• Inefficient prefix generation: Using string conversion inside a loop instead of mathematical division (num /= 10).
• Off-by-one: Counting the number of characters incorrectly.

Interview preparation tip

When searching for "Common Prefixes," always consider a Trie. Even if a Hash Set is easier to implement, mentioning a Trie shows you understand the data structure specifically designed for prefix operations.