Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
Nice thought, i have written a c++ code according to your algorithm
#include <iostream>
using namespace std;
void Saddle_points( int ** , int rows);
int main ()
{
int rows,columns;
cout<<"Enter the rows/columns of the square matrix"<<endl;
cin>>rows;
columns =rows;
int **a= new int*[rows];
//Allocate memory for each column
for(int i=0;i<rows;i++)
a[i] = new int[columns];
cout<<"Enter elements"<<endl;
for(int i = 0; i < rows; i++)
for(int j = 0; j < rows; j++)
cin>>a[i][j];
Saddle_points(a,rows);
//Deallocate memory
for(int i = 0;i<rows;i++)
delete []a[i];
delete [] a ;
return 0;
}
void Saddle_points( int **a, int rows)
{
int max=0,min=0;
int *row_max = new int[rows];
int *column_min = new int[rows];
// Maximum in each row
for(int j=0;j<rows;j++)
{
max = a[j][0];
for(int i=0;i<rows;i++)
{
if(max <a[j][i])
max = a[j][i];
}
row_max[j] = max;
}
//Minimum in each row
for(int i=0;i<rows;i++)
{
min = a[0][i];
for(int j=0;j<rows;j++)
{
if(min >a[j][i])
min = a[j][i];
}
column_min[i] = min;
}
//Check for common elements
for(int i=0;i<rows;i++)
if(row_max[i] == column_min[i] )
cout<<"Saddle point : "<<row_max[i]<<endl;
delete []row_max;
delete []column_min;
}
good algo...just need a correction in printing the saddle point
for(int i=0;i<rows;i++)
{
for(int j=0;j<rows;j++)
if(row_max[i] == column_min[j] )
cout<<"Saddle point : "<<row_max[i]<<endl;
}
To my understanding, this is a correct definition of saddle point. It shouldn't be the "largest" in the row, but "larger" than its two neighbor. The question should be not exactly correct. Am I right?
Problem in this implementation is that: it considers numbers in matrix are unique. what if there are duplicate numbers?
Maq,the worst case goes n*n*logn ,, consider the nxn matrix comprising of all 1s .... isn't it?
your idea is good, but the last step of finding the saddle point is totally wrong. Finding the same value doesn't mean the same point, you need to compare the position (x, y) of the candidate points.
Also, you compare two arrays element by element, that you assume the min and max appear in the same sequence, which is absolutely wrong.
Think about example
2, 3, 1
4, 5, 6
9, 8, 7
the max array of rows is: 3, 6 ,9
the min array of cols is: 2, 3, 1
3 is the saddle point, however, your algorithm can't find that
I was trying to explain my idea, so I attached my code here. This would be more persuasive.
package EPIC;
class IntPair {
public int x;
public int y;
public IntPair(int X, int Y) {
x = X;
y = Y;
}
@Override
public boolean equals(Object other) {
IntPair that = (IntPair) other;
return this.x == that.x && this.y == that.y;
}
}
public class SaddleNumber {
public static void findSaddle(int I[][]) {
if (I == null) {
return;
} else if (I.length == 0) {
return;
}
int height = I.length;
int width = I[0].length;
IntPair max_row[] = new IntPair[height];
IntPair min_col[] = new IntPair[width];
for (int row = 0; row < height; row++) {
int max = I[row][0];
IntPair maxpair = new IntPair(row, 0);
for (int col = 0; col < width; col++) {
if (I[row][col] > max) {
max = I[row][col];
maxpair.x = row;
maxpair.y = col;
}
}
max_row[row] = maxpair;
}
System.out.println("Maxrow");
for (int j = 0; j < max_row.length; j++) {
System.out.println(max_row[j].x + ", " + max_row[j].y);
}
for (int col = 0; col < width; col++) {
int min = I[0][col];
IntPair minpair = new IntPair(0, col);
for (int row = 0; row < height; row++) {
if (I[row][col] < min) {
min = I[row][col];
minpair.x = row;
minpair.y = col;
}
}
min_col[col] = minpair;
}
System.out.println("mincol");
for (int j = 0; j < min_col.length; j++) {
System.out.println(min_col[j].x + ", " + min_col[j].y);
}
for (int row = 0; row < max_row.length; row++) {
for (int col = 0; col < min_col.length; col++) {
if (max_row[row].equals(min_col[col])) {
System.out.println("x: " + max_row[row].x + ", y: "
+ max_row[row].y + " value: "
+ I[max_row[row].x][max_row[row].y]);
}
}
}
}
public static void main(String[] args) {
// int input[][] = {
// { 9, 6, 8, 11 },
// { 7, 3, 1, 32 },
// { 10, 2, 5, 22 },
// { 12, 4, 2, 5 }
// };
int input[][] = {
{ 2, 3, 1},
{ 4, 5, 6},
{ 9, 8, 9 },
};
findSaddle(input);
}
}
static public void printSaddlePoint(int[][] input){
int numRow = input.length();
int numCol = input[0].length();
int[numRow] maxRowIdx;
int[numCol] minColIdx;
int[numCol] minColVal;
for (int j=0; j<numCol; ++j){minColVal[j] = Integer.MAX_VALUE;}
for (int i=0; i<numRow; ++i){
int tempMinVal = Integer.MIN_VALUE;
for (int j=0; j<numCol; ++j){
if (input[i][j] > tempMinVal){
maxRowIdx[i] = j;
tempMinVal = input[i][j];
}
if (input[i][j] < minColVal[j]){
minColIdx[j] = j;
minColVal[j] = input[i][j];
}
}
}
for (int i=0; i<numRow; ++i){
if (maxColIdx[maxRowIdx[i]] == i){
System.out.println("Saddle point found at Row: " + i + ", Col: " + j + ";" );
}
}
}
void saddlePoint(int num[][]){
int maxRow[], minCol[] = int num[0].length;
//find the max of each row
for(i=0;i<n;i++){
int max=num[i][0];
for(j=0;j<n;j++){
if(num[i][j]>max) max = num i j;
//similarly for j first and then i, find min;
syso(“saddle points are:”);
for(i=0;i<n;i++){
if(min[i]=max[i]) syso min[i];
}
}
The Code below do not consider repeated numbers cases. If it's taken into consideration, we should store both value and index of max in row, min in column, then check the two arrays' items value whether equal, if equal then check index, which is much complexed.
public final static int N=5;
public static void main(String args[]){
int[][] matrix= new int[N][N];
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
matrix[i][j]=(int) (1000*Math.random());
System.out.print(matrix[i][j]+",");
if(j==N-1)
System.out.println();
}
ArrayList<Integer> al= new ArrayList<Integer>();
al=SaddleNumber(matrix);
for(int i=0;i<al.size();i++){
int rowValue=(int)al.get(i)/N;
int columnValue=(int)al.get(i)%N;
System.out.println("Row: "+rowValue+" Column: "+columnValue+" Value: "+matrix[rowValue][columnValue]);
}
}
private static ArrayList<Integer> SaddleNumber(int[][] matrix) {
// TODO Auto-generated method stub
ArrayList<Integer> al = new ArrayList<Integer>();
int[] rowMax= new int[N];
int[] columnMin= new int[N];
for(int i=0;i<N;i++)
{
rowMax[i]=0;
for(int j=0;j<N;j++)
{
if(matrix[i][rowMax[i]]<matrix[i][j])
rowMax[i]=j;
}
}
for(int i=0;i<N;i++)
{
columnMin[i]=0;
for(int j=0;j<N;j++)
{
if(matrix[columnMin[i]][i]>matrix[j][i])
columnMin[i]=j;
}
}
for(int i=0;i<N;i++){
if(i==columnMin[rowMax[i]]) {
int index=i*N+rowMax[i];
al.add(index);
}
}
return al;
}
Stupid brutal force way.. taking duplicated max values situation into account:
public static void saddlePointComplete(int[][] matrix){
int N = matrix.length; // row num
int M = matrix[0].length; // col num
int maxRowVal[] = new int[N];
int minColVal[] = new int[M];
for(int i = 0; i<N; ++i){maxRowVal[i] = Integer.MIN_VALUE;}
for(int j = 0; j<M; ++j){minColVal[j] = Integer.MAX_VALUE;}
for (int i=0; i<N; ++i){
for (int j=0; j<M; ++j){
if (matrix[i][j] > maxRowVal[i]){
maxRowVal[i] = matrix[i][j];
}
if (matrix[i][j] < minColVal[j]){
minColVal[j] = matrix[i][j];
}
}
}
HashMap<Integer, ArrayList<Integer> > maxColIdxListMap = new HashMap<Integer, ArrayList<Integer> >();
HashMap<Integer, ArrayList<Integer> > minRowIdxListMap = new HashMap<Integer, ArrayList<Integer> >();
ArrayList<Integer > bufArray = null;
for(int i=0; i<N; ++i){
bufArray = new ArrayList<Integer>();
for(int j=0; j<M; ++j){
if (matrix[i][j] == maxRowVal[i]){
bufArray.add(new Integer(j));
}
}
maxColIdxListMap.put(new Integer(i), bufArray);
}
for(int j=0; j<M; ++j){
bufArray = new ArrayList<Integer>();
for(int i=0; i<N; ++i){
if (matrix[i][j] == minColVal[j]){
bufArray.add(new Integer(i));
}
}
minRowIdxListMap.put(new Integer(j), bufArray);
}
ArrayList<Integer > bufArray2 = null;
for(int i=0; i<N; ++i){
bufArray = maxColIdxListMap.get(new Integer(i));
for (int j=0; j<bufArray.size(); ++j){
bufArray2 = minRowIdxListMap.get(bufArray.get(j));
for (int k=0; k<bufArray2.size(); ++k){
if (minRowIdxListMap.get(bufArray.get(j)).get(k).intValue() == bufArray.get(j).intValue()){
System.out.println("#Saddle Point found at: (["+ i +"],["+ bufArray.get(j).intValue() +"])");
}
}
}
}
}
Used maps to avoid duplicate calculation of max and min of each row and column respectively.
import java.util.HashMap;
import java.util.Map;
public class MatrixSaddle {
private static final int[][] arr = {{9, 6, 8}, {7, 3, 1}, {10, 2, 5}, {12, 4, 2}};
private static final Map<Integer, Integer> rowMax = new HashMap<Integer, Integer>();
private static final Map<Integer, Integer> colMin = new HashMap<Integer, Integer>();
private static int getMaxInRow(int rowId) {
Integer lookup = rowMax.get(rowId);
if (lookup != null) {
return lookup;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr[rowId].length; i++) {
if (arr[rowId][i] > max) {
max = arr[rowId][i];
}
}
rowMax.put(rowId, max);
return max;
}
private static int getMinInCol(int colId) {
Integer lookup = colMin.get(colId);
if (lookup != null) {
return lookup;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i][colId] < min) {
min = arr[i][colId];
}
}
colMin.put(colId, min);
return min;
}
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == getMaxInRow(i) && arr[i][j] == getMinInCol(j)) {
System.out.println("Saddle at [" + i + ", " + j + "]. Value = " + arr[i][j]);
}
}
}
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if(max > a[i][j])
{
max = a[i][j];
maxcol = j;
}
if (min < a[i][j])
{
min = a[i][j];
mincol = j;
}
for (int k = 0; k < col; k++)
{
if (!breakmax)
{
if (max > a[maxcol][k])
{
breakmax = true;
}
}
if (!breakmin)
{
if (min < a[mincol][k])
{
breakmin = true;
}
}
}
if (!breakmax)
{
saddle[m++] = max;
}
if (!breakmin)
{
saddle[m++] = min;
}
}
}
import java.io.*;
public class SaddlePoint{
public static void main(String abc[])
{
String row,column,allnumbers;
int rows,columns,count;
int [][] matrix;
System.out.println("Enter number of rows: ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int maxrownum=0,mincolnum=0,colnum=0;;
row= br.readLine();
rows = Integer.parseInt(row);
System.out.println("Enter number of columns: ");
br = new BufferedReader(new InputStreamReader(System.in));
column= br.readLine();
columns = Integer.parseInt(column);
matrix = new int[rows][columns];
for(int i=0;i<rows;i++){
count=columns;
System.out.println("Enter numbers for rows "+(i+1)+" as comma seperated values: ");
allnumbers= br.readLine();
String []allNums= allnumbers.split(",");
System.out.println("length is "+allNums.length);
for(int j=0;j<columns;j++)
matrix[i][j]=Integer.parseInt(allNums[j]);
}
System.out.println("*********************");
for(int i=0;i<rows;i++){
for(int j=0;j<columns;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println("");
}
System.out.println("*********************");
for(int i=0;i<rows;i++)
{
maxrownum=matrix[i][0];
for(int j=0;j<columns;j++)
{
System.out.println("current maxrownum is "+maxrownum+" for a["+i+"]["+j+"]");
if(maxrownum>=matrix[i][j])
{
maxrownum=matrix[i][j];
colnum=j;
// System.out.println("maxrownum is "+maxrownum+" for a["+i+"]["+colnum+"]");
}
}
System.out.println("maxrownum is "+maxrownum+" for a["+i+"]["+colnum+"]");
mincolnum=maxrownum;
for(int k=0;k<rows;k++){
if(mincolnum<=matrix[k][colnum])
{
mincolnum=matrix[k][colnum];
}
}
System.out.println("mincolnum is "+mincolnum);
if(mincolnum==maxrownum){
System.out.println("saddle point is "+maxrownum);
}
}
} catch (IOException e) {
System.out.println("Error!");
}
}
}
public class horse {
public static void main(String[] args) {
int[][] arr={{9, 6, 8}, {7, 3, 1}, {10, 2, 5}, {12, 4, 2}};
for(int i=0;i<arr.length;i++){
int maxrow=arr[i][0];
int c=0;
for(int j=0;j<arr[i].length;j++){
if(arr[i][j]>maxrow){
maxrow=arr[i][j];
c=j;
}
}//find max in row and its column , then check if this colomn is the min in this colomn
int min=arr[0][c];
int r=0;
for(int k=0;k<arr.length;k++){
if(min>arr[k][c]){
r=k;
}
}
if(r==i){
System.out.println("this node is saddle point is"+maxrow+": row index :"+i+" and column index:"+c);
}
}
}
}
Python working code. didn't take repeat number into consideration ..
"""
11:33
@Python 2.7
write a program in c# or java or c that prints saddle points in a N by N Matrix.
saddle point is nothing but a cell values which has greater value among all the cell values in that row as well as it should be the smallest value among the column in which it is found......???
- vamcrulz09 on February 19, 2012 in United States Report Duplicate | Flag
Max in row, Min in col
"""
class SaddlePoint(object):
def __init__(self, matrix):
if matrix is None:
print 'invalid matrix'
raise SystemExit
self._matrix = matrix
def getSaddle(self):
rowMax = []
colMin = []
output = []
# find max in each row
for i in range(len(self._matrix)):
curMax = self._matrix[i][0]
rowMax.append([i, 0])
for j in range(len(self._matrix[i])):
if self._matrix[i][j] > curMax:
curMax = self._matrix[i][j]
rowMax.pop()
rowMax.append([i, j])
# find min in each col
for i in range(len(self._matrix[0])):
curMin = self._matrix[0][i]
colMin.append([0, i])
for j in range(len(self._matrix)):
if self._matrix[j][i] < curMin:
curMin = self._matrix[j][i]
colMin.pop()
colMin.append([j, i])
# print rowMax
# print colMin
#find all the Saddle Point
for c in rowMax:
if c in colMin:
output.append(c)
return output
if __name__ == '__main__':
s = SaddlePoint([[4,5,6],
[1,3,9],
[7,8,7],
[10,11,12]
])
print s.getSaddle()
#include <stdio.h>
void saddle(int (*m)[4], int row, int col)
{
int i,j, max;
int *maxRowIndex, *maxColIndex;
int index;
maxRowIndex = (int*)malloc(row*sizeof(int));
maxColIndex = (int*)malloc(col*sizeof(int));
for(i=0;i<row;i++)
{
max = -999;
for(j=0;j<col;j++)
{
if (m[i][j] > max)
{
max = m[i][j];
index = j;
}
}
maxRowIndex[i] = index;
}
for(i=0;i<col;i++)
{
int min = 999;
for(j=0;j<row;j++)
{
if (m[j][i] < min)
{
min = m[j][i];
index = j;
}
}
maxColIndex[i] = index;
}
/*
for (i=0;i<row;i++)
printf("%d ", maxRowIndex[i]);
printf("\n");
for (i=0;i<col;i++)
printf("%d ", maxColIndex[i]);
*/
for (i=0;i<row;i++)
{
if (maxColIndex[maxRowIndex[i]] == i)
{
printf("\narray[%d %d] = %d", i, maxRowIndex[i], m[i][maxRowIndex[i]]);
}
}
}
int main()
{
int a[][4] = {{5,2,2,3}, {4,5,1,4}, {3,2,1,1}};
saddle(a, 3,4);
}
In the below C++ solution i have assumed that this is a square matrix as mentioned in the question.
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int i, j, n, temp, **arr, *row, *col, flag=0;
cin>>n;
row=new int[n];
col=new int[n];
arr=new int*[n];
for (i=0; i<n; i++)
{
arr[i]=new int[n];
}
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
cin>>arr[i][j];
}
}
for (i=0; i<n; i++)
{
temp=arr[i][0];
for (j=0; j<n; j++)
{
if (arr[i][j]>=temp)
{
temp=arr[i][j];
}
}
row[i]=temp;
}
for (i=0; i<n; i++)
{
temp=arr[0][i];
for (j=0; j<n; j++)
{
if (arr[j][i]<=temp)
{
temp=arr[j][i];
}
}
col[i]=temp;
}
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if (row[i]==col[j])
{
cout<<row[i]<<endl;
flag=1;
break;
}
}
if (flag==1)
{
break;
}
}
return 0;
}
Saddle point is cell value which is minimum in a row and maximum in a column (in question its mentioned opposite ).Below program caters duplicates and matrices other than sqaure matrix
#include<iostream>
#include <map>
using namespace std;
void FindSaddlePoint ( int ** a, int m, int n )
{
map<int,int> row;
map<int,int> column;
int p=0,q=0;
bool found =false;
int min=INT_MAX,max=INT_MIN;
for ( int i=0; i<m; i++ )
{
for ( int j=0; j<n; j++ )
{
if ( min>a[i][j] )
{
min=a[i][j];
p=j;
}
}
row[i]=p;
min=INT_MAX,max=INT_MIN ;
}
for ( int i=0; i<n; i++ )
{
for ( int j=0; j<m; j++ )
{
if ( max<a[j][i] )
{
max=a[j][i];
q=j;
}
}
column[i]=q;
min=INT_MAX,max=INT_MIN;
}
for ( int i=0; i<m; i++ )
{
for ( int j=0; j<n; j++ )
{
if ( i==column[j] &&row[i]==j ) {
found=true;
cout<<a[i][j];
}
}
}
if ( found==false ) {
cout<<"No Saddle Point Exist";
}
}
int main()
{
int m,n;
cin>>m>>n;
int **a=new int*[m];
for ( int j=0; j<m; j++ )
{
a[j]=new int[n];
}
for ( int i=0; i<m; i++ )
for ( int j=0; j<n; j++ )
{
cin>>a[i][j];
}
FindSaddlePoint ( a,m,n );
for ( int i = 0 ; i < m ; i++ ) {
delete [] a[i] ;
}
delete [] a ;
}
void main()
{
int a[][3]={{1,2,3},
{9,5,4},
{8,6,7}
};
int colmin[3]={INT_MAX,};
int rowmax[3]={INT_MIN,};
for(int i=0;i<3;i++)//ROW
{
for(int j=0;j<3;j++) //COL
{
if(rowmax[i]<a[i][j])
rowmax[i]=a[i][j]; //3,9,8
}
}
for(int j=0;j<3;i++)//COL
{
for(int i=0;i<3;i++) //ROW
{
if(colmin[j]>a[i][j])
colmin[j]=a[i][j]; //1,2,3
}
}
for(int i=0;i<3;i++)//ROW
{
for(int j=0;j<3;j++) //COL
{
if(rowmax[i]==colmin[j])
printf("Saddle Point: %d",rowmax[i]);
}
}
}
package EPIC;
class IntPair {
public int x;
public int y;
public IntPair(int X, int Y) {
x = X;
y = Y;
}
@Override
public boolean equals(Object other) {
IntPair that = (IntPair) other;
return this.x == that.x && this.y == that.y;
}
}
public class SaddleNumber {
public static void findSaddle(int I[][]) {
if (I == null) {
return;
} else if (I.length == 0) {
return;
}
int height = I.length;
int width = I[0].length;
IntPair max_row[] = new IntPair[height];
IntPair min_col[] = new IntPair[width];
for (int row = 0; row < height; row++) {
int max = I[row][0];
IntPair maxpair = new IntPair(row, 0);
for (int col = 0; col < width; col++) {
if (I[row][col] > max) {
max = I[row][col];
maxpair.x = row;
maxpair.y = col;
}
}
max_row[row] = maxpair;
}
System.out.println("Maxrow");
for (int j = 0; j < max_row.length; j++) {
System.out.println(max_row[j].x + ", " + max_row[j].y);
}
for (int col = 0; col < width; col++) {
int min = I[0][col];
IntPair minpair = new IntPair(0, col);
for (int row = 0; row < height; row++) {
if (I[row][col] < min) {
min = I[row][col];
minpair.x = row;
minpair.y = col;
}
}
min_col[col] = minpair;
}
System.out.println("mincol");
for (int j = 0; j < min_col.length; j++) {
System.out.println(min_col[j].x + ", " + min_col[j].y);
}
for (int row = 0; row < max_row.length; row++) {
for (int col = 0; col < min_col.length; col++) {
if (max_row[row].equals(min_col[col])) {
System.out.println("x: " + max_row[row].x + ", y: "
+ max_row[row].y + " value: "
+ I[max_row[row].x][max_row[row].y]);
}
}
}
}
public static void main(String[] args) {
// int input[][] = {
// { 9, 6, 8, 11 },
// { 7, 3, 1, 32 },
// { 10, 2, 5, 22 },
// { 12, 4, 2, 5 }
// };
int input[][] = {
{ 2, 3, 1},
{ 4, 5, 6},
{ 9, 8, 9 },
};
findSaddle(input);
}
}
Step 1: Find maximum in each row
- mag February 19, 2012Step 2: Find minimum in each column
Step 3: Find common element in outputs of step 1 and step 2, the common element is the saddle point.