## Palantir Technology Interview Question for Front-end Software Engineers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

My Solution. Though I was not able to complete in 100 min. Wasted a golden opportunity.

-----------------------------

``````import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

import javax.swing.text.html.HTMLDocument.Iterator;

class Result{
int value;
char tag;
Result next;

public Result(int value){
this.value = value;
this.next = null;
}
}

public class Solution {
static int dimension;
static Result land[][];
static List<Integer> list;

public static Result calculateMinimum(Result i, Result j){
Result min = null;
if(i.value < j.value){
min = i;
} else {
min = j;
}
return min;
}

public static Result calculateMinimum(Result i, Result j, Result k) {
Result min = null;
if(i.value < j.value && i.value < k.value){
min = i;
}
if(j.value < i.value && j.value < k.value){
min = j;
}
if(k.value < i.value && k.value < j.value){
min = k;
}
return min;
}

public static Result calculateMinimum(Result i, Result j, Result k, Result l){
Result min = null;
if(i.value < j.value && i.value < k.value && i.value < l.value){
min = i;
}
if(j.value < i.value && j.value < k.value && j.value < l.value){
min = j;
}
if(k.value < i.value && k.value < j.value && k.value < l.value){
min = k;
}
if(l.value < i.value && l.value < j.value && l.value < k.value){
min = l;
}
return min;
}

public static void findBasin(){
if(dimension == 1){
System.out.print(1);
return;
}
char start = 'A';
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
Result min = null;
if(row - 1 < 0){
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row + 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row + 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row + 1][col]);
}
} else if(row + 1 >= dimension){
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row - 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row - 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row - 1][col]);
}
} else {
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row - 1][col], land[row + 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row - 1][col], land[row + 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row - 1][col], land[row + 1][col]);
}
}
if(min.value > land[row][col].value){
land[row][col].next = null;
land[row][col].tag = start;
start += 1;
} else {
if(min.next == null){
land[row][col].next = min;
} else {
land[row][col].next  = min.next;
}
}
}
}
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
Result temp = land[row][col];
while(temp.next != null){
temp = temp.next;
}
land[row][col].tag = temp.tag;
}
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
if(map.size() > 0){
if(map.containsKey(land[row][col].tag)){
map.put(land[row][col].tag, map.get(land[row][col].tag) + 1);
} else {
map.put(land[row][col].tag, 1);
}
} else {
map.put(land[row][col].tag, 1);
}
}
}

Collection<Integer> values = map.values();
list = new ArrayList<Integer>(values);
Collections.sort(list);
Collections.reverse(list);

for(Integer i : list){
System.out.print(i + " ");
}
}

public static void main(String[] args) throws Exception {
land = new Result[dimension][dimension];
for(int i = 0; i < dimension; i++){
int j = 0;
StringTokenizer st = new StringTokenizer(line);
while(st.hasMoreTokens()){
int no = Integer.parseInt(st.nextToken());
//System.out.println(no);
Result temp = new Result(no);
land[i][j] = temp;
j++;
}
j = 0;
}

findBasin();
}
}``````

Comment hidden because of low score. Click to expand.
0

too slow...... >O(n^2)

Comment hidden because of low score. Click to expand.
0

I'm pretty sure you can't do this problem better than O(n^2)... At the very least, you have to find which square each square's water flows to, and you can't do that in less than O(n^2).

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````package com.nbethi.basins;

import java.util.HashMap;
import java.util.StringTokenizer;

public class BasinUtil {

public static void main(String args[]) throws Exception {
System.out.print("Please enter square size : ");
int size = Integer.parseInt(line);
int area[][] = new int[size][size];

for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print("("+x+","+y+")"+" : ");
area[x][y] = Integer.parseInt(line.trim());
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(area[x][y]+" ");
}
System.out.println("");
}

calculateBasins(area);
System.out.println("DONE");
}

public static void calculateBasins(int area[][]) {
int size = area.length;
String basins[][] = new String [size][size];
HashMap map = new HashMap();
char uniqueChar = 'A';
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
basins[x][y] = lowestPlot(area,x,y,'A');
if(map.containsKey(basins[x][y])) {
String valueString = (String)map.get(basins[x][y]);
StringTokenizer tokens = new StringTokenizer(valueString,":");
char basinUniqueueChar = tokens.nextToken().charAt(0);
int basinSize = Integer.parseInt(tokens.nextToken());
basinSize = basinSize + 1;
map.put(basins[x][y], basinUniqueueChar+":"+basinSize);
} else {
map.put(basins[x][y], uniqueChar+":"+1);
uniqueChar++;
}
}
}

for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(map.get(basins[x][y])+" ");
}
System.out.println("");
}
}

public static String lowestPlot(int area[][],int x, int y, char ch) {
String lowestPoint = x+","+y;
int size = area.length;
int leftX, leftY, rightX, rightY, topX, topY, bottomX, bottomY;
int minX, minY,minValue;

leftX = x;
leftY = y - 1;

rightX = x;
rightY= y + 1;

topX = x - 1;
topY = y;

bottomX = x + 1;
bottomY = y;

minX = x;
minY = y;
minValue = area[x][y];

if (!isOutOfBounds(leftX, leftY, size)) {
if (area[leftX][leftY] < minValue) {
minX = leftX;
minY = leftY;
minValue = area[leftX][leftY];
}
}
if (!isOutOfBounds(rightX, rightY, size)) {
if (area[rightX][rightY] < minValue) {
minX = rightX;
minY = rightY;
minValue = area[rightX][rightY];
}
}
if (!isOutOfBounds(topX, topY, size)) {
if (area[topX][topY] < minValue) {
minX = topX;
minY = topY;
minValue = area[topX][topY];
}
}
if (!isOutOfBounds(bottomX, bottomY, size)) {
if (area[bottomX][bottomY] < minValue) {
minX = bottomX;
minY = bottomY;
minValue = area[bottomX][bottomY];
}
}
if(minX == x && minY == y) {
//self is the lowest;
} else {
lowestPoint = lowestPlot(area, minX, minY, ch);
}
return lowestPoint;
}

public static boolean isOutOfBounds(int x, int y, int size) {
boolean flag = false;
if (x < 0 || x >= size) {
flag = true;
}
if (y < 0 || y >= size) {
flag = true;
}
return flag;
}

}

