• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to solve this problem  RSS feed

 
Rajan Chinna
Ranch Hand
Posts: 320
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have the below problem in hand, can some one please give me an idea how to solve this problem. Do I need to use Tree/BTree or any data structures?
Advance thanks.
-----------------------------------------------------------------------
Goal:
-----
Given an input file in plain text, each line specifying a "path", build an in-memory ontology (directed graph) that can be queried against.

Specification:
--------------
Input:
Raw text file, each line being a "path" or "class" in the ontology.
The lines are of the format:
RootName|PathElementName|PathElementName|....|LeafName
For example:
Film|Tapes|Media
Represents one concept of 'Media', namely that 'Media' is a
type of 'Tapes', which is a type of 'Film'.

Names that contain commas or ampersands should be split up.
For example:
Film,Movies|Tapes|Media,Film
Will become the four paths in the ontology:
Film|Tapes|Media
Film|Tapes|Film
Movies|Tapes|Media
Movies|Tapes|Film
The paths should be kept in all lowercase. You do not need
to preserve the original upper/lower case.

NOTE: The names can contain spaces, but multiple spaces or
spaces in front or at the end of a name should be pruned out.

Output:
Given a free-text query, return all the nodes whose name has
the query text in its prefix. This should be case-insensitive.
Also include the path from the node up to the root node.

For example, given the four paths in the above example:
Query: Film (or film or FILM, ...)
Output:
film
film -> tapes -> film
movies -> tapes -> film

Query: TAP
Output:
film -> tapes
movies -> tapes

Query: m
Output:
movies
movies -> tapes -> media
film -> tapes -> media

NOTE: The order of the output does not matter.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please UseAMeaningfulSubjectLine and DoYourOwnHomework

There is a starter here, which part is causing you problems?
 
Rajan Chinna
Ranch Hand
Posts: 320
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have an input like this
A,B|C|D,E

I expect the output to be
A|C|D
A|C|E
B|C|D
B|C|E

Any solution to arrive this output?
Thanks
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not A Code Mill

You will get a similar answer to your post on the Sun forum but I can guarantee it won't be as polite.

[ June 12, 2008: Message edited by: Joanne Neal ]
[ June 12, 2008: Message edited by: Joanne Neal ]
 
Rajan Chinna
Ranch Hand
Posts: 320
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
#Joanne Neal

I am not asking for code, I am looking for some ideas/pointers if people worked on this kind of problems.

If you don't have solution please close your eyes and skip this thread.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David gave you a link to a pointer. What have you tried since reading that ?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm sure many people here have done very similar things. to be blunt, we're not going to HAND you anything.

YOU tell US what you think might work. Why do you think you need a data structure? WHY do you think a Tree or a Binary Tree would be a good choice?

Have you looked at any other data structures? If so, why do you think they would be poor choices?

Our goal here is not to provide solutions, or even blueprints for solutions. we're trying to help people be better programmers, and part of that is learning how to solve these for yourself.

Also, Joanne is a very bright person, who is highly respected here. I'm sure she could write this in her sleep. Just because she won't GIVE you the answer doesn't mean she doesn't HAVE the answer.
[ June 12, 2008: Message edited by: fred rosenberger ]
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hush now Fred, you're making me blush
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!