Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
1. Search min for rows - O(N^2)
2. Search max for columns - O(N^2)
3. Check if exist i such max=min[i] - it works because we have matrix with unique integers - O(N^2)
-------------------------------------------------
so it works in O(N^2)
how its order on N^2 man... you can find min and max in the order of N ..
we need to handle also condition id no element in the matrix is setisfing the given condition.
input is matrix NxN. It is N^2 because I am looking for min/max in each column/row. Each row/column has N elements.
N rows/columns x N elements in row/column = N^2
O(n) finding minimum for rows
O(n) finding maximum for columns
O(n) checking if min and max the same
N here should be referred to the same value as given in question, i.e. N=number of rows=number of columns.
People suggesting O(N) solution are assuming N to be all the elements of the matrix.
Hi all,
Here is a simple solution for this problem.
step1: Identify minimum value present in each row. This takes O(n) time for 1 row.Store the column number and least value in a Table.
step 1.1: If you encounter a column number being repeated, store the minimum value for that the column.
Step 2: Now, we have a column and its corresponding value. Check to see if the value is the least value in the column, if yes. Print it as out put, else display "such number do not exist".
So total run time of Algorithm is O(n^2)
<pre lang="" line="1" title="CodeMonkey49039" class="run-this">#include<iostream>
#include<iomanip>
using namespace std;
void main()
{
short matrix[10][10],rows,i,j,maxInRow,minCol,minColx,minColy,k,maxRowCol;
bool flag = false;
cout <<"Enter the Row size or Column Size << Square Matrix They Are Equal >> :";
cin >> rows;
cout <<"Enter " << rows * rows <<" values in to the matrix " << endl;
for ( i = 0; i < rows; i++)
{
for ( j = 0; j < rows; j++)
{
cin >> matrix[i][j];
}
}
system("cls");
cout <<"Printing the Matrix " << endl;
for ( i = 0; i < rows; i++ )
{
for ( j = 0; j < rows; j++ )
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
//Calculating the biggest in row and smallest in column
for ( i = 0; i < rows; i++ )
{
maxInRow = matrix[0][i];
maxRowCol = 0;
//minCol = matrix[i][0];
for ( j = 0; j < rows; j++)
{
if ( matrix[i][j] > maxInRow )
{
maxInRow = matrix[i][j];
maxRowCol = j;
}
}
//now checking whether the maximum value for each row is smaller in the same column
minCol = 32767;
for ( k = 0; k < rows; k++)
{
if ( minCol > matrix [k][maxRowCol] )
{
minCol = matrix[k][maxRowCol];
minColx = k;
minColy = maxRowCol;
}
}
if ( minCol == maxInRow )
{
flag = true;
cout<<"("<<minColx<<", "<<minColy<<") => " << minCol <<endl;
}
}
if (!flag)
{
cout << "There is no such number in the matrix " << endl;
}
system("pause");
exit(0);
}
</pre><pre title="CodeMonkey49039" input="yes">1 2 3
4 5 6
7 8 9
(0 , 2 ) ==> 3
10 9 8
7 6 5
4 3 2
There is no such element
10 9 8
11 6 5
12 4 3
(0 , 0) == > 10
</pre>
<pre lang="" line="1" title="CodeMonkey96874" class="run-this">public static void main(String[] args) {
setMatrix();
int minRow = 0;
int[] maxCol = new int[matrix.length];
int rowI = 0;
int rowJ = 0;
int[] colI = new int[matrix.length];
int[] colJ = new int[matrix.length];
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix[i].length; ++j) {
if(j == 0) {
minRow = matrix[i][j];
rowI = i; rowJ = j;
} else {
if(minRow > matrix[i][j]) {
minRow = matrix[i][j];
rowI = i; rowJ = j;
}
}
if(i == 0) {
maxCol[j] = matrix[i][j];
colI[j] = i;
colJ[j] = j;
} else {
if(maxCol[j] < matrix[i][j]){
maxCol[j] = matrix[i][j];
colI[j] = i;
colJ[j] = j;
}
}
}
System.out.println(minRow + " [i] : " + rowI + " [j] : " + rowJ);
}
for(int i = 0; i < matrix.length; ++i) {
System.out.println(maxCol[i] + " " + colI[i] + " " + colJ[i]);
}
}
It works clearly. total complexity is O(n).</pre><pre title="CodeMonkey96874" input="yes">
</pre>
LOL ho my.. are you kidding me?
this is double dimension matrix.. row*col = number of elements which is O(n).
lol..... dude its does not matter whether youa are accessing a double dimensional matrix or thrible dimensional matrix... you are using two nested for loops with constant range from 0 to n...so the order is O(n*n)...
you are not accessing n elements for the whole problem,to solve the problem this way you have to look at the entire data set before coming to a conclusion, in this case of an NXN matrix, there will be n^2 elements, so it is O(n^2)
#include <iostream>
using namespace std;
void findSaddle()
{
int n = 4;
int matrix[n][n];
for(int i = 0; i < n ;++ i)
{
for (int j = 0 ; j < n ; ++ j)
{
matrix[i][j] = 17-i-j;
cout<<" "<<matrix[i][j];
}
cout<<endl;
}
int max = 0;
int index;
bool flag;
for(int i = 0 ; i < n ; ++ i )
{
max = 0;
flag = 1;
for(int j = 0; j < n ; ++ j)
{
if(matrix[i][j] > max)
{
max = matrix[i][j];
index = j;
}
}
for (int k = 0; k < n ; ++ k)
{
if(matrix[k][index] < max )
flag = 0;
}
if(flag == 1)
{
cout<<"i="<<i<<" j="<<index<<endl;
return;
}
}
cout<<"not found"<<endl;
}
int main()
{
findSaddle();
}
#include <iostream>
using namespace std;
void findSaddle()
{
int n = 4;
int matrix[n][n];
for(int i = 0; i < n ;++ i)
{
for (int j = 0 ; j < n ; ++ j)
{
matrix[i][j] = 17-i-j;
cout<<" "<<matrix[i][j];
}
cout<<endl;
}
int max = 0;
int index;
bool flag;
for(int i = 0 ; i < n ; ++ i )
{
max = 0;
flag = 1;
for(int j = 0; j < n ; ++ j)
{
if(matrix[i][j] > max)
{
max = matrix[i][j];
index = j;
}
}
for (int k = 0; k < n ; ++ k)
{
if(matrix[k][index] < max )
flag = 0;
}
if(flag == 1)
{
cout<<"i="<<i<<" j="<<index<<endl;
return;
}
}
cout<<"not found"<<endl;
}
int main()
{
findSaddle();
}
import java.util.ArrayList;
public class MinMaxOfMatrix {
/**
* @param args
*/
public static ArrayList<Integer> getRowStatus(int[][] array, int rowCount,int colCount)
{
ArrayList<Integer> minPosList = new ArrayList<Integer>();
for(int row =0; row<rowCount;row++)
{
int max = Integer.MIN_VALUE;
int pos=0;
for(int col = 0; col<colCount;col++)
{
int value = array[row][col];
if(value>max)
{
max = value;
pos = col;
}
}
int index = 2*row;
minPosList.add(index,max);
minPosList.add(index+1,pos);
}
return minPosList;
}
public static ArrayList<Integer> getColStatus(int[][] array, int rowCount,int colCount)
{
ArrayList<Integer> minPosList = new ArrayList<Integer>();
for(int col =0; col<colCount;col++)
{
int min = Integer.MAX_VALUE;
//int pos=0;
for(int row = 0; row<rowCount;row++)
{
int value = array[row][col];
if(value<min)
{
min = value;
//pos = col;
}
}
minPosList.add(col,min);
//minPosList.add(index+1,pos);
}
return minPosList;
}
public static void printMinMax(int[][] array,int numRow, int numCol)
{
ArrayList<Integer> rowMax = getRowStatus(array,numRow,numCol);
ArrayList<Integer> colMax = getColStatus(array,numRow,numCol);
int index = 0;
for(Integer min: colMax)
{
for(int posPresent=1;posPresent<rowMax.size();posPresent=posPresent+2)
{
if(rowMax.get(posPresent)==index && rowMax.get(posPresent-1)==min)
{
System.out.println(rowMax.get(posPresent-1)+" "+(posPresent-1)+" "+index);
}
}
index++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] array = {{1,2,3},{4,5,6},{7,8,9}};
printMinMax(array,3,3);
}
}
#include <iostream>
using namespace std;
#define N 4
#define max(a,b) a>b?a:b;
#define min(a,b) a<b?a:b;
int main(){
int mat[N][N]={7,8,3,4,9,11,12,5,2,15,6,14,21,10,1,16};
int imax[N], jmin[N];
for(int i=0; i<N; i++){
imax[i]=0;
jmin[i]=999999;
}
for(int i=0; i<N; i++)
for(int j=0; j<N; j++){
if(mat[j][i] < jmin[i]) jmin[i] = mat[j][i];
imax[i] = max( mat[i][j], imax[i]);
}
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(imax[i] == jmin[j])
cout<<i<<" "<<j<<endl;
return 0;
}
#include<stdio.h>
main()
{ int i,j,a[10][10],n,s=0,tmp=-26987,t=456789,l,k,m=100000,p;
printf("Enter the value of n\n");
scanf("%d",&n);
printf("Enter the elements\n");
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf("%d",&a[i][j]);
for(i=0;i<n;i++)
{ for(j=0; j<n;j++)
{ if(tmp<a[i][j])
{ tmp=a[i][j]; l=j; }
}
printf("The higest elment is %d\n",tmp);
for(k=0; k<n; k++)
{ if(t>a[k][l])
t=a[k][l];
}
printf("The smallest element is %d\n",t);
if(m>t)
m=k;
}
printf("The required element is %d\n",m);
}
//SADDLE POINT or Given an NxN matrix with unique integers : Find and print positions of all numbers such that it is the biggest in its row and also the smallest in its collumn .
#include<iostream>
using namespace std;
#define n 3
int findsaddlepoint(int a[][n],int r)
{
int i,j,max,min,count=0,count1=0,rmax[r],cmax[n];
for(i=0;i<r;i++)
{
max=a[i][0];
for(j=0;j<n;j++)
{
if(max<a[i][j])
max=a[i][j];
}
rmax[count++]=max;
}
for(i=0;i<n;i++)
{
min=a[0][i];
for(j=0;j<r;j++)
{
if(min>a[i][j])
min=a[i][j];
}
cmax[count1++]=min;
}
// cout<<"row wise greater";
//for(i=0;i<count;i++)
//cout<<rmax[i];
//cout<<"col wise smaller";
//for(i=0;i<count1;i++)
//cout<<cmax[i];
//cout<<"solutions"<<"\n";
for(i=0;i<count;i++)
for(j=0;j<count1;j++)
if(rmax[i]==cmax[j])
cout<<"common point or saddle point is"<<rmax[i];
}
int main()
{
int a[][n]={{1,2,3},
{4,5,6},
{7,8,9},
};
findsaddlepoint(a,3);
int k;
cin>>k;
return 0;
}
Simple java code just copy paste and execute
public void bigRowSmallColumn(int[][] array){
int maxInRow=0;
int maxInRowCol=0;
int minInCol=999;
int minInColRow=0;
for(int i=0; i<array.length; i++){
for(int j=0; j<array[0].length; j++){
if(array[i][j] > maxInRow){
maxInRow = array[i][j];
maxInRowCol = j;
}
if(j==array[0].length-1){
// check if this number is min in column
for(int k=0; k<array.length; k++){
if(array[k][maxInRowCol] < minInCol){
minInCol = array[k][maxInRowCol];
minInColRow = k;
}
}
if(minInCol == maxInRow){
System.out.println(minInColRow+","+maxInRowCol);
}
else{
//reset values
minInCol = 999;
maxInRow = 0;
}
}
}
}
}
<pre lang="" line="1" title="CodeMonkey68374" class="run-this">#include<iostream>
- Anonymous November 23, 2011using namespace std;
int main()
{
int N=5;
int Mat[N][N];
int maxInRow[N];
int i=0;
int j=0;
int minCol=0;
int minX=0;
int minY=0;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
cin>>Mat[i][j];
}
}
//get min for rows
for(i=0;i<N;i++)
{
maxInRow[i]=Mat[0][i];
for(j=0;j<N;j++)
{
if(maxInRow[i]<Mat[i][j]) maxInRow[i]=Mat[i][j];
}
}
//find max for columns
for(i=0;i<N;i++)
{
minCol=Mat[i][0];
for(j=0;j<N;j++)
{
if(minCol>Mat[j][i]) {minCol=Mat[j][i];minX=j;minY=i;}
}
//NxN matrix with unique integers
for(int k=0;k<N;k++)
{
if(minCol==maxInRow[k])
cout<<"("<<minX+1<<", "<<minY+1<<") => " <<minCol<<endl;
}
}
return 0;
}
</pre><pre title="CodeMonkey68374" input="yes">
1 2 3 4 5
10 11 12 13 14 15
20 21 22 23 24 25
34 45 56 66 77 88
101 102 103 104 105</pre>