CODEWITHSUNDEEP
javacollections
Martijn Burger
Martijn Burger

Reputation: 7543

Lookupvalue that is equal or between two values

I have a CSV file that links a region to a zip code. It looks like this (lowest-zip, highest-zip, region):

1600,1799,1
1800,1899,1
4300,4699,1
2820,2839,2
2850,2879,2
2930,2949,2
5600,5819,3
5850,6514,3
6516,6549,3
6800,6849,3

I need a function that returns the region based on the zip code. Something like this:

foo = getRegion(1600) // foo is set to 1
bar = getRegion(1642) // bar is set to 1
baz = getRegion(4351) // baz is set to 2
qux = getRegion(1211) // qux is set to null

The way I currently implemented this is using a HashMap. When I read the CSV I iterate over every value between 1600 and 1799 and create a key-value pair for each zip code / region combination and repeat that for every row in the CSV. The result is a HashMap looking like this:

1600,1
1601,1
1602,1
...
1799,1
1800,2
1801,2
...

This creates a large HashMap, which does work. Is there a more (memory) efficient implementation than exploding this small table to a large HashMap?

Upvotes: 0

Views: 71

Answers (2)

MarcoS
MarcoS

Reputation: 13574

I think you want a segment tree

Upvotes: 1

Raman Shrivastava
Raman Shrivastava

Reputation: 2953

Something like below will help - 

class ZipRange {
    int start;
    int end;
}

// Fill up this map parsing through csv
Map<ZipRange, Integer> zipToRegion;

int zipToSearch = 2870;

// Create method which returns integer which corresponds to region
for (ZipRange zip : zipToRegion.keySet()) {
    if (zipToSearch >= zip.start && zipToSearch <= zip.end) {
        return zipToRegion.get(zip);
    }
}
return -1;

Upvotes: 1

Related Questions