sample input ant output
Please enter square size : 5
(0,0) : 1
(0,1) : 0
(0,2) : 2
(0,3) : 5
(0,4) : 8
(1,0) : 2
(1,1) : 3
(1,2) : 4
(1,3) : 7
(1,4) : 9
(2,0) : 3
(2,1) : 5
(2,2) : 7
(2,3) : 8
(2,4) : 9
(3,0) : 1
(3,1) : 2
(3,2) : 5
(3,3) : 4
(3,4) : 2
(4,0) : 3
(4,1) : 3
(4,2) : 5
(4,3) : 2
(4,4) : 1
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
A:11 A:11 A:11 A:11 A:11
A:11 A:11 A:11 A:11 A:11
B:7 B:7 A:11 C:7 C:7
B:7 B:7 B:7 C:7 C:7
B:7 B:7 C:7 C:7 C:7
DONE

took less time but below not implemented
sorting of basins size:
what if if two lowest basins are adjacent.``````

Comment hidden because of low score. Click to expand.
0

``````approach:
matrix1: all plots with altitudes.
for each given plot find the lowest plot which we can find through recursion (recursion will end if the plot is lower than all of its neighbor plots).

store these lowest point in a separate matrix2
matrix2: all plot's corresponding lowest plot

now iterate through matrix2
--lowest plot does not exist in the HashMap--put an object with count as 1
--lowest plot exists in the HashMap--retrieve it and increase the count by 1.

at the end we will have all the LowestPlots and their corresponding count in the HashMap.``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Guys instead of pasting code here, please discuss algorithms and techniques you used, because that will be more helpful to all of us. I know this can be done, its not that tough question.

Just that I was not able to do it in 100 min (time given by palantir).

I just wanted to know different approaches to solve this question.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This question can be solved decently via Union-Find.
Specifically, use quick union here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.nbethi.basins;

import java.util.HashMap;
import java.util.StringTokenizer;

public class BasinUtil {

public static void main(String args[]) throws Exception {
System.out.print("Please enter square size : ");
int size = Integer.parseInt(line);
int area[][] = new int[size][size];

for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print("("+x+","+y+")"+" : ");
area[x][y] = Integer.parseInt(line.trim());
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(area[x][y]+" ");
}
System.out.println("");
}

calculateBasins(area);
System.out.println("DONE");
}

public static void calculateBasins(int area[][]) {
int size = area.length;
String basins[][] = new String [size][size];
HashMap map = new HashMap();
char uniqueChar = 'A';
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
basins[x][y] = lowestPlot(area,x,y,'A');
if(map.containsKey(basins[x][y])) {
String valueString = (String)map.get(basins[x][y]);
StringTokenizer tokens = new StringTokenizer(valueString,":");
char basinUniqueueChar = tokens.nextToken().charAt(0);
int basinSize = Integer.parseInt(tokens.nextToken());
basinSize = basinSize + 1;
map.put(basins[x][y], basinUniqueueChar+":"+basinSize);
} else {
map.put(basins[x][y], uniqueChar+":"+1);
uniqueChar++;
}
}
}

for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(map.get(basins[x][y])+" ");
}
System.out.println("");
}
}

public static String lowestPlot(int area[][],int x, int y, char ch) {
String lowestPoint = x+","+y;
int size = area.length;
int leftX, leftY, rightX, rightY, topX, topY, bottomX, bottomY;
int minX, minY,minValue;

leftX = x;
leftY = y - 1;

rightX = x;
rightY= y + 1;

topX = x - 1;
topY = y;

bottomX = x + 1;
bottomY = y;

minX = x;
minY = y;
minValue = area[x][y];

if (!isOutOfBounds(leftX, leftY, size)) {
if (area[leftX][leftY] < minValue) {
minX = leftX;
minY = leftY;
minValue = area[leftX][leftY];
}
}
if (!isOutOfBounds(rightX, rightY, size)) {
if (area[rightX][rightY] < minValue) {
minX = rightX;
minY = rightY;
minValue = area[rightX][rightY];
}
}
if (!isOutOfBounds(topX, topY, size)) {
if (area[topX][topY] < minValue) {
minX = topX;
minY = topY;
minValue = area[topX][topY];
}
}
if (!isOutOfBounds(bottomX, bottomY, size)) {
if (area[bottomX][bottomY] < minValue) {
minX = bottomX;
minY = bottomY;
minValue = area[bottomX][bottomY];
}
}
if(minX == x && minY == y) {
//self is the lowest;
} else {
lowestPoint = lowestPlot(area, minX, minY, ch);
}
return lowestPoint;
}

public static boolean isOutOfBounds(int x, int y, int size) {
boolean flag = false;
if (x < 0 || x >= size) {
flag = true;
}
if (y < 0 || y >= size) {
flag = true;
}
return flag;
}

}

sample input ant output
Please enter square size : 5
(0,0) : 1
(0,1) : 0
(0,2) : 2
(0,3) : 5
(0,4) : 8
(1,0) : 2
(1,1) : 3
(1,2) : 4
(1,3) : 7
(1,4) : 9
(2,0) : 3
(2,1) : 5
(2,2) : 7
(2,3) : 8
(2,4) : 9
(3,0) : 1
(3,1) : 2
(3,2) : 5
(3,3) : 4
(3,4) : 2
(4,0) : 3
(4,1) : 3
(4,2) : 5
(4,3) : 2
(4,4) : 1
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
A:11 A:11 A:11 A:11 A:11
A:11 A:11 A:11 A:11 A:11
B:7 B:7 A:11 C:7 C:7
B:7 B:7 B:7 C:7 C:7
B:7 B:7 C:7 C:7 C:7
DONE

took less time but below not implemented
sorting of basins size:
what if if two lowest basins are adjacent.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript Implementation

``````/**
* our test cases
*/
function test(){
var results = [];
var alts = [[1,0]];
var res = findBasinSizes(alts);
results.push(res.A == 1);

var alts = [[1,5,2],
[2,4,7],
[3,6,9]];
res = findBasinSizes(alts);
results.push( res.A == '7' && res.B == '2');

var alts = [[1, 0, 2, 5, 8],
[2, 3, 4, 7, 9],
[3, 5, 7, 8, 9],
[1, 2, 5, 4, 2],
[3, 3, 5, 2, 1]]
var res = findBasinSizes(alts);
results.push( res.A == '11' && res.B == '7' && res.C == '7' );
return results;
}

// list of surrounding coords up, down, left, right, and current
var surroundingCoords = [[0, +1],
[0, -1],
[+1, 0],
[-1, 0],
[0, 0]];

