Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I think "island" refers to a block of numbers whose sum is maximum. But still keeping the question open for Kiran to clarify.
Two cells is a matrix will be called connected if they are adjacent on either x-axis or y-axis (but not diagonally) For. eg., a[0,0] will be connected to both cells a[0,1] and a[1,0]. But it will not connected to cell a[1,1]
For this problem, lets say, cells denoted by integer <= 0 represent Water and cells denoted by non-zero positive integer represent Land. An Island is a connected land cells. Weight of an island is the sum of all integers in that island.
1 0 0 0
1 0 1 2
2 1 0 2
0 0 0 1
In above example matrix, there are two islands { a[0,0], a[1,0], a[2,0], a[2,1] } with weight of 5 units { a[1,2], a[1,3], a[2,3], a[3,3] }, with weight of 6 units
heaviest island is { a[1,2], a[1,3], a[2,3], a[3,3] } elements with weight 6
int[][] tri; tri = new int[10][]; // allocate array of rows for (int r=0; r<tri.length; r++) { tri[r] = new int[r+1]; } // print the triangular array (same as above really) for (int r=0; r<tri.length; r++) { for (int c=0; c<tri[r].length; c++) { System.out.print(" " + tri[r][c]); } System.out.println("");
en.wikipedia.org/wiki/Connected-component_labeling
- Anonymous May 15, 2012