Cluster computing

Wednesday, November 22, 2023

#codingexercise

Given an array of varying heights above sea level for adjacent plots, and the array of water levels on consecutive days, find the number of islands. An island is a slice of array such that plots adjacent to the boundary of the island are under water.

class Solution {

public int[] solution(int[] A, int[] B) {

return Arrays

.stream(B)

.map(water -> IntStream

.range(0, N)

.filter(j -> (A[j] > water) && (j == N - 1 || A[j + 1] <= water))

.map(i -> 1)

.sum()) .toArray();

}

For example, given the following arrays A and B:

A[0] = 2 B[0] = 0

A[1] = 1 B[1] = 1

A[2] = 3 B[2] = 2

A[3] = 2 B[3] = 3

A[4] = 3 B[4] = 1

Solution:

result[0] = 1

result[1] = 2

result[2] = 2

result[3] = 0

result[4] = 2

For a water level, the number of islands is just the sum of changes in the number of islands as the water level is decreasing.

Optimized solution:

class Solution {

public int[] solution(int[] A, int[] B) {

int limit = Math.max(maxLevel(A), maxLevel(B));

int[] island = new int[limit + 2];

IntStream.range(0, A.length - 1)

.filter( j -> A[j] > A[j+1])

.forEach(j -> {

island[A[j]] += 1;

island[A[j + 1]] -= 1;

});

island[A[A.length-1]] += 1;

IntStream.range(-limit, 0)

.forEach(i -> island[-i] += island[-i+1]);

return Arrays.stream(B).map(water -> island[water + 1]).toArray();

}

public int maxLevel(int[] A) {

return Arrays.stream(A).max().getAsInt();

}

// before cumulation

island[0] = 0

island[1] = -1

island[2] = 0

island[3] = 2

island[4] = 0

// after cumulation

island[0] = 1

island[1] = 1

island[2] = 2