/*
* finds the sizes for each basin
* @param NxN array of altitudes
* @return object - object with category as key and basin size as the value
*/
function findBasinSizes(alts){
var map = copyArray(alts);
freqList = {};
basinCount = 65; // char code for "A"

// set sinks
alts.forEach(function(row, i){
row.forEach(function(value, j){
if (isSink(i,j,alts)){
map[i][j] = String.fromCharCode(basinCount++);
}
});
});

// assign each element to a basin category
alts.forEach(function(row,i){
alts.forEach(function(value,j){
var cat = findBasinCategory(i,j,map,alts);
map[i][j] = cat;
freqList[cat] = freqList[cat] ? ++freqList[cat] : 1;
});
});

return freqList;
}

/**
* finds the category the current index belongs to
* @param i - x coord
* @param j - y coord
* @param map - 2d array with basin categories
* @param alts - 2d array of altitudes
* @return string - basin category
*/
function findBasinCategory(i,j,map,alts){
var val = 0;
// if we haven't found a sink or basin yet
while (typeof val !== 'string'){
val = map[coords][coords];
i = coords;
j = coords;
}
return val;
}

/**
* A sink is defined as an index surrounded by altitudes higher than itself
* @param i - x index
* @param j - y index
* @param alts - altitude map
* @return bool - whether the current index is a sink hole
*/
function isSink(i,j,alts){
var surrounding = getSurrounding(i,j,alts);
return Math.min.apply(this,surrounding) === alts[i][j];
}

/**
* @param i - x index
* @param j - y index
* @param alts - 2d array of altitudes
* @return coords - [i,j] index of the lowest adjacent altitude
*/
var min = Infinity;
var coords = [];
surroundingCoords.forEach(function(v){
if (alts[i + v] && alts[i + v][j + v] < min){
min = alts[i + v][j + v];
coords = [i + v, j + v];
}
});

return coords;
}

/**
* @param i - x index
* @param j - y index
* @param alts - 2d array of altitudes
* @return array - array of surrounding altitude values
*/
function getSurrounding(i,j,alts){
var b = [];
surroundingCoords.forEach(function(v){
if (alts[i + v] && alts[i + v][j + v] != undefined){
b.push(alts[i + v][j + v]);
}
});
return b;
}

/**
* copy helper for 2d array
*/
function copyArray(arr){
var a = arr.slice(0);
a.forEach(function(v,i){
a[i] = a[i].slice(0);
});
return a;
}

console.log(test());``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Wrote this in C. Haven't implemented sorting of basin sizes.

``````#include <stdlib.h>
#include <stdio.h>

struct Cell {
int elevation;
int basinIndex;

};

struct Cell *elevationData;
int plotSize;
int currentBasinIndex;
int *basinSizes;

struct Cell* new_Cell() {
struct Cell* cell = (struct Cell*) malloc(sizeof(struct Cell));
cell->elevation = 0;
cell->basinIndex = -1;
return cell;
}

void processCell(int i, int j) {
int minElevation = 500;
struct Cell *cell = elevationData[i][j];
struct Cell *left = NULL, *top = NULL, *right = NULL, *bottom = NULL;
int minElevationCellI, minElevationCellJ;
if (cell->basinIndex != -1)
return;
if ((i - 1) >= 0) {
left = elevationData[i - 1][j];
if (left->elevation < minElevation) {
minElevation = left->elevation;
minElevationCellI = i - 1;
minElevationCellJ = j;
}
}
if ((i + 1) < plotSize) {
right = elevationData[i + 1][j];
if (right->elevation < minElevation) {
minElevation = right->elevation;
minElevationCellI = i + 1;
minElevationCellJ = j;
}
}
if ((j - 1) >= 0) {
top = elevationData[i][j - 1];
if (top->elevation < minElevation) {
minElevation = top->elevation;
minElevationCellI = i;
minElevationCellJ = j - 1;
}
}
if ((j + 1) < plotSize) {
bottom = elevationData[i][j + 1];
if (bottom->elevation < minElevation) {
minElevation = bottom->elevation;
minElevationCellI = i;
minElevationCellJ = j + 1;
}
}
if (minElevation > cell->elevation) {
//Current cell is the sink. Form a new basin
cell->basinIndex = ++currentBasinIndex;
} else {
processCell(minElevationCellI, minElevationCellJ);
cell->basinIndex = elevationData[minElevationCellI][minElevationCellJ]->basinIndex;
}
basinSizes[cell->basinIndex]++;
}

int main() {
int i, j, dummy;
currentBasinIndex = -1;
scanf("%d", &plotSize);
basinSizes = (int *) calloc(plotSize * plotSize, sizeof(int));
for (i = 0; i < plotSize; i++) {
for (j = 0; j < plotSize; j++) {
elevationData[i][j] = new_Cell();
scanf("%d", &(elevationData[i][j]->elevation));

}
}
for (i = 0; i < plotSize; i++) {
for (j = 0; j < plotSize; j++) {
processCell(i, j);
}
}

for (i = 0; i <= currentBasinIndex; i++) {
printf("%d ", basinSizes[i]);
}
scanf("%d", &dummy);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution {
private Cell[][] matrix;
private int size;
private Scanner scanner = new Scanner(System.in);;

public class Cell {
private int x;
private int y;
private int altitude;
private Integer basinsNo;
private boolean isVisited;

public int getX() {
return x;
}

public void setX(int x) {
this.x = x;
}

public int getY() {
return y;
}

public void setY(int y) {
this.y = y;
}

public int getAltitude() {
return altitude;
}

public void setAltitude(int altitude) {
this.altitude = altitude;
}

public Integer getBasinsNo() {
return basinsNo;
}

public void setBasinsNo(Integer basinsNo) {
this.basinsNo = basinsNo;
}

public boolean isVisited() {
return isVisited;
}

public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}

public Cell(int altitude, int x, int y) {
super();
this.altitude = altitude;
basinsNo = -1;
isVisited = false;
this.x = x;
this.y = y;
}

public Cell[] getNieghbors(int x, int y) {
Cell[] neighbors = new Cell;
if (x - 1 >= 0 && matrix[x - 1][y].isVisited == false) {
neighbors = matrix[x - 1][y];
} else {
neighbors = null;
}
if (x + 1 < size && matrix[x + 1][y].isVisited == false) {
neighbors = matrix[x + 1][y];
} else {
neighbors = null;
}
if (y - 1 >= 0 && matrix[x][y - 1].isVisited == false) {
neighbors = matrix[x][y - 1];
} else {
neighbors = null;
}
if (y + 1 < size && matrix[x][y + 1].isVisited == false) {
neighbors = matrix[x][y + 1];
} else {
neighbors = null;
}
return neighbors;
}

private Cell getSmallestNeighbor(int x, int y) {
// if self is the smallest one, return self
Cell smallestneighbor = matrix[x][y];

if (x - 1 >= 0) {
if (matrix[x - 1][y].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x - 1][y];
}
}
if (x + 1 < size) {
if (matrix[x + 1][y].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x + 1][y];
}
}
if (y - 1 >= 0) {
if (matrix[x][y - 1].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x][y - 1];
}
}
if (y + 1 < size) {
if (matrix[x][y + 1].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x][y + 1];
}
}
return smallestneighbor;
}
}

