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.io.InputStreamReader;
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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		dimension = Integer.parseInt(br.readLine());
		land = new Result[dimension][dimension];
		for(int i = 0; i < dimension; i++){
			String line = br.readLine();
			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();
	}
}

- Nitin Gupta February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Kyle January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

package com.nbethi.basins;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BasinUtil {

	public static void main(String args[]) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Please enter square size : ");
		String line = reader.readLine();
		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+")"+" : ");
				line = reader.readLine();
				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.

- nbethi February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- nbethi February 05, 2013 | Flag
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.

- Nitin Gupta February 05, 2013 | Flag Reply
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.

- Philip May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.nbethi.basins;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BasinUtil {

public static void main(String args[]) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter square size : ");
String line = reader.readLine();
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+")"+" : ");
line = reader.readLine();
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.

- naresh b February 03, 2013 | Flag Reply
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'){
      var coords = findLowestAdjacent(i,j,alts);
      val = map[coords[0]][coords[1]];
      i = coords[0];
      j = coords[1];
    }
    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
 */
function findLowestAdjacent(i,j,alts){
   var min = Infinity;
   var coords = [];
   surroundingCoords.forEach(function(v){
      if (alts[i + v[0]] && alts[i + v[0]][j + v[1]] < min){
         min = alts[i + v[0]][j + v[1]];
         coords = [i + v[0], j + v[1]];
      }
   });
    
   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[0]] && alts[i + v[0]][j + v[1]] != undefined){
         b.push(alts[i + v[0]][j + v[1]]);
      }
    });   
    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());

- Nick February 03, 2013 | Flag Reply
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[5000][5000];
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;
}

- Evans February 04, 2013 | Flag Reply
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.LinkedList;
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[4];
			if (x - 1 >= 0 && matrix[x - 1][y].isVisited == false) {
				neighbors[0] = matrix[x - 1][y];
			} else {
				neighbors[0] = null;
			}
			if (x + 1 < size && matrix[x + 1][y].isVisited == false) {
				neighbors[1] = matrix[x + 1][y];
			} else {
				neighbors[1] = null;
			}
			if (y - 1 >= 0 && matrix[x][y - 1].isVisited == false) {
				neighbors[2] = matrix[x][y - 1];
			} else {
				neighbors[2] = null;
			}
			if (y + 1 < size && matrix[x][y + 1].isVisited == false) {
				neighbors[3] = matrix[x][y + 1];
			} else {
				neighbors[3] = 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() {

		List<Cell> stack = new LinkedList<Cell>();
		stack.add(matrix[0][0]);
		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()) {
					stack.add(neighbor);
				}
			}
		}
	}

	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 + " ");
		}
	}
}

- Anon February 05, 2013 | Flag Reply
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.)
--if not found make this root (its a sink).
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.

- Vinay Gangoli February 05, 2013 | Flag Reply
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

- David March 06, 2013 | Flag Reply
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: {{{ - Kevin September 20, 2013 | Flag Reply
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: {{{ - Kevin September 20, 2013 | Flag Reply
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.

- Kevin September 20, 2013 | Flag Reply
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[3][3] of type int.

At this point, make a new char array say Map[3][3] (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[3][3]
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[3][3] 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).

- Arunbha Choudhury-Rock Chalk Jayhawk December 05, 2013 | Flag Reply
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 [4] 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 [2] <-- should be a 3
3 3 5 2 1

- Hunter January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys
import pdb
basins = {}

points = {}

map_size = int(sys.stdin.readline().strip())


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[0], lowest[1])
    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)

- zyzz January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys
import pdb
basins = {}

points = {}

map_size = int(sys.stdin.readline().strip())


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[0], lowest[1])
    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)

- zyzz January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

basins = {}

points = {}

map_size = int(sys.stdin.readline().strip())


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[0], lowest[1])
    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)

- zyzz January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

fuarr

- jbw January 05, 2014 | Flag
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;
}

- Ankit Sablok January 24, 2014 | Flag Reply
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.

