Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
//start from 1st element in second row, second column
for(int i=1; i<m; i++) //rows
{
for(int j=1; j<n;j++) //columns
{
if ((a[i][j] > a[i-1,j-1]) &&
(a[i][j] > a[i,j-1]) &&
(a[i][j] > a[i+1,j-1]) &&
(a[i][j] > a[i+1,j]) &&
(a[i][j] > a[i+1,j+1]) &&
(a[i][j] > a[i,j+1]) &&
(a[i][j] > a[i-1,j+1]) &&
(a[i][j] > a[i-1,j]))
{
a[i][j] = "MP"; //mountain point
i++; //skip the next column, if this is a mountain point
}
}
}
void printMountainPoint(int[][] matrix, int M, int N){
int row_start = 1;
int col_start = 1;
for(int row = row_start;row <M-1; row++){
for(int col = col_start;col <N-1; col++){
if(isMP(row,col,matrix))
System.out.print("row: "+i+"; col: "+j);
}
}
}
boolean isMP(int row, int col, int[][] matrix{
int offset = 3;
int candidate = matrix[row][col];
int max = Integer.min;
for(int i = row-1;i<=row+1;i++){
for(int j=col-1;j<col+1;j++){
if(max<matrix[i][j])
max = matrix[i][j];
}
}
return max == candidate;
}
for(int i=1; i<m; i++) //rows
{
for(int j=1; j<n;j++) //columns
{
if ((a[i][j] > a[i-1,j-1]) &&
(a[i][j] > a[i,j-1]) &&
(a[i][j] > a[i+1,j-1]) &&
(a[i][j] > a[i+1,j]) &&
(a[i][j] > a[i+1,j+1]) &&
(a[i][j] > a[i,j+1]) &&
(a[i][j] > a[i-1,j+1]) &&
(a[i][j] > a[i-1,j]))
{
a[i][j] = "MP"; //mountain point
i+=2; //skip the next column, if this is a mountain point
}
j++;
}
}
R:
mountain <- function(M = 10, N = 10) {
a <- matrix(floor(runif(n=M*N, min = 0, max = 100)), nrow = N, ncol = M)
moves <- expand.grid(-1:1, -1:1)
moves <- moves[-which(moves[,1] == 0 & moves[,2] == 0),]
result <- c()
for(i in 2:N-1){
for(j in 2:M-1){
pos <- c(i,j)
check <- pos + moves
if( length(which(a[i,j] > a[as.matrix(check)])==T) == 8){
result <- c(result, a[i,j])
}
}
}
return(list(result, a))
}
mountain(5,5)
import java.util.Random;
public class MountainPoints {
public static void main(String[] args) {
Random r = new Random();
int ROW_SIZE = r.nextInt(10) + 1;
int COL_SIZE = r.nextInt(10) + 1;
System.out.println(ROW_SIZE + "," + COL_SIZE);
int [][] mtx = generateMatrix(ROW_SIZE,COL_SIZE);
printMatrix(mtx,ROW_SIZE,COL_SIZE);
System.out.println();
printMountains(mtx,ROW_SIZE,COL_SIZE);
}
private static void printMountains(int[][] mtx, int R, int C) {
for(int i = 1;i<R-1;i++)
{
for(int j =1;j<C-1;j++)
{
if(mtx[i][j]>mtx[i-1][j-1]&&mtx[i][j]>mtx[i+1][j+1] // NW to SE diaogonal
&&mtx[i][j]>mtx[i-1][j]&&mtx[i][j]>mtx[i+1][j] //up and down
&&mtx[i][j]>mtx[i][j-1]&&mtx[i][j]>mtx[i][j+1] //left and right
&&mtx[i][j]>mtx[i+1][j-1]&&mtx[i][j]>mtx[i-1][j+1])//SW to NE
System.out.print(mtx[i][j] + " ");
else
System.out.print("X ");
}
System.out.println();
}
}
private static void printMatrix(int[][] mtx, int rOW_SIZE, int cOL_SIZE) {
for(int i = 0;i<rOW_SIZE;i++)
{
for(int j =0;j<cOL_SIZE;j++)
{
System.out.print(mtx[i][j] + " ");
}
System.out.println();
}
}
private static int[][] generateMatrix(int rOW_SIZE, int cOL_SIZE) {
Random r = new Random();
int [][] res = new int[rOW_SIZE][cOL_SIZE];
for(int i = 0;i<rOW_SIZE;i++)
for(int j =0;j<cOL_SIZE;j++)
res[i][j] = r.nextInt(100) + 1;
return res;
}
}
I think the question is already properly answered, but I had one thought about using extra space and avoid visiting some elements. In other words, all the elements surrounding the mountain element are not going to be the mountain element, hence there is no need to check all eight surrounding elements for them.
Any thoughts about the extra efficiency introduced by using extra space?
You can create an 2D array storing the status of all indices of the original 2D array. Initiate it will all 0's. Run the loop and update the status array for two conditions:
1. if a MP is found, update the status of MP to +1, indicating a MP, and more importantly, update the surrounding status all to -1 so that those locations will not be checked
2. if a MP is not found, do nothing
Here is a similar solution that skips rows and columns that don't have mountain elements:
public static boolean greaterThanNeighbours(int[][] matrix, int i, int j) {
if(matrix[i][j] > matrix[i-1][j-1] &&
matrix[i][j] > matrix[i][j-1] &&
matrix[i][j] > matrix[i+1][j-1] &&
matrix[i][j] > matrix[i-1][j] &&
matrix[i][j] > matrix[i+1][j] &&
matrix[i][j] > matrix[i-1][j+1] &&
matrix[i][j] > matrix[i][j+1] &&
matrix[i][j] > matrix[i+1][j+1])
return true;
return false;
}
public static void printMountainPoints(int[][] matrix) {
int m = matrix.length; // rows
int n = matrix[0].length; // columns
int count = 0;
boolean skipRow = false;
for(int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if(greaterThanNeighbours(matrix, i, j)) {
count += 1;
skipRow = true;
System.out.println("The number " + matrix[i][j++] + " is a mountain point.");
}
}
if (skipRow) {
i += 1;
skipRow = false;
}
}
if (count == 0) {
System.out.println("No mountain points.");
}
}
simple c++
void findMP(const vector<vector<int>> &matrix){
for(int i = 1;i!=matrix.size()-1;i++){
for(int j=1;j!=matrix[0].size()-1;j++){
int fir(count_if(matrix[i-1].begin()+j-1,matrix[i-1].begin()+j+2,[&](int e){
return e>=matrix[i][j];
}));
if(fir) continue;
int sec(count_if(matrix[i+1].begin()+j-1,matrix[i+1].begin()+j+2,[&](int e){
return e>=matrix[i][j];
}));
if(sec) continue;
int final(count_if(matrix[i].begin()+j-1,matrix[i].begin()+j+2,[&](int e){
return e<matrix[i][j];
}));
if(final!=2) continue;
else{
cout<<"porint["<<i<<","<<j<<"]"<<endl;
}
}
}
}
package epic.mountainpoint;
public class MountainPoint {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {{2,4,5,6,7},
{4,5,67,3,5},
{5,6,7,8,54},
{3,4,5,6,8},
{3,4,56,4,5}};
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
{
find(matrix, 5, 5, i, j, matrix[i][j]);
}
}
public static void find(int[][] matrix, int m, int n, int i, int j, int point)
{
final int[] delta_i = {-1, -1, -1, 0, 1, 1, 1, 0 };
final int[] delta_j = {1, 0, -1, -1, -1, 0, 1, 1};
int value = matrix[i][j];
int index_i = 0, index_j = 0;
boolean isMountain = true;
for(int k=0; k<8 ; k++)
{
index_i = (i + delta_i[k]);
index_j = (j + delta_j[k]);
if(index_i > 0 && index_i < m && index_j > 0 && index_j < n)
{
if(value <= matrix[index_i][index_j])
{
isMountain = false;
}
}
}
if(isMountain)
System.out.println(point);
}
}
public class mountainPoint {
public static void main(String[] args)
{
int matrix[][] = {{2,4,5,6,7},
{4,5,67,3,5},
{5,6,7,8,54},
{3,4,5,6,8},
{3,4,56,4,5}};
int m = matrix.length;
int n = matrix[0].length;
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if((i-1)>=0 && (i+1)<m && (j-1)>=0 && (j+1)<n)
{
if(matrix[i][j]>matrix[i-1][j-1]
&& matrix[i][j]>matrix[i-1][j]
&& matrix[i][j]>matrix[i-1][j+1]
&& matrix[i][j]>matrix[i][j-1]
&& matrix[i][j]>matrix[i][j+1]
&& matrix[i][j]>matrix[i+1][j-1]
&& matrix[i][j]>matrix[i+1][j]
&& matrix[i][j]>matrix[i+1][j+1])
{
System.out.println("Mountain Point:"+matrix[i][j]+"at index i:"+i+", "+j);
}
}
}
}
}
}
public void PrintMountainPoint(int[][] matrix) { // start from the second element in the second row for (int i = 1; i < matrix.length - 1; i++) { for (int j = 1; j < matrix[0].length - 1; j++) { if (matrix[i][j] > matrix[i - 1][j - 1] && matrix[i][j] > matrix[i - 1][j] && matrix[i][j] > matrix[i - 1][j + 1] && matrix[i][j] > matrix[i][j - 1] && matrix[i][j] > matrix[i][j + 1] && matrix[i][j] > matrix[i + 1][j - 1] && matrix[i][j] > matrix[i + 1][j] && matrix[i][j] > matrix[i + 1][j + 1]) { System.out.println("(" + i + "," + j + ")"); j++; //skip the next column } } }}
- lvhuayu November 15, 2014