Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Solving http://programmingpraxis.com/2013/11/15/twitter-puddle/
- Twitter interview question
- */
- package com.company;
- import java.util.*;
- enum Orientation {DOWN, UP};
- class Walls{
- public static void main(String []args){
- HashMap<String, Integer> tests = new HashMap<String,Integer>();
- tests.put("2 5 1 2 3 4 7 7 6", 10);
- tests.put("2 2 5 1 3 1 2 1 7 7 6", 17);
- tests.put("2 7 2 7 4 7 1 7 3 7", 18);
- tests.put("4 6 7 7 4 3 2 1 5 2", 10);
- tests.put("5 2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4", 26);
- Iterator it = tests.entrySet().iterator();
- while (it.hasNext()) {
- Map.Entry pairs = (Map.Entry)it.next();
- it.remove();
- String[] strings = ((String)pairs.getKey()).split(" ");
- int[] walls = new int[strings.length];
- for (int i = 0; i < walls.length; i++){
- walls[i] = Integer.parseInt(strings[i].trim());
- }
- System.out.println(pairs.getKey()+" result="+accumulatedWater(walls)+" expected= " +pairs.getValue());
- }
- }
- static int accumulatedWater(int []wall){
- int MAX = 0;
- int start = 0;
- for(int i=0;i < wall.length;i++){ //let's go to the first peak
- if(wall[i] >= MAX){
- MAX = wall[i];
- start = i;
- }else{
- break;
- }
- }
- int []accumulate_max = new int[MAX+1]; // sums up to certain height
- int []accumulate_max_step = new int[MAX+1]; // steps up to certain height
- Orientation going = Orientation.DOWN;
- int prev = MAX;
- int local_sum=0;
- int total_sum=0;
- int PREVPEAK = MAX;
- for(int i=start+1; i< wall.length; i++){
- if( i == wall.length -1 ||
- wall[i] < prev && going == Orientation.UP ){
- going = Orientation.DOWN;
- if(wall[i-1] >= MAX){
- total_sum += accumulate_max_step[MAX-1] * MAX - accumulate_max[MAX-1];
- MAX = wall[i-1];
- PREVPEAK = MAX;
- accumulate_max = new int[MAX+1];
- accumulate_max_step = new int[MAX+1];
- local_sum = 0;
- }else{
- int indexNewPeak = (i == wall.length -1 && wall[i]> wall[i-1]) ? i : i-1;
- int water = accumulate_max_step[wall[indexNewPeak]-1] * wall[indexNewPeak] - accumulate_max[wall[indexNewPeak]-1];
- if(wall[indexNewPeak] > PREVPEAK){
- local_sum = water;
- PREVPEAK = wall[indexNewPeak];
- }else{
- local_sum += water;
- }
- }
- }else if(wall[i]>prev){
- going = Orientation.UP;
- }
- for(int j=wall[i];j <= MAX;j++){
- accumulate_max[j] += wall[i];
- accumulate_max_step[j] += 1;
- }
- prev = wall[i];
- }
- return total_sum + local_sum;
- }
- }
Add Comment
Please, Sign In to add comment