- Alex February 07, 2014 | Flag Reply
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 
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		String line = reader.readLine();
		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 elevations = reader.readLine();
			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;
	
	}
		
}

- jbweimar April 29, 2014 | Flag Reply
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[0]
				yt = pair[1]
				visited[yt][xt] = visited[minY][minX]
			return num
		
		x = minX
		y = minY
	
	for pair in currVisitList:
		xt = pair[0]
		yt = pair[1]
		visited[yt][xt] = num
		
	visited[minY][minX] = num
	return num+1 
	
		
#-------------------------------------------------------------------------------	
#Start by opening the file.
fIn = open(sys.argv[1],'r')

n = int( fIn.readline() )

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

- Mzuka May 02, 2014 | Flag Reply
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.io.InputStreamReader;
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[0].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);
            basins.add(count);
            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 {
                BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
                String line = bufferedReader.readLine();
                int size = Integer.parseInt(line.trim());
                matrix = new int[size][size];
                line = bufferedReader.readLine().trim();
                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());
                    }
                    line = bufferedReader.readLine();
                }
            } catch(Exception ignored) {
            }
            return matrix;
        }

}

- Chris July 31, 2014 | Flag Reply
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
	size = sys.stdin.readline()
	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()

- Anonymous October 05, 2014 | Flag Reply
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

- Nadav February 09, 2015 | Flag Reply
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][2] = { {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][0]+i,S) && issafe(neighbour[k][1]+j,S) ) {
            int tmp = min(sm, m[ neighbour[k][0]+i ] [ neighbour[k][1]+j ]);
            if(sm != tmp)
            	pos = S*(neighbour[k][0]+i) + neighbour[k][1]+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;
}

- ~amit June 02, 2015 | Flag Reply
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.

- Anonymous June 23, 2015 | Flag Reply
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;
}

- shoumikhin December 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- shoumikhin December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Union find algorithm is the right fit for this problem.
For each cell find another cell where it flows to and the group them in one group.
Finally return the number of basins.

class Solution:
    def group_of_basins(self):
        N, M = list(map(int, input().split()))
        graph = self.get_graph(N, M)
        parent = {(row, col):(row, col) for row in range(N) for col in range(M)}
        self.size = {(row, col):1 for row in range(N) for col in range(M)}
        
        for row in range(N):
            for col in range(M):
                sink_row, sink_col = row, col 
                value = graph[row][col]
                DIR = [(1, 0), (0, 1), (-1, 0), (0, -1)]
                for row_increase, col_increase in DIR:
                    new_row = row + row_increase 
                    new_col = col + col_increase 
                    if 0 <= new_row < N and 0 <= new_col < M:
                        if graph[new_row][new_col] < value:
                            sink_row = new_row 
                            sink_col = new_col 
                            value = graph[new_row][new_col]
                self.union((row, col), (sink_row, sink_col), parent)
        processed = set()
        result = []
        for row in range(N):
            for col in range(M):
                par = self.find((row, col), parent)
                if par not in processed:
                    result.append(self.size[par])
                    processed.add(par)
        return sorted(result, reverse = True)
    
            
                
                
    def find(self, x, parent):
        if parent[x] == x:
           return x 
        parent[x] = self.find(parent[x], parent)
        return parent[x]
    
    def union(self, x, y, parent):
        x_parent = self.find(x, parent)
        y_parent = self.find(y, parent)
        if x_parent != y_parent:
            if self.size[x_parent] < self.size[y_parent]:
                x_parent, y_parent = y_parent, x_parent
         
            self.size[x_parent] += self.size[y_parent]
            parent[y_parent] = x_parent 
        
        
    def get_graph(self, N, M):
        graph = []
        for _ in range(N):
            graph.append(list(map(int, input().split())))
        return graph 
solution = Solution()
result = solution.group_of_basins()
print(result)

- sefineh.T November 19, 2022 | Flag Reply
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.

- struggleyb February 03, 2013 | Flag Reply
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).

- Amit Singh Gaurav May 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- jbweimar May 08, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More