public Solution() {
super();
size = Integer.parseInt(scanner.nextLine());
if (!checkInput(size)) {
System.out.println("Size should be smaller than 5000.");
System.exit(0);
}
matrix = new Cell[size][size];
int y = 0;
int index = size;
while (index != 0) {
String line = scanner.nextLine();
String[] altitudes = line.split(" ");
if (altitudes.length != size) {
System.err.println("Input Error");
System.exit(-1);
}
for (int i = 0; i < altitudes.length; i++) {
matrix[i][y] = new Cell(Integer.parseInt(altitudes[i]), i, y);
}
y++;
index--;
}
}

private Cell findLowestCell(Cell c) {
Cell cell = c.getSmallestNeighbor(c.x, c.y);
if (cell == c) {
return c;
} else {
return findLowestCell(cell);
}
}

private boolean checkInput(int size) {
return size <= 5000;
}

public void findBasins() {

int basinsNo = 0;
Cell cell;
while (!stack.isEmpty()) {
cell = stack.remove(stack.size() - 1);
Cell smallestCell = findLowestCell(cell);
if (smallestCell.getBasinsNo() == -1) {
basinsNo++;
smallestCell.setBasinsNo(basinsNo);
}
cell.setBasinsNo(smallestCell.getBasinsNo());
cell.setVisited(true);
Cell[] neighbors = cell.getNieghbors(cell.x, cell.y);
for (Cell neighbor : neighbors) {
if (neighbor != null && !neighbor.isVisited()) {
}
}
}
}

public void print() {

for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
System.out.print(matrix[x][y].getBasinsNo() + "\t");
}
System.out.println();
}
}

public Integer[] stat() {
Map<Integer, Integer> stat = new TreeMap<Integer, Integer>();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (stat.get(matrix[i][j].getBasinsNo()) == null) {
stat.put(matrix[i][j].getBasinsNo(), 1);
} else {
stat.put(matrix[i][j].getBasinsNo(),
stat.get(matrix[i][j].getBasinsNo()) + 1);
}
}
}
List<Integer> list = new ArrayList<Integer>(stat.values());
Integer[] num = new Integer[stat.size()];
for (int i = 0; i < stat.size(); i++) {
num[i] = list.get(i);
}
Arrays.sort(num,Collections.reverseOrder());
return num;
}

/**
* @param args
*/
public static void main(String[] args) throws Exception {
Solution s = new Solution();
s.findBasins();
Integer[] num = s.stat();
for (int n : num) {
System.out.print(n + " ");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
For every element in 2D array find lowest neighboring element.
--if found, make it a child of this element. (note that this lowest neighbor element might already be in a tree, in which case you grow the tree further.)
you will end up with multiple trees (i.e number of basins)
number of elements in each tree is the size of basin.

The challenge is building the tree itself.
Every element will have a list of children and a parent.
Note: If no children element is a high altitude point, if no parent its a sink point.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My algorithm:

- search the 2D array for local minimums (the number of local mins will be the number of basins)
- grow each minimum out as far as possible:
- add all neighburs of each local min to a list of potential locations that are a part of that basin
- for each of these candidates check their neighbours to see if they are in fact a part of that basin (they have no neighbours less than the local min)
- move these points to the list of points in the basin if the candidate passes the test, otherwise move to a list of rejected candidates
- for each new point in the basin, repeat this process for all neighbouring points that are not already in the basin and are not already in the list of rejected candidates

Comment hidden because of low score. Click to expand.
0
of 0 vote
1) Search through 2d array for basins, adding each basin to a hashmap/hashtable. This will be O(n) where n is the number of entries in the 2d array. A basin can be defined as an entry whose value is less than those of it's neighbours. 2) For each basin, perform a BFS or DFS (same runtime) to count the number of entries that belong to this basin. This is defined recursively as: {{{
Comment hidden because of low score. Click to expand.
0
of 0 vote
1) Search through 2d array for basins, adding each basin to a hashmap/hashtable. This will be O(n) where n is the number of entries in the 2d array. A basin can be defined as an entry whose value is less than those of it's neighbours. 2) For each basin, perform a BFS or DFS (same runtime) to count the number of entries that belong to this basin. This is defined recursively as: {{{
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, accidentally submitted.

The recursive algorithm to count the number of points that belong to a basin:

``````int basinSize(Node n) {
int size = 1;
for(Node neighbour : getSources(n)) {
size += basinSize(neighbour);
}
return size;
}``````

The method getSources(Node n) returns the set of nodes adjacent to Node n, such that n is the local sink for those nodes. For all non-basin nodes, this method will return at most 3 neighbour nodes.

Once we have the basin sizes for all basins, we simply sort the results.

Comment hidden because of low score. Click to expand.
0
of 0 vote

An easy solution (works for all the cases, showing just the first one):
Input:
3
1 5 2
2 4 7
3 6 9

Solution:
Let us consider the input is stored in an array Basin of type int.

At this point, make a new char array say Map (same as the size of the Basin)
Map holds the direction in which the number at a particular position should flow.

Now go through every number in Basin[i][j] (i,j=1 to 3) using a nested for loop (one pass, so complexity O(n)):
for each number, a Maximum of 5 check is required as follows:
set 1st number=current number(number being checked say Basin [i][j])
set 2nd number=number East(E) of current number (that is Basin[i][j+1])
set 3rd Number=number West(W) of current number (that is Basin[i][j-1])
set 4th Number=number North(N) of current number (that is Basin[i-1][j])
set 5th Number=number South(S) of current number (that is Basin[i+1][j])

now find the min of 5 numbers (which is not too bad)

