## Google Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)).

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node {
public:
~Node()
{
for (auto &c : children_) {
delete c.second;
}
}
Node *Child(int k) const
{
auto it = children_.find(k);
return it != children_.end() ? it->second : NULL;
}
{
Node *n = Child(k);
if (!n) {
children_[k] = n = new Node();
}
return n;
}

private:
unordered_map<int, Node *> children_;
};

class Trie {
public:
Node *Root()
{
return &root_;
}

private:
Node root_;
};

pair<int, int> LargestCommonSubarray(vector<int> const &a1, vector<int> const &a2)
{
Trie trie;

for (int i = 0; i < a2.size(); ++i) {
Node *n = trie.Root();
for (int j = i; j < a2.size(); ++j) {
}
}

pair<int, int> out;
int max_size = 0;
for (int i = 0; i < a1.size(); ++i) {
Node *n = trie.Root();
int size = 0;
for (int j = i; j < a1.size(); ++j) {
n = n->Child(a1[j]);
if (!n) {
break;
}
if (++size > max_size) {
max_size = size;
out = pair<int, int>(i, i + size - 1);
}
}
}
return out;
}

int main()
{
auto out = LargestCommonSubarray({1, 2, 3, 4, 5}, {2, 3, 4, 5, 6});
cout << out.first << " -> " << out.second << "\n";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.