Amazon Interview Question Software Engineer / Developers
This is not correct
See the matrix below. Here the row and column matched for i=1 and j=2.
X X 1
1 2 2
X X 2
Pseudo Code:
Create a map that takes a string as key and vector<int> as data
For every row construct a string using the values. (for ex: "4:5:10:9:2:"
Check if your map already contains the key,
if yes then retrieve and add the row index
else insert a new item with this key and data as rowIndex
For every column construct a string using the values.
Check if your map contains the key
if yes then this column matches with all the indices in the 'data' for this key
else no rows exist that are same as this column
///Complexity: O(N^2 + N^2) => O(N^2)
#include <map>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
map<string, vector<int> > valStrings;
map<string,vector<int> >::iterator it;
string str;
int n = 4;
int matrix[][4] = { {2,2,2,15},
{2,2,5,5},
{15,5,2,2},
{15,5,2,2}};
vector<int> indxs;
for(int i=0;i<n;++i) //for every row
{
char bfr[4];
str="";
for(int j=0;j<n;++j){
sprintf(bfr,"%d",matrix[i][j]);
str.append(bfr);str.append(":");
}
it=valStrings.find(str);
if(it!=valStrings.end())
indxs = (*it).second;
indxs.push_back(i);
valStrings[str] = indxs;
indxs.clear();
}
for(int i=0;i<n;++i) //for every column find if there's a key already inserted
{
char bfr[4];
str="";
for(int j=0;j<n;++j){
sprintf(bfr,"%d",matrix[j][i]);
str.append(bfr);str.append(":");
}
it=valStrings.find(str);
if(it!=valStrings.end()){ //if key already exists then obtain row values
cout<<endl<<"Column "<<i<<" matches row(s) : ";
indxs = (*it).second;
for(int k=0;k<indxs.size();++k)
cout<<indxs[k]<<",";
indxs.clear();
}
}
}
//Column 1 matches row(s) : 1,
//Column 3 matches row(s) : 2,3,
@chennavari, i dont think it will work in O(n^2) because the comparing within the map which you are doing for the string obtained with each column, would take O(n^2) for each each column as the map created will have to match an entire string which is the key here.
So i think it will still be O(n^3).
Not n^3 but O(N^2*(logN))
Explanation:
The elements in a map are sorted and any operation for map takes logarithmic time.
Construction of Map:
Find operation takes logn because there are n strings.
But for finding, we need to match strings so matching operation takes n (because n elements in each row) total complexity of find operation = nlogn and for inserting = nlogn.
The first for loop runs n times and its inner loop runs n times, then find and insertion takes 2nlogn
total computations for constructing map=> n * (n + 2nlogn)
Searching if column matches any key in the map:
The same way computations => n * (n + nlogn)
Total complexity => O( (n*(n+2nlogn)) + (n*(n+nlogn)) ==> O(2n^2 + 3n^2(logn)) ==> O(n^2*(logn))
well naive solution is to check each row`s element with every column`s element . This will take o(n3) time. Can we do better than this ?
bool found = true;
for(int i = 0; i < n; i++)
{
for(int k = 0; k < n; k++)
{
for(int j =0; j < n; j++)
{
if(a[i][j] == a[j][k]) continue;
else
{
found = false;
break;
}
}
if(found)
return i;
}
}
Use prefix tree can solve this in nLog(n) time. Regard every number as a char, then every row and column is a string. Build prefix tree for all rows (nLog(n)), then for each column, traverse the prefix tree to check if the column is contained (nLog(n)).
sry am kind of lost.. there are n rows, and for every row, if you construct a string then you are accessing n elements. just for accessing elements would take O(n^2). how would you build a tree from n^2 elements in less than n^2? just accessing each element would take n^2. I believe you meant to say, O(n^2 * Log(n^2))??
I think it can be solved less than O(n^2) building up on chennavari's solution
1. Go through first column and add all the elements to a hash table. The element being the key and the row numbers being the values.
2. Go through the first row of elements and find if there is an entry for that element in the hash table. If there is, more than one row numbers for that key value(means there were more than one occurance of an element in the 1st column in step 1). Take one at a time.
3. Now compare the entire column corresponding to the element from the first row and the row corresponding to the entry from the hash table.
4. Repeat this process untill you find a match for all elements in a given row and a given column.
If I understand the question properly the row and column should be exact replicas. In which I clearly see a pattern.
When I am considering a column I need not check for all the rows.
x a x x x
y b y y y
x c x x x
x d x x x
x e x x x
A bit of optimization can be done. Given that your column doesnt have side by side repetitions, you can see that you in trying to match the column 'a b c d e' you will just have to concentrate on row 2 'y b y y y' otherwise you will never get an exact match. In this case you can finish your check in O(N). But if there are side by side repetitions as 'a a a b c' then yes you may have to check for the other columns. But even there you can eliminate some cases.
But if the order is not important then yes we will have to check for everything.
Make numbers by using every elements in the row in array row[]. Similarly convert coloum elements into numbers and put them in array col[]. Now compare both the arrays where the number matches print the index of both row[] and col[] array...
eg:-
2, 3, 4
3, 4, 5
6, 5, 1
col[] contains 236, 345, and 451 and row[] contains 234, 345, and 651. On Comparison both has 345 as common total with index (1,1) and is the desired answer.
On a second thought it looks lame.
1 21 3
2 3 5
13 9 20
Your solution will match 1st row and column :(
How about if we sum all the numbers in a row and do the same for columns? Then we only look at the rows and the columns where the sum is the same?
I will make a Trie out of the rows of the array such that the root of the Trie is null. Next level contains the first element of the rows, so on and so forth. Construction will take O(n^2) <--- Am I right?
Next Match each column in the Trie. (Each column will take O(n)). Total Matching -> O(n^2).
So, Overall complexity -> O(n^2) + O(n^2) = O(n^2)
void rowColumnMatch (int matrix[][], int n)
{
int k = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][k] == matrix[k][j])
findRowCol (matrix, i, j);
}
}
}
void findRowCol (int matrix[][], int i, int j)
{
for (k = 0; k < n; k++)
{
if (matrix[i][k] == matrix[k][j])
continue;
else
break;
}
if (k == n)
{
for (int k = 0; k < n; k++)
printf("%d",matrix[i][k]);
}
}
How about divide and conquer?
RCEQUAL(A,i1..12,j1..j2)// A is n*n matrix
if(i2-i1==2 && j2-j1==2 && b[n*i1+1..n*i2] has [j1..j2])
use brute force to check if the rows and columns are same.
if (any rows and columns are same)
store the row and column numbers in b[1..n^2].//b[1],b[n+1],b[2n+1] store row no, others col #.
else
RCEQUAL(A,1..n/2,1..n/2);
RCEQUAL(A,n/2..n,1..n/2);
RCEQUAL(A,1..n/2,n/2..n);
RCEQUAL(A,n/2..n,n/2..n);
wrong
- chennavarri November 06, 2010