Google Interview Question
SDE1sCountry: United States
If we have only 2 arrays, this is another example of KMP pattern searching. The answer can be found in O(n):
function findLongestSuffixPrefix(nums1, nums2) {
return Math.max(
findLongestSuffix(nums1, nums2),
findLongestSuffix(nums2, nums1));
}
function findLongestSuffix(nums1, nums2) {
var tf = buildTf(nums2);
var state = 0;
for (var i = 0; i < nums1.length; i++) {
state = tf[state].get(nums1[i]) || 0;
}
return state;
}
function buildTf(nums) {
var result = [];
var lps = -1;
for (var i = 0; i <= nums.length; i++) {
result[i] = lps >= 0 ? new Map(result[lps]) : new Map();
if (i < nums.length) {
result[i].set(nums[i], i + 1);
lps = lps >= 0 && result[lps].get(nums[i]) || 0;
}
}
return result;
}
2d matrix is harder as you will need to split the second matrix into multiple rows, finding 1 row in the first matrix is O(n^2), finding k rows in the first matrix is O(kn^2), or max O(n^3).
O(n) using longest prefix which is also a suffix KMP algo
#include <iostream>
using namespace std;
int GetValue(int* a, int* b, int m, int n, int index)
{
if(index < n)
{
return b[index];
}
else
{
return a[index-n];
}
}
void FindSubfixPrefix(int* a, int* b, int m, int n)
{
int lps[m+n];
lps[0] = 0;
for(int i=1; i<m+n; i++)
{
int length = lps[i-1];
while(length > 0)
{
if(GetValue(a, b, m, n, length) == GetValue(a, b, m, n, i))
{
lps[i] = length + 1;
break;
}
else
{
length = lps[length-1];
}
}
if(length == 0)
{
if(GetValue(a, b, m, n, 0) == GetValue(a, b, m, n, i))
{
lps[i] = 1;
}
else
{
lps[i] = 0;
}
}
}
int result = lps[m+n-1];
if(result > m || result > n)
{
result = m < n ? m : n;
}
for(int i=0; i<result; i++)
{
cout<<b[i]<<" ";
}
}
int main() {
int n;
int m;
cin>>m;
cin>>n;
int a[m];
int b[n];
for(int i=0; i<m; i++)
{
cin>>a[i];
}
for(int i=0; i<n; i++)
{
cin>>b[i];
}
FindSubfixPrefix(a, b, m, n);
}
For arrays we can use a trie (the code below). O(n^2 + m * n) time and O(min(n, m)^2) space.
In case of a 2d array, I assume we are looking for the largest common rectangle. We can use sum of the rectangle values as a hash. For each cell, we can find the sum of values of rectangle with upper left corner 0,0, and lower right corner at the cell, for O(n*m) time. Then, we iterate through each rectangle in Matrix 1 in O(n1*m1*min(n1, m1)) time. For each rectangle we find sum of its values in O(1) time (using the precomputed sums of rectangles starting from 0,0), and append a hashmap at key = sum with coordinates fo the rectangle.
In Matrix 2 we iterate through all rectangles and get from the hashmap possible matches.
The worst case time is O(m1 * n1 * min(m1, n1) * n2 * m2), but the expected time feels like O(m1 * n1 * min(m1, n1)).
- Alex December 07, 2017