Now there are 2 cases:
1) if current number if min, it is the Sink,
Update Map[i][j] as 1 (means it is first sink, you can do it using a counter and for the next sink, counter++)
2) if any other number is min (say E,W,N,S) set Map[i][j] to that character (it means, the flow is in that direction for the current number.

The Map Array after one pass through Basin looks like this:
1 W 2
N W N
N W W

Make a new array farmLand
Now Go through this Char array using a nested for loop and update farmLand[i][j] as follows:
if Map[i][j]=1 then 1st Basin and firmLand[i][j]=1

if Map[i][j]=W then go west of Map[i][j] which is Map[i][j-1] and check:
it is 1, set firmLand[i][j]=1

if Map[i][j]=N then go North of Map[i][j] which is Map[i-1][j] and check:
it is 1, set firmLand[i][j]=1

And so on,
The firmLand array will look like this:
1 1 2
1 1 2
1 1 1

Counting the number of elements in each Basin is very easy, as one is making firmLand, one can keep and ArrayList that is initialized with zero for every Sink. In this case we have 2 sink so the ArrayList count=new ArrayList() will look like this
count=[0,0]
As one finds a basin each time, just increment the count(i) by 1.
Finally for this case: count=[7,2]

Note: in the second pass also the running time O(n) and hence the the total running time is O(n)+O(n)=O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

The input block for the second example has an incorrect number:

Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5  2
3 3 5 2 1

Output:
11 7 7

The number in brackets above does not have a *unique* lowest neighbor, according to the actual Palantir page the 2 in position [4, 3] should be a 3

5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4  <-- should be a 3
3 3 5 2 1

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import sys
import pdb
basins = {}

points = {}

for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]

def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']

lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])

points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0

return lowest

def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest, lowest)
return points[(row, col)]['sink']

def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]

return [neighbor for neighbor in adjacent if neighbor in points]

for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1

basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import sys
import pdb
basins = {}

points = {}

for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]

def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']

lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])

points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0

return lowest

def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest, lowest)
return points[(row, col)]['sink']

def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]

return [neighbor for neighbor in adjacent if neighbor in points]

for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1

basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import sys

basins = {}

points = {}

for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]

def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']

lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])

points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0

return lowest

def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest, lowest)
return points[(row, col)]['sink']

def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]

return [neighbor for neighbor in adjacent if neighbor in points]

for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1

basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)``````

Comment hidden because of low score. Click to expand.
0

fuarr

Comment hidden because of low score. Click to expand.
0
of 0 vote

I wrote the following code for the problem, the problem had a slight modification as each cell had 8 neighboring cells, but the code returned bad_alloc error and I am not able to figure out why its happening when the memory limit is 256 MB

``````#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>

using namespace std;

// this function is used to assign a label to each cell in the farmer's land representing the connected component it belongs to
char assignLabel(vector< vector<int> >& elevationData , vector< vector<char> >& basinLabels , int i , int j , int S){

// these variables are used to find the index of the minimum elevation data cell
int minRow , minCol , minElevation;
minRow = i;
minCol = j;
minElevation = elevationData[i][j];

// check the cell above
if(i-1 > 0){
if(elevationData[i-1][j] < minElevation){
minRow = i-1;
minCol = j;
minElevation = elevationData[i-1][j];
}
}

// check the cell below
if(i+1 <= S){
if(elevationData[i+1][j] < minElevation){
minRow = i+1;
minCol = j;
minElevation = elevationData[i+1][j];
}
}

// check the cell to the left
if(j-1 > 0){
if(elevationData[i][j-1] < minElevation){
minRow = i;
minCol = j-1;
minElevation = elevationData[i][j-1];
}
}

// check the cell to the right
if(j+1 <= S){
if(elevationData[i][j+1] < minElevation){
minRow = i;
minCol = j+1;
minElevation = elevationData[i][j+1];
}
}

// compare with the cell diagonally to the left above
if(i-1 > 0 && j-1 >0){
if(elevationData[i-1][j-1] < minElevation){
minRow = i-1;
minCol = j-1;
minElevation = elevationData[i-1][j-1];
}
}

// compare with the cell diagonally below to right
if(i+1 <= S && j+1 <= S){
if(elevationData[i+1][j+1] < minElevation){
minRow = i+1;
minCol = j+1;
minElevation = elevationData[i+1][j+1];
}
}

// compare with the cell diagonally to the right above
if(i-1 > 0 && j+1 <= S){
if(elevationData[i-1][j+1] < minElevation){
minRow = i-1;
minCol = j+1;
minElevation = elevationData[i-1][j+1];
}
}

// compare with the cell diagonally to the left below
if(i+1 <= S && j-1 > 0){
if(elevationData[i+1][j-1] < minElevation){
minRow = i+1;
minCol = j-1;
minElevation = elevationData[i+1][j-1];
}
}

if(basinLabels[minRow][minCol] != 'A'-1){
basinLabels[i][j] = basinLabels[minRow][minCol];
return basinLabels[i][j];
}
else
basinLabels[i][j] = assignLabel(elevationData,basinLabels,minRow,minCol,S);
}

// this function is used to check if a particular cell is a sink or not
bool checkSink(vector< vector<int> >& elevationData , int i , int j, int S){

// compare with the cell above
if(i-1 > 0){
if(elevationData[i-1][j] < elevationData[i][j])
return false;
}

// compare with the cell below
if(i+1 <= S){
if(elevationData[i+1][j] < elevationData[i][j])
return false;
}

// compare with the cell to the left
if(j-1 > 0){
if(elevationData[i][j-1] < elevationData[i][j])
return false;
}

// compare with the cell to the right
if(j+1 <= S){
if(elevationData[i][j+1] < elevationData[i][j])
return false;
}

// compare with the cell diagonally to the left above
if(i-1 > 0 && j-1 >0){
if(elevationData[i-1][j-1] < elevationData[i][j])
return false;
}

// compare with the cell diagonally below to right
if(i+1 <= S && j+1 <= S){
if(elevationData[i+1][j+1] < elevationData[i][j])
return false;
}

// compare with the cell diagonally to the right above
if(i-1 > 0 && j+1 <= S){
if(elevationData[i-1][j+1] < elevationData[i][j])
return false;
}

// compare with the cell diagonally to the left below
if(i+1 <= S && j-1 > 0){
if(elevationData[i+1][j-1] < elevationData[i][j])
return false;
}

return true;
}

int main(){

// this integer represents the width and height of the farmer's land
int S;
cin >> S;

// this 2D vector represents the farmer's land
vector< vector< int > > elevationData(S+2 , vector<int>(S+2));

// scan the elevation data
for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j)
cin >> elevationData[i][j];
}

// this set actually stores all the sinks present in the farmer's land
set< pair<int,int> > sinkSet;

for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(checkSink(elevationData,i,j,S))
sinkSet.insert( make_pair(i,j) );
}
}

