HackerRank : Stryker Codesprint- Point Filtering

By | September 18, 2016

You are given a main list of entries that consists of 3D points where each point has a unique integer ID, , that corresponds to an coordinate value. You are also given a bucket size, . Then sort the main list by decreasing value (it is guaranteed that the value is distinct), remove the first points, and put them in the bucket. Next, you must perform an unknown number () of queries in the following form:

  • F k or f k: Find point in the bucket. If the point exists in the bucket, print k = (x,y,z) where is the point ID and are the point’s coordinates; otherwise, print Point doesn’t exist in the bucket..
  • R k or r k: Remove point from the bucket. Then remove the next item in the main list (i.e., the item having the maximal value) and add it to the bucket; otherwise print one of the following (depending on the current state):
    • If the point is not found in the bucket, print Point doesn’t exist in the bucket..
    • If the point exists in the bucket but there are no more points in the main list to replenish the bucket once it’s removed, print No more points can be deleted..

Note: You must maintain a bucket size of at all times.

Input Format

The first line contains two space-separated integers denoting the respective values of (the number of IDs) and (the bucket size).
Each of the subsequent lines contains four space-separated numbers where the first number is an integer denoting a point ID, , followed by three double values (up to three points after the decimal) representing the respective , , and coordinates corresponding to point .

This is followed by some unknown number of lines of queries. Each query is a single line of two space-separated values, where the first value is a case-insensitive letter (either F or R) followed by an integer, , denoting a point ID. The letter F denotes a find query and the letter R denotes a remove query.

Constraints

  • (up to three points after the decimal)

Output Format

Process the queries in order and print the result for each query on a new line.

For a find (F) query, if the point with the given ID is found, print k = (x,y,z) where is the point ID and are the values for that point (rounded to 3 decimal places); otherwise, print Point doesn’t exist in the bucket.

For a remove (R) query, if the point with the given ID is found and removed successfully, print Point id k removed. where is the ID of the removed point; otherwise, print one of the following (depending upon the program’s current state):

  • If the point is not found in the bucket, print Point doesn’t exist in the bucket..
  • If the point exists in the bucket but there are no more points in the main list to replenish the bucket once it’s removed, print No more points can be deleted..

Sample Input

4 2
1 25.5 50.2 -60.5
2 12.2 60.2 -75.89
3 65.1 25.6 -55.9
4 22.6 12.6 -30.8
F 3
F 2
R 2
R 4
R 1
R 2

Sample Output

3 = (65.100,25.600,-55.900)
Point doesn't exist in the bucket.
Point doesn't exist in the bucket.
Point id 4 removed.
Point id 1 removed.
No more points can be deleted.

Soution

I am not sure why the solution is working only for initial test case but not for others.
All the test cases are getting timed out. Trying to find other optimised ways to solve the problem,
Please suggest if you have any suggestions. 


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Solution {
public static int getMaxId(Map<Integer, ArrayList<Double>> map) {
 
 Double max=-1001.00;
 int maxId=0;
 if(map.isEmpty())
 {
 maxId=-1;
 }
 else
 {
 for(Entry<Integer, ArrayList<Double>> entry: map.entrySet())
 {
 List<Double> tList=entry.getValue();
 
 if(tList.get(2)>max)
 {
 max=tList.get(2);
 maxId=entry.getKey();
 }
 }
 }
 
 return maxId;
 
 }
 public static void main(String[] args) {
 Scanner scan= new Scanner(System.in);
 
 int id,bucketsize;
 id=scan.nextInt();
 bucketsize=scan.nextInt();
 
 Map<Integer, ArrayList<Double>> map=new HashMap<Integer, ArrayList<Double>>();
 
 Map<Integer, ArrayList<Double>> bucket=new HashMap<Integer, ArrayList<Double>>();
 
 for(int i=0;i<id;i++)
 { 
 List<Double> list= new ArrayList<Double>();
 list.clear();
 int idNumber=scan.nextInt();
 double x=scan.nextDouble();
 double y=scan.nextDouble();
 double z=scan.nextDouble();
 x=Double.parseDouble(String.format("%.3f",x));
 y=Double.parseDouble(String.format("%.3f",y));
 z=Double.parseDouble(String.format("%.3f",z));
 list.add(x);
 list.add(y);
 list.add(z);
 map.put(idNumber,(ArrayList<Double>) list); 
 }
 
 List<Double> tempList=new ArrayList<Double>();
 
 for(int i=0;i<bucketsize;i++)
 {
 int max=getMaxId(map);
 // System.out.println("maxxxx" + max);
 tempList=map.get(max);
 bucket.put(max,(ArrayList<Double>) tempList);
 map.remove(max);

 }
 
 /* System.out.println(map);
 System.out.println("bucket" +bucket); 
 */ 
 // maintain bucket

 
 scan.nextLine();
 
 String inputLine;
 
 while(scan.hasNext()) {
 inputLine = scan.nextLine();
 // System.out.println(inputLine);
 String str[]=inputLine.split(" ");
 int operation=Integer.parseInt(str[1]);
 // System.out.println("operation "+operation);
 
 if(str[0].equals("F"))
 {
 if(bucket.containsKey(operation))
 {
 List<Double> tList= bucket.get(operation);
 // System.out.println(tList);
 System.out.println(operation +" = ("+
 String.format("%.3f",tList.get(0)) + ","+String.format("%.3f",tList.get(1))
 +","+String.format("%.3f",tList.get(2))+")");
 }
 else
 {
 System.out.println("Point doesn't exist in the bucket.");
 }
 }
 else if(str[0].equals("R"))
 {
 if(bucket.containsKey(operation))
 {
 
 int maxId=getMaxId(map);
 
 
 
 if(maxId==-1)
 {
 System.out.println("No more points can be deleted.");
 }
 else
 {
 List<Double> getList= new ArrayList<Double>();
 getList=map.get(maxId);
 // System.out.println("mymax "+maxId);
 bucket.put(maxId,(ArrayList<Double>) getList);
 map.remove(maxId);
 map.remove(operation);
 bucket.remove(operation);
 System.out.println("Point id "+operation+" removed.");
 }
 }
 else
 {
 System.out.println("Point doesn't exist in the bucket.");
 }
 }
 /* System.out.println(map);
 System.out.println(bucket);
 */
 } //while
 
 }
}