Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

<pre lang="" line="1" title="CodeMonkey68374" class="run-this">#include<iostream>

using 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>

- Anonymous November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- abc November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sanjay.2812 November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- abc November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) finding minimum for rows
O(n) finding maximum for columns
O(n) checking if min and max the same

- Rayden November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the question is what is the n in O(n)?

- abc November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Learner November 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rayden: O(n) finding minimum for rows? how is this possible?

is it not O(n2).

for(each row) {
//process each column
for(col 0-n-1) {
check if smaller than alreay chosen element.
}
}

correct me if a non-naive approach exist

- Somisetty November 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- kalyan359 February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, could you please tell me how did we calculate the complexity for this algorithm that you have written?

- Charu July 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you sure that the example's answer is correct?

I guess the position must be (1,3)

- rajeshkumar.a November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad it is (1,3)

- fchristopher239 November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There was an erroneous statement in the above program. Uploading the corrected one.

Changed to maxInRow = matrix[i][0]; from MaxInRow = matrix [0][i];

- Vinod Varma December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- SuperK December 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude you are using nested for loop.. how come the complxity is O(n)?... its O(n*n)....

- Venki January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL ho my.. are you kidding me?

this is double dimension matrix.. row*col = number of elements which is O(n).

- Anonymous January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Venki January 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry dude... its O(n) only... my bad

- Venki January 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Venki, how did you figure it out to be O(n)? I still don't quite understand why it is not O(n^2).

- Anonymous June 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does anyone think there can be more than 1 number in a 2d array that satisfies the given condition?. I tried with some math equations, I see that its not possible to have more than one.

- kurra.nani January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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();
}

- desmond February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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();
}

- desmond February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- Anjana April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- salt22 August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- @123 August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- coderm December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That answer (2,2) is actually wrong! the coordinates of 3 is (0,2)

- Kachi August 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

- Shashank January 22, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More