// this is used to assign a unique character to each sink
char sinkLabel = 'A';

// this vector stores the labels of the different basins in the farmer's land
vector< vector< char > > basinLabels(S+2 , vector< char >(S+2));

for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(sinkSet.find( make_pair(i,j) ) != sinkSet.end()){
basinLabels[i][j] = sinkLabel;
++sinkLabel;
}else{
basinLabels[i][j] = 'A'-1;
}
}
}

for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(basinLabels[i][j] == 'A'-1)
assignLabel(elevationData , basinLabels , i , j , S);
}
}

// this vector stores the sizes of the components
vector<int> basinSize;
sinkLabel = 'A';

// count the number of cells in a single connected component
for(int i = 0 ; i < (int)sinkSet.size() ; ++i){
int count = 0;
for(int j = 1 ; j < S+1 ; ++j){
for(int k = 1 ; k < S+1 ; ++k){
if(basinLabels[j][k] == sinkLabel)
++count;
}
}

basinSize.push_back(count);
++sinkLabel;
}

// sort the connected components by size
sort(basinSize.begin() , basinSize.end());

for(int i = (int)basinSize.size() - 1 ; i >= 0 ; --i)
cout << basinSize[i] << " ";
cout << endl;

elevationData.clear();
basinLabels.clear();

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution is O(n * m) (size of the matrix).
First let's build a graph: for each cell we define the cell where the water goes.
Now the answer is the number of connected components. We can do DFS for that. We start from some not labeled cell with DFS and mark all cells with some new_number (id). If we found vertex already marked with other id, connected to current component, we can then repaint everything with this color. BFS would be better probably, cause we can just save all the queue and repaint it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Took me 80 minutes. My method:

I start from each point in the land to go down the stream and I number a second array with basin numbers. If I hit an basin number other than the current one I reassign the basin numbers (on my way out from recursion). I also increment an array with basin counters (hash) each time I assign a basin number in this double loop. Then I sort and output.
Code:

