Google Interview Question
Java DevelopersCountry: United States
#include <iostream>
#include <vector>
//Author = Jean
bool isSubMatrix(const std::vector<std::vector<int>>& small, const std::vector<std::vector<int>>& large){
int sizeYLarge = large.size();
int sizeXLarge = large[0].size();
int sizeYSmall = small.size();
int sizeXSmall = small[0].size();
int li,lj,si,sj;
for (li = 0 ; li < sizeXLarge ; li++){
for (lj = 0 ; lj < sizeYLarge ; lj++){
if (large[li][lj] == small[0][0]){
for (si = 0 ; si< sizeXSmall ; si ++){
for (sj = 0 ; sj < sizeYSmall ; sj++) {
std::cout<<"large "<<large[si+li][sj+lj]<<"small "<<small[si][li]<<std::endl;
if (large[si+li][sj+lj]!=small[si][sj]){
break;
}
}
}
}
}
}
if (si == sizeXSmall && sj == sizeYSmall)
return true;
return false;
}
main (){
std::vector<std::vector<int>> large={{1 ,2 , 3},
{4 ,5 , 6},
{7 ,8 , 9},
{10,11, 12}};
std::vector<std::vector<int>> small={{5, 6},
{8,10}};
std::cout<<isSubMatrix(small,large);
}
#include <iostream>
#include <vector>
//Author = Jean
bool isSubMatrix(const std::vector<std::vector<int>>& small, const std::vector<std::vector<int>>& large){
int sizeYLarge = large.size();
int sizeXLarge = large[0].size();
int sizeYSmall = small.size();
int sizeXSmall = small[0].size();
int li,lj,si,sj;
for (li = 0 ; li < sizeXLarge ; li++){
for (lj = 0 ; lj < sizeYLarge ; lj++){
if (large[li][lj] == small[0][0]){
for (si = 0 ; si< sizeXSmall ; si ++){
for (sj = 0 ; sj < sizeYSmall ; sj++) {
std::cout<<"large "<<large[si+li][sj+lj]<<"small "<<small[si][li]<<std::endl;
if (large[si+li][sj+lj]!=small[si][sj]){
break;
}
}
}
}
}
}
if (si == sizeXSmall && sj == sizeYSmall)
return true;
return false;
}
main (){
std::vector<std::vector<int>> large={{1 ,2 , 3},
{4 ,5 , 6},
{7 ,8 , 9},
{10,11, 12}};
std::vector<std::vector<int>> small={{5, 6},
{8,10}};
std::cout<<isSubMatrix(small,large);
}
Here is O(n * m * k) or slightly faster than O(n^3) implementation using Finite Automata based on kmp, it is actually not very hard and described in the article "Pattern Searching | Set 6 (Efficient Construction of Finite Automata)".
O (n * m * k) space. It requires some space, but O(n^3) is faster than O(n^4) from the comments above.
But I expect that even O(n^3) isn't the ideal answer, I think the proper answer requires using Rabin-Karp algorithm, it is much harder to implement though.
var matrix = [
[1,1,1,1,2],
[1,1,1,1,2],
[1,1,1,1,2],
[1,1,1,2,2],
];
var smallMatrix = [
[1,1],
[1,2],
];
findMatrix(matrix, smallMatrix); // i: 2, j: 2
function findMatrix(matrix, smallMatrix) {
var calculatedStates = [];
for (var k = 0; k < smallMatrix.length; k++) {
calculatedStates[k] = [];
// build state machine for each row of small matrix
var tf = buildTf(smallMatrix[k]);
for (var i = 0; i < matrix.length; i++) {
calculatedStates[k][i] = [];
var state = 0;
for (var j = 0; j < matrix[i].length; j++) {
// state is how many numbers of smallMatrix[k]
// are matched at (i,j)
state = tf[state].get(matrix[i][j]) || 0;
calculatedStates[k][i][j] = state;
}
}
}
for (var i = 0; i < matrix.length; i++) {
for (var j = 0; j < matrix[i].length; j++) {
var matchingRows =
getMatchingRows(i, j, calculatedStates, smallMatrix);
if (matchingRows == smallMatrix.length) {
return {i: i, j: (j - smallMatrix[0].length + 1)};
}
}
}
return {i: -1, j: -1};
}
function getMatchingRows(i, j, calculatedStates, smallMatrix) {
for (var k = 0; k < smallMatrix.length &&
i + k < calculatedStates[k].length; k++) {
if (calculatedStates[k][i + k][j] != smallMatrix[k].length) {
return k;
}
}
return smallMatrix.length;
}
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;
}
- Anonymous February 12, 2018