Find String range using String parameter

Question

I have a collection of the following type:

class Container
{
   private String startValue;
   private String endValue;
}

Let's say it contains these entries...

{"123, "789"},
{"1", "8"},
{"9", "10"},

Then I want to ask the collection to give me all entries which satisfy the predicate between start and end values of each Container, such as the String "5" parameter would return the two first entries above (but not the last one) whereas "9" would only return the first one (and so on).

It should behave as SQL BETWEEN operator on a VARCHAR column.

Changing type from String is not an option. Changing data structure is not an issue.

Performance is also a very importan here. The data structure is rarely changed, but retrieval is very common. A bit extra space taken if speed can be gained is also fine.

Any ideas?

satisfy the predicate between start and end values of each Container. can you please explain it a bit? — Trying
– Trying, Commented Nov 18, 2013 at 17:06
How does "9" return the first entry? What is the logic here? — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Nov 18, 2013 at 17:08
@DavidWallace It's a lexicographic comparison not a numeric one. — crownjewel82
– crownjewel82, Commented Nov 18, 2013 at 17:10
@DavidWallace Oops. I think my brain automatically corrected it to the last one. — crownjewel82
– crownjewel82, Commented Nov 18, 2013 at 17:14

Dawood ibn Kareem · Accepted Answer · 2013-11-18 17:11:50Z

2

Add this method to the Container class

public boolean contains(String argument) {
    return argument != null && startValue.compareTo(argument) <= 0 && endValue.compareTo(argument) >= 0;
}

Then iterate through your collection, calling contains on each element.

answered Nov 18, 2013 at 17:11

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ruslan Ostafiichuk · Accepted Answer · 2013-11-18 17:13:25Z

1

You have to implement "Interval search tree" using red-black BST.

http://algs4.cs.princeton.edu/92search/ https://d396qusza40orc.cloudfront.net/algs4partI/slides%2F99GeometricSearch.pdf

Find all elements will cost R*logN, where R - number of elements to return, N - number of all elements.

answered Nov 18, 2013 at 17:13

Ruslan Ostafiichuk

4,7427 gold badges32 silver badges35 bronze badges

Comments

Pedro Vítor · Accepted Answer · 2013-11-18 17:42:26Z

1

Well... without Integer conversion and change the structure...

You can use stringToCompare.compareTo(str) to compare Strings.

Or, you can use a fixed array of Strings like {"1", "2", "3", "4", "5", "6", "7", "8", "9"}. So, you can split the Strings startValue and endValue, getting character by character and verifying the index (a int) in your array. With this int value you can do some comparisons.

answered Nov 18, 2013 at 17:42

Pedro Vítor

1911 silver badge6 bronze badges

Collectives™ on Stack Overflow

Find String range using String parameter

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related