``````public class Main {

public static int MAX_ELEVATION = 1000000; // maximum elevation
public static int MAX_BASINS = 1000;

public static void main ( String [] arguments ) throws IOException
{

// get user input

int size = Integer.parseInt(line.trim());

int [][]land = new int[size][size];
int [][]basins = new int[size][size];
int []basinCounts = new int[MAX_BASINS];

for (int i = 0; i < size; i ++) {

String[] splitted = elevations.split("\\s+");

for (int j = 0; j < size; j ++) {

land[i][j] = Integer.parseInt(splitted[j].trim());
basins[i][j] = -1;

}

}

// walk through land and count basins

for (int i = 0; i < size; i ++) {

for (int j = 0; j < size; j ++) {

basinCounts[walkThroughBasin(i, j, 0, land, basins, size)] ++;

}

}

// sort basins

Arrays.sort(basinCounts);

for( int i = 0; i < basinCounts.length/2; ++i ) {
int temp = basinCounts[i];
basinCounts[i] = basinCounts[basinCounts.length - i - 1];
basinCounts[basinCounts.length - i - 1] = temp;
}

// output

for (int i = 0; i < currentBasin; i ++) {

System.out.print(basinCounts[i] + " ");

}

}

public static int currentBasin = 0;

public static int walkThroughBasin(int i, int j, int basin, int [][]land, int [][]basins, int size) {

if (basins[i][j] != -1)
return basins[i][j];

int vl = i > 0 ? land[i-1][j] : MAX_ELEVATION;
int vr = i < size - 1 ? land[i + 1][j] : MAX_ELEVATION;
int vu = j > 0 ? land[i][j - 1] : MAX_ELEVATION;
int vd = j < size - 1 ? land[i][j + 1] : MAX_ELEVATION;

if (vl <= vr && vl <= vu && vl <= vd && vl < land[i][j]) {

basin = walkThroughBasin(i - 1, j, basin, land, basins, size);

} else

if (vr <= vl && vr <= vu && vr <= vd && vr < land[i][j]) {

basin = walkThroughBasin(i + 1, j, basin, land, basins, size);

} else

if (vu <= vr && vu <= vl && vu <= vd && vu < land[i][j]) {

basin = walkThroughBasin(i, j - 1, basin, land, basins, size);

} else

if (vd <= vr && vd <= vu && vd <= vl && vd < land[i][j]) {

basin = walkThroughBasin(i, j + 1, basin, land, basins, size);

} else {

basins[i][j] = currentBasin;
return currentBasin ++;

}

basins[i][j] = basin;
return basin;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python implementation

``````import sys
#-------------------------------------------------------------------------------
def printFunc(x,y):
sys.stdout.write( "(" +str(x) + "," + str(y)+")" )

#-------------------------------------------------------------------------------
def printFunc1(x):
sys.stdout.write( str(x)+" " )

#-------------------------------------------------------------------------------
def isSink(x,y,n,grid):
curr  = grid[y][x]

#North
if (y-1) >= 0 and grid[y-1][x] < curr:
return False
#South
if (y+1) < n and grid[y+1][x] < curr:
return False
#West
if (x-1) >= 0 and grid[y][x-1] < curr:
return False
#East
if (x+1) < n and grid[y][x+1] < curr:
return False
return True

#-------------------------------------------------------------------------------
def drainToSink(x,y,n,grid,visited,num):

curr = grid[y][x]

if visited[y][x] >= 0:
return num

minX = x
minY = y
currVisitList=[]
while not isSink(x,y,n,grid):
#North
if (y-1) >= 0 and grid[y-1][x] < curr:
minY = y-1
minX = x
curr = grid[minY][minX]
#South
if (y+1) < n and grid[y+1][x] < curr:
minY = y+1
minX = x
curr = grid[minY][minX]
#West
if (x-1) >= 0 and grid[y][x-1] < curr:
minX=x-1
minY = y
curr = grid[minY][minX]
#East
if (x+1) < n  and grid[y][x+1] < curr:
minX=x+1
minY = y
curr = grid[minY][minX]

currVisitList.append([x,y])
if visited[minY][minX] >= 0:
#Trace back and assign the value of visited node
for pair in currVisitList:
xt = pair
yt = pair
visited[yt][xt] = visited[minY][minX]
return num

x = minX
y = minY

for pair in currVisitList:
xt = pair
yt = pair
visited[yt][xt] = num

visited[minY][minX] = num
return num+1

#-------------------------------------------------------------------------------
#Start by opening the file.
fIn = open(sys.argv,'r')

landGrid=[]

#Create an array of integers representing elevation.
for line in fIn:
intList = map(int, line.split(' '))
landGrid.append( intList )
#print intList

#practice printing arrays
for y in range(0,n):
for x in range(0,n):
printFunc1(landGrid[y][x])
print

#Initialize and empty 2d array.
#-1 marks unvisited elements
visited =[]
for y in range(0,n):
tempList = []
for x in range(0,n):
tempList.append( -1 )
visited.append(tempList)

print "-----------------------------------"

numSinks = 0
for y in range(0,n):
for x in range(0,n):
numSinks = drainToSink(x,y,n,landGrid,visited,numSinks)

print numSinks

for y in range(0,n):
for x in range(0,n):
printFunc1(visited[y][x])
print

#initialize an array with basin counts.
basinCounts=[]
for i in range(0,numSinks):
basinCounts.append(0)

#now count them.
for lst in visited:
for x in lst:
basinCounts[x] = basinCounts[x]+1

basinCounts.sort(reverse=True)
print
for x in basinCounts:
sys.stdout.write( str(x)+" " )

print``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution follows the O(m*n) scan and DFS algorithm. I'm pretty sure this is O(m*n) because each node is guaranteed to be visited once. In layman's terms this is what I do:

1. Scan each node marking the node as visited iff the node is considered a sink
2. For sink nodes, perform a DFS on the node to find the members of this basin.
3. For each member of the current basin, mark as visited and continue checking while incrementing the current count.
4. Add the basin count to the result list.
5. Once all nodes have been visited, print the basin size list in descending order.

EDIT: Fixed the output to be in-line with the required solution and removed debug printing.

``````import java.io.BufferedReader;
import java.io.FileInputStream;
import java.util.*;

/**
* @author chris moran
*/
public class RainfallDFS {
public static void main(String[] args) {
int[][] rain = buildMatrix("rainfall.txt");
boolean[][] visited = new boolean[rain.length][rain.length];
for(boolean[] v : visited)
Arrays.fill(v, false);

List<Integer> basins = new ArrayList<Integer>();
for(int y = 0; y < rain.length; y++) {
for(int x = 0; x < rain[y].length; x++) {
processMatrix(rain, visited, y, x, basins);
}
}
Collections.sort(basins, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for(int basin:basins)
System.out.print(basin + " ");
}
private static List<Integer> processMatrix(int[][] rain, boolean[][] visited, int y, int x, List<Integer> basins) {
if(visited[y][x])
return basins;
if(isSink(rain, y, x)) {
int count = processDFS(rain, visited, y, x);
visited[y][x] = true;
}
return basins;
}

private static int processDFS(int[][] rain, boolean[][] visited, int y, int x) {
int count = 0;
if(visited[y][x])
return count;
visited[y][x] = true;
count++;

if(x + 1 < rain[y].length && rain[y][x + 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x+1)) {//Are we the lowest of right's neighbors?
count += processDFS(rain, visited, y, x + 1);
}
if(x - 1 >= 0 && rain[y][x - 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x-1)) {//Are we the lowest of left's neighbors?
count += processDFS(rain, visited, y, x - 1);
}
if(y + 1 < rain.length && rain[y+1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y+1, x)) {//Are we the lowest of down's neighbors?
count += processDFS(rain, visited, y+1, x);
}
if(y - 1 >= 0 && rain[y-1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y-1, x)) {//Are we the lowest of up's neighbors?
count += processDFS(rain, visited, y-1, x);
}
return count;
}

private static int findLowest(int[][] rain, int y, int x) {
int clow = Integer.MAX_VALUE;
if(x + 1 < rain[y].length) {//r
clow = Math.min(clow, rain[y][x+1]);
}
if(x - 1 >= 0) {//l
clow = Math.min(clow, rain[y][x-1]);
}
if(y + 1 < rain.length) {//d
clow = Math.min(clow, rain[y+1][x]);
}
if(y - 1 >= 0) {//u
clow = Math.min(clow, rain[y-1][x]);
}
return clow;
}

private static boolean isSink(int[][] rain, int y, int x) {
boolean isSink = true;
if(x + 1 < rain[y].length) {//r
isSink = rain[y][x] < rain[y][x + 1];
}
if(x - 1 >= 0) {//l
isSink &= rain[y][x] < rain[y][x - 1];
}
if(y + 1 < rain.length) {//d
isSink &= rain[y][x] < rain[y + 1][x];
}
if(y - 1 >= 0) {//u
isSink &= rain[y][x] < rain[y - 1][x];
}
return isSink;
}

private static int[][] buildMatrix(String s) {
int[][] matrix = null;
try {
int size = Integer.parseInt(line.trim());
matrix = new int[size][size];
for(int i = 0; i < size; i++) {
StringTokenizer st = new StringTokenizer(line);
for(int j = 0; j < size; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken().trim());
}
}
} catch(Exception ignored) {
}
return matrix;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import sys

def find_root(i, set):
if set[i] < 0:
return i
else:
return find_root(set[i],set)

def method():
# taking stdin and making a matrix
print(size)
size = int(size)
matrix = [None]*size
count = 0
for line in sys.stdin:
row = line.split(' ')
print(row)
for i in range(len(row)):
row[i] = int(row[i])
matrix[count] = row
count+=1
print(matrix)

# we also want to make a list of size = size*size
set_map = [None]*(size*size)

# iterate through the whole matrix
for i in range(size):
for j in range(size):
my_val = matrix[i][j]
my_idx = -1
east = matrix[i][j]
west = matrix[i][j]
north = matrix[i][j]
south = matrix[i][j]

if i+1 < size:
south = matrix[i+1][j]
if j+1 < size:
east = matrix[i][j+1]
if i-1 >= 0:
north = matrix[i-1][j]
if j-1 >= 0:
west = matrix[i][j-1]

if my_val > east:
my_val = east
my_idx = size*i + j + 1

if my_val > west:
my_val = west
my_idx = size*i + j - 1

if my_val > south:
my_val = south
my_idx = size*(i+1) + j

if my_val > north:
my_val = north
my_idx = size*(i-1)+j

#find the minimum value and set the index of the min value direction
# as the root of the current index
# basically you are making a disjoint set
set_map[size*i+j] = my_idx

# we have made a disjoint set  with the set_map now
# it is time to find the number of roots
root_dict = {}

for i in range(size*size):
root = find_root(i, set_map)
if root in root_dict:
root_dict[root] += 1
else:
root_dict[root] = 1
print(root_dict) #this will print out the a dictionary of root and the number
# of elements in the set that have the root as their key

if __name__ == '__main__':
method()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I did it in O(n), i using DFS concept.
You can look at the code in my github/nadavcohe

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just another solution -
1) For every element in matrix(at pos1), find smallest(pos2) in its surroundings and record its position in format (row*ROWS+col);
2) union the original position to this position. union1(pos1,pos2);
3)store in map and sort by frequency
4)print it

