Ledger Nano X - The secure hardware wallet
SHARE
TWEET

twitter puddle

marianolatorre Oct 25th, 2014 174 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Solving http://programmingpraxis.com/2013/11/15/twitter-puddle/
  3. Twitter interview question
  4. */
  5. package com.company;
  6. import java.util.*;
  7.  
  8. enum Orientation {DOWN, UP};
  9.  
  10. class Walls{
  11.     public static void main(String []args){
  12.  
  13.         HashMap<String, Integer> tests = new HashMap<String,Integer>();
  14.         tests.put("2 5 1 2 3 4 7 7 6", 10);
  15.         tests.put("2 2 5 1 3 1 2 1 7 7 6", 17);
  16.         tests.put("2 7 2 7 4 7 1 7 3 7", 18);
  17.         tests.put("4 6 7 7 4 3 2 1 5 2", 10);
  18.         tests.put("5 2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4", 26);
  19.  
  20.         Iterator it = tests.entrySet().iterator();
  21.         while (it.hasNext()) {
  22.             Map.Entry pairs = (Map.Entry)it.next();
  23.             it.remove();
  24.  
  25.             String[] strings = ((String)pairs.getKey()).split(" ");
  26.             int[] walls = new int[strings.length];
  27.             for (int i = 0; i < walls.length; i++){
  28.                 walls[i] = Integer.parseInt(strings[i].trim());
  29.             }
  30.             System.out.println(pairs.getKey()+" result="+accumulatedWater(walls)+" expected= " +pairs.getValue());
  31.  
  32.         }
  33.     }
  34.  
  35.     static int accumulatedWater(int []wall){
  36.         int MAX = 0;
  37.         int start = 0;
  38.  
  39.         for(int i=0;i < wall.length;i++){  //let's go to the first peak
  40.             if(wall[i] >= MAX){
  41.                 MAX = wall[i];
  42.                 start = i;
  43.             }else{
  44.                 break;
  45.             }
  46.         }
  47.         int []accumulate_max = new int[MAX+1];  // sums up to certain height
  48.         int []accumulate_max_step = new int[MAX+1]; // steps up to certain height
  49.  
  50.         Orientation going = Orientation.DOWN;
  51.         int prev = MAX;
  52.         int local_sum=0;
  53.         int total_sum=0;
  54.  
  55.         int PREVPEAK = MAX;
  56.  
  57.         for(int i=start+1; i< wall.length; i++){
  58.  
  59.             if( i == wall.length -1 ||
  60.                 wall[i] < prev  && going == Orientation.UP ){
  61.                 going = Orientation.DOWN;
  62.                 if(wall[i-1] >= MAX){
  63.                     total_sum +=  accumulate_max_step[MAX-1] * MAX - accumulate_max[MAX-1];
  64.                     MAX = wall[i-1];
  65.                     PREVPEAK = MAX;
  66.                     accumulate_max = new int[MAX+1];
  67.                     accumulate_max_step = new int[MAX+1];
  68.                     local_sum = 0;
  69.                 }else{
  70.                     int indexNewPeak = (i == wall.length -1 && wall[i]> wall[i-1]) ? i : i-1;
  71.                     int water =  accumulate_max_step[wall[indexNewPeak]-1] * wall[indexNewPeak] - accumulate_max[wall[indexNewPeak]-1];
  72.                     if(wall[indexNewPeak] > PREVPEAK){
  73.                         local_sum = water;
  74.                         PREVPEAK = wall[indexNewPeak];
  75.                     }else{
  76.                         local_sum += water;
  77.                     }
  78.  
  79.                 }
  80.             }else if(wall[i]>prev){
  81.                 going = Orientation.UP;
  82.             }
  83.  
  84.             for(int j=wall[i];j <= MAX;j++){
  85.                 accumulate_max[j]      += wall[i];
  86.                 accumulate_max_step[j] += 1;
  87.             }
  88.  
  89.             prev = wall[i];
  90.         }
  91.         return total_sum + local_sum;
  92.     }
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top