• Post Reply Bookmark Topic Watch Topic
  • New Topic

datastructure to store two attributes with two search criteria  RSS feed

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I have one question I was asked in an interview. I would like to know the answer for that. The question is like this: we have a two attributes, name and age. we need to create a datastructure which will fulfil two conditions:
1) search age by giving the name
2) search the group of people who fall in a particular age group

I tried solving it using map, but it did not work out well. the second condition fails. If I use a custom class called Person to hold this and use it as the key, the second search will have issue, as I won't have the name attribute when searching for the age group.

Here is what I tried:



Is there some structure which will have near equal time complexity for both operations?

Thanks
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Check out there from the package java.util

SortedMap
TreeMap
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ivan Jozsef Balazs wrote:Check out there from the package java.util

SortedMap
TreeMap


Okay, I checked it. But all operations are using key only. How to get values for a given range. subset using key will only give me name ranges, but i need the second operation where, based on age group i return a list of names.
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And there are of course also Map/HashMap.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ivan Jozsef Balazs wrote:And there are of course also Map/HashMap.


I know the structure, but how does it help in finding range of values? Key value pair search is straight forward. the range search is what I am not able to solve.
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a Script called the API Docs.
Class TreeMap

It is a valuable source of information, many contemplations stem from there, it spreads ideas and yields guidance even about style.

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ivan Jozsef Balazs wrote:There is a Script called the API Docs.
Class TreeMap

It is a valuable source of information, many contemplations stem from there, it spreads ideas and yields guidance even about style.


public SortedMap<K,V> subMap(K fromKey,
K toKey)

/*
Returns a view of the portion of this map
whose keys range from fromKey, inclusive,
to toKey, exclusive. (If fromKey and toKey
are equal, the returned map is empty.) The
returned map is backed by this map,
so changes in the returned map are reflected
in this map, and vice-versa. The returned map
supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException
on an attempt to insert a key outside its range.
*/


But all this is based on key, and for the first search, we need name as the key. submap would have been better applciable if I was looking for an age group but not age of any particular name.
I thought of creating a custom object with name and age, but the issue is that, without the name, I can not find the age group as the custom object would be incomplete for the equals to work.
As I had specified earlier
But all operations are using key only.
filtering value is what I think might be required here.
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can have two collections: one for the name-> age mapping and one for the other way around.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ivan Jozsef Balazs wrote:You can have two collections: one for the name-> age mapping and one for the other way around.

but will it be considered a single datastructure? I was asked to design a datastructure that can fulfil both these searches. I too thought of two collections, as relating both was looking very difficult. but did not answer that.
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hide them behind a façade and call it a data structure ;-)
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!