``````#include    <iostream>
#include    <algorithm>
#include	<climits>
#include	<unordered_map>
#include	<vector>
#define NEIGHBOURS 4
using namespace std;
typedef vector< vector<int> > matrix;
int neighbour[NEIGHBOURS] = { {0,-1}, {-1,0},{0,1},{1,0} };
int find(int id[],int p) {
while(p != id[p])
p = id[p];
return p;
}
void union1(int id[],int p,int q) {
int proot = find(id,p);
int qroot = find(id,q);
if(proot != qroot)
id[proot] = qroot;
}
bool issafe(int p,int S) {
return (p>=0 && p < S);
}
int small(matrix m,int i,int j,int S) {
int sm = m[i][j];
int pos = i*S+j;
for(int k=0;k<NEIGHBOURS;k++) {
if( issafe(neighbour[k]+i,S) && issafe(neighbour[k]+j,S) ) {
int tmp = min(sm, m[ neighbour[k]+i ] [ neighbour[k]+j ]);
if(sm != tmp)
pos = S*(neighbour[k]+i) + neighbour[k]+j;
sm = tmp;
}
}
return pos;
}
int main()
{
/*matrix mat = {
{1, 5, 2},
{2, 4, 7},
{3, 6, 9}
};*/
matrix mat = {
{1, 0, 2, 5, 8},
{2, 3, 4, 7, 9 },
{3, 5, 7, 8, 9},
{1, 2, 5, 4, 2},
{3, 3, 5, 2, 1}
};
int S = 5;
unordered_map<int,int> m;
vector<int> v;
int id[S*S];
for(int i=0;i<S*S;i++) {
id[i] = i;
}
for(int i=0;i<S;i++) {
for(int j=0;j<S;j++) {
int s = small(mat,i,j,S);
if( s != i*S +j)
union1(id,i*S+j,s);
}
}
for(int i=0;i<S*S;i++) {
m[ find(id,id[i]) ]++;
}
for(auto i:m) {
v.push_back(i.second);
}
sort(v.rbegin(),v.rend());
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This also seems like a problem that would could be solved easily with a functional programming language.

Can someone solve this in Haskell, Scala, or Clojure and post the code here?
Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct Cell
{
int x, y;
char marker;
};

bool is_digit(char c)
{
return '0' <= c && c <= '9';
}

void clasterize(vector<vector<char>> &map)
{
char marker = 'A';
auto compare = [](pair<int, Cell> const &lhs, pair<int, Cell> const &rhs){ return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second.x < rhs.second.x) || (lhs.first == rhs.first && lhs.second.x == rhs.second.x && lhs.second.y < rhs.second.y); };
set<pair<int, Cell>, decltype(compare)> queue(compare);

for (auto i = 0; i < map.size(); ++i)
for (auto j = 0; j < map[i].size(); ++j)
{
bool top, bottom, right, left;

top = bottom = right = left = false;

if (0 == i || (i > 0 && map[i-1][j] > map[i][j]))
top = true;

if (map.size()-1 == i || (i < map.size()-1 && map[i+1][j] > map[i][j]))
bottom = true;

if (0 == j || (j > 0 && map[i][j-1] > map[i][j]))
left = true;

if (map[i].size()-1 == j || (j < map[i].size()-1 && map[i][j+1] > map[i][j]))
right = true;

if (top && bottom && left && right)
queue.insert(make_pair(map[i][j], Cell({.x = i, .y = j, .marker = marker++})));
}

while (!queue.empty())
{
auto cell = (*queue.begin()).second;

queue.erase(queue.begin());

if (is_digit(map[cell.x][cell.y]))
{
map[cell.x][cell.y] = cell.marker;

if (cell.x > 0 && is_digit(map[cell.x-1][cell.y]))
queue.insert(make_pair(map[cell.x-1][cell.y], Cell({.x = cell.x-1, .y = cell.y, .marker = cell.marker})));

if (cell.x < map.size()-1 && is_digit(map[cell.x+1][cell.y]))
queue.insert(make_pair(map[cell.x+1][cell.y], Cell({.x = cell.x+1, .y = cell.y, .marker = cell.marker})));

if (cell.y > 0 && is_digit(map[cell.x][cell.y-1]))
queue.insert(make_pair(map[cell.x][cell.y-1], Cell({.x = cell.x, .y = cell.y-1, .marker = cell.marker})));

if (cell.y < map[cell.x].size()-1 && is_digit(map[cell.x][cell.y+1]))
queue.insert(make_pair(map[cell.x][cell.y+1], Cell({.x = cell.x, .y = cell.y+1, .marker = cell.marker})));
}
}
}

int main()
{
vector<vector<char>> map =
{
{'1', '0', '2', '5', '8'},
{'2', '3', '4', '7', '9'},
{'3', '5', '7', '8', '9'},
{'1', '2', '5', '4', '2'},
{'3', '3', '5', '2', '1'}
};

clasterize(map);

for (auto v : map)
{
for (auto c : v)
cout << c << " ";

cout << endl;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

It's a kind of shortest path problem, so use BFS and a priority queue.
At the beginning traverse the map and find all sinks. Push them to the priority queue, where primary priority is land's height at that sink. You should also assign a marker to any cell you push to the queue. Initially just increment your marker starting with 'A' and assign it to each sink you find.
The loop until queue is empty. Pop a cell on the top of the queue and if the land corresponding to that cell has not being marked, mark it with the cell's marker and add to the queue any unmarked neighbors.
To count the number of As, Bs, etc. just count what marker you're assigning to an unmarked land once you've popped the next cell from the queue.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a modified version of BFS, which start from the lowest value.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This could be done in liner time with having extra space.
start for first element and mark a unique flag (start with 1) for each element that has visited and its corresponding lowest neighbor.if lowest neighbor has been visited then mark that position with same flag, else assign different flag .
In case If a different flags lowest neighbor is already visited and its flag is differ then make both flag with same group.
In the last you may count nbr of basin on the basis of flag(flag group).

Comment hidden because of low score. Click to expand.
0

What you describe is not linear. Even if it is, you still need to display the basins in descending order. How do you do this linearly?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.