Interview Question
Country: United States
Interview Type: Written Test
@Lucy What the algorithm does is iteratively find the minimum element of the first row, and see if that element is the largest one in its column. If it is, then we've found the solution. If not, move to the next row, and do the same thing.
void FindSmallRowBigCol()
{
int a[][4]={1,2,3,4
,5,6,7,8
,9,10,11,12
,13,14,15,16};
int mini=0,minj=0;
bool bfound=1;
for(int i=0;i<4;i++)
{
bfound=1;
for(int j=0;j<4;j++)
{
mini=i;
minj=0;
if(a[i][j]<a[mini][minj])
{
mini=i;
minj=j;
}
}
for(int k=0;k<4;k++)
{
if(a[mini][minj]<a[k][minj])
{ bfound=0;
break;
}
}
if(bfound==1)
{
printf("[%d][%d]:%d",mini,minj,a[mini][minj]);
}
}
}
#include <stdio.h>
const int rowN = 3;
const int colN = 3;
int findElement(int matrix[rowN][colN]){
/* if matrix is null, return null*/
if(matrix == NULL)
return NULL;
int result = NULL;
/* matrix size */
int numOfRows = rowN;
int numOfCols = colN;
/* create an auxiliary list boolean array */
int smallestColPerRow[numOfRows];
/*find the smallest element in each row*/
int rowIter, colIter;
for(rowIter=0; rowIter < numOfRows; rowIter++){
int smallestCol = 0;
for(colIter=0; colIter < numOfCols; colIter++){
if(matrix[rowIter][colIter] < matrix[rowIter][smallestCol])
smallestCol = colIter;
}
smallestColPerRow[rowIter]= smallestCol;
}
/* search for largetst element in each col, check if it is the smallest element in that row too*/
for(colIter=0; colIter< numOfCols; colIter++){
int largestRow = -100000;
for(rowIter=0; rowIter< numOfRows; rowIter++){
if(matrix[rowIter][colIter] > matrix[largestRow][colIter])
largestRow = rowIter;
}
if(smallestColPerRow[largestRow]== colIter){
result =matrix[largestRow][colIter];
break;
}
}
return result;
}
int main(){
int matrix [rowN][colN] = {
{1,1,3},
{0,1,-1},
{1,-1,2}};
int result = findElement(matrix);
if(result == NULL)
printf("\nnot found");
else
printf("\nresult is:%d\n", result);
return 0;
}
#define ARRAY_SIZE 3
/*
3 0 5
6 0 10
110 100 80*/
main()
{
int x[3][3] = {3,0,5,6,0,10,110,100,80};
int i, j, k;
int min_index = 0;
int min, min_row, min_row_index;
printf("size is %d\n", ARRAY_SIZE);
for(i = 0; i < ARRAY_SIZE; i++) {
min_row = x[i][0];
min_row_index = 0;
/* searching each row */
for(j = 0; j < ARRAY_SIZE; j++) {
if(min_row > x[i][j]) {
min_row_index = j;
min_row = x[i][j];
}
}
printf("min_row %d min_row_index %d\n", min_row, min_row_index);
/* so we found out the minimum in the row now let's search
if it is greater in the corresponding column */
for(k = 0; k < ARRAY_SIZE; k++) {
printf("x[k][min_row_index] %d\n", x[k][min_row_index]);
if(min_row < x[k][min_row_index])
break;
}
if(k == ARRAY_SIZE) {
printf("we found it %d\n", min_row);
break;
}
}
}
maxmin( int arr[ ][ ];row;col)
- It brother October 18, 2012{
int min=arr[0[[0];int ro,co
for(i=0;i<row;i++)
{
for(j=o;j<col;j++)
{
if(arr[i][j]<min)
min=arr[i][j];ro=i;co=j;
}
if(max(arr,min,ro,co))
return min
}
}
int max(arr,int min,int row,int co)
{
for(j=o;j<row;j++)
{
if(arr[j][co]>min)
return -1
}
return 1
}